Code covered by the BSD License  

Highlights from
de Bruijn sequence generator

Be the first to rate this file! 30 Downloads (last 30 days) File Size: 3.66 KB File ID: #28015

de Bruijn sequence generator

by

 

25 Jun 2010 (Updated )

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

| Watch this File

File Information
Description

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

Acknowledgements

Combn (4.3) inspired this file.

MATLAB release MATLAB 7.0.4 (R14SP2)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (9)
17 Sep 2014 W. 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).

17 Sep 2014 vinod

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

29 May 2013 W. 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.

24 May 2013 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.

19 Aug 2011 W. 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!

16 Aug 2011 Alex

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

29 Jul 2011 fan

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.

29 Jun 2011 W. 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.

01 May 2011 fan

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

Updates
28 Jun 2010

Edited description, added tags

14 Jul 2010

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

22 Jul 2011

edited description

Contact us