Error correction on a short decimal number

Question

I have short, variable length decimal numbers, like: #41551, that are manually transcribed by humans. Mistyping one will cause undesirable results, so my first thought is to use the Luhn algorithm to add a checksum -- #41551-3. However, that will only detect an error, not correct it. It seems adding another check digit should be able to detect and correct a single-digit error, so given #41515-3? (a transposition error) I'd be able to recover the correct #41551.

Something like a Hamming code seems like the right place to look, but I haven't been able to figure out how to apply them to decimal, instead of binary, data. Is there an algorithm intended for this use, or can Hamming/Reed-Solomon etc be adapted to this situation?

I think this is a very tricky issue due to the weird errors of the "channel": missing a digit, swapping two digits, etc. — Szocske, Mar 06 '12 at 08:52

score 4 · Answer 1 · edited Nov 17 '11 at 21:33

4

Yes, you can use Hamming codes in addition with check equations for correction. Use summation of data modulo 10 for finding check digits. Place check digits in 1,2,4,8, ... positions.

edited Nov 17 '11 at 21:33

Nightfirecat

11,432
6
35
51

answered Nov 17 '11 at 19:27

varun j

41
1

score 0 · Answer 2 · answered Jan 19 '19 at 15:18

I can only provide an algorithm with FIVE extra digits. Note: 5 original digits is really a worst case. With FIVE extra digits you can do ECC for up to 11 original digits. This like classical ECC calculations but in decimal:

Original (decimal) 5-digit number: o0,o1,o2,o3,o4

Distribute digits to positions 0..9 in the following manner:

0    1    2    3    4    5    6    7    8    9
               o0        o1   o2   o3        o4
c4   c0   c1        c2                  c3  <-  will be calculated check digits

Calculate digits at positions 1,2,4,8 like this:

c0, pos 1: (10 - (Sum positions 3,5,7,9)%10)%10
c1, pos 2: (10 - (Sum positions 3,6,7)%10)%10
c2, pos 4: (10 - (Sum positions 5,6,7)%10)%10
c3, pos 8: (10 - (Sum positions 9)%10)%10

AFTER this calculation, calculate digit at position:

c4, pos 0: (10 - (Sum positions 1..9)%10)%10

You might then reshuffle like this:

o0o1o2o3o4-c0c1c2c3c4

To check write all digits in the following order:

0  1  2  3  4  5  6  7  8  9
c4 c0 c1 o0 c2 o1 o2 o3 c3 o4

Then calculate:

c0' = (Sum positions 1,3,5,7,9)%10
c1' = (Sum positions 2,3,6,7)%10
c2' = (Sum positions 4,5,6,7)%10
c3' = (Sum positions 8,9)%10
c4' = (Sum all positions)%10

If c0',c1',c2',c3',c4' are all zero then there is no error.

If there are some c[0..3]' which are non-zero and ALL of the non-zero c[0..3]' have the value c4', then there is an error in one digit.

You can calculate the position of the erroneous digit and correct. (Exercise left to the reader).

If c[0..3]' are all zero and only c4' is unequal zero, then you have a one digit error in c4.

If a c[0..3]' is unequal zero and has a different value than c4' then you have (at least) an uncorrectable double error in two digits.

score 0 · Answer 3 · answered Apr 28 '20 at 13:18

0

I tried to use Reed-Solomon, generating a 3-digit code that can correct up to 1 digit: https://epxx.co/artigos/edc2_en.html

answered Apr 28 '20 at 13:18

epx

1,066
9
17

Error correction on a short decimal number

3 Answers3