2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | T.4.1 | ||
| Paper Title | Efficient Algorithm for the Linear Complexity of Sequences and Some Related Consequences | ||
| Authors | Yeow Meng Chee, National University of Singapore, Singapore; Johan Chrisnata, Nanyang Technological University, Singapore; Tuvi Etzion, Technion - Israel Institute of Technology, Israel; Han Mao Kiah, Nanyang Technological University, Singapore | ||
| Session | T.4: Sequences | ||
| Presentation | Lecture | ||
| Track | Topics in Information Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | The linear complexity of a sequence $s$ is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence $s$ of length $N$ (where $N$ is of some given form) over a finite field $\F_q$ in $O(N)$ symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period~$2^n$, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires~$\beta N$ bit operations for a small constant $\beta$, where $N$ is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
