Does any error correction code still work in such situation?

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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).