DOC PREVIEW
WUSTL CSE 362M - Chapter 8: Error Checking

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 8, Sec. 8.5 : Error CheckingError Detection and CorrectionParity Checking: Error DetectionHamming CodesMultiple Parity Checks Making up a Hamming CodeExp: Venn Diagram showing Error Detection & Correction using the Hamming CodeEncode 1011 Using the Hamming Code & Odd ParitySECDED (Single Error Correct, Double Error Detect)Compute the odd parity SECDED encoding of 01101011Extract the Correct Data Value from the SECDED-Encoded String 0110101101101, Assuming odd ParitySECDED (Single Error Correct, Double Error Detect)Cyclic Redundancy Check, CRCCRC Generator Based on the Polynomial x16 + x12 + x5 + 1.Serial Data Transmission with Appended CRC CodeReceiving Serial Data with Appended CRCComp Sys Design & Arch 2nd Ed © 2004 Prentice HallChapter 8, Sec. 8.5 : Error Checking Error detection – Error correction Parity approaches Hamming Codes Cyclic Redundancy CheckingComp Sys Design & Arch 2nd Ed © 2004 Prentice HallError Detection and Correction Bit Error Rate (statistical property) BER = prob {on reading, a given bit will be in error} Important where noise and signal integrity cannot be so easily controlled: I/O and communications Magnetic Storage DRAM BER inside processor ~ 10-18 BER outside processor ~ 10-8-10-12Comp Sys Design & Arch 2nd Ed © 2004 Prentice HallParity 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 HallHamming 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 HallMultiple Parity Checks Making up a Hamming Code 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.Bit positionP11P22D33P44D55D66D7Parity or data bit7Check 0Check 1Check 220 21 22001 010 011 100 101 110 111P1 = D3+ D5 + D7P2= D3+ D6+ D7P4= D5+ D6+ D7Comp Sys Design & Arch 2nd Ed © 2004 Prentice HallExp: Venn Diagram showing Error Detection & Correction using the Hamming Codea. insert dataa. Sender: computes & inserts even parity bitsa. Receiver: recomputes parity bits, detects and corrects error.P1+P2 = 011 Æ location of the bit in errorComp Sys Design & Arch 2nd Ed © 2004 Prentice HallEncode 1011 Using the Hamming Code & Odd Parity Insert the data bits: P1P21 P40 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 01 1. Note that the Hamming encoding scheme assumes that at most one bit is in error.D3D5D6D7Comp Sys Design & Arch 2nd Ed © 2004 Prentice HallSECDED (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: The string ck-1, . . ., c1, c0will be the binary index of the erroneous bit (as before). The overall parity will be wrong. In the case of a 2-bit error: 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 HallCompute the odd parity SECDED encoding of 01101011The 8 data bits 01101011 would have 5 parity bits added to them to make the 13-bit value:P0P1P20 P41 1 0 P81 0 1 1D1D2D3D4D5 D6D7D8-------------------------------------------------------------------------------------------------------------------------P1 = D1⊕ D2⊕ D4⊕ D5⊕ D70 = 0 1 0 1 1-------------------------------------------------------------------------------------------------------------------------P2= D1⊕ D3 ⊕ D4 ⊕ D6 ⊕ D7P4= D2⊕ D3 ⊕ D4 ⊕ D8P8= 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:1 0 1 0 0 1 1 0 0 1 0 1 1Comp Sys Design & Arch 2nd Ed © 2004 Prentice HallExtract the Correct Data Value from the SECDED-Encoded String 0110101101101, Assuming odd Parity The string shows even parity, so there must be a single bit in error. Checks c2and c4fail, giving the binary index of the erroneous bits as 0110 = 6, so D6 is in error. It should be 0 instead of 1Comp Sys Design & Arch 2nd Ed © 2004 Prentice HallSECDED (Single Error Correct, Double Error Detect)SEC SECDEDDATA BITSCHK BITS% iNCREASECHK BITS% iNCREASE84 50 5 62.5165 31.25 6 37.5326 18.75 7 21.88647 10.94 8 12.51288 6.25 9 7.032569 3.52 10 3.91Comp Sys Design & Arch 2nd Ed © 2004 Prentice HallCyclic Redundancy Check, CRC When data is transmitted serially over communications lines, thepattern 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 HallCRC Generator Based on the Polynomial x16+ x12+ x5+ 1. 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


View Full Document

WUSTL CSE 362M - Chapter 8: Error Checking

Download Chapter 8: Error Checking
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 8: Error Checking and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 8: Error Checking 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?