2.12.1错误检测的奇偶校验法
- ◇ 奇偶校验位给出一个数中1的个数是奇数还是偶数.
许多系统都使用一个奇偶校验位,作为位错误检测的手段.任意的多位数组都包含奇数个 1或偶数个 1.将一个奇偶校验位附加到多位数组中,使得这组数中 1 的个数总是偶数或者总是奇数.一个偶校验位使得 1 的总数为偶数,而奇校验位使得 1 的总数为奇数.
一个给定的系统运行于偶校验或者奇校验,而不是同时运行于两者.例如,如果某系统运行于偶校验,则对于所接收的每一个多位数组都做一个检查,以确保这个多位数组中 1 的总数是偶数.如果有奇数个 1,就有一个错误发生了.
作为对奇偶校验位怎样附加到编码中的一个说明,表2.7列出了每个BCD码的偶校验和奇校验的奇偶校验位.每个BCD码的校验位处于P列上. $$ 表2.7~~带奇偶校验位的 ~BCD ~码 $$ $$偶校验$$
| 校验位 P | BCD |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 1 | 0010 |
| 0 | 0011 |
| 1 | 0100 |
| 0 | 0101 |
| 0 | 0110 |
| 1 | 0111 |
| 1 | 1000 |
| 0 | 1001 |
$$奇校验$$
| 校验位 P | BCD |
|---|---|
| 1 | 0000 |
| 0 | 0001 |
| 0 | 0010 |
| 1 | 0011 |
| 0 | 0100 |
| 1 | 0101 |
| 1 | 0110 |
| 0 | 0111 |
| 0 | 1000 |
| 1 | 1001 |
奇偶校验位可以附加到码的开头或者结尾,这取决于系统的设计.注意,1 的总数 包括奇偶校位上的 1,对于偶校验总是偶数,对于奇校验总是奇数.
检测一个错误奇 偶校验位提供了单个位错误的检测(或者任何奇数个错误,这种可能性较小),但是不能检测一组数中的两个错误.例如,假设我们希望传送 BCD 码 0101.(奇校验可以应用于任何位数的码;使用 4 位作为说明.)所传送的总的码,包括偶校验位如下所示
现在,让我们假设从左边数第3位发生了错误(1变为0),如下所示:
当该码被接收时,奇偶校验检测电路检测出只有一个 1(奇数),但是应当有偶数个 1.因为在码被接收时,偶数个 1 没有出现在码中,所以就指出了一个错误.
奇校验位提供了相似的方式,用以检测给定位数的数组的单个错误.
2.12.2循环冗余校验码(CRC)
在通信链路的数字数据的传送过程中,循环冗余校验码(CRC)广泛用于检测一位或两位传送错误.通信链路存在于两台通过网络相连的计算机之间,或者是一个数字存储装置(例如CD,DVD或硬盘)和一台PC之间.如果设计合理,循环冗余校验码还可以检测一组比特数中的多个连续的错误(区间误差).在循环冗余校验码中,检测位的数目有时称为校验和,它被加到传送的数据位中(加在最后).接收器使用循环冗余校验码来检测接收到的数据的错误.循环冗余校验码并不能检测出所有可能出现的错误,但是它比简单的奇偶校验要有效得多.
循环冗余校验码在数学上通常描述为两个多项式相除,并产生一个余数.多项式就是一个数学表达式,这个表达式具有多个正指数项的和.如果各项系数仅为 1 和 0 时,就称为单变量多项式.单变量多项式的一个例子是 $1x^3+0x^2+1x^1+1x^0$,或简写为 $x^3+x^1+x^0$,这完全可以用 4 位二进制数 1011 来表示.大多数循环冗余校验码使用 16 位或较大的多项式,但是为了解释简单,这里使用 4 位.
模-2运算 可以简单地认为,循环冗余校验码就是基于两个二进制数的相除,除法就是一系列的减法和移位.进行减法操作时,使用一个称为 模-2 加法的方法.模-2加法(或减法)和不考虑进位的二进制加法相同,如表2.8的真值表所示.如同第3章将要学习的那样,真值表广泛地用于描述逻辑电路的运算.两位数位在真值表中有四种可能的组合.这个特定的表描述的模-2运算,也称为异或运算,可以由第3章将要介绍的逻辑门来实现.模-2运算的一个简单规则就是如果两个输入不同,输出就是 1,否则输出为 0. $$ 表2.8 ~~模-2运算 $$
| 输入位 | 输出位 |
|---|---|
| 0 0 | 0 |
| 0 1 | 1 |
| 1 0 | 1 |
| 1 1 | 0 |
循环冗余校验码的处理步骤 如下所示:
- 选择一个固定的生成码,它可以比校验的数据位的位数少.这个生成码要事先让发送器和接收器都能识别,并且对于发送器和接收器必须都是相同的.
- 附加上若干个 0, 0 的个数和加到数据位的生成码的 0 的个数相同.
- 使用模-2方法,把数据位和附加的生成位合在一起除以生成码.
- 如果余数为 0,那么数据位和附加的位原样发送.
- 如果余数不为 0,那么为了使发送数据前余数为 0,附加的位改为余数位.
- 在接收端,接收器使用和发送器相同的生成数位除以接收到的附加的数据位.
- 如果余数为 0,就没有检测到错误(多个错误的可能性很小,使用时不考虑这种情况).如果余数不为 0,就检测到在传送过程中有一个错误,接收器会发出一个重传请求.
图2.7为循环冗余校验码的处理步骤的示意图.
$$
(a)通信链路的发送端
$$
$$
(b)通信链路的接收端
$$
$$
图2.7~~循环冗余校验码的处理步骤
$$