File Exchange

image thumbnail

de Bruijn sequence generator

version 1.3 (3.66 KB) by

Generates example de Bruijn sequences of specified number of characters and subsequence lengths.

6 Downloads

Updated

View License

This function will compute an example of an interleaved pseudo-random de Bruijn sequence, a member of the larger class of M-sequences. The sequence will contain an equal number of each character and subsequence of characters. The sequence is, by nature, circular, so the final members of pairs (or triplets, quadruplets, etc...) are found wrapped around to the beginning of the sequence.
Example:
>> sequence = debruijn_generator(3,2)'
sequence =
[1 2 1 3 3 2 2 3 1]

A sequence of N characters with a subsequence length of L would be
---------------------------------------------
N^L characters in length,and would contain:
N^(L-1) examples of each character,
N^(L-2) examples of each pair of characters,
N^(L-3) examples of each possible triplet of characters,
and so on.
---------------------------------------------

Computation times will be *considerable* and unpredictable for large numbers of characters (>10) and subsequence lengths (>4). Sometimes the code will be unable to compute a solution and will restart. This restart is initiated when the total computation time exceeds time taken before the first backtrack times a multiplier of 4 (arrived at empirically as the multiplier that results in the fastest average solution).

Revised: 14th July, 2010 - Changed method for permuting all possible combinations to that created by Jos van der Geest (combn.m available on File Exchange).

If you find this function useful and use it for experimental design, please consider citing Brimijoin and O'Neill, 2010 - (Hearing Research).

Comments and Ratings (9)

Owen Brimijoin

@vinod

In its current form, no, there is no way to force it to generate all possible 4^2 sequences short of exhaustively running the function in a while loop and checking for unique results until all 16 are generated (not particularly efficient, to put it mildly).

vinod

vinod (view profile)

Using this code am i able to generate all debruijn sequences?........for example for n=4 and k=2,there are 16 debruijn sequences.

Owen Brimijoin

@Mahdiyar - from the error you are getting, I'd guess that you haven't put the m-file in a directory that Matlab knows anything about. Either use addpath or place the file in your current directory and it should work just fine.

Mahdiyar

I run the code attached at this page but it gives me the following error

>> sequence = debruijn_generator(3,2)'
Undefined function 'debruijn_generator' for input arguments of type
'double'.
Please let me know what should I do.

Owen Brimijoin

@fan

It’s a bit of a needle-in-the-haystack problem. While it’s true there are many valid (k,n) de Bruijn sequences (this many: factorial(k)^(k*(n-1))/k*n), there are k^(k^n) possible ways to combine k characters in a sequence of equal length!

This m-file keeps a *simple* history of dead-ends in its attempt to find a valid sequence, the simplicity of it being an advantage in avoiding out-of-memory problems, but I do not doubt there are better ways to do it. Suggestions are most definitely appreciated!

Alex

Alex (view profile)

2D-key 0011

000 0 Do
001 1 Re
011 2 Mi
111 3 Re
101 2

(1*sqrt(0)+1*sqrt(1)+2*sqrt(2)+1*sqrt(3))*2/4=pi

3D-key 00010111

0000 0 Do
0001 1 Mi
0101 2 Re
0111 3 Mi
0011 2 Fa
1011 3 Re
1001 2 Mi
1101 3 Re
1111 4

(1*sqrt(0)+1*sqrt(1)+3*sqrt(2)+3*sqrt(3)+1*sqrt(4))*2/8=pi

5D-key 00000101100100011101010011011111

000000 0 Do
000001 1 Mi
000101 2 Re
000111 3 So
010111 4 Fa
011111 5 Mi
011011 4 Re
011001 3 So
001001 2 Do
001000 1 Mi
001100 2 Fa
000100 1 So
010100 2 Re
010110 3 Mi
010010 2 Fa
011010 3 So
001010 2 La
101010 3 Fa
100010 2 So
110010 3 Re
110000 2 Mi
110100 3 Fa
111100 4 So
101100 3 Re
101110 4 La
001110 3 Fa
000110 2 Mi
000010 1 Re
000000 0 So
010000 1 Fa
011000 2 Mi
011100 3 Re
011110 4

(2*sqrt(0)+5*sqrt(1)+10*sqrt(2)+10*sqrt(3)+5*sqrt(4)+1*sqrt(5))*2/31=pi

fan

fan (view profile)

I have another question.Since this function generates the requierd DB sequence through searching all the possible symbol combinations according to the character, arbitrary DB sequence can be obtained without regard to the limitaion of time and memory in principle. However, the generation of the sequence with large period is rather timing consuming. The command 'debruijn_generator(4,8)' gived no result after running for 8 hours. Any sugestions for this problem? Thank you very much.

Owen Brimijoin

In principle you could reseed Matlab's random number generator to the same value each time:

rand('seed',0);
sequence1 = debruijn_generator(5,3)
rand('seed',0);
sequence2 = debruijn_generator(5,3)

These ought to be the same. On the other hand, there is no reason you could not simply save a given sequence and load it whenever you need it.

fan

fan (view profile)

Thank you for author's kind sharing. But how to obtain the same DB sequence each time?

Updates

1.3

edited description

1.2

Improved help text (added H1 line), added more input error checking, and changed method for initially computing all possible combinations to that written by Jos van der Geest (combn.m available on File Exchange).

1.1

Edited description, added tags

MATLAB Release
MATLAB 7.0.4 (R14SP2)
Acknowledgements

Inspired by: permn(V, N, K)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video