元件故障\噪声干扰等各种因素常常导致计算机在处理信息过程中出现错误。为了防止错误,可将信号采用专门的逻辑线路进行编码以检测错误,甚至校正错误。通常的方法是,在每个字上添加一些校验位,用来确定字中出现错误的位置。
最简单且应用广泛的检错码是采用一位校验位的奇校验或偶校验。
设X＝(X0X1…Xn－1)是一个n位字,则奇校验位Ｃ定义为
C＝X0⊕X1⊕…⊕Xn－1 | ||||
式中⊕代表按位加,表明只有当X中包含有奇数个1时,才使C＝1,即C＝0。
同理,偶校验位Ｃ定义为
C＝X0⊕X1⊕…⊕Xn－1 | ||||
即ｘ中包含偶数个1时,才使C＝0。
假设一个字ｘ从部件 A 传送到部件 B。在源点 A,校验位C可用上面公式算出来,并合在一起将(ｘ0ｘ1…ｘn－1C)送到B。假设在B点真正接收到的是ｘ＝(ｘ'0ｘ'1…ｘ'n－1C '),然后计算
F＝ｘ'0⊕ｘ'1⊕…⊕ｘ'n－1⊕C '
若F＝1,意味着收到的信息有错,若F＝0,表明ｘ字传送正确。奇偶校验提供奇数个错误检测,无法检测偶数个错误,更无法识别错误信息的位置。
[例]已知下表中左面一栏有5个字节的数据。请分别用奇校验和偶校验进行编码,填在中间一栏和右面一栏。
| 数 据 | 偶校验编码Ｃ | 奇校验编码Ｃ |
1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 1 0 1 0 1 0 1 0 - 0 1 0 1 0 1 0 0 - 0 0 0 0 0 0 0 0 - 0 1 1 1 1 1 1 1 - 1 1 1 1 1 1 1 1 - | 1 0 1 0 1 0 1 0 - 0 1 0 1 0 1 0 0 - 0 0 0 0 0 0 0 0 - 0 1 1 1 1 1 1 1 - 1 1 1 1 1 1 1 1 - |
[解:]
假定最低一位为校验位,其余高8位为数据位,列表如下。从中看出,校验位的值取0还
是取1, 是由数据位中1的个数决定的。
数 据 | 偶校验编码Ｃ | 奇校验编码Ｃ |
1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 | 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 |