Optimal DC-free line encoding

Question

I have a block of n bits that I'd like to encode into m bits that have an equal number of zeros and ones.

I looked at protocols like 8b/10b but it wastes 25% of the data to achieve balance.

As an example, it turns out that 128 bits have ${128 \choose 64}$ combinations where there is an equal number of zeros and ones. This number is greater than $2^{124}$. This means that I should be able to encode 124 bits of data into 128 bits that have an equal number of zeros and ones.

I have no idea how to do this mapping though. Obviously I can't make a look-up table of size $2^{124}$. Anyone have any ideas?

Answer 1

Your problem can be restated as the following:

"Find an easily computable bijection from the integers $0 .. {n \choose n / 2} - 1$ to the set of binary strings of length $n$ with exactly $n / 2$ zeros and $n / 2$ ones."

Formulated this way, this looks like a combinatorial numbering problem.

Decoding is quite simple and involves accumulating binomial coefficients for each bit set in the codeword. The encoding looks more complicated. Having enough ROM/RAM to store a big binomial coefficients table helps a lot in any case. You might want to repost on cs / math stackexchange, mentioning only the combinatorics aspect (not the digital communications application) if you are in search of more memory-efficient algorithms.

See python code for encoding and decoding here.

---

High-level explanation.

Let us consider the case $n = 6$ (3 ones and 3 zeros). The goal is to find a mapping between the strings 000111, 001011, 001101 up to 111000... and the numbers 0, 1, 2, 3 up to 19. This is equivalent to coding $\log_2 20 = 4.32$ bits into a 6-bit DC-free code.

There are ${6 \choose 3} = 20$ strings made of 3 zeros and 3 ones. ${5 \choose 3} = 10$ of them start with a 0 and ${5 \choose 2} = 10$ of them start with 1. So we can assign the numbers 0 to 9 to the first group, and 10 to 19 to the second group.

Within the first group, there are ${4 \choose 3} = 4$ which start with 00 and ${4 \choose 2} = 6$ which start with 01. So we can assign the numbers 0 to 3 to the 00 group and 4 to 9 to the second group.

Within the 00* group, there are ${3 \choose 3} = 1$ which start with 000 and ${3 \choose 2} = 3$ which start with 001. So we can assign the number 0 to the first one (000111), and the numbers 1 to 3 to the second group (001*). And so on...

Observe that in all the ${n \choose k}$ we have written, $n$ is always the number of remaining positions, and $k$ the number of unallocated ones. So the partitions of the $0 .. 19$ set we have built are created by adding ${\text{position at which we allocate a one} \choose \text{number of remaining ones}}$ terms.

Let us formalize this procedure. If the bitstring to decode is $b_5b_4b_3b_2b_1b_0$, the number we have associated to it is:

$b_5 {5 \choose b_4 + b_3 + b_2 + b_1 + b_0} + b_4 {4 \choose b_3 + b_2 + b_1 + b_0} + b_3 {3 \choose b_2 + b_1 + b_0} + b_2 {2 \choose b_1 + b_0} + b_1 {1 \choose b_0} + b_0$.

That's all for the decoding (DC-free bitstring to number)!

The encoding (number to DC-free bitstring) works by trying to "fit" the terms of this sum to the integer to encode. For example, given the number 15 to encode:

• This number is above ${5 \choose 2}$ so the first digit is 1, and the first term of the sum is $1 {5 \choose 2} = 10$. 2 ones remains to be allocated. 5 remains in the sum.
• The remainder is less than ${4 \choose 2} = 6$ so the next digit can't be a 1, so the second term of the sum is $0 {4 \choose 2}$. 2 ones remain to be allocated. 5 remains in the sum.
• The remainder is above ${3 \choose 2} = 3$, so the next digit is 1, and the third term of the sum is $1 {3 \choose 2}$. 1 one remains to be allocated. 2 remains in the sum.
• The remainder is equal to ${2 \choose 1} = 2$, so the next digit is 1, and the fourth term of the sum is $1 {2 \choose 1}$. All ones are allocated. All terms of the sum are accounted for.
• The remaining terms are $0 {1 \choose 0} + 0$.

Thus, the bitstring associated to 15 is 101100.

Answer 2

There are more modern protocols that should be able to achieve the efficiency that you want. For example, PCI Express 3.0 (the most recent revision) uses 128b/130b encoding, which encodes 128 information bits into 130 channel bits. Ther seems to be on the order of overhead that you are looking for.

I'm not aware of the implementation details for this specific encoder, but that should give you a place to start looking. For such a widespread standard, I'm guessing that you can find a description somewhere, or at least look at the standard for information.

Edit: It appears that in this case, a linear-feedback shift register is used. According to this forum post, the polynomial is:

$$ x^{23} + x^{21} + x^{16} + x^8 + x^5 + x^2 + 1. $$

This doesn't tell the complete story, because I'm not sure how the register is initialized or how the data is fed through.

Answer 3

To add to the other comments and answers, managing the DC component in your signaling stream is generally done by employing bipolar line coding techniques. There are many. Here is a reference: http://www.engr.sjsu.edu/rmorelos/ee161s12/PulseShaping.pdf