# Name and generator for no-repeating-substring bit strings

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.
• hmm a subset of MLS LFSR's maybe dspguru.com/dsp/tutorials/a-little-mls-tutorial Jun 16, 2023 at 12:53
• Jun 16, 2023 at 13:02
• FWIW: The 3-bit example is a Johnson counter, or twisted-ring counter. Jun 16, 2023 at 13:18

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.

• Yes the reset is illegal with non-inverting feedback and 111 illegal with inverted XOR's Jun 16, 2023 at 13:06
• 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. Jun 19, 2023 at 11:41
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