The structure and enumeration of periodic binary sequences with high nonlinear complexity
Abstract
Nonlinear complexity, as an important measure for assessing the randomness of sequences, is defined as the length of the shortest feedback shift registers that can generate a given sequence. In this paper, the structure of n-periodic binary sequences with nonlinear complexity larger than or equal to 3n/4 is characterized. Based on their structure, an exact enumeration formula for the number of such periodic sequences is determined.
Fields of Study & Subjects
Coding theory and cryptography
semigroups and automata theory
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 1 February 2026
- Document type
- Preprint