How would I go about implementing this algorithm?

Question

Friday afternoon seems like a good time to ask this question...

A while back I was trying to brute force a remote control which sent a 12 bit binary 'key'.

The device I made worked, but was very slow as it was trying every combination at about 50 bits per second (4096 codes = 49152 bits = ~16 minutes)

I opened the receiver and found it was using a shift register to check the codes and no delay was required between attempts. This meant that the receiver was simply looking at the last 12 bits to be received to see if they were a match to the key.

This meant that if the stream 111111111111000000000000 was sent through, it had effectively tried all of these codes.

111111111111    111111111110    111111111100    111111111000
111111110000    111111100000    111111000000    111110000000
111100000000    111000000000    110000000000    100000000000
000000000000

In this case, I have used 24 bits to try 13 12 bit combinations (>90% compression).

Does anyone know of an algorithm that could reduce my 49152 bits sent by taking advantage of this?

I'm not working on the gadget anymore, but it's always been in the back of my head that there must be some algorithm to reduce the bits sent.

Answer 1

Off the top of my head, I suppose flipping one bit in each 12-bit sequence would take care of another 13 combinations, for example 111111111101000000000010, then 111111111011000000000100, etc. But you still have to do a lot permutations, even with one bit I think you still have to do 111111111101000000000100 etc. Then flip two bits on one side and 1 on the other, etc.

Answer 2

What you're talking about is a de Bruijn sequence. If you don't care about how it works, you just want the result, here it is.

Answer 3

This is a well studied problem.
See here:
http://garden.irmacs.sfu.ca/?q=op/smallest_universal_supersequence
The first comment contains a link for a paper which solves it.