1
$\begingroup$

I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess).

There are two good resources I am looking at for better understanding (it seems like they have a good model of them):

Looking first at the website, they say that $k$ is the number of symbols in the alphabet (so for binary it's 2), and $n$ is the length of each substring in an overall string (I don't know what the string is labeled as, maybe "DB sequence" I guess, de Bruijn sequence, of substrings). They show this as a $k = 2, n = 4$ system:

0000 0001 0010 0101 1011 0110 1101 1010
0100 1001 0011 0111 1111 1110 1100 1000

So I see, $n = 4$ (length of substring), and $k = 2$ ($1$ and $0$).

However, then I get lost at the sentence:

0000101101001111 is a DB sequence where the 16 unique substrings of length 4 visited in order are:

I get there are 16 unique substrings, but where does 0000101101001111 come from? Breaking it into 4, it is:

0000
1011
0100
1111

That's the 1, 5, 9, 13 elements of that sequence. Why did they just use that to describe this DB sequence?

Then in the linked paper, they show:

enter image description here

They say each of these lines is a DB sequence with $k = 2$ and $n = 6$. So from all that I conclude that the substring is length 6 in this case. So I break down the first line:

000000
100001
100010
100011
100100
101100
110100
111101
010111
011011
1111

It doesn't even break into equal length substrings all of length $6$, what am I missing? I thought this should be substrings of length 6 which cover all possibilities of the substring combinations...

So going back to wikipedia, they have some examples, let's see.

Taking A = {0, 1}, there are two distinct B(2, 3): 00010111 and 11101000, one being the reverse or negation of the other.

where $B(k, n)$. Breaking the first down into 3 chunks, we have:

000 101 11

Also not chunks of 3. What am I misinterpreting?

$\endgroup$
3
  • 2
    $\begingroup$ The substrings overlap inside the bigger string. E.g.: within "0000101101001111", look at substring(0,3), substring(1,4), substring(2,5), etc... $\endgroup$
    – mhum
    Commented Apr 20, 2022 at 19:28
  • $\begingroup$ That answers it, thanks. $\endgroup$
    – Lance
    Commented Apr 21, 2022 at 4:54
  • $\begingroup$ Also, I believe the "sequence" in "DeBruijn sequence" refers to the sequence of symbols themselves (i.e.: in this case the ones and zeroes) rather than a sequence of substrings. $\endgroup$
    – mhum
    Commented Apr 21, 2022 at 18:59

1 Answer 1

2
$\begingroup$

A deBruijn sequence $B(k,n)$ has length $N=k^n$ and is cyclic i.e. it can be extended by repeating the sequence.

If it is $x_0,\ldots,x_{N-1}$ then the subsequences $$ x_0\cdots x_{k-1}\\ x_1 \cdots x_{k}\\ ~\\ \vdots\\ ~\\ x_{N-1} \cdots x_{N+k-1} $$ are all distinct and thus cover each $n-$tuple over an alphabet of size $k.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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