A deBruijn sequence of span n is a periodic sequence in which every possible n-tuple over the alphabet occurs exactly once.

In this project, I created both a sequence generator and a decoder.

deBruijns can be in any base (that's why i used "alphabet" in the first sentence) but I'm only interested in binary at the moment, so most of this code assumes binary.

Papers

• Lempel 1992.pdf: Describes a method of construction of a deBruijn sequence with an n+1 span from an n-span sequence. Also allows such sequences to be efficiently decoded.
• Mitchell.pdf: Describes a method of construction of deBruijn sequences that can then be decoded. Mitchell's construction builds 2n-span sequences from n-span sequences, and allows for recursive application and decoding to work with large dataset sizes.
• Patterson 1995.pdf
• The_Art_of_Computer_Programming - Vol 1.pdf
• tuliani2001.pdf

Generators

• Mitchell.py generates a sequence of span 2n from a sequence span of n . It's structured as a python iterator.
• KnuthAlgorithmR.py generates a sequence of span n+1 from a sequence of span n . It's structured as a python iterator.
• generate.py is an iterator that uses the above 2 iterators to generate a sequence of any desired length. Import this file and call "iterbruijn(n)" to get a sequence of span n
• deBruijn.py is just a constant definition.

Scratch

This folder is where I'm putting old code experiments I don't want to actually delete for whatever reason. Some of them worked until I broke them, some never worked, some work but I don't like how they work.

The Maths

A deBruijn is an infinite recurring sequence, but we usually just write down one round of the recurrence. Eg: ...0011001100110011... is a span 2 deBruijn, but we can really just write 0011 and remember that its effectively circular. That also means we could write 1001, or 1100, or 0110. They're all the same, effectively.

I like to call a span-v deBruijn D_v. Its much simpler than "Span-v deBruijn sequence". The length of D_v is always going to be 2^v

We'll need to remember the location of the all-0-tuple and all-1-tuple for decoding purposes later. These are called s and s^' respectively.

[MitchellEtAl1996] talks about modifications to deBruijns:

Punctured deBruijn

If you take D_v, find the v-tuple of all zeroes, and then remove one 0 from there, you're left with a sequence that has almost all possible v-tuples, called a punctured deBruijn. Let's call this D^'_v

Double-Punctured deBruijn

If you take a punctured deBruijn, find the v-tuple of all ones, and remove one 1 from there, you're left with a double-punctured deBruijn sequence. Let's call this D^''_v

Enhanced deBruijn

[MitchellEtAl1996] never names but uses a sequence that rather than having a 0 and 1 removed as in a double-punctured deBruijn, adds a 0 and a 1. This yields a sequence that has all possible tuples, but the all-zero and all-one tuples are in there twice. I call these "enhanced" deBruijns, but I write it as D⁺_v

[MitchellEtAl1996] Construction

Its actually pretty straight-forward. Start with a known D_v. Create A=D^''_v, and B=D⁺_v. If the length of D_v is n, then length of A is n-2, and the length of B is n+2. If you concatenate 1+n/2 copies of A, you'll get a sequence of the same length as n/2 -1 concatenated copies of B.

The construction method is:

1. interleave these two sequences B and A, creating a sequence 2²ⁿ-4 long.
2. find the v-2 tuple (1,0,1,0,...) and insert (1,0). The location of the (1,0,1,0...) v-tuple is another important value we need to remember. It's called T. You're now left with D^''_2v. From here, you can trivially generate D_2v as well as D⁺_2v. With those, you can do another iteration and create D_4v, etc.

[MitchellEtAl1996] Decoding

The algorithm as described by [MitchellEtAl1996] works only with double-punctured deBruijns constructed using the above algorithm. Decoding looks convoluted, but is actually straight-forward. D^''_2n was built from 2 sequences A and B. If x is a 2n-tuple to be decoded, you decode by mapping even bits of x to one of A or B, and the odd bits to the other. Since there are several copies each of A and B in D^''_2n, we end up with 2 simultaneous equations we need to solve. 2 equations, 1 unknown, so it's not terribly hard to solve. There are several ways to map the even bits of x to A or B:

1. If the even bits are all 0 or all 1, then the even bits must map to B.
2. if the odd bits are all 0 or all 1, then the odd bits must map to B.
3. if both the even bits tuple and the odd bits tuple are at an even position within A, then the position of x must be even, and the odd bits tuple maps to A.
4. if both the even bits tuple and the odd bits tuple are at an odd position within A, then the position of x must be even, and the odd bits tuple maps to A.
5. if the even bits tuple and odd bits tuple are of different parity, then the position of x must be odd, and the odd bits tuple maps to B.

The above can be a little hard to follow. It certainly took me a few weeks to internalize. I found that working through the construction and decoding methods on paper starting with D₃ helped a lot. I'd welcome efforts to restate the above to make it easier to follow.

Using the Code

At the moment, the code is asymmetric: it can generate deBruijns of any span greater than 2, but it cannot decode odd-sized deBruijns at all, and for even deBruijns, it actually works against double-punctured deBruijns with a span of 6 or larger, not a simple deBruijn... I consider these limits bugs which I'm working around, for the moment.

To generate a deBruijn of any length:

import generate
deBruijn_of_span_v = [y for y in generate.iterbruijn(v)]

To generate a double-punctured deBruijn suitable for decoding:

import generate
double_punctured_deBruijn_of_span_v = [y for y in generate.iterdpdB(v)]

To decode:

import MitchellDecode
position_of_x = MitchellDecode.MitchellDecode(x)

setup for using mouseImageFetch

you'll need to be able to connect to the mouse. you can either be root, or do the following:

(from https://stackoverflow.com/a/31994168) create a file in /etc/udev/rules.d, mine is named 50-RichardWazHeer.rules

in it, put something like:

ACTION=="add", SUBSYSTEMS=="usb", ATTRS{idVendor}=="04f3", ATTRS{idProduct}=="0235", MODE="666", GROUP="richard", PROGRAM="/bin/sh -c 'echo -n $id:1.0 >/sys/bus/usb/drivers/usbhid/unbind'"

sudo udevadm control --reload sudo udevadm trigger

unplug and replug your mouse.