DOC PREVIEW
U of I CS 438 - Error Coding

This preview shows page 1-2-3-4-5-34-35-36-37-68-69-70-71-72 out of 72 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 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 72 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 72 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Error Coding Transmission process may introduce errors into amessage. Single bit errors versus burst errors Detection: Requires a convention that some messages are invalid Hence requires extra bits An (n,k) code has codewords of n bits with k data bits andr = (n-k) redundant check bits Correction Forward error correction: many related code words map tothe same data word Detect errors and retry transmissionParity 1-bit error detection with parity Add an extra bit to a code to ensure an even (odd) numberof 1s Every code word has an even (odd) number of 1s01111000Validcodewords010110100000011111101001ParityEncoding: White – invalid(error)Voting 1-bit error correction with voting Every codeword is transmitted n times010110100000011111101001Voting: White – correct to 1Blue - correct to 001ValidcodewordsBasic Concept:Hamming Distance Hamming distance of two bitstrings = number of bitpositions in which they differ. If the valid words of a codehave minimum Hammingdistance D, then D-1 biterrors can be detected. If the valid words of a codehave minimum Hammingdistance D, then [(D-1)/2] biterrors can be corrected.1 0 1 1 01 1 0 1 0HD=2Examples Parity01111000Validcodewords010110100000011111101001ParityEncoding: White – invalid(error)010110100000011111101001Voting: White – correct to 1Blue - correct to 001Validcodewords VotingDigital Error DetectionTechniques Two-dimensional parity Detects up to 3-bit errors Good for burst errors IP checksum Simple addition Simple in software Used as backup to CRC Cyclic Redundancy Check (CRC) Powerful mathematics Tricky in software, simple in hardware Used in network adapterTwo-Dimensional Parity Use 1-dimensional parity Add one bit to a 7-bit code to ensure aneven/odd number of 1s Add 2nd dimension Add an extra byte to frame Bits are set to ensure even/odd number of1s in that position across all bytes in frame Comments Catches all 1-, 2- and 3-bit and most 4-biterrorsTwo-Dimensional Parity Use 1-dimensional parity Add one bit to a 7-bit code to ensure aneven/odd number of 1s Add 2nd dimension Add an extra byte to frame Bits are set to ensure even/odd number of1s in that position across all bytes in frame Comments Catches all 1-, 2- and 3-bit and most 4-biterrors010100111010011011110000111001101001011111DataTwo-Dimensional Parity Use 1-dimensional parity Add one bit to a 7-bit code to ensure aneven/odd number of 1s Add 2nd dimension Add an extra byte to frame Bits are set to ensure even/odd number of1s in that position across all bytes in frame Comments Catches all 1-, 2- and 3-bit and most 4-biterrors1011101111011 0ParityBitsParityByte010100111010011011110000111001101001011111DataInternet Checksum Idea Add up all the words Transmit the sum Internet Checksum Use 1’s complement addition on 16bit codewords Example Codewords: -5 -3 1’s complement binary: 1010 1100 1’s complement sum 1000 Comments Small number of redundant bits Easy to implement Not very robustIP Checksumu_short cksum(u_short *buf, int count) {register u_long sum = 0;while (count--) {sum += *buf++;if (sum & 0xFFFF0000) {/* carry occurred, so wrap around */sum &= 0xFFFF;sum++;}}return ~(sum & 0xFFFF);}Cyclic Redundancy Check(CRC) Goal Maximize protection, Minimize extra bits Idea Add k bits of redundant data to an n-bit message N-bit message is represented as a n-degree polynomial with each bit inthe message being the corresponding coefficient in the polynomial Example Message = 10011010 Polynomial= 1 ∗x7 + 0 ∗x6 + 0 ∗x5 + 1 ∗x4 + 1 ∗ x3 + 0 ∗x2 + 1 ∗x + 0= x7 + x4 + x3 + xCRC Select a divisor polynomial C(x) with degree k Example with k = 3: C(x) = x3 + x2 + 1 Transmit a polynomial P(x) that is evenly divisibleby C(x) P(x) = M(x) + k bitsCRC - Sender Steps T(x) = M(x) by xk (zero extending) Find remainder, R(x), from T(x)/C(x) P(x) = T(x) – R(x) ⇒ M(x) followed by R(x) Example M(x) = 10011010 = x7 + x4 + x3 + x C(x) = 1101 = x3 + x2 + 1 T(x) = 10011010000 R(x) = 101 P(x) = 10011010101CRC - Receiver Receive Polynomial P(x) + E(x) E(x) represents errors E(x) = 0, implies no errors Divide (P(x) + E(x)) by C(x) If result = 0, either No errors (E(x) = 0, and P(x) is evenly divisible by C(x)) (P(x) + E(x)) is exactly divisible by C(x), error will not bedetectedCRC – Example EncodingC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding1101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding1101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding11011101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding100111011101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding1001110111011101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding10011101100011011101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding100111011000110111011101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example Encoding1001110110001101101111011101k + 1 bit checksequence c,equivalent to adegree-kpolynomial10011010000Message plus kzerosC(x) = x3 + x2 + 1 = 1101 GeneratorM(x) = x7 + x4 + x3 + x = 10011010 MessageCRC – Example


View Full Document

U of I CS 438 - Error Coding

Documents in this Course
Routing

Routing

5 pages

TCP

TCP

26 pages

TROLL

TROLL

3 pages

Load more
Download Error Coding
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 Error Coding 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 Error Coding 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?