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

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

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


checksum data-entry error-correction
person Gavin Wahl    schedule 10.11.2011    source источник
comment
Я думаю, что это очень сложная проблема из-за странных ошибок канала: отсутствие цифры, замена двух цифр и т. д.   -  person Szocske    schedule 06.03.2012
comment
Вау, люди действительно не хотят даже нажимать на этот вопрос.   -  person Prof. Falken    schedule 31.08.2015

Ответы (3)


arrow_upward
4
arrow_downward

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

person varun j    schedule 17.11.2011

arrow_upward
0
arrow_downward

Я могу предоставить алгоритм только с ПЯТЬЮ дополнительными цифрами. Примечание: 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.

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

person Ingo Blackman    schedule 19.01.2019

arrow_upward
0
arrow_downward

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

person epx    schedule 28.04.2020