From: Jan de Wit <[EMAIL PROTECTED]>
>Pray tell, what *are* base-2 deBruijn sequences? I know what deBruijn
>terms are, and have some code for them, but as for sequences...
>I think you are going to get a lot of replies like this one ;-)
The following three are examples of binary de Bruijn sequences:
8bit sequence for 3bit words
00010111
32bit sequence for 5bit words
00000100011001010011101011011111
256bit sequence for 8bit words
0000000010000001100000101000001110000100100001011000011010000111
1000100010011000101010001011100011001000110110001110100011111001
0010100100111001010110010110100101111001100110101001101110011101
1001111010011111101010101110101101101011111011011110111011111111
The sequences are cyclic and any n bits in an associated p^n sequence are
unique, therefore all p^n unique patterns occur.
I certainly didn't expect any of the type of replies you are inferring. de
Bruijn sequences have been kicking around in one form or another for over
50 years - you can find the basics of the theorem in most books on discrete
math or combinatrics. The method I was "taught" to make the sequences
involves drawing out a p^(n-1) node and p^n edge (directed) graph (more or
less a FSM), labelling it appropriately, and finding an Euler cycle through
it.
I was able to get some very sloppy C code to do the job, but I'm far
from happy with it... it came completely undocumented and is quite
difficult to trace through. The other code I have is concise and
(supposedly) efficient, but it is in NESL, which I have no way of running.
Wayne
