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