Error Detection and CorrectionOutline for Today1. Parity Check Code2. Bounds based on Hamming distance3. Hamming CodeCan You Raed Tihs?“I cnduo’t bvleiee taht I culod aula clty uesdtannrd waht I was rdnaieg. Unisg the icndeblirepweor of the hmuan mnid, aocdcrnig to rseecrah at Cmabrigde Uinervtisy, it dseno’t mttaer inwaht oderr the lterets in a wrod are, the olny irpoamtnt tihng is taht the frsit and lsat ltteerbe i n the r hgit pclae. The rset can be a taotl mses and you can sitll raed it whoutit a pboerlm.Tihs is bucseae the huamn mnid deos not raed ervey lt t eer by istlef, but t he wrod as a wlo he.Aaznmig, huh? Yaeh and I awlyas tg hhuot slelinpg was ipmora ntt! See if yuor fdreins can raedtihs too.”– languagehat.com (original source unknown)1One Example: Error DetectionBits are occasionally fl ipped in t r ansmission. For example, a sender may transmit 1101001,and the receiver gets the string 0101011.Adding redundancy can allow us to detect, and possibly cor r ect, some errors of this type.Simple approach: Repeat each bit• Repeat each bit twice. For bit x, transmit xx. If the receiver gets two different bits, itrequests retransmissi o n. This in an error-detecting code - it allows one error to be detected,but it i s not erro r -correcting, since r etr a nsmission is necessar y.• Repeat each bit three ti mes. For each bit x, transmit xxx. Now the receiver can correcta single error. (How?)2Parity Check Code: Detecting an Odd Numbe r of Bit FlipsDefinitio n: A bit string has odd p arity if the number o f 1s in the str ing is odd. A bit stringhas eve n parity if the number o f 1s in the stri ng is even.Recall: 0 is an even number.Example:01100, 000, and 110010 01 have even par i ty.1000011, 1, and 00010 have odd pari ty.Assume we are transmitting blocks of k bits.• A block w of length k is encoded as wa, where the value of the parity bit a is chosen sothat wa has even parity.– Example: If w = 10110, we send wa = 101101, which has even parity.• If there are a positive, even number of bit fl ip errors in transmis sion, t he receiver gets a bitstring with even parity, and the error ( s) go undetected.• If there are an odd number of bit fl ip errors in transmission, the receiver gets a bit stringwith odd parity, i ndicating an error occurred. The receiver requests r etransmission.3Assumption: Bit flips are rare, so we can tolerate a very small percentage of corrupted blocksthat have an even number of flips.4Single Parity Check Code - Undetectable ErrorsAny time a block of length n (with parity bit) contai ns an even number of bit errors, the errorcannot be detected. Let p be the probability of an error in a single bit. The probability o f 2bit flips in the block is:n2p2(1 − p)n−2i.e, the number of ways to choose 2 bits fro m n bits, times p2, the probability of those bitsbeing errors, ti m es pn−2, the probability of the rema ining n − 2 bits being correct.The probability of an undetected error is:n2p2(1 − p)n−2+n4p4(1 − p)n−4+ ...For bit st r ings of length n = 32 and p = 0.001, the probabili ty of an undetectable error isapproximately 0.00 05.52D Parity CheckBlock of bits is orga nized i n rows and columns, say an m × n matrix.• The parity bit of each row is calculated, and appended to the row before it is transmitted.• The parity of each column is calculated, a nd the parity bit of the entire matrix is computed- these are also transmitted to the receiver.• m + n + 1 parity bits are computed.• A tota l of mn + m + n + 1 bits are sent to the receiver.62D Parity CheckExample:Original data: 1100, 1011, 0111, 0101row pari ty1 1 0 0 01 0 1 110 1 1 110 1 0 100 1 0 1 0 (matrix parity bit)col parity bitsExercise: Describe an err o r that cannot be detected with this approach.7Hamming Distance between CodewordsExample: Suppose we want to send 2-bit strings. Each codeword contains two copies of thestring plus a parity bit. If the bit-s t ring is 01, we send t he 5-bit string 01x01, w here x is theparity bit. So in this example, the s ender transmits the codeword 01101.For this code, there are only four 5-bit codewords: 00000, 01101, 10110, 11011. Whenthe receiver sees any other string, the erro r is corrected by replacing it with the codeword thathas the least Hamming distance to the received word.Suppose that the string 10001 is received. Fo r Hamming dis t ance d,d(10101, 00000) = 3, d(10101, 01101) = 2, d(10101, 10110) = 1, d(10101, 11011) = 3.So the closest codewor d t o the received string is 10110, so the r eceiver assumes that this wasthe ori ginal string.The number of erro rs that can be detected and corrected depends on the Hamming distancebetween the codewords .8Hamming Distance and Bounds on Error Co r rectionTheorem: Let S be a set of codewords and let h be the minimum Hammi ng distance betweenany two codewords in S. Then:1. It is possible to detect any number of errors less than h2. It is possible to correct any number of errors less than h/2Proo f: Assume that codeword x i s sent and string y is received.If d(x, y) < h, then y is obviously either x, o r y is not a codeword. So the receiver will detectan error.If d(x, y) < h/2, then we will s how that x is the closest codeword to y, a nd so the receiver cancorrect the error by replacing y with closest codeword x. Let z be any codeword other than x,and suppose that d(y, z) ≤ d(y, x). Then since d(y, x) < h/2, it f o llows that d(y, z) < h/2.Sod(x, z) ≤ d(x, y) + d(y, z) by the triangle inequality< h/2 + h/2 = h. Contradiction, since x and z are bot h codewords. Therefore x is t he closestcodeword to y. 9Hamming DistanceExercise: We looked previously at a code that has four 5-bit codewords: 00000, 01101,10110, 11011. C a lculate the minimum Hamming distance between a ny two codewords. Sowe are:1. Guaranteed to be able to correct any number of errors less than.2. And guaranteed to detect any number of errors less than.10Hamming CodeAssume we are transmitting codewords of length k.Hamming code:• Sends a logarithmic number l additional bits per word, called the check bits.• Allows o ne error to be corrected f or each block (of k + l bits) tra ns m itted.11Hamming Code: How Many Check Bits?Choo se l to be the smallest positive integer so that the representation of k + l has l bits. Forexample:1. If k = 1, what should l be?2. if k = 2, what is l?Question: What is the maxi mum number of data bits k corresponding to a given number ofcheck bits l?The positive