0
\$\begingroup\$

While solving a different problem I stumbled across an interesting class of bit patterns: a 2n-bit cyclic sequence, all of whose n-bit subsequences are unique. With n=3, for example, the bits 11101000, starting from an initial state of 000, generates 001 011 111 110 101 010 100 and back to 000. It's trivial to prove that the reverse is also such a sequence; also the negation (with negated starting state).

  • Does this kind of sequence have a name?
  • Is there a simple generator for the pattern? I'm hoping for some kind of linear-feedback shift register or similar arrangement. Currently I can find them with a depth-first search program, but that's not very satisfactory.

The first solution I'm able to find for each n up to 8 are as follows. I noticed that all begin with n ones, a zero, then n - 2 ones; all end with n zeros; up to n=4, they are "antipalindrome" -- from left-to-right, ones match zeros reading right-to-left; there are in general very many qualifying solutions.

1 10
2 1100
3 11101000
4 11110110 01010000
5 11111011 10011010 11000101 00100000
6 11111101 11100111 01011100 01101101 00110010 11000010 10100010 01000000
7 11111110 11111001 11101011 11000111 01101110 10011100 10111000 01101100
  11010101 10100011 00100110 00101100 00010101 00101000 01001000 10000000
8 11111111 01111110 01111101 01111100 01111011 01111010 01111001 01111000
  01110111 01100111 01010111 01000111 00110111 00100111 00010111 00000110
  11010110 11000110 10100110 10010110 10000110 01100101 01100100 01100010
  01100001 01100000 01010101 00010100 10010100 00010010 00010001 00000000

It's clear that as n grows, the number of solution patterns grows very rapidly.


  • The problem I was solving was this: a memory chip with a shift register connected to its n address inputs, wanting to visit all the addresses with 2n clocks. My actual application has n at least 16, perhaps 24.
\$\endgroup\$
3

2 Answers 2

1
\$\begingroup\$

According to many sources such as Wikipedia, that should be a PRBS, your example being almost a PRBS-k sequence with k=3 but it should have only 7 output bits as for 3 bits the state of 000 can't exist as it will be stuck 000 forever. A PRBS-k sequence should only have N=2^k-1 output sequences of k bits, i.e. for k=3 N=7.

So for k-bit LFSR swith that has a maximal length sequence, it will have only length of 2^k-1, so you can't have k-bit shift register and access a memory chip with k-bit address bus, as you are missing the all bits zero address.

So the solution to your original problem is of course for k-bit memory address bus is to use a k+1 bit shift register, and use only any k bits out of it for the memory while initializing it to non-zero value.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Yes the reset is illegal with non-inverting feedback and 111 illegal with inverted XOR's \$\endgroup\$ Jun 16, 2023 at 13:06
  • \$\begingroup\$ Thanks for interesting suggestion re k+1 LFSR. As far as I understand it, that would visit every lengt=k address twice (except 0, only once). For some uses I can see that would be an elegant if non-optimal solution. Just to be clear though, I'm after a bit stream, such as would be generated by the bottom bit of such a k+1 LFSR. \$\endgroup\$
    – jonathanjo
    Jun 19, 2023 at 11:41
0
\$\begingroup\$
  1. These are De Bruijn Sequences, named after Dutch mathematician Nicolaas De Bruijn
  2. The simplest generator is a maximal length LFSR with a prepended '0'.

Generators

A simple generator program is as follows, using the generators 0x3, 0x6, 0xC, 0x14, 0x30, 0x60, 0xB8, 0x110, 0x240, 0x500, 0xE08, 0x1C80, 0x3802, 0x6000, 0xD008, 0x12000, 0x20400, 0x72000, 0x90000, 0x140000, 0x300000, 0x420000, 0xE10000: (The example polynomials for maximal LFSRs from Wikipedia.)

There are 22n-1-n solutions for n-bit substrings; this code just finds one, which conveniently is based on an LFSR and starts with all-zeroes.

checkseq(2, "0" + lfsr_galois_rightshift(2, 0x3))
checkseq(3, "0" + lfsr_galois_rightshift(3, 0x6))
checkseq(4, "0" + lfsr_galois_rightshift(4, 0xc))
checkseq(5, "0" + lfsr_galois_rightshift(5, 0x14))

With output showing the bit strings:

checking 4-bit sequence for 2-bit substrings 0011
repeated 2-bit substring at 4
checking 8-bit sequence for 3-bit substrings 00011101
repeated 3-bit substring at 8
checking 16-bit sequence for 4-bit substrings 0000111101011001
repeated 4-bit substring at 16
checking 32-bit sequence for 5-bit substrings 00000101011101100011111001101001
repeated 5-bit substring at 32

I tested this up to n=21.

The checker and generator can be coded naively in Python as follows:

def lfsr_galois_rightshift(n, taps):
    res = ""
    reg = 1
    for i in range(0, 2**n - 1):
        if reg & 1:
            reg = (reg >> 1) ^ taps
            res = "1" + res
        else:
            reg = reg >> 1
            res = "0" + res
    return res

def checkseq(n, seq):
    print("checking %d-bit sequence for %d-bit substrings %s" %
        (len(seq), n, seq[:48] + ("..." if len(seq)>32 else "")))
    seq2 = seq + seq   # for "wraparound" substrings
    found = set()
    for i in range(0, len(seq2)):
        subseq = seq2[i:(i+n)]
        #print("  %3d %s" % (i, subseq))
        if subseq in found:
            break
        found.add(subseq)
    print("repeated %d-bit substring at %d" % (n, i))

References

At OEIS, "De Bruijn sequence" is used to mean 1, 1, 2, 16, 2048, ..., the number of distinct 2n-bit cyclic strings with 2n distinct n-bit substrings. (OEIS 16031).

At other sources, "De Bruijn sequence" is used to mean a qualifying 2n-bit string; often generalised to nonbinary alphabets of length k.

These references cover other ways to find the sequences and deeper mathematical treatment. Both have online generators.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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