CS232 Fall 2006 Discussion 11: ECC Dec 4, 2006Error Correcting CodesComponents of a computer system perform the following functions:1. Information processing (logic elements, CPU etc.)2. Information storage (RAM, registers etc.)3. Information transmission (interconnects, lines etc.)All these components are susceptible to failures and therefore can produce erroneous output(s),i.e., some of the output bits are changed. Our concern here is to detect an erroneous outputand if possible take a corrective action.We achieve this by encoding information, i.e., by appending some redundant bits to theinformation bits in such a manner that the errors can be detected and possibly corrected byspecial logic circuits. Let us demonstrate the principle by a simple example.Duplication: Let us consider the case where each information bit x is duplicated (for exampletransmitted over two lines or stored at two locations in RAM). If only one error is likely tooccur, then instead of receiving xx we will receive x¯x or ¯xx (but not ¯x¯x or xx). Thus, wewill immediately know that an error has occurred whenever we receive two non-identical bits.This is error detection. Of course, we will not be able to determine what was transmitted.Error detectionOne of the simplest schemes for single error detection is to use a check bit called parity bit. LetA = a0, a1, ..., an−1be an n bit word. A parity bit p is defined as p = a0⊕ a1⊕ a2⊕ ... ⊕ an−1,i.e. p = 0 if A has an even number of ones, and p = 1 otherwise (⊕ denotes the Exclusive-ORoperation). In this scheme every word A is stored in RAM along along with its parity bit p. Onreading RAM, parity is recomputed and checked against stored value of p. An error is said tohave occurred if computed(p) 6= stored(p). It is not difficult to see that the above scheme willdetect not only a single error but an odd number of errors in the stored word. Note also thatthe error(s) detected need not be confined to the word A – they could also involve the paritybit itself!Error correctionThe Hamming distance between binary ve ctors A = ha0, a1, . . . , an−1i and B = hb0, b1, . . . , bn−1iis the number of bits of A we need to flip to get B. Mathematically, H(A, B) =Pi=n−1i=0(ai⊕bi).Example: For A = (0100) and B = (0010), H(A, B) = 2Another way to lo ok at the Hamming distances is that if A and B are nodes of a binary n-cube,then the Hamming distance b e tween them is the minimum number of links traversed to getfrom node A to B (or from node B to A). It is also evident that two adjacent nodes on thebinary n-cube have a Hamming distance of one.In order to introduce redundancy, we add extra bits to a data word – the result is called acodeword. The extra bits are selected in such a way that the minimum Hamming distancesbetween all pairs of code words is maximized. Consider the case of appending a parity bit toeach data word. Suppose every code word has an even numbers of 1’s in it. From this, we canconclude that the minimum Hamming distance for such a code will be at least two (at least twobits need to be flipped to get from codeword A to codeword B, since flipping one bit makes thenumber of 1’s odd).1CS232 Fall 2006 Discussion 11: ECC Dec 4, 2006Problems1. Every bit in a message is replicated k times before transmitting it over a noisy channel.How many errors in each set of k copies can be detected? How many can be corrected?2. Data is transmitted in byte-sized packets (i.e. 8 bits each). What is the largest number oferrors per packet that can occur so that a suitable correction scheme can correctly decodethe original data? How many “true” bits of data are transmitted per packet?3. A me ss age is m bits long and k redundant bits are added to ensure that any single-biterror can be detected and corrected. Show that 2k≥ m + k + 1.Hint: Each codeword c has size m + k bits, so there are m + k non-codewords that areHamming-distance 1 from c. Each of these non-codewords must be corrected to c.4. Bonus: Generalize your answer so that t errors can be detected and corrected (t ≥
View Full Document
Unlocking...