CODEWITHSUNDEEP
algorithmdata-structuresbit-manipulation
Jackson Tale
Jackson Tale

Reputation: 25842

Generate a longest bit sequence where all 5-bits consecutive sub sequence are unique

Generate a longest bit sequence (only 0 or 1 for every slot).

In this sequence, all consecutive m-bit sub sequences are distinct.

For example, if m = 2, then 00110 is such a longest sequence. All 2-bit sub-sequences are unique: 00 01 11 10.

Using brute-force we can surely find such a sequence for a m.

However, is there a clever way?

Upvotes: 3

Views: 404

Answers (3)

Aki Suihkonen
Aki Suihkonen

Reputation: 20037

One way to accomplish this is to use arithmetic in Galois Field.

Starting with a polynomial P_0(x) = 0*x^4 + 0*x^3 + 0*x^2 + 0*x^1 + 1 == 0b00001, we can compute the next element P_1(x) = P_0(x) * x mod R(x), where R(x) must be a primitive polynomial in GF(2^5).

What follows is a sequence of length 2^5 - 1, where each bit position goes through most of the unique subsequences -- except the sequence 0b00000.

This can be easily fixed by starting with a zero, and appending the MSB term of each polynomial P_i(x).

 void linear_feedback_shift_register() {
     uint8_t poly = 0b00001;
     // start with an extra zero, otherwise we can't have '00000'
     std::cout << "0" << (poly >> 4);
     for (int i = 0; i < 32+2; i++) {
         poly <<= 1;
         if (poly & 0b100000) {
             poly ^= 0b100101; // 1+x^2+x^5 is a primitive polynomial
         }
         std::cout << (poly >> 4);
     }
     std::cout << "\n";
 }

Output:

 000001001011001111100011011101010000

(Total 36 characters printed, with all 32 subsequences of 5)

Upvotes: 0

r3mainer
r3mainer

Reputation: 24587

This is called a De Bruijn sequence.

There seems to have been a lot of research on these, but unfortunately the results are mostly stuck behind paywalls

I did find one paper available online.

Upvotes: 2

artur grzesiak
artur grzesiak

Reputation: 20348

You can find the solution in: Invitation to Discrete Mathematics by Matousek and Nesetril page 140 (btw. one of the most beautiful books on the subject).

The answer is surprisingly: 2k for each k >= 1 (in your case 32). I will cite:

Define a graph G = (V,E) in the following manner: (%) V is the set of all sequences of 0s and 1s of length k - 1 (%) The directed edges are all pairs of (k-1)-digit sequences of the form ((a1,...,ak-1),(a2,...,ak)). Directed edges are in a bijective correspondence with k-digit sequences (a1,...,ak).

And then it is enough to find an Eulerian tour in G.

EDIT They treat the sequence as if it its end and start were glued. E.g. to get 00 from 0110 we start at the last digit and then the next digit is the first digit of the sequence. So the 2k-sequence can be actually extended by appending the first (k-1) digits to the end.

Upvotes: 4

Related Questions