# Convert m-Sequence into a de Bruijn Sequence

In his paper Alternating Step Generator Controlled by de Bruijn Sequence, C.G. Günther states on page three that

a de Bruijn sequence (..) can easily be obtained from an m-sequence (maximal length LFSR sequence)

Unfortunately he gives no method for doing this in the paper, and I have been unable to find such a method in my own research. Can anyone clue me in as to what Mr. Günther had in mind there? Is there an easy circuit for converting an m-sequence into a de Bruijn sequence?

-
@fgrieu: My thinking is that Gunther is alluding to a shift register with some kind of nonlinear feedback function consisting of XOR gate(s) with some other nonlinear gate(s), AND, OR, some combination thereof. –  William Hird Apr 8 '14 at 4:41
I don't understand why Gunther says in the paper "it is easy to convert an m-sequence into a deBruijn sequence. To me easy means simple. If you read some of the papers on generating deBruijn sequences, the syntheses are very complicated!! –  William Hird Apr 8 '14 at 5:20

A de Bruijn Sequence, as defined in N.G. de Bruijn's A combinatorial problem, Proc. K. Ned. Akad. Wet., vol. 49, pp 758-764, 1946 (with attribution to Ir. K. Posthumus) is

an ordered cycle of $2^n$ digits 0 or 1, such that the $2^n$ possible ordered sets of $n$ consecutive digits of that cycle are all different.

The example given for $n=3$ is the sequence 00010111, yielding sets 000, 001, 010, 101, 011, 111, 110, 100.

Given that, a de Bruijn Sequence of length $2^n$ is obtained from any m-sequence of length $2^n-1$ (that is, the cyclic output of a LFSR with a primitive polynomial of degree $n$ starting from a non-zero state) by inserting a single 0 in the single subsequence with $n-1$ consecutive 0.

Update per comment: We can implement a circuit that outputs a de Bruijn Sequence of length $2^n$ using $n$ D-type flip-flops connected as for a maximal-length Fibonnaci LFSR with $n$ stages, by adding an additional XOR term equal to the NOR of the outputs of the $n-1$ flip-flops on the feedback's side. In the following drawing (which outputs the example sequence above), the added gates are NOR1 and XOR2.

Note 0: When the number of stages $n$ gets large, the NOR gate with $n-1$ inputs gets annoying; one can trade this for a $\lceil\log_2(n)\rceil$-bit counter with reset, counting the number of consecutive zeroes in the output, giving a $1$ when reaching $n-1$ consecutive zeroes, and that output the additional XOR term.

Note 1: A de Bruijn generator is used in the paper only for the control generator of the ASG, deciding which of the other two are clocked. It would be questionable to also use a de Bruijn generator for any of the other two generators: notice that if the control generator has $c$ bits, a slave generator $x$ bits, and both are de Bruijn, the overall period of the slave's output is $2^{\max(c,x+1)}$, rather than $2^c\cdot(2^x-1)$ when the slave is a maximal-length LFSR.

Note 2: I do not see why the ASG's security would be weakened if the control generator was a maximal-length LFSR rather than a de Bruijn generator, with both slaves maximal-length LFSRs, provided $\gcd(2^{c-1}-1,2^x-1)$ is small [as well as $\gcd(2^x-1,2^y-1)$], where $c$ (resp. $x$, $y$) are the number of bits of the control generator (resp. the slave generator clocked when the control generator outputs $0$, the other slave generator). The original paper hints at another paper (submitted to IEEE Transactions on Information Theory, but I could not locate it) covering the case of maximal-length LFSR as control generator. It also seems to be the case in this article on the ASG, and some of its references.

Late addition: This is also easy in software. Assume $x^\mathtt n+x^\mathtt k+1$ is a primitive trinomial over $GF(2)$ (suitable constants $\mathtt n$ and $\mathtt k$ can be obtained from Jörg Arndt's Complete list of primitive trinomials over GF(2) up to degree 400). If x is an unsigned integer variable at least $\mathtt n$ bits wide, then the C expression
x = ((((x>>k)^x)&1)<<(n-1))|(x>>1);
readily implements a LFSR with period $2^\mathtt n-1$ (when starting from any positive x less than $2^\mathtt n$). We can change this to
x = ((((x>>k)^x^!(x>>1))&1)<<(n-1))|(x>>1);
which implements a NLFSR with period $2^\mathtt n$ (when starting from any non-negative x less than $2^\mathtt n$).

-
Nice work but this not show me the electronic real-world circuit for inserting the zeros in the right places! You can't make an actual ASG without a schematic :-( –  William Hird Apr 8 '14 at 11:40
Just what I was looking for, you are the best. Not sure what "adding an XOR term equal to the NOR of the outputs of the n-1 flip flops" means??? Say I have a 63 bit register, for an m-sequence I will be tapping tap locations 62 and 63 with a single XOR gate for my feedback function. What am I adding to this to get the de Bruijn sequence? –  William Hird Apr 8 '14 at 17:02
@William Hird: Does the drawing help? Assuming $x^{63}+x+1$ is primitive (or equivalently $x^{63}+x^{62}+1$), you need a 62-input NOR gate with inputs the outputs 1 thru 62 (assuming the feedback goes at the input of 1); and one XOR gate inserted in the feedback, with the other input the output of the NOR. –  fgrieu Apr 8 '14 at 17:03
Wow, how did you find this? You are fast!!! –  William Hird Apr 8 '14 at 17:18
A feedback function with a 62 input NOR gate is going to be way too slow for my purposes :-( –  William Hird Apr 8 '14 at 18:00