4003-420-01/4005-740-01 Data Communications and Networks I The Hamming Code Prof. Alan Kaminsky -- Fall Quarter 2012 Rochester Institute of Technology -- Department of Computer Science The Original (7,4) Hamming Code Invented in 1950 by Richard W. Hamming (1915-1998) 4 data bits 3 check bits 7 total bits Detects and corrects a one-bit error Does not detect or correct more than one bit error Data Codeword Data Codeword 0000 . . . 0000 000 1000 . . . 1000 111 0001 . . . 0001 011 1001 . . . 1001 100 0010 . . . 0010 101 1010 . . . 1010 010 0011 . . . 0011 110 1011 . . . 1011 001 0100 . . . 0100 110 1100 . . . 1100 001 0101 . . . 0101 101 1101 . . . 1101 010 0110 . . . 0110 011 1110 . . . 1110 100 0111 . . . 0111 000 1111 . . . 1111 111 Richard W. Hamming Hamming Distance Hamming distance between two words = Number of bit positions at which the two words differ   Example: The Hamming distance between 0001011 and 0010101 is 4 0001011 0010101 xxxx <-- Differ in 4 bit positions In the Hamming code, if two data words' Hamming distance is 1, then the corresponding codewords' Hamming distance is at least 3 Error Correction With a Hamming Code The above table lists the 16 valid codewords   The remaining 112 possible codewords are invalid codewords   When a codeword is received (possibly with a bit error), find the closest (Hamming distance) valid codeword, and use the data bits from that valid codeword   This works because a single bit error shifts a valid codeword a distance of only 1, but any other valid codeword is at a distance of at least 3, so the original codeword is still the closest valid codeword Larger Hamming Codes Data Bits Check Bits Total Bits 1 2 3 4 3 7 8 4 12 32 6 38 64 7 71 Error Detection and Correction With a Hamming Code 4 data bits 3 check bits plus 1 parity bit 8 total bits Detects and corrects a one-bit error Detects but does not correct a two-bit error Does not detect or correct more than two bit errors Data Codeword Data Codeword 0000 . . . 0000 000 0 1000 . . . 1000 111 0 0001 . . . 0001 011 1 1001 . . . 1001 100 1 0010 . . . 0010 101 1 1010 . . . 1010 010 1 0011 . . . 0011 110 0 1011 . . . 1011 001 0 0100 . . . 0100 110 1 1100 . . . 1100 001 1 0101 . . . 0101 101 0 1101 . . . 1101 010 0 0110 . . . 0110 011 0 1110 . . . 1110 100 0 0111 . . . 0111 000 1 1111 . . . 1111 111 1 Now, if two data words' Hamming distance is 1, then the corresponding codewords' Hamming distance is at least 4   A single-bit error is corrected as before   A two-bit error yields an invalid codeword at a distance 2 from the original codeword, halfway between two valid codewords We can tell the codeword is invalid -- we can detect the two-bit error We cannot tell which valid codeword was the original one -- we cannot correct the two-bit error   Modern computer memories often use this technique with 32- or 64-bit words -- "ECC memory" Data Communications and Networks I • 4003-420-01/4005-740-01 • Fall Quarter 2012 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 10-Dec-2006. Please send comments to ark­@­cs.rit.edu.