(A) construction of de bruijn sequences using maximum length linear sequences

Abstract

In this thesis, a construction of doe Brujin sequences using maximum length linear sequences is considered. The construction is based on the well known cross-join method. Maximum length linear sequences are used to produce due Bruijn sequences by a cross-join process. Properties of the cross-join pairs in the maximum length linear sequence are investigated. It is conjectured that the number of cross-join pairs in a maximum length linear sequence is given by $\frac{1}{3}(2^{2n-3}+1)-2^{n-2}, n ≥ 2$, where n is the length of the shift register. Cross-join pairs for some special cases are obtained. An algorithm for finding cross-join pairs is described and a method of implementation is discussed briefly.