1
$\begingroup$

Remark. I have zero knowledge of any fancy terminology used to describe hamming codes, and am only aware of the basic principle of how they work (and why it works), that given a message, a few extra bits can be used as parity checks on the original message to locate and correct up to 1 error. (i.e. I've seen the 3Blue1Brown videos on the topic)

The idea of parity checking seems so ingenious that when I search for codes that can correct up to 2 errors (or more), I get complicated looking codes, eg. Reed Solomon, something something generating polynomial, CRC yadda yadda.

I wonder, are there any such codes that only rely on parity checks (perhaps one will need a lot more such checks) to detect and correct a 2 bit error in a message? Is such a code efficient at doing so?

For instance, given a $11$-bit message, a minimum of $4$ redundancy bits would be required to correct up to 1 error. What is the minimum number of extra redundancy bits required to correct upto a 2-bit error? And what would the associated parity checks look like? Is this as efficient as the original hamming code, for whatever metric of "efficiency" means? Why is such a code not popular? i.e. I searched alot on google with keywords eg. "2 bit error correction", "parity checks", "hamming code 2 bit error", with no results.

$\endgroup$

2 Answers 2

1
$\begingroup$

There are codes doing exactly what you want. For example BCH codes can be designed to correct $t=2$ errors, which mean they must have minimum distance $d=2t+1=5$. Start at the wikipedia page here.

This page here has a more gentle example including correcting two errors.

The question of exactly how many redundant bits are needed is hard in general and is the general problem of coding theory. It is combinatorial in nature. However there are bounds known. See for example the tables http://www.codetables.de/.

Entering $n=15, k=11$ gives the maximum possible minimum distance as $d=3.$ Your expectation was too optimistic. Look up Hamming bound to begin to see why.

Increasing $n$ to 20 gives a code with minimum distance 5. In fact the tables tell us this is the shortest codeword length possible.

$\endgroup$
0
$\begingroup$

Just some coarse answers without details (I am no expert either...): parity checks can only detect an odd number of errors, so 2 errors is out of scope:

Altera white paper

. Parity can only detect an odd number of errors. If an even number of errors occurs, the computed parity will match the transmitted parity

which of course applies to a single parity check. You can split your data into groups, and do a parity check on each of them. Because an even number of errors is however undetected by a single parity check, you must have a tree of overlapping groups to be able to correctly detect multiple errors. That becomes ugly soon regarding the amount of overhead, so that's why they are not popular and smarter algorithms with less redundancy are used.

Error correction is done to prevent re-transmit systems which are highly inefficient. The general goal is to transfer as much as bits using as less resources as possible (bandwidth, time, transmit power, etc.). Simple correction algorithms require much redundancy=overhead, so we see a tendency to use more complex algorithms that can do with less redundancy. It is however actually a tradeoff between computing power and redundancy. The highly efficient LDPC codes for example were already known in the 1960s (Gallagher), but became only widespread after the year 2005 or so because of the required computing power that was simply not available before then. Now you see them in DVB-C2, DVB-S2X, DOCSIS 3.0 standards etc.

Regarding effciency: the better a code can approach the limit for transferring data in a channel (Shannon capacity), the more efficient it is called. Simple parity codes are bad, Reed-Solomon much better (a few dB from the Shannon capacity when using its basic implementation), LDPC more or less the best we can do these days (within tenths of a dB from the Shannon capacity).

$\endgroup$

You must log in to answer this question.

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