Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

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?

share|improve this question
    
Can you change the underlying pulse shape? You could use a DC-free pulse shape instead of relying on the statistics of the bitstream to be balanced. One example would be to use a Manchester-encoded pulse. –  Jason R Jan 16 '13 at 13:46
    
Jason, nope, I've got to work within the constraints I mentioned. –  Dan Sandberg Jan 16 '13 at 13:48
    
Is the "DC-free" band for your line infinitely small, or of any finite bandwidth? –  hotpaw2 Jan 16 '13 at 14:14
1  
hotpaw2's question is roughly equivalent to the following: What is the size of the observation/counting window through which you want the number of ones to be equal to the number of zeros? I am sure the scheme you have in mind does not go as far as ensuring that 10 consecutive bits are always 5 zeros and 5 ones... –  pichenettes Jan 16 '13 at 18:55
1  
Just as a note, your requirements would discount any sort of linear block code (as would typically be used for error correction), as linear codes always contain the all-zero codeword. –  Jason R Jan 16 '13 at 19:04
show 3 more comments

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Wow, impressive! I've accepted this as the answer. I agree that I might want to re-post elsewhere -- I wasn't sure whether to post this on math or cs or dsp. Can you give a super high-level explanation of how the code works? I'm looking at it but I'm not grokking the list comprehensions and big picture idea. Thanks! –  Dan Sandberg Jan 16 '13 at 21:58
    
I have added an explanation for the case n = 6. It's hard to share how intuitive this looks to me - it's a bit like the steps required to convert a number into base 2, except that instead of decomposing into a sum of powers of 2, we decompose into a sum of binomial coefficients which depend on the number of 1 and 0 we have written so far. –  pichenettes Jan 16 '13 at 23:11
    
Excellent! Thank you so much! –  Dan Sandberg Jan 17 '13 at 8:51
add comment

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.

share|improve this answer
    
Hi Jason, from what I've read the 128b/130b scheme doesn't provide the DC-free guarantees that 10b/8b does. I think the polynomial you mentioned above is used for a different purpose. It's apparently called 128b/130b because the first two bits are some kind of header. I couldn't find a ton of information about it so I'm not 100%. –  Dan Sandberg Jan 16 '13 at 18:47
    
@DanSandberg: Upon further review, it appears that there isn't a DC guarantee with that standard. You have a very interesting question here. –  Jason R Jan 16 '13 at 19:00
add comment

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

share|improve this answer
    
Hi Bruce, yeah, I've looked at those schemes but none of them are appropriate. I'm looking for a way to encode 124 bits into 128 bits. –  Dan Sandberg Jan 16 '13 at 18:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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