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.
- 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
- 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.
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.
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 Dv. Its much simpler than "Span-v deBruijn sequence". The length of Dv is always going to be 2v
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:
If you take Dv, 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
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
[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
Its actually pretty straight-forward. Start with a known Dv. Create A=D''v, and B=D+v. If the length of Dv 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:
- interleave these two sequences B and A, creating a sequence 22n-4 long.
- 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 D2v as well as D+2v. With those, you can do another iteration and create D4v, etc.
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:
- If the even bits are all 0 or all 1, then the even bits must map to B.
- if the odd bits are all 0 or all 1, then the odd bits must map to B.
- 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.
- 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.
- 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 D3 helped a lot. I'd welcome efforts to restate the above to make it easier to follow.
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.
import generate
deBruijn_of_span_v = [y for y in generate.iterbruijn(v)]import generate
double_punctured_deBruijn_of_span_v = [y for y in generate.iterdpdB(v)]import MitchellDecode
position_of_x = MitchellDecode.MitchellDecode(x)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.