Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Information RedundancyCode, codeword, binary codeError detection, error correctionHamming distance: –number of bits in which two words differOdd/even parity–the total number of 1s is odd/evenBasic 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/CorrectionLet’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 ParitySyndrome 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 ParityExample–data = 1110 0001–compute check bits:least significant bitmost significant bit6Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Overlapped ParityExample–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 codesAll code words are n bits in length and contain exactly m 1sSimple implementation: –add/append second data word–select word such that code word contains m 1s–code is separable–100% overheadHamming distance is 2–e.g. 1st error sets bit, 2nd error resets other bit9Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4ChecksumSeparable code to achieve error detection capabilityChecksum is the sum of the original dataSingle-precision checksum–overflow problem, i.e. adding n bits modulo 2nDouble-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 wordsResidue checksum–like single-precision checksum, but overflow is now fed back as carry10Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Cyclic codesCyclic 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 codesIdea 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 numberMultiply M by 2n to shift and add F to padded 0s12Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 4Dividing 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 codesTherefore, 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 codesexample, 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 codesWhat 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 + 1for G = 11001 we get G(X) = X4 + X3 + 1Math 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 + 1Hardware Implementation:cn-1cn-2c1c0+ + + + +...x x x
View Full Document