2
$\begingroup$

If I understood correctly, Hamming codes assume the uniform correction among all the bits. This means all the bits have the same weight in terms of correction.

Are there any error correcting codes out there that assume non-uniform error correction probability among the bits? For example, I want a error correcting code that corrects the first bit all the time, but it is fine to correct the second bit 90% of the time.

$\endgroup$
  • $\begingroup$ I don't understand your question. What exactly do you want your error-correction code to satisfy? Try explaining with more words. $\endgroup$ – Yuval Filmus Jun 24 '15 at 18:03
  • $\begingroup$ Thanks for reply. Suppose I have a 2-bit code (00, 01, 10, 11). I want my error correction code to fix any error on the most significant bit. However, it is fine if the error correction code can not fix the error on the least significant bit all the time. Let's say I want the error correction to fix error on the least significant bit 90% of the times. $\endgroup$ – AmirC Jun 24 '15 at 18:06
  • 1
    $\begingroup$ Hamming codes are worst-case codes: they are designed to fix a certain number of errors. You are interested in a different regime, in which errors happen according to a probabilistic model, and you are interested in your average ability to correct errors; this is the setting behind Shannon's theorem. $\endgroup$ – Yuval Filmus Jun 24 '15 at 18:10
  • $\begingroup$ Shannon's theorem talks about the correction ability? $\endgroup$ – AmirC Jun 24 '15 at 18:13
  • $\begingroup$ Shannon's theorem talks about transmitting information. I'm referring to this one: en.wikipedia.org/wiki/Noisy-channel_coding_theorem. $\endgroup$ – Yuval Filmus Jun 24 '15 at 18:14
1
$\begingroup$

The topic you want is Unequal Error Protection (UEP) codes. There are a number of constructions in this area and a google scholar search yields quite a few hits.

Intuitively, imagine partitioning your code into disjoint point clouds, where cloud centres are chosen by the more important bits, thus intra-centre distance is high, hence those bits are more robust to noise.

Some references:

On linear unequal error protection codes, B Masnick, J Wolf - IEEE Transactions on Information Theory, 1967.

Multilevel codes for unequal error protection AR Calderbank, N Seshadri - IEEE Transactions on Information Theory, 1993.

A more information theoretic perspective is the Borade et al paper here on the arXiV.

Lastly, Prof. Lloyd Welch published a nice paper on "Codes correcting selected error patterns", which I can't seem to find a reference to.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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