please dont rip this site

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:

Archive:

Questions:

Comments:


file: /Techref/method/error/hamming.htm, 8KB, , updated: 2020/9/4 10:55, local time: 2024/12/3 22:46,
TOP NEW HELP FIND: 
18.97.14.82:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?
Please DO link to this page! Digg it! / MAKE!

<A HREF="http://www.massmind.org/Techref/method/error/hamming.htm"> Hamming Data Link Error Detection / Correction Method</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to massmind.org!

 

Welcome to www.massmind.org!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .