On the distribution of de Bruijn sequences of low complexity
type: Item
instance of: scholarly article
title: On the distribution of de Bruijn sequences of low complexity
zbMATH Open document ID: 0583.68036
DOI: 10.1016/0097-3165(85)90074-3
author: Tuvi Etzion
published in: Journal of Combinatorial Theory. Series A
publication date: 1985-01-01T00:00:00Z
review text: The paper deals with a problem of complexity of de Bruijn sequences of order n, i.e. binary sequences \(s=s_ 0,\ldots,s_{2^ n-1}\) satisfying a recurrence equation of the following type: \(f(s_ i,\ldots,s_{i+n-1})+s_{i+n}=0\) (for \(0\leq i\leq 2^ n-1\) and with the other coefficients taken modulo \(2^ n)\) where n is the smallest number for which such a recurrence holds. Because of numerous applications, since a long time the problem of synthesis of de Bruijn sequences has been considered, but the complexity problem has been clearly formulated not so long ago. In the last years there appeared papers dealing with the so called linear complexity of de Bruijn sequences meant as the smallest number m such that \(\sum^{m}_{j=1}a_ js_{i+m-j}+s_{i+m}=0\), in GF(2), for some binary digits \(a_ 1,\ldots,a_ m\). It is known that \(2^{n-1}+n\leq m\leq 2^ n-1\). There exist many open problems for such a notion of complexity. This paper solves some of them for the sequences whose complexity is between \(2^{n-1}+n\) and \(2^{n-1}+2^{n-2}\). The application of an interesting technique allows to evaluate the number of such sequences and to give a recursive method to generate sequences of complexity \(2^{n-1}+2^{n-2}\).
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3934421
zbMATH Keywords: linear recurrence
zbMATH Keywords: linear complexity
MaRDI profile type: Publication
full work available at URL: 0097-3165(85)90074-3
OpenAlex ID: W1986762795
cites work: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
cites work: On the complexities of de-Bruijn sequences
cites work: On the distribution of de Bruijn sequences of given complexity
cites work: A fast algorithm for determining the complexity of a binary sequence with period&lt;tex&gt;2^n&lt;/tex&gt;(Corresp.)
cites work: On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers
description: scientific article; zbMATH DE number 3934421