Блог

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

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

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

Я могу предоставить алгоритм только с ПЯТЬЮ дополнительными цифрами. Примечание: 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))
c1, pos 2: (10 - (Sum positions 3,6,7))
c2, pos 4: (10 - (Sum positions 5,6,7))
c3, pos 8: (10 - (Sum positions 9))
  

ПОСЛЕ этого вычисления вычислите цифру в позиции:

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

Затем вы можете произвести перестановку следующим образом:

 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)
c1' = (Sum positions 2,3,6,7)
c2' = (Sum positions 4,5,6,7)
c3' = (Sum positions 8,9)
c4' = (Sum all positions)
  

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

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

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

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

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

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