9.校验码
- 差错控制—CRC与海明校验码
- 什么是检错和纠错
- 什么是码距？
一个编码系统的码距是整个编码系统中任意（所有）两个码字的最小距离。
就是改变多少个位就可以变成另外一个码字
例：
若用1位长度的二进制编码，若A=1，B=0。这样A，B之间的最小码距位1。
- 这个是发现不了错误的
若用2位长度的二进制编码，若A=11，B=00。这样A，B之间的最小码距位2。
- 当接收到的是10时，是可以发现编码错误。因为我们在之前就规定了11为A，00为B。没有10，所以是可以发现错误的。但是不能进行纠错，因为发过来的可能是A也可能是B
若用3位长度的二进制编码，若A=111，B=000。这样A，B之间的最小码距位3。
- 当接收到的是101时，发现编码时错误的。这个时候也可以进行纠错。因为我们认为通信链路时比较可靠的，不会出现错多位的情况，这个时候就可以和合法编码进行比较，通过比较可以将错误的编码更正为正确的编码。最终更正为111.
- 码距与检错、纠错有何关系？
- 在一个码组内为了检测e个误码，要求最小码距d应该满足：d>=e+1
- 在一个码组内为了纠正t个误码，要求最小码距d应该满足：d>=2t+1
- 校验码—循环校验码CRC
- 它是一种可以做检错，但不能进行纠错的一种编码
什么时模2除法，它和普通的出发有何区别？
模2除法是指在做除法运算的过程中不计其进位的除法。
例如，1011对110进行模2除法为：
普通除法是：101不够，所以要1011，然后相减，再把最后的1拿下来，再减
模2除法：直接取前三位，不是相减，而是按位做异或操作（同为0，异为1）。
- 例题：
- x的多少次方对应的二进制位是0还是1。
- 之后要在原始报文的基础上加若干个0，加多少位=生成多项式的位数减1个0。
- 进行模2除法，得到的余数代替掉之前加的0
- 最后原始报文信息补上余数部分就是完整的信息。
- 用完整的信息与多项式转化的二进制进行模2除法。最后得到的结果为0就是正确的
- 校验码—海明校验码
这里的校验位公式可以定为：
其中x代表有多少位，也就是信息位，而r为校验位。
- 求海明编码：
- 首先确定信息位以1011为例。从而知道x的长度是4位
- 通过校验位公式可以得到校验位为3。
- 现在开始进行分配校验位：一般校验位都会放在2 ^ n的位置上（1，2，4…）
- 通过上述步骤可以看到校验位加上信息位一共是7位，画张表解决
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位置 |
| 1 | 0 | 1 | 1 | 信息位 | |||
| r2 | r1 | r0 | 校验位 |
- 确定每个位置的校验位：校验i位就等于校验位所在位置的加和。例如校验第3位，那么3就是1 + 2，这样就是需要第一个校验位和第二个校验位来进行校验。以此类推。得到下表：
| 位置 | 占用的校验位号 | 备注 |
| 1 | 1 | 1 = 1 |
| 2 | 2 | 2 = 2 |
| 3 | 1，2 | 3 = 1+ 2 |
| 4 | 4 | 4 = 4 |
| 5 | 1，4 | 5 = 1 + 4 |
| 6 | 2，4 | 6 = 2 + 4 |
| 7 | 1，2，4 | 7 = 1 + 2 + 4 |
- 数据汇总
| r0 | 1，3，5，7 |
| r1 | 2, 3, 6, 7 |
| r2 | 4, 5, 6, 7 |
- 计算校验位的值（通过异或运算）
r0 = 3 5 7的异或
r1 = 3 6 7的异或
r2 = 5 6 7的异或
- 根据公式得到值分别为 1 0 0。将得到的值填入下面的表格
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位置 |
| 1 | 0 | 1 | 1 | 信息位 | |||
| 0 | 0 | 1 | 校验位 |
- 至此就可以得到最后的海明码：1010101
- 除了检错还可以纠错。如果收到的信息是101101，通过它获得一个海明码，如果得到的校验码是001。需要和我们开始得到的正确的校验码（这个不是说我之前写过的码，这里只是举个例子与之前得到的海明码无关）按位进行异或运算，也就是001与000进行异或运算。得到的结果位001就是第一位出现了问题，如果得到010就是第二位出现了问题，如果得到110就是第六位出现了问题。
