What is the advantage of this checksum method in NHS numbers?

Question

All British citizens are provided with a National Health Service (NHS) number either at birth or when they first register with an NHS doctor. According to the NHS Number wikipedia page, the 10 digit number contains a checksum digit, which is calculated using the following algorithm:

The current system uses a ten-digit number in '3 3 4' format with the final digit being an error-detecting checksum. Examples given include 987 654 4321.[4]

The checksum is calculated by multiplying each of the first nine digits by 11 minus its position. Using the number 943 476 5919 as an example:

The first digit is 9. This is multiplied by 10.

The second digit is 4. This is multiplied by 9.

And so on until the ninth digit (1) is multiplied by 2.

The result of this calculation is summed. In this example: >910+49+38+47+76+65+54+93+1*2 = 299.

The remainder when dividing this number by 11 is calculated, yielding a number in the range 0–10, which would be 2 in this case.

Finally, this number is subtracted from 11 to give the checksum in the range 1–11, in this case 9, which becomes the last digit of the NHS number.

A checksum of 11 is represented by 0 in the final NHS number. If the checksum is 10 then the number is not valid.

This seems to be a rather complicated method of acquiring a checksum, so my question is: what is the advantage of using this particular checksum method for these numbers?

Answer 1

The general purpose of checksums is to allow errors in transcription to be detected by means of a simple algorithm applied to the number itself, and without access to any other information (such as access to central records).

Error-detection methods require a certain amount of redundancy in the data, and there is generally a desire to economise on the amount of redundancy, because handling additional data increases the clerical workload, and increases the very risk of transcription errors whose occurrence you are trying to detect and prevent. You wouldn't want to double the number of digits, for example, as the price of including a checksum.

Therefore, most checksums are tailored to detecting certain kinds of the most common transcription errors whilst introducing the smallest possible amount of redundancy into the data.

If I remember correctly, the most common transcription error is getting a single digit in a single position wrong, followed in second place by the swapping of two adjacent digits (i.e. getting two digits in two positions wrong, but in a specific pattern).

Many trivial algorithms can detect the first kind of error - the change of one digit in one place. The most trivial is just adding up all the digits - hence the name, "checksum".

But the algorithm you describe is specifically designed to detect the second kind of error as well as the first, and without introducing any extra checksum digits.

The general tradeoff with complicated algorithms is that more-commonly-encountered kinds of error are detected, at the expense of the algorithm detecting fewer more-rarely-encourered kinds of error. But more complicated algorithms therefore detect more errors overall, because they are better at detecting the errors that clerks frequently make, and the errors they cannot detect are errors of the kind that clerks rarely make anyway.

A particular feature of the algorithm you describe is that when applied to any possible input number, it produces a result between 0 and 10 for the checksum, the last of which requires two digits to represent (in decimal numbers, which run 0-9).

Since it is undesirable to introduce additional digits, and because the designers probably didn't want to introduce an alphanumeric aspect (such as how hexadecimal numbers are represented by 0-9 then A-F, or how the ISBN checksum scheme represents 10 using the letter 'X', which corresponds to the Roman numeral for 10), they simply don't allocate base numbers which cause a checksum of 10.

Because no valid base number then has a checksum of 10, any calculated checksum of 10 always indicates a transcription error.

As to why they chose to disallow a checksum of 10 specifically (when they could have chosen any in the range 1 to 11), I cannot say offhand, but there is almost certainly some additional statistical or computational rationale, that either makes the algorithm more straightforward to apply (by hand or by computer), or which maximises the overall number of transcription errors detected.

Answer 2

This is the same idea that is in the Varshamov-Tenengolts code with some modifications as explained in the answer above by @Steve.

Since $p=11$ is prime, the set of integers modulo 11, denoted $GF(11),$ is a field (nonzero elements are invertible, you have distributive law, etc). If we have a parity check of the form $$ C=\sum_{k=1}^n k x_k \pmod{11} $$ or its negative (we are subtracting from 11 which is taking a negative in the field $GF(11)$ which is the case here: $$ C=-\sum_{k=1}^n k x_k \pmod{11} $$ One can observe the digits and re-compute the parity check digit. This would be $C_{correct}$ and is equal to $C_{printed} if there are no errors.

If there is a symbol error printed in position $k,$ we can recalculate what the check should be, and solve $$ C_{printed}-C_{correct} = k \delta \pmod{11} $$ uniquely for $k$ and $\delta$ since a linear map $$ k\mapsto k \delta $$ is a permutation in $GF(11)$ (It is one to one and hence invertible). If the digit in location $k$ did not get printed, then you know $k$ and you can solve and get the correct digit by the same method.