7
$\begingroup$

I'm looking for a kind of error correction code or solution that can correct my codeword in this case:

My message holds k bits, and 2*k bits codeword (rate is 1/2) is produced by the generator matrix, e.g. k=5, so it yields 10 bits codeword 1001100111. If the codeword is erased for some reason and it becomes 1xx1x00xx1 (similar to the codeword transmitted through Binary Erasure Channel, and x is unknown, either '0' or '1'), can I still correct all the "x bits" in such situation as bit error rate is 1/2?

I have read about some error correction code, such as block code, convolutional code and LDPC and got the following questions:

  1. All these ECC have pratical application in communication, so do they still work when BER is close to 1/2 (I think BER is impossible so high)?

  2. Are there any feasible solution to my case? In fact, my message is 30 bits and I can introduce another 30 bits redundancy as parity bits. Can I still correct my codeword even if half bits are corrupted?

Any guides or suggestions are appreciated!

$\endgroup$
4
  • $\begingroup$ Are you considering erasure (where the recipient knows which bits he didn't receive properly) or corruption (where the recipient may misreceive some bits but doesn't know which they are)? $\endgroup$ Mar 27, 2013 at 14:13
  • $\begingroup$ You might want to ask this in theoretical CS as well. $\endgroup$ Mar 27, 2013 at 14:28
  • $\begingroup$ @HenningMakholm I'm considering "erasure" as you mention, and the rest of bits will not flip if they are not erased. $\endgroup$
    – WangYudong
    Mar 27, 2013 at 14:49
  • 1
    $\begingroup$ Have you considered a fountain code with a packet size of 1 bit? (Where the codewords are formed by gluing the packets together one after another.) I'm not sure how well it will actually work in practice, but it might be worth doing some simulations. Note that the resulting code will have rate slightly less than 1/2. Is that okay? $\endgroup$
    – Snowball
    Mar 27, 2013 at 15:03

3 Answers 3

8
$\begingroup$

No, that is not possible.

Assume, to the contrary, that we have such as code. Because we can erase the $k$ last bits in a code words, by the pigeonhole principle all of the $2^k$ possible combinations of the first $k$ bits must be used by exactly one codeword. Without loss of generality we can therefore assume that the first $k$ bits in each codeword are the unchanged message bits. We can also assume that message $0^k$ has codeword $0^{2k}$. (If not, we can make it so by uniformly negating certain bit positions in all codewords).

What is the second half of the codeword for message $0^{k-1}\,1$? If we erase the 1 in the first half and all but a single bit in the last half of the codeword, there must be at least 1 left; otherwise we could not distinguish it from message $0^k$. But that can only be the bit we didn't erase in the second half, and this reasoning holds no matter what the position of the bit is, so $0^{k-1}\,1^{k+1}$ is a codeword.

By quite similar reasoning, $1\,0^{k-1}\,1^k$ must be a codeword.

But $0^{k-1}\,1^{k+1}$ and $1\,0^{k-1}\,1^k$ look alike when we erase the first $k$ bits. This is a contradiction.

$\endgroup$
3
$\begingroup$

As others have explained, you cannot do this with absolute certainty, because then you will bang your head against the wall of Hamming distance. However, `rateless' codes can do this with a very high probability with effective rate an epsilon over 1/2, and longer blocks of data. In other words, Snowball's comment is a good one.

In some sense the philosophy (that to some extent was a paradigm shift for ECC designers) is that the approach based on optimizing the Hamming distance is that of playing the game against an intelligent, evil adversary, who erases (or toggles) precisely those bits that will give you trouble. In natural communication, the actual opponent is the more benign random noise occurring in nature.

Look up fountain codes and (for an improvement) Raptor Codes for definitions and papers with probabilistic analysis (if you can stomach the gloating of a person, who insists calling bitwise XOR as a transform named after himself).

$\endgroup$
5
  • $\begingroup$ For the record: yours truly largely gave up coding theoretical research, when the focus shifted from algebraic/combinatorial/number theoretic methods to stochastics. I'm an algebraist at heart. $\endgroup$ Mar 28, 2013 at 12:58
  • $\begingroup$ Your block of 30 bits is probably too short for the rateless benefits to kick in. $\endgroup$ Mar 28, 2013 at 13:02
  • $\begingroup$ Does the Hamming bound apply to erasure codes? That would have been the easy answer, but I figured it would not be applicable. For example, as Zander suggests, $\{01,10\}$ can survice single-bit erasures, but it does't fit within the Hamming bound for correcting single-bit errors. $\endgroup$ Mar 28, 2013 at 13:42
  • $\begingroup$ @Henning: A code with minimum Hamming distance $d$ can correct $e$ erasures and $t$ errors, iff $d>2t+e$. A generic scheme is to make two errors-only decoding attempts, one with erasures filled in as 0s the other with 1s (and check afterwards that not too many corrections outside the error positions were made). Anyway, at one extreme we have errors only, and make the familiar requirement $d\ge 2t+1$. At the other we have erasures only, when we need $d>e$ to be guaranteed to succeed. $\endgroup$ Mar 28, 2013 at 15:13
  • $\begingroup$ x @Jyrki: Ah, of course, that makes sense. $\endgroup$ Mar 28, 2013 at 16:39
2
$\begingroup$

The way you describe it you are using a block code, seeking error free decoding and thus can check the Hamming bound. $$ A_2(n,d) = \frac{2^n}{\sum_{j=0}^{\lfloor(d-1)/2\rfloor}\binom{n}{j}} $$

Here you have $n=10$ and you want every pair of codewords to be distinguishable even if 5 bits are lost, so you need a minimum Hamming distance $d=6$, which bounds the number of distinct codewords at 18, so you won't be able to encode all 5-bit messages.

With a longer message block it's even worse, $A_2(30,16)<2^{14}$.

For $k<4$ the bound is not so tight, but as @HenningMakholm already showed you won't be able to construct such a code when $k>1$.

For $k=1$ the code $\{01,10\}$ allows you to correct any one bit erasure, technically allowing you to successfully decode when the "bit error rate is 1/2" in the received message.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .