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:

• 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

Archive:

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

Questions:

• ~NOSPAM~lightsancygnalsKILLspam at 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?
  " +
• ~NOSPAM~gastridinoKILLspam at 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" +

Comments:

PICList 2008 contributors: o List host: MIT, Site host massmind.org, Top posters @20081121 Apptech, Jinx, Xiaofan Chen, olin piclist, Vitaliy, William \Chops\ Westfield, Tamas Rudnai, Alan B. Pearce, JonnyMac, Gerhard Fiedler, * Page Editors: James Newton, David Cary, and YOU! * Roman Black of Black Robotics donates from sales of Linistep stepper controller kits. * Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters. * Monthly Subscribers: Shultz Electronics, Timothy Weber, on-going support is MOST appreciated! * Contributors: Richard Seriani, Sr.

  .