Nonlinear complexity of binary sequences and connections with Lempel-Ziv compression

被引：0
|
作者：
Limniotis, Konstantinos [1 ]
Kolokotronis, Nicholas [1 ]
Kalouptsidis, Nicholas [1 ]
机构：
[1] Natl Kapodistrian Univ Athens, Dept Informat & Telecommun, Athens 15784, Greece
来源：
SEQUENCES AND THEIR APPLICATIONS - SETA 2006 | 2006年 / 4086卷
关键词：
cryptography; Lempel-Ziv compression; nonlinear complexity; nonlinear feedback shift registers; sequences;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：168 / 179
页数：12
相关论文
共 50 条
  • [1] On Lempel-Ziv complexity of sequences
    Doganaksoy, Ali
    Gologlu, Faruk
    SEQUENCES AND THEIR APPLICATIONS - SETA 2006, 2006, 4086 : 180 - 189
  • [2] On the Nonlinear complexity and Lempel-Ziv complexity of finite length sequences
    Limniotis, Konstantinos
    Kolokotronis, Nicholas
    Kalouptsidis, Nicholas
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2007, 53 (11) : 4293 - 4302
  • [3] Lempel-Ziv dimension for Lempel-Ziv compression
    Lopez-Valdes, Maria
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006, PROCEEDINGS, 2006, 4162 : 693 - 703
  • [4] Lempel-Ziv and Multiscale Lempel-Ziv Complexity in Depression
    Kalev, K.
    Bachmann, M.
    Orgo, L.
    Lass, J.
    Hinrikus, H.
    2015 37TH ANNUAL INTERNATIONAL CONFERENCE OF THE IEEE ENGINEERING IN MEDICINE AND BIOLOGY SOCIETY (EMBC), 2015, : 4158 - 4161
  • [5] ON THE BIT-COMPLEXITY OF LEMPEL-ZIV COMPRESSION
    Ferragina, Paolo
    Nitto, Igor
    Venturini, Rossano
    SIAM JOURNAL ON COMPUTING, 2013, 42 (04) : 1521 - 1541
  • [6] On the bit-complexity of Lempel-Ziv compression
    Ferragina, Paolo
    Nitto, Igor
    Venturini, Rossano
    PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2009, : 768 - 777
  • [7] A relative Lempel-Ziv complexity: Application to comparing biological sequences
    Liu, Liwei
    Li, Dongbo
    Bai, Fenglan
    CHEMICAL PHYSICS LETTERS, 2012, 530 : 107 - 112
  • [8] Generalized Lempel-Ziv compression for audio
    Kirovski, Darko
    Landau, Zeph
    IEEE TRANSACTIONS ON AUDIO SPEECH AND LANGUAGE PROCESSING, 2007, 15 (02): : 509 - 518
  • [9] Lempel-Ziv Parsing for Sequences of Blocks
    Kosolobov, Dmitry
    Valenzuela, Daniel
    ALGORITHMS, 2021, 14 (12)
  • [10] Lempel-Ziv Complexity of Photonic Quasicrystals
    Monzon, Juan J.
    Felipe, Angel
    Sanchez-Soto, Luis L.
    CRYSTALS, 2017, 7 (07):
12345