Nonlinear Complexity of Binary Sequences and Connections with Lempel-Ziv Compression
Nonlinear Complexity of Binary Sequences and Connections with Lempel-Ziv Compression
复制标题
DOI：
10.1007/11863854_14
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
Konstantinos Limniotis;N. Kolokotronis;N. Kalouptsidis
中科院分区：
文献类型：
--
作者：
Konstantinos Limniotis;N. Kolokotronis;N. Kalouptsidis
本文研究了二值序列的非线性复杂性。提出了一种新的递归算法，它产生给定序列的最小非线性反馈移位寄存器。此外，建立了序列的非线性复杂度和压缩能力之间的联系。证明了给定序列可以实现的 Lempel-Ziv 压缩比的下界，这取决于其非线性复杂度。
The nonlinear complexity of binary sequences is studied in this paper. A new recursive algorithm is presented, which produces the minimal nonlinear feedback shift register of a given sequence. Further, a connection between the nonlinear complexity and the compression capability of a sequence is established. A lower bound for the Lempel-Ziv compression ratio that a given sequence can achieve is proved, which depends on its nonlinear complexity.