Further Investigations on Nonlinear Complexity of Periodic Binary Sequences

2024/04/25 by Yuan, Qin, Li, Chunlei, Zeng, Xiangyong +2 · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2404.16313

Abstract

Nonlinear complexity is an important measure for assessing the randomness of sequences. In this paper we investigate how circular shifts affect the nonlinear complexities of finite-length binary sequences and then reveal a more explicit relation between nonlinear complexities of finite-length binary sequences and their corresponding periodic sequences. Based on the relation, we propose two algorithms that can generate all periodic binary sequences with any prescribed nonlinear complexity.

Cited by

• A closed formula for the Geil-Matsumoto bound on semigroups and curves with many points

Related

• Efficient Algorithm for the Linear Complexity of Sequences and Some\n Related Consequences
• Characterization of 2ⁿ-periodic binary sequences with fixed 3-error or 4-error linear complexity
• The k-error linear complexity distribution for 2ⁿ-periodic binary sequences
• The linear complexity of new binary cyclotomic sequences of period pⁿ
• About the Linear Complexity of Ding-Hellesth Generalized Cyclotomic Binary Sequences of Any Period