jija

• Network


  Must be able to transfer data with complete accuracy
• Data can be corrupted during transmission
• Error detection and correction


  Mechanism required to detect and correct errors
• Single-bit error


  • Only 1 bit in the data unit has changed from 1 to 0 or from 0 to 1
• Burst error


  • 2 or more bits in the data unit have changed from 1 to 0 or from 0 to 1

  
• Redundancy concept


  Adding extra bits to original data by the sender in order to detect or correct errors

  
• Error detection


  Just to see if any error has occurred, number of errors is not important
• Error correction


  Need to know the exact number of bits that are corrupted, number of errors are important

  
• Modular-2 arithmetic


  Use XOR (exclusive OR) operation for both addition and subtraction
• Hamming distance


  The number of differences between corresponding bits of two words of the same size
• Block coding


  1. Divide message into blocks, each of k bits, called datawords

  2. Add r redundant bits to each block to make the length n = k + r, resulting n-bit blocks are called codewords
• Error detection in block coding


  Receiver checks if the received codeword is valid, if not, an error has occurred

  
• Linear block codes


  The exclusive OR (XOR) of any two valid codewords creates another valid codeword
• Simple parity-check code


  • Single-bit error-detecting code where n = k + 1 and dmin = 2
  • The extra bit, called the parity bit, is selected to make the total number of 1s in the codeword even or odd
  • Can detect either an even or odd number of errors

  
• Two-dimensional parity-check code


  • Organizes bits in a table (rows and columns), calculates parity bit for each data unit and table, increases likelihood of detecting burst errors
• Hamming codes


  • Originally designed with dmin = 3, can detect up to two errors or correct one single error
  • Relationship between m and n is n = 2^m - 1 and k = n - m

  
• Cyclic codes


  If a codeword is cyclically shifted (rotated), the result is another codeword
• Cyclic redundancy check (CRC)


  Used in networks such as LANs and WANs, can detect all burst errors that affect an odd number of bits and all burst errors of length less than or equal to the degree of the polynomial

  
• CRC encoder


  Divides the data by the generator polynomial and the remainder becomes the CRC
• CRC decoder


  Divides the received data (including CRC) by the generator polynomial, if the remainder is 0 then no error

  
• Checksum


  Used in the Internet by several protocols, based on the concept of redundancy
• One's complement


  Representation of numbers where the negative of a number is found by inverting all bits

  
• Internet checksum


  1. Sender divides message into 16-bit words, sets checksum to 0, adds all words using one's complement addition, complements the sum to get the checksum

  2. Receiver adds all words including checksum using one's complement addition, if final checksum is 0 then no error
• Checksum can detect all errors involving an odd number of bits as well as most errors involving an even number of bits

  
• Checksum cannot detect errors when one or more bits of a segment are damaged and the corresponding bit or bits of opposite value in a second segment are also damaged