2.2 Methods of error detection

• why we need to check for error?

  - electrical interference - can corrupt data

  - packet switching - data can be lost or unsynchronised

  - skewing of data - bits arrive but not longer synchronised
• Parity checks

  Checks a byte of data

  
  

  Check is performed when data is received

  
  

  A parity bit is added (to the parity byte - as an 8th bit)

  
  

  Counts / checks number of 1's //

  Counts / checks to see if 1's in total are even/odd

  
  

  Can be even or odd

  
  

  If parity is incorrect, error is detected
• Parity blocks


  can be used to determine exactly which bit has been corrupted / changed following data transmission
• Checksum


  - A digit calculated by agreed algorithm between ( S+R computer)

  - representing the sum of the correct digits

  - in a piece of stored or transmitted digital data,

  - against which later comparisons can be made to detect errors in the data.
• Check digits

  
  

  e.g ?

  
  

  can detect?

  - check digit is a value calculated by modulo-11 or ISBN-13

  - digit is added onto end of num ( right hand side)

  
  

  - check digit used to ensure barcode is read correctly

  
  

  - incorrect digits entered

  - transposition errors

  - omitted or extra digits in the number

  - phonetic errors e.g 13 instead of 30
• Echo check


  - Data sent to and from another device twice.

  - Sender compares 2 sets of data,

  - if the sets of data are different, an error has occurred.

  - it is not known when error occurred, either 1st send or on the echo send
• Automatic repeat requests ( ARQ)

  - use positive and negative acknowledgements and timeout

  - receiving device receives error detection code as part of data (usually CRC)

  - this is used to check is any errors occurred during transmission.

  - if no errors, a positive acknowledgement sent to sending device

  
  

  - if error is detected send a negative acknowledgement, and requests a re-transmission of the data.
• How does timeout work on ARQ checks?

  - used by the sending device by waiting a predetermined amount of time

  - if no acknowledgement of any type by

  then it automatically resends the data

  - until a positive acknowledgement is received

  - or until pre-determined number of re-transmission has taken place.
• The ISBN-10 and the ISSN checksum

  1. First all digits are multiplied individually with a multiplier.
  2. If result 11 is calculated for this checksum procedure, the checksum is 0.
  3. As result the 0 could not be calculated, because in the previous step (remainder with division by 11) 11 is impossible as a result.
  4. The multiplier corresponds to the position of the digit + 1 from the right.
  5. All resulting products are added.
  6. The result is then divided by 11.
  7. The resulting remainder is subtracted from 11 and results in the check digit.
• example of Modulo - 11

  Digits: 3 9 2 8 4 4 4 0 4

  
  

  Weight: 10 9 8 7 6 5 4 3 2

  
  

  Results:30 + 81 + 16 + 56 + 24 + 20 + 16 + 0 + 8 = 251

  
  

  Calculate checksum:251 / 11 = 22

  
  

  Remainder 9 -> 11 - 9 = 2

  
  

  Check digit2
• ISBN 13

  1. Take the first 12 digits of the 13-digit ISBN

  2. Multiply each number in turn, from left to right by a number. The first digit is multiplied by 1, the second by 3, the third by 1 gain, the fourth by 3 again, and so on to the eleventh which is multiplied by 1 and the twelfth by 3.

  3. Add all of the 12 answers.

  4. Do a modulo 10 division on the result from step 2. (It's just the remainder from a whole number division by 10.)

  5. Take that remainder result from step 4.

  6. If the remainders isn't zero then subtract the remainder from 10. The answer to that is your check digit.