Коррекция ошибок на короткое десятичное число

У меня короткие десятичные числа с переменной длиной слова, например: #41551, которые вручную транслируются людьми. Ошибочный результат вызовет нежелательные результаты, поэтому моя первая мысль - использовать алгоритм Луна для добавления контрольной суммы - #41551-3. Тем не менее, это только обнаружит ошибку, не исправляет ее. Кажется, добавление еще одной контрольной цифры должно быть в состоянии обнаружить и исправить одноразрядную ошибку, поэтому, учитывая #41515-3? (ошибка транспонирования), я смогу восстановить правильный #41551.

Что-то вроде кода Хэмминга выглядит как подходящее место для поиска, но я не смог понять, как применять их к десятичным, а не двоичным, данным. Существует ли алгоритм, предназначенный для этого использования, или можно адаптировать Хэмминг/Рид-Соломон и т.д. К этой ситуации?

Ответ 1

Да, вы можете использовать коды Хэмминга в дополнение к уравнениям проверки для коррекции. Используйте суммирование данных по модулю 10 для нахождения контрольных цифр. Поместите контрольные цифры в позиции 1,2,4,8,....

Ответ 2

Я могу предоставить алгоритм только с пятью дополнительными цифрами. Примечание: 5 оригинальных цифр - действительно худший случай. С ПЯТЬю дополнительными цифрами вы можете сделать ECC до 11 оригинальных цифр. Это как классические вычисления ECC, но в десятичном виде:

Оригинальное (десятичное) 5-значное число: o0, o1, o2, o3, o4

Распределите цифры по позициям 0..9 следующим образом:

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

Рассчитайте цифры в позициях 1,2,4,8 следующим образом:

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

ПОСЛЕ этого расчета рассчитайте цифру в позиции:

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

Вы можете затем перестановить, как это:

o0o1o2o3o4-c0c1c2c3c4

Для проверки напишите все цифры в следующем порядке:

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

Затем рассчитайте:

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

Если c0 ', c1', c2 ', c3', c4 'равны нулю, то ошибки нет.

Если есть некоторые c [0..3] ', которые не равны нулю, и ВСЕ ненулевые c [0..3]' имеют значение c4 ', то возникает ошибка в одной цифре.

Вы можете рассчитать позицию ошибочной цифры и исправить. (Упражнение оставлено читателю).

Если c [0..3] 'все равны нулю и только c4' является неравным нулем, то у вас есть ошибка с одной цифрой в c4.

Если ac [0..3] 'не равен нулю и имеет значение, отличное от c4', то у вас есть (как минимум) неисправимая двойная ошибка в две цифры.