Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Information Redundancy!Code, codeword, binary code!Error detection, error correction!Hamming distance: –number of bits in which two words differ!Odd/even parity–the total number of 1s is odd/even!Basic parity approaches–bit-per-word–bit-per-byte–bit-per-chip– bit-per-multiple-chips– interlaced parity1Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Error Detection/Correction!Let’s look at an old principle to error correction–Hamming Code–any computer organization book will be a good reference»e.g. William Stallings’ Computer Organization and Architecture–rely on check bits to identify whether bit has been changed–identification of changed bit allows for correction2Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Overlapped Parity m = data bitsk = parity bits3Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Overlapped Parity!Syndrome is derived from comparing, i.e. XOR, transmitted and received/recomputed check bits.!Syndrome has following characteristics (previous example)–if syndrome contains all 0’s»no error has been detected–if syndrome contains one and only one bit set to 1»error has occurred in one of the 4 check bits–if syndrome contains more than one bit set to 1»numerical value of the syndrome indicates the position of the data-bit error»this bit is then inverted for correction4Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Compute Check5Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Overlapped Parity!Example–data = 1110 0001–compute check bits:least significant bitmost significant bit6Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Overlapped Parity!Example–data sent is 1110 0001 and transmitted check bits are 1110–received data is: 01100001 »Note the most sig. bit has been corrupted–received check bits are: 1110–recomputed check bits:–Syndrome: 1110 XOR 0010 = 1100! C1 = 1 " 0 " 0 " 0 "1 = 0C2 = 1 " 0 " 0 " 1 " 1 = 1C3 = 0 " 0 " 0 " 0 = 0C4 = 0 "1 "1 " 0 = 07Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Applying SyndromeSyndrome 1100 detects D8 as faulty8Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4m-of-n codes!All code words are n bits in length and contain exactly m 1s!Simple implementation: –add/append second data word–select word such that code word contains m 1s–code is separable–100% overhead!Hamming distance is 2–e.g. 1st error sets bit, 2nd error resets other bit9Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Checksum!Separable code to achieve error detection capability!Checksum is the sum of the original data!Single-precision checksum–overflow problem, i.e. adding n bits modulo 2n!Double-precision checksum–uses double precision, i.e. compute 2n-bit checksum from n-bit words using modulo-22n arithmetic.!Honeywell checksum–compose word of double length by concatenating 2 consecutive words–compute checksum on these double words!Residue checksum–like single-precision checksum, but overflow is now fed back as carry10Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codes!Cyclic Redundancy Checks (CRC)–Parity bits still subject to burst noise, uses large overhead (potentially) for improvement of 2-4 orders of magnitude in probability of detection.–CRC is based on a mathematical calculation performed on message. We will use the following terms:»M - message to be sent (k bits)»F - Frame check sequence (FCS) to be appended to message (n bits)»T - Transmitted message includes both M and F =>(k+n bits)»G - a n+1 bit pattern (called generator) used to calculate F and check T11Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codes!Idea behind CRC–given a k-bit frame (message)–transmitter generates a n-bit sequence called frame check sequence (FCS)–so that resulting frame of size k+n is exactly divisible by some predetermined number!Multiply M by 2n to shift and add F to padded 0s12Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4!Dividing 2nM by G gives quotient and remainder then using R as our FCS we get on the receiving end, division by G leads toCyclic codesremainderis 1 bit less than divisorNote: mod 2 addition,no remainder13Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codes!Therefore, if the remainder of dividing the incoming signal by the generator G is zero, no transmission error occurred.!Assume T + E was received (Note: E is the error) since T/G does not produce a remainder, an error is detected only if E/G produces a non-zero value 14Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codes!example, assume generator G(X) has at least 3 terms–G(x) has three 1-bits»detects all single bit errors»detects all double bit errors»detects odd #’s of errors if G(X) contains the factor (X + 1)»any burst errors < length of FCS»most larger burst errors»it has been shown that if all error patterns likely, then the likelihood of a long burst not being detected is 1/2n 15Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codes!What does all of this mean?–A polynomial view:»View CRC process with all values expressed as polynomials in a dummy variable X with binary coefficients, where the coefficients correspond to the bits in the number."for M = 110011 we get M(X) = X5 + X4 + X + 1"for G = 11001 we get G(X) = X4 + X3 + 1"Math is still mod 2»An error E(X) is received and undetected iff it is divisible by G(X)16Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codes–Common CRCs»CRC-12 = X12 + X11 + X3 + X2 + X + 1»CRC-16 = X16 + X15 + X2 + 1»CRC-CCITT = X16 + X12 + X5 + 1»CRC-32 = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1!Hardware Implementation:cn-1cn-2c1c0+ + + + +...x x x