Paper 2015/1091

Construction for de Bruijn Sequences with Large Orders

Junwu Dong and Dingyi Pei

Abstract

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of designing de Bruijn sequences has received considerable attention. There is only one full cycle in the state graph of de Bruijn sequences. Most popular algorithms for generating de Bruijn sequences start from a nonsingular linear feedback shift register producing several shorter cycles in its state graph, then join them into one cycle. Unfortunately, the order $n$ of the resulting de Bruijn sequence by using this kind of algorithms is small so far (usually $n\le 40$). We introduce a new concept of correlated cycles between the cycles in the state graph of a LFSR. Based on this concept we present a algorithm for constructing de Bruijn sequences with large orders (such as $$). This is the first publication for designing de Bruijn sequences with such large orders.