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:
d_{1} 1 0 0 0 0 1 1 d_{2} 0 1 0 0 1 0 1 d_{3} 0 0 1 0 1 1 0 d_{4} 0 0 0 1 1 1 1 ------------- D_{1}D_{2}D_{3}D_{4}E_{1}E_{2}E_{3}
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.
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 11:55, local time: 2024/4/24 02:48, |
©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? <A HREF="http://www.piclist.com/techref/method/error/hamming.htm"> Hamming Data Link Error Detection / Correction Method</A> |
Did you find what you needed? |
PICList 2024 contributors:
o List host: MIT, Site host massmind.org, Top posters @none found - 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: Gregg Rew. on-going support is MOST appreciated! * Contributors: Richard Seriani, Sr. |
Welcome to www.piclist.com! |
.