``Periods'' of de Bruijn sequences
type: Item
instance of: scholarly article
title: ``Periods'' of de Bruijn sequences
zbMATH Open document ID: 0767.11014
DOI: 10.1016/0196-8858(92)90007-J
author: S. W. Golomb
published in: Advances in Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: A de Bruijn sequence of degree \(n\) is a periodic binary sequence of periodicity \(2^ n\) in which each of the \(2^ n\) possible subsequences of length \(n\) occurs exactly once (in each periodicity). In each periodicity of length \(2^ n\) there are \(2^{n-2}\) ``periods'' (a run of 1's followed by a run of 0's). On the average the length per period is \(M_ 1=4\). In each de Bruijn sequence of degree \(n\geq 4\), and for each \(p\) with \(2\leq p\leq n-2\), periods of length \(p\) occur exactly \((p- 1)2^{n-2-p}\) times in each periodicity of the sequence, accounting for exactly \(2^{n-2}-(n-1)\) periods. The main interest in this paper is in the remaining \(n-1\) periods with length greater than \(n-2\). The sum of the lengths of these long periods is \(n^ 2-n-2\). The two extreme cases relative to these long periods are: one period of length \(2n\) and \(n-2\) periods of length \(n-1\); and \(n-3\) periods of length \(n\) and two periods of length \(n+1\). After establishing these and related results, the paper concludes with a list of open questions concerning the periods, their higher moments, etc., of the \(2^{2^{n-1}-n}\) de Bruijn sequences of degree \(n\).
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 11B85
Mathematics Subject Classification ID: 94A55
zbMATH DE Number: 91495
zbMATH Keywords: de Bruijn sequence
zbMATH Keywords: periodic binary sequence
zbMATH Keywords: periods
zbMATH Keywords: higher moments
reviewed by: Stanley E. Payne
MaRDI profile type: Publication
cites work: Q5684568
cites work: Distributions of periods and frequencies of runs in random binary sequences
description: scientific article; zbMATH DE number 91495