Chapter 8 Sec 8 5 Error Checking Error detection Error correction Parity approaches Hamming Codes Cyclic Redundancy Checking Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Error Detection and Correction Bit Error Rate statistical property Important where noise and signal integrity cannot be so easily controlled BER prob on reading a given bit will be in error I O and communications Magnetic Storage DRAM BER inside processor 10 18 BER outside processor 10 8 10 12 Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Parity Checking Error Detection Add a Parity Bit to the word Even Parity Make the parity bit 1 bit if needed to make number 1 of bits even else make it 0 Odd Parity Make the parity bit a 1 bit if needed to make number of 1 bits odd else make it 0 Example for word 10011010 to add odd parity bit 100110101 What sort of errors can be detected Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Hamming Codes Hamming codes are a class of codes that use combinations of parity checks to both detect and correct errors They add a group of parity check bits to the data bits For ease of visualization intersperse the parity bits within the data bits Reserve bit locations numbered 1 r whose bit numbers are powers of 2 for the parity bits A given parity bit is computed from data bits whose bit numbers contain a 1 at the parity bit number Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Multiple Parity Checks Making up a Hamming Code Check 2 Check 1 Check 0 Bit position 1 2 3 4 5 6 7 P1 P2 D3 P4 D5 D6 D7 20 21 001 010 101 110 111 P1 22 011 100 D3 P2 D5 D3 P4 Parity or data bit D5 D7 D6 D7 D6 D7 Thus each bit takes part in a different combination of parity checks When the word is checked if only one bit is in error all the parity bits that use it in their computation will be incorrect Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Exp Venn Diagram showing Error Detection Correction using the Hamming Code a insert data a Sender computes inserts even parity bits a Receiver recomputes parity bits detects and corrects error P1 P2 011 location of the bit in error Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Encode 1011 Using the Hamming Code Odd Parity D3 D5 D6 D7 Insert the data bits P1 P2 1 P4 0 1 1 P1 is computed from P1 D3 D5 D7 1 so P1 1 P2 is computed from P2 D3 D6 D7 1 so P2 0 P4 is computed from P4 D5 D6 D7 1 so P4 1 The final encoded number is 1 0 1 1 0 1 1 Note that the Hamming encoding scheme assumes that at most one bit is in error Comp Sys Design Arch 2nd Ed 2004 Prentice Hall SECDED Single Error Correct Double Error Detect Add another parity bit at position 0 computed to over all bits data parity Let ci the check bit I be 1 if check i fails otherwise 0 In the case of a 1 bit error In the case of a 2 bit error The string ck 1 c1 c0 will be the binary index of the erroneous bit as before The overall parity will be wrong One or more Hamming checks will fail The overall parity will be correct Assumption The probability of 3 bits being in error is negligible Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Compute the odd parity SECDED encoding of 01101011 The 8 data bits 01101011 would have 5 parity bits added to them to make the 13 bit value P0 P1 P2 0 P4 1 1 0 P8 1 0 1 1 D1 D2 D3 D4 D5 D6 D7 D8 P1 D1 D2 0 0 1 D4 D5 0 1 D7 1 P2 D1 P4 D3 D4 D2 D3 D4 D6 D7 D8 P8 D5 D6 D7 D8 Now P1 0 P2 1 P4 0 P8 0 and we can compute that P0 overall parity 1 giving the encoded value 1010011001011 Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Extract the Correct Data Value from the SECDEDEncoded String 0110101101101 Assuming odd Parity The string shows even parity so there must be a single bit in error Checks c2 and c4 fail giving the binary index of the erroneous bits as 0110 6 so D6 is in error It should be 0 instead of 1 Comp Sys Design Arch 2nd Ed 2004 Prentice Hall SECDED Single Error Correct Double Error Detect SEC SECDED DATA BITS CHK BITS iNCREASE CHK BITS iNCREASE 8 4 50 5 62 5 16 5 31 25 6 37 5 32 6 18 75 7 21 88 64 7 10 94 8 12 5 128 8 6 25 9 7 03 256 9 3 52 10 3 91 Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Cyclic Redundancy Check CRC When data is transmitted serially over communications lines the pattern of errors usually results in several or many bits in error due to the nature of line noise e g crackling noise on telephone lines is this kind of noise Parity checks are not as useful in these cases Instead CRC checks are used The CRC can be generated serially It usually consists of XOR gates Comp Sys Design Arch 2nd Ed 2004 Prentice Hall CRC Generator Based on the Polynomial x16 x12 x5 1 b0 b1 b2 b3 b4 Data b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 The number position of XOR gates is determined by the polynomial CRC does not support error correction but the CRC bits generated can be used to detect multi bit errors The CRC results in extra CRC bits which are appended to the data word sent along The receiving entity can check for errors by recomputing the CRC and comparing it with the one that was transmitted Comp Sys Design Arch 2nd Ed 2004 Prentice Hall Serial Data Transmission with Appended CRC Code Word 1 Word 2 Word 3 Word 4 Word N CRC Generator CRC Word N Word 3 Word 2 Word 1 Sending a Packet Output Buffer Comp Sys Design Arch 2nd Ed time Transmission Line 2004 Prentice Hall Receiving Serial Data with Appended CRC Input Buffer CRC Generator Received CRC Transmission Line Input YES NO Received Packet Correct Send ACK Word 1 Word 2 Word 3 Word 4 Word N Received Packet Incorrect Send NACK Word N Word 3 Word 2 Word 1 time Comp Sys Design Arch 2nd Ed 2004 Prentice Hall