校验码标准系统

5.5.2　校验码标准系统

目前正在使用的校验码系统有一百多个，其中许多系统的特性非常接近，大多数系统并未起到有效的作用。现存的应用系统中，仅有少数经过严格的数学验证，有些还存在严重的缺陷。同时，系统的多样性无形中也损害着校验码系统的经济效益，影响数据的校验。因此，必须选择一些可满足不同需要的、兼容的校验码系统，即要选择校验码标准系统。

ISO/IEC和我国的标准化机构出台了相应的数据处理校验码系统标准，为大部分的应用提供校验的标准方法(见GB/T 17710-1999，ISO/IEC 7064)。

标准的校验码系统分为纯系统和混合系统，两者的区别在于:纯系统只使用一个模数，而混合系统中使用两个模数。下面将详细介绍这两种系统下的校验码标准系统。

1.纯系统的校验码标准系统

在纯系统中，每一个系统的所有运算都使用单一模数，见表5-10。

表5-10　纯系统

1)在MOD之后的第1个数字是模数，第2个数字是底数。

2)前两个系统可在被校验的字符串处产生1位附加校验码，当不能使用附加校验码，又只能产生一位检验码时，应避免使用产生附加校验码的系统，如果既不能使用附加校验码，又不能使用一位校验码，则应使用混合系统。

字符串应满足下列公式的校验:

∑［a_i×r^i－1］≡1(mod M)(i=1，…，n)

式中，符号“≡”表示同余(congruence)的概念。同余指在同一组整数中，两两之差与模数有倍数的关系的特性。如39≡6(模11)，即指39－6

=33是11的倍数。n表示包括校验码的字符串的字符个数;i表示从右边开始的字符所在的位置序号(包括校验码在内)，即最右边的字符i=1，空格与分割符不计在内;a_i表示处于i位置上的字符值;r表示底数(即几何级数的基数);M表示模数。字符对应的值见表5-11。

表5-11　字符对应的值

续表

任何运算都按公式进行，校验码在字符串的最右端。

1)带一位校验码的纯系统的计算方法

在带有一位校验码的纯系统中，校验码的计算方法有两种:递归法和多项式法，两种方法的计算结果一致。

(1)递归法

在递归法中，字符串的字符从左到右逐位处理，用j=1，…，n来表示下标，n为包括校验码在内的字符串中字符的数目。当j=1时，P_j=M。计算如下:

S_j=P_j+a_n－j+1

P_j+1=S_j×r

式中，a_n－j+1为n－j+1位置上的数值的字符值;r为底数。

如果S_n≡1(mod M)，由字符串满足校验要求。选择校验码a₁时，应使之满足公式P_n+a₁=1(mod M)。

示例:假定使用校验码系统ISO 7064 MOD 11-2为字符串0794设置一个校验码，此时，M=11，r=2，n=5(4位字符加1位校验码)。运算过程见表5-12。

表5-12　递归法校验码运算过程

续表

此处结果为P_n=100，加上校验码的值必须与1(mod 11)同余，而100本身就与1(mod 11)同余，因此校验码值为零，整个受保护的字符串则为0794 0，校验码加在字符串的最右边。

为了校验该字符串是否正确，如上所示，再按步骤j=1～5进行计算，将校验码值0也包括在内，如果运算结果与1(mod 11)同余，则证明该字符串是正确的。

如果计算过程中任一步的结果或是中间和大于模数M，用其余数继续运算。在ISO 7064 MOD 11-2系统中，有效的校验码值为0～10，如果校验码的值为10，就由字符“X”表示。

(2)多项式法

多项式法采用r^i－1或r^i－1(mod M)的值乘以字符串中每一字符值来计算。表5-13列出了所有纯系统的r^i－1(mod M)的前15个值。

表5-13　纯系统的权系数

注:此处列出前15个位置的系数，其余的可用下列公式无限扩展:

r^i－1(mod M)，W_i为位置序号i的系数。

将字符串与它们的权数相乘，再将结果相加，如果这些结果之和与1(mod M)同余，则包含校验码内的字符串是有效的。

示例:假定使用校验码系统ISO 7064 MOD 11-2为字符串0794设置一个校验码。运算过程见表5-14。

表5-14　多项式法校验码运算

总和100加上校验码必须与1(mod 11)同余，而100本身就与1(mod 11)同余，因此校验码值为零，整个受保护的字符串则为0794 0，校验码加在字符串的最右边。

2)带两位校验码的纯系统的计算方法

这些系统与含一位校验码的系统的计算方法完全一致，只需再加一步，除了底数是10的系统求出两个字符值作为校验码。用底数除运算结果得到的整商数即为i=2位置上的校验码值，余数则是i=1位置上的校验码值。

下面是递归法应用的一个例子:用ISO 7064 MOD 1271-36系统计算字符串“ISO79”的两个校验码，字母数字的字符值在表5-11中给出。运算步骤的前6步见表5-15。

表5-15　两位校验码的计算步骤

续表

第7步:为了计算校验码值，用M+1减去最后的P_j+1值:

1271+1=1272

1272－1132=140

为了得到单个的校验码值，用140除以底数36，商数是3，整余数为32。

这样，商数3即为位置i=2处的校验码值，整余数32为位置i=1处的校验码值。按表5-13，3与32分别对应着字符3和字符W，因而带有校验码的完整字符串为ISO 79 3W。

2.混合系统的校验码标准系统

混合系统在运算中采用了两个模数，其中一个等于被保护的字符集中的字符数，另一个模数比它大1，形成的校验码位于被保护的字符串组成的字符集内，见表5-16。

表5-16　混合系统

在系统表示法中，紧跟在MOD后面的两个数字是两个模数。

在混合系统中，校验码的位置也设在字符串的最右端。在混合系统中，采用递归法计算校验码及验证含校验码的字符串。

在递归法中，字符串的字符从左到右逐个处理。用j=1，…，n来表示，n为包括校验码在内的字符串中字符的数目。当j=1时，定义P_j=M。公式如下:

S_j=P_j|_M+1+a_n－j+1

P_j+1=S_j‖M×2

式中，‖M表示除以M后的整余数，如果为0，则用M代替;|_M+1表示除以M+1后的整余数，在经过上述处理后，该余数不会为0;a_n－j+1为n－j+ 1位置上的数值的字符值。

验证:如果S_n≡1(mod M)，则字符串正确。确定校验码a₁时，应使之满足P_n+a₁≡1(mod M)。

例如，假定用系统ISO 7064 MOD 11，10为字符串0794设置校验码，其中M=10，M+1=11，n=5(4位字符加1位校验码)。计算步骤如表5-17所示。

表5-17　混合系统递归法校验码计算步骤

由上式得到的校验码值为5，完整的字符串为0794 5，校验码放在原字符串的最右端。验证时，第1步至第5步如表5-17所示，且校验码值5的计算也包括在内，最后结果必须与1(mod 10)同余。