Исправление ошибок на коротком десятичном числе

Question

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

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

Answer 1

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

Answer 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', то у вас есть (как минимум) неисправимая двойная ошибка из двух цифр.