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

Question

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

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

Answer 1

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

Answer 2

Я попытался использовать код Рида-Соломона, создав трехзначный код, который может исправить до 1 цифры: https://epxx.co/artigos/edc2_en.html

Answer 3

Я могу предоставить алгоритм только с пятью дополнительными цифрами. Примечание: 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 возникает ошибка с одной цифрой.

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