On the Nonlinear Complexity and Lempel–Ziv Complexity of Finite Length Sequences
Konstantinos Limniotis, Nicholas Kolokotronis, N. Kalouptsidis · IEEE Transactions on Information Theory · 2007
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.