algorithm - 如何确定 6 + 1 位的最大纠错/检测方法？

Question

我对将从图像中识别的数字有以下限制:

• 6 位数据
• 1 位纠错
• 不能更改前 6 位数字(它们必须是人类可读的)
• 校验位必须是数字

目前的纠错方案是基于校验和，使得第 7 位是前 6 位和的最后一位。

例如

123456 => 1234561
999999 => 9999994
472912 => 4729125
219274 => 2192745

我如何确定此方案可以检测/纠正的错误数量和类型，是否有一种方案可以提供更好的错误检测？ (对于我的用例，错误检测比纠错更重要)。

Answer 1

你可以试试Luhn ，它比您描述的要复杂一些，但它会满足您的要求。

从维基百科复制粘贴:

The Luhn algorithm will detect any single-digit error, as well asalmost all transpositions of adjacent digits. It will not, however,detect transposition of the two-digit sequence 09 to 90 (or viceversa). It will detect 7 of the 10 possible twin errors (it will notdetect 22 ↔ 55, 33 ↔ 66 or 44 ↔ 77).

Other, more complex check-digitalgorithms (such as the Verhoeff algorithm and the Damm algorithm) candetect more transcription errors. The Luhn mod N algorithm is anextension that supports non-numerical strings.

Because the algorithmoperates on the digits in a right-to-left manner and zero digitsaffect the result only if they cause shift in position, zero-paddingthe beginning of a string of numbers does not affect the calculation.Therefore, systems that pad to a specific number of digits (byconverting 1234 to 0001234 for instance) can perform Luhn validationbefore or after the padding and achieve the same result.

Prepending a0 to odd-length numbers enables you to process the number from left toright rather than right to left, doubling the odd-place digits.

Thealgorithm appeared in a US Patent for a hand-held, mechanical devicefor computing the checksum. It was therefore required to be rathersimple. The device took the mod 10 sum by mechanical means. Thesubstitution digits, that is, the results of the double and reduceprocedure, were not produced mechanically. Rather, the digits weremarked in their permuted order on the body of the machine.