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

Author

Hai Xiong ; Longjiang Qu ; Chao Li

Author_Institution

Coll. of Sci., Nat. Univ. of Defense Technol., Changsha, China

Volume

60

Issue

4

fYear

2014

fDate

41730

Firstpage

2399

Lastpage

2406

Abstract

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 ≡ 1mod4, 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.

Keywords

Legendre polynomials; binary sequences; computational complexity; random sequences; 2-adic complexity; 2-level autocorrelation; Ding-Helleseth-Lam sequences; Legendre sequences; binary sequences; linear complexity; optimal autocorrelation sequences; pseudo-random sequences; Complexity theory; Correlation; Linear feedback shift registers; Polynomials; 2-adic complexity; ideal 2-level autocorrelation sequence; linear complexity; optimal autocorrelation sequence;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2014.2304451

Filename

6736120