Check Digits (CIE IGCSE Computer Science)

• Check Digits to determine if data has been corrupted but do not reveal where
• Data is sent in blocks and an additional check digit value is added at the end of the block
• Check Digits are custom user-created algorithms that perform mathematical calculations on data
  
• An example of a check digit is the ISBN value on books:
  • Each book has a unique ISBN number that identifies the book
  • A standard ISBN number may be ten digits, for example, 965-448-765-9
  • The check digit value is the final digit (9 in this example). This number is chosen specifically so that when the algorithm is completed the result is a whole number (an integer) with no remainder parts
  • A check digit algorithm is performed on the ISBN number. If the result is a whole number then the ISBN is valid

ISBN Check Digit Walkthrough

• • • To calculate an ISBN check digit the following algorithm is performed on 965-448-765-9:

      • Multiply each ISBN digit by 1 to 10 and add them all up: 

        • 9x1 + 6x2 + 5x3 + 4x4 + 4x5 + 8x6 + 7x7 + 6x8 + 5x9 + 9x10 = 352

      • Take the total number and divide it by 11: 352/11 = 32. 32 is a whole number with no remainder so the ISBN is valid
        

• Another example of a check digit is barcodes on purchasable items:
  • Barcodes consist of black and white lines which can be scanned using barcode scanners. Barcode scanners shine a laser on the black and white lines which reflect light into the scanner. The scanner reads the distance between these lines as numbers and can identify the item
  • Barcodes also use a set of digits to uniquely identify each item. The number of digits varies from code to code. An example would be 9780201379624
  • The final digit on a barcode is usually the check digit. Like an ISBN this can be used to validate and authenticate an item
    

Barcode Check Digit Walkthrough

• • To calculate a barcode check digit we can perform the following example algorithm on 9780201379624 (the final digit is the check digit):
    • Multiply each digit by 1 or 3, alternating between these two values and add them all up
      • 9x1 + 7x3 + 8x1 + 0x3 + 2x1 + 0x3 + 1x1 + 3x3 + 7x1 + 9x3 + 6x1 + 2x3 = 96
        
    • The check digit (the final digit) should be the difference between the sum and the closest multiple of 10 that is larger or equal to the sum
      • 96 rounded to the nearest 10 = 100
      • 100-96 = 4
      • The check digit is therefore 4 which matches our original barcode number
        
• An example of a custom check digit algorithm in computer science is:
  • A check digit byte is defined as a value between 1 and 255 which is stored in 8 bits. 8 bits are collectively known as a byte
  • If the sum of all of the bytes of a transmitted block of data is <= 255 then the check digit value is the sum of all of the bytes
  • If the sum of all of the bytes is > 255 then the check digit is calculated with an algorithm:
    • X = sum of all of the bytes
    • Y = X / 256
    • Round down Y to a nearest whole number
    • Z = Y * 256
    • Check digit = X - Z
      

Custom Check Digit Walkthrough

• • If X = 1496
    • Y = 1496 / 256 = 5.84
    • Rounded down Y = 5
    • Z = 5 * 256 = 1280
    • Check digit = 1496 - 1280 = 216
  • The check digit value in this example would be 216
    
• When a block of data is to be transmitted, the check digit is first calculated and then transmitted with the rest of the data
• When the data is received the check digit value is calculated based on the received data and compared to the check digit value received. If they are the same then the data does not contain any errors
• If an error does occur then a resend request is sent and the data is retransmitted