Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
@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 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 at 5:20

1 Answer 1

up vote 2 down vote accepted

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.

schematic

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$).

share|improve this answer
    
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 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 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 at 17:03
    
Wow, how did you find this? You are fast!!! –  William Hird Apr 8 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 at 18:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.