A New Method to Compute the 2-Adic Complexity of Binary Sequences

作者：Xiong, Hai^*; Qu, Longjiang; Li, Chao

来源：IEEE Transactions on Information Theory, 2014, 60(4): 2399-2406.

DOI：10.1109/TIT.2014.2304451

• 2-adic complexity
• linear complexity
• ideal 2-level autocorrelation sequence
• optimal autocorrelation sequence

In this paper, a new method is presented to compute the 2-adic complexity of pseudo-random sequences. With this method, the 2-adic complexities of all the known sequences with ideal 2-level autocorrelation are determined in a unified way. Results show that their 2-adic complexities equal their periods. In other words, their 2-adic complexities attain the maximum. In addition, 2-adic complexities of two classes of optimal autocorrelation sequences with period N equivalent to 1 mod 4, namely Legendre sequences and Ding-Helleseth-Lam sequences, are investigated. This method also can be used to compute the linear complexity of binary sequences regarded as sequences over other finite fields.

• 出版日期2014-4
• 单位中国人民解放军国防科学技术大学