Hamming Data Link Error Detection / Correction Method

In a Hamming code, multiple extra bits are computed such that each extra bit will be affected by the data bits in a distinct way. For example, in a system with 4 data bits, the first extra bit might be affected by a change in data bits 2 thru 4, but not by a change in the first data bit. The second extra bit would be unaffected by an error in the second data bit, and the last extra bit would have no relation to data bit 3. The matrix for this Hamming code would look like this:

d1  1 0 0 0 0 1 1
d2  0 1 0 0 1 0 1
d3  0 0 1 0 1 1 0
d4  0 0 0 1 1 1 1
    -------------
    D1D2D3D4E1E2E3

When the extra bits are recalculated at the recieving end, any differences will call out any single corrupted data bit, or indicate an error if two bits are corrupted.

1011 is encoded as 1011 010. If the first bit is corrupted, 0011 010 will be recieved. Using the first 4 (data) bits to re-calculate the hamming code returns 001. XORing the recieved extra bits with the calculated extra bits gives us 010^001=011 which is the pattern in the extra bits on the top line of the matrix, indicating an error in the first bit. The XOR of the expected error-checking bits with those actually received is called the syndrome of a received codeword.

A more carefully chosen pattern of error correcting bits can simplify the calculation of the corrupted bit as shown in A short spiel on 1-bit error correction codes.

RAM subsystems often use Hamming codes. By using small code words, these codes offer simple decoding and correction at high speeds. Hamming codes typically ensure detection in fixed-length strings of multiple-bit errors. Detecting more than 1 bit error requires larger number of extra bits. Here are some examples for single bit error correction.

1. 4-bit data path requires 3 bits for ECC (8 entry table) (75% increase in size)
2. 8-bit data path requires 5 bits for ECC or 1 bit for parity.
3. 11-bit data path requires 4 bits for ECC (16 entry table)
4. 16-bit data path requires 6 bit for ECC or 2 bits for parity
5. 32-bit data path requires 7 bits for ECC or 4 bits for parity (21.8% increase in size)
6. 64-bit (8 byte) data path requires 8 bits for ECC and parity (12.5% increase in size)
7. 128-bit (16 bytes) data path requires 9 bits for ECC or 16 bits for parity (7% increase in size)

Notice that the number of bits required seems to be increaseing less as we increase the size of the data block. This makes sense as we are still only correcting one bit.

Alan King says:

A  five bit correction code adds in similarly, and added in with the 8 bits for 13 bit total codes, there is a code pattern where the valid codes are right, and if you try to correct any one bit error by changing the data one bit at a time, is still a wrong code for any of the other 12 bits but when you change the one bit in error you get a right code. If you do this to all 13 bits, with no valid code, you had a two or more bit error. It takes a 3 or more bit error to come back up with another valid but wrong code..

Think of the data you're encoding as 256 seperate objects. Normally they're side by side objects, and any single bit flip objects are still valid objects and touching each other. What you want to do, is add enough bits to make a much bigger object array. Then pick your 256 valid objects so that all 1 bit 'error' objects are still touching the correct object, and not touching an incorrect one. Then it takes at least a 2 bit error to even touch an incorrect object. And it so happens that with binary codes, enough bits (13) to do this also let you have enough space that all 2 bit errors are still not 1 bit errors to another code. In other words, your correct codes are all touching their own 1 bit error codes, and there is at least some 2 bit error 'space' between every 1 bit error blob. So if you get a 1 bit error, you're still looking at the right code blob for the correct code..

See also:

• https://www.youtube.com/watch?v=X8jsijhllIA Hamming codes, hâ– w to ovâ– rcoâ– e nâ– ise.
  https://www.youtube.com/watch?v=b3NxrZOu_CE Excellent video on how to implement Hamming codes in software.
   
• https://www.youtube.com/watch?v=EBy7IYtJRKs "Correcting those errors"
• http://burtleburtle.net/bob/math/errorcor.html (cached 20000418090405) Simple and very clear example of 1 bit error correction. Example uses 4 extra bits per 11 bits data (encoded to 15 bits)
• http://www.elecdesign.com/magazine/1999/sept0799/ifd/0907id.shtml Simple. Example uses 3 extra bits per 4 bits data (encoded to 7 bits)
• http://www.embedded.com/1999/9912/9912connect.htm
• http://www.quadibloc.com/crypto/mi0602.htm
  • U. S. Patent 3,623,155 is an optimized [72,64,4] Hamming code.
  • "...another such code was devised by Shigeo Kaneda at Nippon Telegraph and Telephone. This code is called a SEC-DED-S4ED code, which means that, in addition to providing correction of a single bit error, and detection of a double-bit error, it will detect an error involving three or four bits, as long as they belong to the same 4-bit nybble of the 72-bit word fetched from memory. Anyone who has looked at a 72-pin memory stick, and found there were fewer than 36 chips on it, or a 168-pin DIMM, and found there were fewer than 72 chips on it, will appreciate the relevance of this property."

Archive:

• PICList post "Hamming codes -- CORRECTION (AGAIN)"
• PICList post "Hamming codes"

Questions:

• lightsancygnals@hotmail.com asks: " is it possible to correct upto 4 bits of error using Hamming code. if so, can u suggest a method of error correction?
  " James Newton of James Newton's Massmind replies: See: Golay codes

• gastridino@boltblue.com asks: " I would like to know if it's possible to detect error's in a codeword with 2 bit's wrong, or if with the Hamming code we can only detect 1 wrong bit" James Newton of James Newton's Massmind replies: It depends entirely on the number of check bits used in the Hamming code. The examples given above detect 2 errors and can correct 1.

Comments: