Casting Out Nines
"Casting out Nines" is an ancient Arabic expression that describes the use of the fact that the sum of the digits of any number is equal to it's modulus(9), ie the remainder of that number divided by nine. For larger numbers, you have to repeat the process until the sum is only one digit. They used it to check their accounting sums. ie if A+B=C then A(mod9) + B(mod9) = C(mod9).A popular email number puzzle uses this, by multiplying a random "secret" number by 9 making X(mod9)=0, add K, (K=1 to 8), and then adding the digits which will always total K, (0+K=K). To hide the process, you add extra steps in the middle and at the end.
Another is found at http://digicc.com/fido/ . This one uses the fact that numbers made of the same set of digits will have the same remainder when divided by 9. So if you subtract one from another, the result will have a zero remainder, ie be divisible by 9. They them ask for all but one digit of the result. Then the digit you kept "secret" can be calculated as 9 - (sum of the other digits)mod(9). Bankers will recognize this as the principle behind the fact that is your balance error is divisible by 9, the error is likely due to transposed digits.
Forward Error Correction
Casting out Nines was perhaps the first error detection algorithm. Today, we use error detection and correction in just about every electronic data system, including music CDs and DVD movies. It is called forward error correction because we add extra data at the source of the recording, or transmission, to make correcting errors possible at the receiving end. This is quite a science, and still being developed today.The most common FEC system is called Reed-Solomon Codes. The basic plan is to record data in blocks, and add extra redundancy data so that the block represents a number that is a multiple of several specially chosen constants. When we receive the data block, we divide it by each of these constants. If the remainders (called syndromes) are not all zero, then we know an error has occurred.
Provided the number of errors is less than half the number of extra redundancy data, we can use the syndromes to locate and quantify the errors, then subtract out the errors leaving error free data. Because we are correcting the whole block, it doesn't mater where in the block the error happened. It can be in the original data, or in the added redundancy data. There are many constraints and calculations for this to work, but I will not try to describe them here. For more detail see:
An Introduction to Error Correcting Codes