检错、纠错和码距
码距是整个编码系统中任意两个码字的最小距离，码距越大，排错能力越好。
海明校验码
海明校验码的编码规则：
下标为 2 的次方的，为校验位，其余位置为数值位，如下表所示。
| 位数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 信息位 | I1 | I2 | I3 | I4 | I5 | I6 | ||||
| 校验位 | r0 | r1 | r2 | r3 |
10以内的二进制表示如下
10 = 2^3 + 2^1
9 = 2^3 + 2^0
8 = 2^3 （校验位 3）
7 = 2^2 + 2^1 + 2^0
6 = 2^2 + 2^1
5 = 2^2 + 2^0
4 = 2^2（校验位 2）
3 = 2^1 + 2^0
2 = 2^1（校验位 1）
1 = 2^0（校验位 0）
整理发现，包含 2 的 3 次方的非校验位数字有 10、9。
包含 2 的 2 次方的非校验位数字有 7、6、5。
包含 2 的 1 次方的非校验位数字有 10、7、6、3。
包含 2 的 0 次方的非校验位数字有 9、7、5、3。
所以 r3 = 表格中下标为 10、9 的数字的异或，即 I6 异或 I5。
所以 r2 = 表格中下标为 7、6、5 的数字的异或，即 I4 异或 I3 异或 I2。
所以 r1 = 表格中下标为 10、7、6、3 的数字的异或，即 I6 异或 I5 异或 I3 异或 I1。
所以 r0 = 表格中下标为 9、7、5、3 的数字的异或，即 I5 异或 I4 异或 I2 异或 I1。
循环校验码
CRC 循环校验码是一个只能检错但不能纠错的校验码。
下面通过一个例子来进一步解释CRC的基本工作原理:
(1)假设约定的生成多项式为G(x)=x^4+x+1，则其二进制表示为10011，共5位，其中k=4。
(2)假设要发送数据序列的二进制为101011，共6位，则报文多项式为M(x)=x^5
+X^3+X+1
(3)将报文多项式乘以xk,即乘以x4，生成M(x)*xk=x9+x^7 +x5+x4，表示为二进制则为1010110000，即等于在要发送的二进制数据后面加4个0，共10位。
(4)用生成多项式的二进制表示10011去除1010110000，按模2算法求得余数比特序列为0100(注意余数一定是k位的)。
余数，因不够要求的4位，所以前面一个“0”不能省略
(5)将余数添加到要发送的数据后面，得到真正要发送的数据的比特流:1010110100，其中前6位为原始数据，后4位为CRC校验码。
(6)接收端在接收到带CRC校验码的数据后，如果数据在传输过程中没有出错，将一定能够被相同的生成多项式G(x)除尽，如果数据在传输中出现错误，生成多项式G(x)去除后得到的结果肯定不为0。
奇偶校验码
1.确定校验位的位置： 首先确定校验位的位置，通常是在数据位的末尾添加一个校验位。
2.计算校验位的值： 对于奇校验，使得数据位加上校验位中1的个数总和为奇数；对于偶校验，使得数据位加上校验位中1的个数总和为偶数。
3.填充校验位： 将计算得到的校验位填充到校验位的位置上。
网友评论