4-Adic Complexity of Interleaved Quaternary Sequences

Tang and Ding \cite{X. Tang} present a series of quaternary sequences $w(a, b)$interleavedbytwobinarysequences$a$and$b$ with ideal autocorrelation and show that such interleaved quaternary sequences have optimal autocorrelation. In this paper we consider the 4-adic complexity $F{C}_w(4)$ of such quaternary sequence $w=w(a,b)$. We present a general formula on $F{C}_w(4)$, $w=w(a,b)$. As a direct consequence, we obtain a general lower bound $F{C}_w(4)\ge {\log }_4(4^n-1)$ where $2n$ is the period of the sequence $w$. By taking $a$ and $b$ to be several types of known binary sequences with ideal autocorrelation ($m$-sequences, twin-prime, Legendre, Hall sequences and their complement, shift or sample sequences), we compute the exact values of $F{C}_w(4)$, $w=w(a,b)$ and show that in most cases $F{C}_w(4)$ reaches or nearly reaches the maximum value ${\log }_4(4^{2n}-1)$. Our results show that the 4-adic complexity of the quaternary sequences defined in \cite{X. Tang} are large enough to resist the attack of the rational approximation algorithm.