Title :
On the Nonlinear Complexity and Lempel–Ziv Complexity of Finite Length Sequences
Author :
Limniotis, Konstantinos ; Kolokotronis, Nicholas ; Kalouptsidis, Nicholas
Author_Institution :
Nat. & Kapodistrian Univ. of Athens, Athens
Abstract :
The nonlinear complexity of binary sequences and its connections with Lempel-Ziv complexity is studied in this paper. A new recursive algorithm is presented, which produces the minimal nonlinear feedback shift register of a given binary sequence. Moreover, it is shown that the eigenvalue profile of a sequence uniquely determines its nonlinear complexity profile, thus establishing a connection between Lempel-Ziv complexity and nonlinear complexity. Furthermore, a lower bound for the Lempel-Ziv compression ratio of a given sequence is proved that depends on its nonlinear complexity.
Keywords :
binary sequences; computational complexity; cryptography; data compression; eigenvalues and eigenfunctions; feedback; recursive functions; Lempel-Ziv complexity; cryptographic system security; data compression; eigenvalue profile; finite length binary sequences; minimal nonlinear feedback shift register; nonlinear complexity; recursive algorithm; Binary sequences; Communication system security; Cryptography; Eigenvalues and eigenfunctions; Error correction; Length measurement; Linear feedback shift registers; Probability distribution; Shift registers; Spread spectrum communication; Compression; Lempel–Ziv complexity; cryptography; eigenvalue; nonlinear complexity; nonlinear feedback shift registers; sequences;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2007.907442
