De Bruijn sequences, irreducible codes and cyclotomy
type: Item
instance of: scholarly article
title: De Bruijn sequences, irreducible codes and cyclotomy
zbMATH Open document ID: 0878.94046
DOI: 10.1016/0012-365X(96)00106-9
author: Erik R. Hauge
author: Tor Helleseth
published in: Discrete Mathematics
publication date: 1997-11-16T00:00:00Z
review text: A de Bruijn sequence of order \(n\) is a binary sequence with period \(2^n\) which contains all binary \(n\)-tuples. They are defined by nonlinear feedback functions. The most of the algorithms for generating de Bruijn sequences are variants of the cycle join algorithms (CJA). Each of these algorithms finds a spanning tree in the undirected graph (\textit{adjacency graph}) defined by a feedback function (\textit{starting function}). In this paper, the adjacency graphs of linear feedback functions whose characteristic polynomials are irreducible, are analysed. For such functions a lower bound for the number of de Bruijn sequences that can be obtained, is given. This generalizes the class of the sequences corresponding to the feedback function of which the characteristic polynomials are primitive.
Mathematics Subject Classification ID: 94A55
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 955089
zbMATH Keywords: feedback functions
zbMATH Keywords: irreducible polynomials
zbMATH Keywords: adjacency graphs
zbMATH Keywords: cyclotomic numbers
zbMATH Keywords: de Bruijn sequences
reviewed by: Jerzy Żurawiecki
MaRDI profile type: Publication
cites work: Weights of irreducible cyclic codes
cites work: Q3277097
cites work: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
cites work: On the classification of deBruijn sequences
cites work: An efficient algorithm for the generation of DeBruijn cycles
cites work: Q3216750
cites work: Q4146667
cites work: Q5538955
full work available at URL: 0012-365x(96)00106-9
OpenAlex ID: W2007799433
description: scientific article; zbMATH DE number 955089