3
\$\begingroup\$

Is there a method for sequencing 4-bit binary numbers, where no 4 consecutive bits are repeated anywhere else in the stream?

For example;

bit sequence diagram

Is there a method that would work for 5 and 6 bit numbers?


Thanks for all the great feedback. Here is some info on how the sequence is used:

Pictured below is the data placed on a wheel. As it spins, the bit stream is shifted into a software register from right to left. After 3 shifts, I have a valid number. After the 4th shift, I have the next number and because of its unique position in the sequence, I can associate it to a position on the wheel. Granted it’s not an absolute position system on power up, but after 4 shifts the position is found.

wheel diagram

I’ve expanded this to six bits, but the process was manual. I’m looking for help to make scaling-up a bit easier.

Thanks.

\$\endgroup\$
  • 3
    \$\begingroup\$ I think you are talking about a De Bruijn sequence. \$\endgroup\$ – Harry Svensson Sep 11 '18 at 15:27
  • 1
    \$\begingroup\$ it is unclear what you are asking .... what is the purpose of the bit sequence field? \$\endgroup\$ – jsotola Sep 11 '18 at 15:28
  • \$\begingroup\$ I believe the question is to find the sequence of bits \$b_i\$ for \$0 \le i < 2^n\$ such that the sequence of \$n\$-bit numbers \$x_i = ShiftLeft(x_{i-1}) + b_i\$ (and \$x_0=0\$) has unique numbers only. \$\endgroup\$ – Eugene Sh. Sep 11 '18 at 15:57
  • \$\begingroup\$ Is the purpose to avoid duplicate values in 2^N -1 sequence or create pseudo random values for BER tetsts. If latter, there are many PRSG simple designs. \$\endgroup\$ – Sunnyskyguy EE75 Sep 11 '18 at 16:24
  • \$\begingroup\$ Some bits in the sequence are obviously predetermined. Each sequence has to start with 000..0, continue with 000..1, and end with 100..0 as it has to be cyclic. The last fact is predetermining the last n inputs. Some other rules would apply as well, like that 111...1 can be only followed with 111..10. Other than that I can't formulate additional rules other than backtracking if encountering any of the special sequences above. \$\endgroup\$ – Eugene Sh. Sep 11 '18 at 17:12
3
\$\begingroup\$

Yes it is a De Bruijn Sequence and based on an algorithm J. Tuliani wrote for his Thesis titled "On Window Sequences and Position Locations" the software community created this Sequence Generator;

De Bruijn Sequence

Thanks

\$\endgroup\$
  • \$\begingroup\$ Welcome to the site :-) The comment about it being a De Bruijn sequence was already made a couple of times, so I was surprised to see you write this as the answer to your question. However if you really meant this to be the answer to your question, then please also accept this answer, to signal to the site that no further answers are needed. If, however, you meant this to be a reply or update to someone, then please delete it as an answer and re-write it as a comment to whomever you are replying. (P.S. Please stop adding a signature; it's against site rules. Thanks.) \$\endgroup\$ – SamGibson Sep 14 '18 at 20:46
2
\$\begingroup\$

Perhaps you are looking for maximal length linear feedback shift registers, which have the property that a register of N bits cycles through 2N-1 unique values before repeating.

\$\endgroup\$
  • \$\begingroup\$ I have used a maximal length LFSR precisely as a 'generate all codes' machine for an initialisation problem. However, while the original LFSR only generates 2^N-1 codes, omitting the all 0s state, it's possible to hack it by adding one more zero into the N-1 zeroes state, and then it generates all 2^N states. \$\endgroup\$ – Neil_UK Sep 11 '18 at 18:45
  • \$\begingroup\$ Depending on positive XOR negative LFSR feedback the -1 missing state is "all 1's" XOR "all 0's". Your choice. Otherwise a valid Set or Reset gets stuck if it gets into in the opposite state. "1's" or "0's" \$\endgroup\$ – Sunnyskyguy EE75 Sep 19 '18 at 18:44
-1
\$\begingroup\$

This “almost” looks like the card shuffling counter where no hex values are repeated in 2^N cycles using N bit Gray Code counters where only 1 binary bit changes at a time. If you want a random or arbitrary sequence, this must be defined.

\$\endgroup\$
  • \$\begingroup\$ This doesn't look like an answer but as a rephrasing of the problem. \$\endgroup\$ – Eugene Sh. Sep 11 '18 at 16:11
  • \$\begingroup\$ Perhaps but the use of Gray codes may lead to an explicit solution depending is repetitive or random shuffle with X decks. X=1 or more \$\endgroup\$ – Sunnyskyguy EE75 Sep 11 '18 at 16:19
  • \$\begingroup\$ Somewhat related to Gray, I agree, but I fail to see a unique recipe other than backtracking on the possible bit choices. Also the interesting question would be "how many such a sequences for n-bit numbers?". For two bits, it's only 1, as far as I can tell. If it is one for any n, then this sequence should have a name. \$\endgroup\$ – Eugene Sh. Sep 11 '18 at 16:31
  • \$\begingroup\$ yes 2^n-1 is the sequence max for PRSG but 2^n for gray code counters, with a random seed every cycle. \$\endgroup\$ – Sunnyskyguy EE75 Sep 11 '18 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.