Error Detection and Correction: HammingCode; Reed-Muller CodeGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinHamming Code: Motivation• Assume a word size of k• Recall parity check coding– Send one additional bit per word, the parity bit– Allows detection (but not correction) of a single error (bit flip) inthe k + 1 bits transmitted• Hamming code– Send ` additional bits per word, called the check bits– Allows correction of a single error in the k + ` bits transmittedTheory in Programming Practice, Plaxton, Spring 2005Hamming Code: Determining The Number of CheckBits• We choose ` as the least positive integer such that the binaryrepresentation of k + ` has ` bits– Exercise: Prove that such an ` is guaranteed to exist– Examples: If k = 1, we set ` to 2 since k + ` = 3 = 112; if k = 2,we set ` to 3 since k + ` = 5 = 1012; if k = 4, we set ` to 3 sincek + ` = 7 = 1112• What is the maximum number of data bits k corresponding to a givennumber of check bits `?– The positive numbers with `-bit binary representations range from2`−1to 2`− 1– So we need k + ` ≤ 2`− 1, i.e., k ≤ 2`− ` − 1Theory in Programming Practice, Plaxton, Spring 2005Hamming Code: The Construction• Index the k + ` bit positions from 1 to k + `• Put the ` check bits in positions with indices that are powers of 2, i.e.,20= 1 = 12, 21= 2 = 102, 22= 4 = 1002, 23= 8 = 10002, . . .• Put the k data bits in the remaining positions (preserving their order,say)• Choose values for the check bits so that the XOR of the indices of all1 bits is zero– Can we always find such a setting of the check bits?– Is this setting unique?Theory in Programming Practice, Plaxton, Spring 2005Hamming Code: Decoding• We’d like to argue that if 0 or 1 bit flips occur in transmission ofthe encoded bit string of length k + `, then the decoder can uniquelydetermine the original k data bits• The decoder first computes the XOR of the indices of all 1 bits in the(possibly corrupted) string of length k + ` that it receives– If no errors occurred in transmission, the XOR is zero– If a 0 flipped to a 1 in bit position i, the XOR is i– If a 1 flipped to a 0 in bit position i, the XOR is i• So what rule should the decoder use to determine the original k databits?Theory in Programming Practice, Plaxton, Spring 2005Reed-Muller Code: Motivation• So far we’ve seen efficient codes for detecting a single error (paritycheck code) and for correcting a single error (Hamming code)• What if we want to be able to detect or correct a large number oferrors?– We need to find a set of codewords such that the minimum Hammingdistance between any two codewords is large• For any nonnegative integer n, the Reed-Muller code defines 2ncodewords of length 2nsuch that the Hamming distance betweenany two codewords is exactly 2n−1– How many errors can be detected (as a function of n)?– How many errors can be corrected (as a function of n)?Theory in Programming Practice, Plaxton, Spring 2005Reed-Muller Code: Hadamard Matrices• The Reed-Muller code is based on Hadamard matrices• We now inductively define a 2n× 2nHadamard matrix Hnfor eachnonnegative integer n– H0= [1]– Hn+1is formed by putting a copy of Hninto each quadrant, andcomplementing the copy placed in the lower-right quadrant• For any nonnegative integer n, the 2ncodewords of length 2nof thecorresponding Reed-Muller code are simply the rows of Hn– It remains to argue that the Hamming distance between any twocodewords is exactly 2n−1Theory in Programming Practice, Plaxton, Spring 2005Reed-Muller Code: Proof of the Hamming DistanceProperty• We prove the claim by induction on n ≥ 0• Base case: H0has only one row, so any claim regarding all pairs ofrows holds vacuously• Induction hypothesis: Assume that for some nonnegative integer n, theHamming distance between any two rows of Hnis 2n−1• Induction step– Consider rows i and j (numbering from 1, say) of Hn+1, where i < j– Verify that the Hamming distance between rows i and j is 2nineach of the following cases: (1) j ≤ 2n; (2) i > 2n; (3) i ≤ 2nandj = 2n+ i; (4) i ≤ 2nand j ≥ 2nand j 6= 2n+ iTheory in Programming Practice, Plaxton, Spring
View Full Document
Unlocking...