13

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

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

4

3 回答 3

4

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

于 2011-11-17T19:27:27.943 回答
0

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

于 2020-04-28T13:18:15.230 回答
0

我只能提供一个带有五个额外数字的算法。注意：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' 不同的值，那么您（至少）有两位数的不可纠正的双重错误。

于 2019-01-19T15:18:55.553 回答