Friday, November 23, 2012

Notes - Error Detection and Correction

The following are notes from Computer Networks written by Tanenbaum 5th edition.
  • Communication channels have a wide range of characteristics
  • We must have a way to deal with errors
  • error correction codes
    • FEC(Forward Error Correction)
  • error detection codes
  • both must account for the types of erros that can occur, both have trade offs
    • burst error
    • single bit error
  • sometimes location of an error will be known, erasure channel
Error - Correcting Codes
  • four different codes
    • Hamming Codes
      • Hamming distance, the number of bits that are different between two sequences after exclusive or each bit together
      • to reliably detect d errors you need a distance d+1 code
      • total length of a block is n = m + r
      • n bit code word
      • code rate is the fraction of a codeword that carries non redundant information
      • example
        • 0000000000, 0000011111, 1111100000, 1111111111
        • hamming distance of 5 so can correct double errors or quadruple errors
      • useful for understanding block codes
    • Binary Convolution Codes
      • convolution code, no natural size, as incoming bits come in perform some operation
      • each input bit produces two output bits on the right hand side that are XOR sums of the input and internal state
      • each state is kept in 6 memory registers, each time another bit is inputted all values are shifted to the right, constraint length of this code is k = 7
      • Viterbi algorithm
        • soft decision decoding determine likeliness of 1, 0
        • hard decision decode determine each bit is 0,1 before error correction 
    • Reed - Solomon Codes
      • linear block codes, systematic
      • operates on m bit symbols
      • based on fact that every n degree polynomial is determined by n + 1 points so if 2 points are received in error, we can find the third point that will still lie on the line
      • defined as polynomials that operate over finite fields, strong error correction properties makes them useful in DSL, CDs, DVDs and Blu-Ray
    • Low - Density Parity Check Codes
      • LDPC (Low - Density Parity Check Codes)
      • each output bit is formed from only a fraction of the input bits
      • matrix representation of code with low density of 1s, standard for video broadcasting, 10 Gbps Ethernet and 902.11
  • these all add redundancy to the information that is sent
  • systematic code, m data bits are sent along with check bits
  • linear code check bits are computed as a function of the data bits
    • usually using exclusive or
Error - Detecting Codes
  • types of codes
    • Parity
      • parity bit appended to the end of data to make the number of 1s in the codeword even or odd
      • 1011010 is sent in even parity it will be sent as 10110100 to signify that its already even by appending the 0
      • can only reliably detect single bit error
      • interleaving, can have multiple parity bits n x n matrix with parity bits at the end of each
      • n+1 burst will still be undetected but now capable of correcting bits
    • Checksums
      • 16 bit internet checksum used as part of IP
      • one's compliment arithmetic
    • CRCs(Cyclic Redundancy Checks)
      • polynomial code, treats bits as polynomial coefficients
      • sender and receiver agree upon generator polynomial G(x) in advance
      • algorithm
        • let r be degree of G(x) append r zero bits to the low order end of the frame so its now m+r bits
        • divide the bit string corresponding to G(x) into the bit string using modulo 2 division
        • subtract the remainder using modulo 2 subtraction, the result is checksummed frame to be sent
        • example as follows
      • with single bit or 2 single bit errors the division will not be able to grant the same checksum if burst length is r+1 the remainder will be zero if and only if the burst is identical to G(x)
      • IEE 802 standard is
      • detects all bursts of length 32 or less and all bursts that are odd

No comments:

Post a Comment