短十进制数的纠错

Question

我有短的、可变长度的十进制数字，例如：#41551，它们是由人类手动转录的。输入错误会导致不良结果，所以我的第一个想法是使用 Luhn 算法添加校验和 - #41551-3。然而，这只会检测到错误，而不会纠正它。看来添加另一个校验位应该能够检测并纠正个位数错误，因此给定#41515-3？（换位错误）我能够恢复正确的#41551。

像汉明码这样的东西似乎是合适的地方，但我无法弄清楚如何将它们应用于十进制数据，而不是二进制数据。是否有专门用于此用途的算法，或者 Hamming/Reed-Solomon 等可以适应这种情况吗？

Answer 1

是的，您还可以使用汉明码和检查方程进行校正。使用数据模 10 求和来查找校验位。将校验位放在 1、2、4、8、... 位置。

Answer 2

我只能提供带有五个额外数字的算法。
注意：5 个原始数字确实是最坏的情况。
通过 5 个额外数字，您可以对最多 11 个原始数字进行 ECC。
这类似于经典的 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]' 不等于 0 并且具有与 c4' 不同的值，那么您（至少）有两个数字的不可纠正的双重错误。

Answer 3

我尝试使用 Reed-Solomon，生成一个 3 位代码，最多可以纠正 1 位数字： https: //epxx.co/artigos/edc2_en.html