基于校验和方案的错误检测

Jeffrey Walton

4.72/5 (24投票s)

2006年11月27日

CPOL

12分钟阅读

94198

3121

流行校验和方案调查

引言

校验位（Check Digit）是一个附加在数字上的字母数字字符，用于检测错误。校验位是一种简单易行的方法，可以消除人为输入数据时引入的错误。校验位不是纠错码（Error Correcting Codes）。如果读者想了解更鲁棒的纠错码，请参考 Peterson 和 Weldon 的著作 Error-Correcting Codes。

值得注意的是，CRC码（循环冗余校验）不是校验位方案，因为它会生成多个字母数字位来检测错误。如果读者需要一个适用于非常长的数据集或二进制数据集的系统，可以考虑使用 32 位 CRC、Adler 校验和或基于哈希的校验和。Adler 校验和类似于冗余校验，用速度换取可靠性。在 A File Checksum Shell Menu Extension Dll 中提供了一个使用 CRC32、MD4、MD5、RIPEMD-160、SHA-1、Whirlpool 和 SHA-2 系列哈希的示例哈希应用程序。

本文将讨论以下校验位方案

模 9 方案
模 7 方案
模 11 方案
3-加权方法
IBM 方案
UPC 方案
Verhoeff 算法
ISO 7064 Mod N/N+1

此外，在算法之后，还会对群论进行初步介绍。

常见错误

根据 Richard Hamming 的说法，最常见的两种错误是

12 变成 21（相邻字符对调）
112 变成 122（数字重复错误）

Jacobus Verhoeff 在《Error Detecting Decimal Codes》一书中提出了以下统计数据

Error（错误）	近似百分比	注释
a → b	60% - 90%	单字符错误
ab → aab	10% - 20%	增加一个数字
aab → ab	10% - 20%	省略一个数字
ab → ba	10% - 20%	转置错误
aa → bb	0.5% - 1.5%	双重错误
acb → bca	> 1%	跳跃双重错误
13 → 30	0.5% - 1.5%	语音错误（发音相似）

下载次数

本文共有 5 个可下载内容。它们将在文章末尾提供。

模 9 方案

模 9 系统被美国邮政服务部门用于汇票。如果汇票号码是 123456789 且 c = 0，则汇票上印制的号码为 1234567890。该系统为 c = n % 9。此系统也称为“九余法”。九余法存在无法检测 0 → 9 和 9 → 0 的问题；并且也无法检测转置错误（除非涉及校验位）。

模 7 方案

比九余法更鲁棒的系统是模 7 系统。Bressoud 和 Wagon 在《Computationl Number Theory》一书中证明了以下结论：

单字符错误检测率为 93.81%
转置错误检测率为 93.87%

与模 9 方案类似，c = n % 7。但是，只有 3 种转置错误是无法检测的：70 ↔ 07、81 ↔ 18 和 92 ↔ 29。

模 11 方案

模 11 方案是一个加权方案，也称为国际标准书号 (ISBN)。前 9 位数字代表唯一标识符，第 10 位数字是校验位。由于该方案是模 11，校验位可以是 0-9 或 X。

这个基于模 11 的系统基于点积（即数字 n 的各个数字）。n · (10, 9, ..., 2, 1) mod 10。换句话说，设 a_i 为 n 的第 i 位数字（从最高位到最低位）。则

c = 10a₁ + 9a₂ + 8a₃ + 7a₄ + 6a₅ + 5a₆ + 4a₇ + 3a₈ + 2a₉ mod 11

第 10 位 (a₁₀) 将是 -c，因此以下方程（称为校验方程）成立。

0 = 10a₁ + 9a₂ + 8a₃ + 7a₄ + 6a₅ + 5a₆ + 4a₇ + 3a₈ + 2a₉ + 1a₁₀ mod 11

该方案可以检测所有单字符错误以及任意两位数字的对调（假设总数字位数不超过 10 位）。

// Check Digit Sample 3

_tstring number = _T("073560753"); // c should be 2
_tcout << _T("ISBN: ") << number << endl;

int i = 10, c = 0;
for( _tstring::const_iterator it  = number.begin();
                              it != number.end(); i--, it++ )
{
    if( _T('X') == *it )
        { c += 10 * i; }
    else
        { c += CharToNumber( *it ) * i; }

    c %= 11;        
}
    
// a_10 = -c
c = 11 - c;

if( 10 == c )
    { _tcout << _T("Check digit is: ") << _T("X") << endl; }
else
    { _tcout << _T("Check digit is: ") << c << endl; }

3-加权方法

3-加权方法也称为电子资金转账路由号码方案，由银行业使用。它是一个基于模 10 的系统，但它操作的不是整个数字 n，而是点积（即数字 n 的各个数字）。

因此，给定一个 8 位路由号码，校验位 c = n · (7, 3, 9, 7, 3, 9, 7, 3)，mod 10。换句话说，设 a_i 为 n 的第 i 位数字（从最高位到最低位）。则

c = 7a₁ + 3a₂ + 9a₃ + 7a₄ + 3a₅ + 9a₆ + 7a₇ + 3a₈ mod 10

c 然后连接到 8 位路由号码，形成一个 9 位路由号码。

该方案基于这样一个事实：当乘数是集合 { 1, 3, 7, 9 } 中的数字时，模 10 的乘法会产生 10 个十进制数字的排列；但如果乘数是 5 或偶数，则只会产生十进制数字的一个子集。此系统无法检测相差 5 的相邻数字对调。

3-加权方法不使用简单的模减运算，因此不需要 c = 10 - c 来保持等式。

读者应该会发现以下校验方程成立（其中 a₉ 是 -c）

0 = 7a₁ + 3a₂ + 9a₃ + 7a₄ + 3a₅ + 9a₆ + 7a₇ + 3a₈ + a₉ mod 10

下面将介绍 3-加权方案。读者可以看到，它很容易推广到任意位数的数字。但是，如果读者需要一个适用于非常长的数据集或二进制数据集的系统，请考虑使用 CRC 或 Adler 校验和，或基于哈希的校验和。

// Check Digit Sample 2

_tstring number = "12345678";

int i = 0, c = 0;
for( _tstring::const_iterator it  = number.begin();
                              it != number.end(); i++, it++ )
{
    switch( i % 3 + 1 )
    {
        case 1:
            c += 7 * CharToNumber( *it );
            break;
        case 2:
            c += 3 * CharToNumber( *it );
            break;
        case 3:
            c += 9 * CharToNumber( *it );
            break;
        default:
            assert( false );
            break;
    }

    c %= 10;
}

IBM 校验位方案

IBM 校验位方案是在整数域 (Z) 上可获得的最接近完美的系统。此方案被万事达卡和维萨卡以及加拿大社会保险号码等公司使用。该系统也称为 Luhn 算法。该方案可以检测所有单字符错误和除 0 ↔ 9 之外的所有转置错误。

校验位 c 定义为点积

-(a₁, a₂, a₃, a₄, ..., a_n-1, a_n) · (2, 1, 2, 1, ..., 1, 2) - r (mod 10)

r 是大于 5 的奇数索引数字的数量。这意味着如果 i 是奇数且 a_i> 5，则 r = r + 1。

实际上，该算法的实现方式有所不同。

// Check Digit Sample 4

int i = 1, c = 0;
for( _tstring::reverse_iterator it  = number.rbegin();
                                it != number.rend(); it++, i++)
{
    if( 0 == i % 2 )
    { 
        // Add even indexes
        c += CharToNumber( *it );
    }
    else
    {
        // Cast Out Nines on the odd indexed digits
        //   after multiplying by 2
        int t = 2 * CharToNumber( *it );
        if( t > 9 ) t -= 9;  // mod 9

        c += t;
    }        
}

UPC 方案

万国码 (Universal Product Code) 系统与 IBM 的系统类似，但偶数索引数字的权重为 3。实现留给读者作为练习。

Verhoeff 算法

与前面检查的方法（操作于 Z）不同，Verhoeff 算法操作于二面体群 D₅。

该算法被爱尔兰共和国的 ESB Networks 等公司使用。该算法是完美的，因为它能检测所有单字符错误和所有转置错误。此外，它还能检测大多数（但非全部）双重错误、跳跃双重错误、跳跃转置错误（abc → cba）和语音错误。

Verhorff 的观察如下：可以使用 10 种对称性来编码 10 个数字，使用恒等式表示 0；按顺序旋转表示 1、2、3、4；反射表示 5、6、7、8、9。

准备实现算法的最后一步是定义数字的排列。

令 δ 为以下数字排列

δ 对 0 不进行任何变换
δ 交换 1 和 4
δ 交换 2 和 3
δ 循环置换 5、8、6、9、7

δ(0) = 0
δ(1) = 4
δ(4) = 1
δ(2) = 3
δ(3) = 2
δ(5) = 8
δ(8) = 6
δ(6) = 9
δ(9) = 7
δ(7) = 5

与 Z 不同，D₅ 不可交换：8 ° 7 ≠ 7 ° 8。

°	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	0	6	7	8	9	5
2	2	3	4	0	1	7	8	9	5	6
3	3	4	0	1	2	8	9	5	6	7
4	4	0	1	2	3	9	5	6	7	8
5	5	9	8	7	6	0	4	3	2	1
6	6	5	9	8	7	1	0	4	3	2
7	7	6	5	9	8	2	1	0	4	3
8	8	7	6	5	9	3	2	1	0	4
9	9	8	7	6	5	4	3	2	1	0

读者应该认识到 D₅ 是一个复杂的实体（非函数式的），其元素被或多或少任意地映射到 0 到 9 的整数，并且群运算完全不像加法或乘法。此外，D₅ 没有顺序的概念：< 和 > 没有意义。表格的红色阴影表示乘法运算时丢失了交换律。

一个小插曲：如果要计算 6 ° 1，首先找到第 6 行，然后找到第 1 列。6 ° 1 = 5。

c = δⁿ(a₁) ° δ^n-1(a₂) ° δ^n-2(a₂) ° ... ° δ²(a_n-1) ° δ(a_n)

因此，要编码 1793，读者将执行

c = δ⁴(1) ° δ³(7) ° δ²(9) ° δ¹(3)

δ⁴(1) = δ³(4) = δ²(1) = δ¹(4) = 1
δ³(7) = δ²(5) = δ¹(8) = 6
δ²(9) = δ¹(7) = 5
δ¹(3) = 2

1 ° 6 ° 5 ° 2
(1 ° (6 ° (5 ° 2))) = 4

与其他示例一样，需要 4 的逆元，以便校验方程成立。因此，校验位等于 1（1 ° 4 = 0）。

下面是运行 checkdigit5 对 1000372996 进行处理的结果。由于乘法表、排列表和逆元表，代码相对容易。请注意，c 不再是前一阶段的总和 - 它被用作查找，然后被有效地丢弃。

// Check Digit 5

// skip i = 0 - it is the checkdigit
//  (which is being calculated)
int i = 1, c = 0;
for( _tstring::reverse_iterator it  = number.rbegin();
                                it != number.rend(); it++, i++)
{
    // c = M[ c ][ P[ i % 8 ][ CharToNumber( *it ) ]];
    unsigned int n = CharToNumber( *it );
    unsigned int p = P[ i % 8 ][ n ];
                 c = M[ c ][ p ];        
     
}

c = Inv[ c ];

ISO 7064 Mod N/N+1

本节介绍了一系列校验位。实现已在下载部分提供。

ISO 规范针对以下字母表设计

数字 (10 位：0 至 9)
字母 (26 个字母：A 至 Z)
字母数字 (字母和数字)

ISO 规范旨在检测以下内容（摘自 ISO 网站）

所有单字符替换错误（一个字符被另一个字符替换，例如 4234 代替 1234）；
所有或几乎所有单（局部）转置错误（两个单字符的对调，可以是相邻的，也可以相隔一个字符，例如 12354 或 12543 代替 12345）；
所有或几乎所有移位错误（整个字符串向左或向右移位）；
大部分双字符替换错误（同一字符串中两个独立的单字符替换错误，例如 7234587 代替 1234567）；
大部分其他错误。

	注释
Mod 10/11	欧洲血库，个人唯一标识符（美国 NIH）
Mod 16/17	欧洲银行路由
Mod 36/37	美国牲畜识别

群论

群（Group）是一组对象和一个相关的运算。群每天都在使用。例如，数房间里的人。群是关于整数的，运算是加法，记为+。还可以执行其他运算，例如乘法，记为x。

在加法下，存在一个恒等元素：0。这提供了预期的结果：1 + 0 = 1，0 + 1 = 1 等。在乘法下，恒等元素是 1。乘法也是如此：1 x 1 = 1，5 x 1 = 5，依此类推。

就像可以对整数进行运算一样，也可以对 D₅ 进行运算。运算定义如下。

将定义的第一个运算是 ρ。这是希腊字母 rho，在 D₅ 中表示旋转。ρ⁰ 是旋转下的恒等元素，因为它不改变元素。ρ¹ 使二面体旋转 72°。ρ² 使二面体旋转 144°。最后，ρ⁵ = ρ⁰。

下一个定义的运算是 σ。这是希腊字母 sigma。它在字母表中跟在 rho 之后。它将用于表示反射运算。σ⁰ 不改变元素，而 σ¹ 使元素“翻转”其水平轴。因此 σ² = σ⁰。敏锐的读者应该会意识到 ρ⁵ = σ²。

为了可视化观察，按如下方式对二面体的分区进行编号。

现在，对元素执行运算。例如，ρ⁷σ⁵。ρ⁷ = ρ²，所以

接下来，σ⁵ = σ¹

最后的视觉表示如下图所示。请注意，这被呈现给用户作为视觉演示。它并非用于直观演示 Verhoeff 算法。绿色表示分区 2 的新位置。

摘要

尽管已经提出了一个完美的校验位系统，学术界还提供了更多。在 1978 年的一篇非凡论文中，A. S. Sethi、V. Rajaraman 和 P. S. Kenjale 描述了一个可以用来纠正任何单字符错误或转置错误的校验系统。值得注意的是，该系统需要两个校验位而不是一个，并且仅对某些基数有效。

鼓励读者访问 Error Detecting Decimal Digits（本文包含该内容），了解 Wagner 和 Putter 在为一家商业邮购公司开发校验位系统方面的经验。

下载次数

修订

2007.07.27 修复了语法错误
2007.06.19 删除了示例 1 的无关内容
2007.06.02 重写了引言
2007.06.02 添加了“常见错误”部分
2007.04.17 清理了格式
2006.12.19 添加了对 A File Checksum Shell Menu Extension Dll 的引用
2006.12.10 添加了 ISO 7064 相关内容
2006.12.09 更新了 Verhoeff 示例（扩展了手工计算）
2006.11.26 首次发布

°	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	0	6	7	8	9	5
2	2	3	4	0	1	7	8	9	5	6
3	3	4	0	1	2	8	9	5	6	7
4	4	0	1	2	3	9	5	6	7	8
5	5	9	8	7	6	0	4	3	2	1
6	6	5	9	8	7	1	0	4	3	2
7	7	6	5	9	8	2	1	0	4	3
8	8	7	6	5	9	3	2	1	0	4
9	9	8	7	6	5	4	3	2	1	0

°	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	0	6	7	8	9	5
2	2	3	4	0	1	7	8	9	5	6
3	3	4	0	1	2	8	9	5	6	7
4	4	0	1	2	3	9	5	6	7	8
5	5	9	8	7	6	0	4	3	2	1
6	6	5	9	8	7	1	0	4	3	2
7	7	6	5	9	8	2	1	0	4	3
8	8	7	6	5	9	3	2	1	0	4
9	9	8	7	6	5	4	3	2	1	0

°	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	0	6	7	8	9	5
2	2	3	4	0	1	7	8	9	5	6
3	3	4	0	1	2	8	9	5	6	7
4	4	0	1	2	3	9	5	6	7	8
5	5	9	8	7	6	0	4	3	2	1
6	6	5	9	8	7	1	0	4	3	2
7	7	6	5	9	8	2	1	0	4	3
8	8	7	6	5	9	3	2	1	0	4
9	9	8	7	6	5	4	3	2	1	0