1
$\begingroup$

One bit

Let's suppose that I have a short binary string: 01. This string contains the binary digits 0 and 1 representing the numbers from zero to one. So, a string 2 digits long is required to represent 2 values (1 bit).

Two bits

That wasn't very interesting. However if I want to represent all the numbers that are up to two bits long in a single string, it's:

00110

This contains:

00 01 10 11

In other words, 5 digits are required to represent 4 values (2 bits).

Three bits

I can do three bits:

0001110100

containing:

000 001 010 011 100 101 110 111

10 digits are required to represent 8 values (3 bits).

Four bits

0000111101100101000

contains all of:

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

19 digits are required to represent 16 values (4 bits).

Additional discovery

Finally I discovered an interesting thing.

Having found my first string for 4 bits 1001010000111101100, I realised I could move a digit from the beginning to the end or vice-versa, and the string would still always contain all the numbers, though sometimes (apparently, half the time) the bit needs to be flipped. So I could do it with:

0010100001111011001
0101000011110110010
1010000111101100101  # this one required flipping the moved digit
0100001111011001010  # this one required flipping the moved digit
1000011110110010100
0000111101100101000  # this one required flipping the moved digit
0001111011001010000 
0011110110010100001  # this one required flipping the moved digit
0111101100101000011  # this one required flipping the moved digit
1111011001010000111  # this one required flipping the moved digit
1110110010100001111
1101100101000011110  # this one required flipping the moved digit
1011001010000111101
0110010100001111011
1100101000011110110
1001010000111101100  # this one required flipping the moved digit

I also realised that this means that if the sequence of digits is looped, I can get away with a shorter sequence. i.e. a repeating 0000111101100101... - 16 digits, still containing all my numbers.

I can lop off two digits from the 3-bit sequence to make 00011101... - 8 digits.

Or remove one digit from the 2-bit sequence to make 0011... - 4 digits.

So if I loop the sequence, it looks like I need as many digits as numbers I can represent in the sequence, while unlooped, it's that number plus the bit-depth minus 1.

But, I am not certain if this holds for 5-bit and higher number rangers, I haven't tried to work that out yet, because so far I haven't yet worked out a sequence for more than 4 bits.

My questions

  • What is the smallest string that would contain all the 5-bit numbers?

  • Is there a formula or process for finding the string, other than intuition and trial-and-error (which is what I used)?

  • Will it always be possible, for any bit-depth, to find a string that contains all the numbers of that bit-depth, without repeating any of them?

  • 1 bit requires 2 digits in the (unlooped) string; 2 bits requires 5; 3 bits requires 10; 4 bits requires 19. Is there a pattern to this and can we know how many digits in the string will be required to contain all the binary numbers of a particular bit-depth?

  • Is there a name for any of this, that I could look up to read more about it?

$\endgroup$
2
  • 2
    $\begingroup$ Do you know about de Bruijn sequences? $\endgroup$ Commented Feb 9, 2021 at 0:36
  • $\begingroup$ I didn't, but I do now! I stumbled across these properties while imagining a physical binary dot-matrix display based on lines of tape that could be slid left and right in each row to display every possible combination of dots (i.e. every binary number that many bits wide). It reduces the length of tape required to a minimum, but of course it still gets out of hand as row-length grows. Re-using sequences this way would mean that the tape for a 16-dot-wide matrix will "only" need to be 65'536 dots long instead of 1'048'576, but it would still be fairly impractical. $\endgroup$ Commented Feb 9, 2021 at 9:14

1 Answer 1

Reset to default
3
$\begingroup$

If you allow wraparound, you need only $2^n$ bits to get all $n$-bit sequences; see De Bruijn sequences. If you don’t allow wraparound, you’ll need to repeat the first $n-1$ bits at the end of the string. For example, $00010111$ does the job with wraparound, while without wraparound you need to extend it to $0001011100$, which yields in turn $000$, $001$, $010$, $101$, $011$, $111$, $110$, and $100$.

In particular, to get all $5$-bit numbers you need $2^5=32$ bits with and $2^5+4=36$ bits without wraparound. One possible sequence is

$$00000100011001010011101011011111(0000)\,.$$

$\endgroup$
2
  • $\begingroup$ Thanks for the clear explanation and the name, it's completely fascinating. $\endgroup$ Commented Feb 9, 2021 at 9:15
  • $\begingroup$ @DanieleProcida: You’re welcome. $\endgroup$ Commented Feb 9, 2021 at 18:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.