02 Check Digit

Check Digit

Check Digit

Recall: Chapter 1

Data validation: process to ensure that the data entered is sensible and reasonable

Type	Check if:	Example
Range check	Data value is within certain range	Marks from 0-100
Format check	Data is in right format	dd/mm/yy
Length check	Length of data is entered into a field	Length of password
Presence check	Data is entered into a field	Username cannot be left blank
Check digit	Other digits are correct, checked using last 1 or 2 digits in data	ISBN of a book

Check digit algorithms capture human transcription errors (errors in data entry, e.g. typo error)

⇒ MUST KNOW name of errors!

Incorrect digit errors	E.g. 1234 → 1235
Transposition errors	E.g. 1234 → 1324
Phonetic errors	E.g. 60 (“sixty”) → 16 (“sixteen”)
Omitted digits	E.g. 1234 → 123
Extra digits	E.g. 1234 → 12341

Esp for code numbers (e.g. customer number / product number): often lengthy, prone to errors when being keyed in ⇒ to prevent errors, add a check digit to the end of the code number

• The check digit is arrived by applying some algorithm to the digits of the code number
• E.g. Modulo 11, ISBN-13
• ⇒ The code number with its check digit is self-checking

ISBN 13

• The final character of a ten-digit International Standard Book Number (ISBN)
• 1 x (sum of all “odd-place” digit [i.e. 1st, 3rd, 5th, etc])
• 3 x (sum of all “even-place” digit)
• Add the 2 sums, divide by 10, get remainder
• 10 - remainder = check digit
• If remainder = 0, check digit = 0
• 22. CAMBRIDGE IGCSE (0478-0984) 2.2 Check digits
• Using CHECK DIGITS - MODULO11 and ISBN13 - Data Transmission in Computer Science

Modulus 11 System: find the check digit (used in ISBN 10)

• Multiplying each digit by its position in the number (counting from the right) and taking the sum of these products modulo 11 is 0
• Each digit of the code is assigned with a weight
• Right hand digit is given a weight of 2
• Next digit to the left is 3
• And so on
• ⇒ The check digit to be appended will have a weight of 1
• Each digit is multiplied by its weight and the products are added together
• Sum of the product is divided by 11 and the remainder is subtracted from 11 to give the check digit
• If remainder = 0, check digit 11 (11-0=11) is converted to 0
• If remainder = 1, check digit 10 (11-1=10) is replaced by X
• Else, check digit = remainder
• To validate the check digit, include check digit (at the end of the number) in calculation (with weight of 1) → sum of products should be divisible by 11, then check digit is valid
• E.g. NRIC: last alphabet is a check digit

The weight for the SG NRIC number is: 2 | 7 | 6 | 5 | 4 | 3 | 2 Conversion table to convert the check digit to the corresponding alphabet: Check digit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 Alphabet | A | B | C | D | E | F | G | H | I | Z | J To calculate check digit for the NRIC number 0123456: Original number: | 0 | 1 | 2 | 3 | 4 | 5 | 6 Weights | 2 | 7 | 6 | 5 | 4 | 3 | 2 Multiply digits by its weights: | 0 | 7 | 12 | 15 | 16 | 15 | 12 Add products together: | 0 + 7 + 12 + 15 + 16 + 15 + 12 = 77 Divide by 11: | 7 remainder 0 Subtract remainder from 11: | 11 - 0 = 11 Check digit: | J NRIC no. = S0123456J

Tutorial (NOT MARKED)

1. 
   

Check digits ensure that there has been no error when the membership account number was typed, since this number is long and thus prone to errors when typing. A check digit is a redundant digit or letter calculated from digits of a code number. It is then added to the code number that permits the accuracy of other digits in the code to be checked

Pseudocode to find check digit

BEGIN // (save time, only array declaration is a MUST) DECLARE account_no: STRING DECLARE weight: INTEGER DECLARE sum: INTEGER DECLARE value: INTEGER DECLARE remainder: INTEGER DECLARE check_digit_value: INTEGER DECLARE check_digit_char: STRING DECLARE check_digit: STRING INPUT account_no weight ← 7 sum ← 0 # check first 5 digits out of the 6 (exclude check digit first) FOR i ← 1 TO ~~LENGTH(account_no)~~5 # don’t reverse the string; do according to qn which is from left to right and decrement weight value ← int(account_no[i]) * weight sum ← sum + value weight ← weight - 1 i ← i + 1 # NOT NEEDED FOR FOR LOOP ENDFOR remainder ← sum % 11 check_digit_value ← 11 - remainder (# i think this is a good method lol) check_digit_char ← [‘C’,‘D’,‘E’,‘F’,‘G’,‘H’,‘I’,‘J’,‘K’,‘L’,‘M’] check_digit ← check_digit_char[check_digit_value] END

BEGIN DECLARE account_no: STRING DECLARE check_digit: STRING DECLARE check_digit_value: INTEGER DECLARE sum: INTEGER DECLARE value: INTEGER INPUT account_no check_digit ← account_no[LENGTH(account_no] // (try not to use negative index account_no[-1] for pseudocode) check_digit_char ← [C,D,E,F,G,H,I,J,K,L,M] FOR i ← 1 TO LENGTH(check_digit_char) IF check_digit_char[i] = check_digit check_digit_value ← i ENDIF ENDFOR weight ← 7 sum ← 0 FOR i ← 1 TO LENGTH(account_no) - 1 value ← int1(account_no[i]) * weight sum ← sum + value weight ← weight - 1 ENDFOR sum ← sum + 21 * check_digit_value # (note: weight of check digit is 1 not 2 !!!) IF sum % 11 == 0 OUTPUT “valid membership account number” ELSE OUTPUT “invalid membership account number” ENDIF END
sum ← 0 weight ← 7 # INTEGER(‘x’) returns integer value of letter x FOR i ← 1 TO 5 # note: dont check 6th digit yet, which is check digit sum ← sum + INTEGER(account[i]) * weight weight ← weight - 1 ENDFOR # ASCII(x) returns the ASCII value of the letter x # (minus off the ASCII value of C then +1 to get 1-11) Check digit: C-1, D-2, E-3,…,M-11 checkDigit ← ASCII(account[6]) - ASCII(‘C’) + 1 totalWeightedSum ← sum + checkDigit # a MOD b returns the remainder after dividing a by b IF totalWeightedSum MOD 11 = 0 OUTPUT “Valid” ELSE OUTPUT “Invalid” ENDIF

Check digit is last character in the string 47938K which is K. K is the 9th element of the list check_digit_char. Thus, its check digit value is 9. Using the respective weights, sum = (4*7) + (7*6) + (9*5) + (3*4) + (8*3) + (9*21) = 169160. 169 divided by 11 gives a remainder of 4, not 0. 160 is not divisible by 11. Thus, 47938K is invalid.

def check_digit(input_value): # validates input_data, returns -1 if invalid # checks for valid data types if (type(input_value) != int) and (type(input_value) != str): # (and not or!) return -1 # checks for valid length and containing digits input_value = str(input_value) if len(str(input_value)) != 14 or (not input_value.isdigit()): return -1 else: # (i think no need cos if return -1 function alr ends) new_string = "" input_value = str(input_value) sum = 0 for i in range(len(input_value)): for i in range(13, -1, -1): # check every digit in the string, starting from the right (must follow what qn said!!!) digit = int(input_value[i]) if i % 2 == 1: # digit in odd numbered position # double the digit doubled = digit * 2 # add sum of digits if doubled >= 10 (i.e. 2 digit no.) # add the doubled digits to sum # tens digit = doubled // 10; ones digit = doubled % 10 sum += doubled // 10 + doubled % 10 else: # digit in even numbered position sum += digit check_digit = sum % 10 # modulo 10 check digit if check digit != 0: # (cos if remainder 0, check digit is still 0, not 10) check_digit = 10 - check_digit return 10 - check_digit print(check_digit(14576567654934))

Comments from the Word document

Footnotes

1. Comment by ANDREA TAN KAI XUAN HCI: is this allowed for pseudocodes ↩