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位，画张表解决

• 确定每个位置的校验位：校验i位就等于校验位所在位置的加和。例如校验第3位，那么3就是1 + 2，这样就是需要第一个校验位和第二个校验位来进行校验。以此类推。得到下表：

• 数据汇总

• 计算校验位的值（通过异或运算）
  

r0 = 3 5 7的异或
r1 = 3 6 7的异或
r2 = 5 6 7的异或

• 根据公式得到值分别为 1 0 0。将得到的值填入下面的表格

• • 至此就可以得到最后的海明码：1010101

• 除了检错还可以纠错。如果收到的信息是101101，通过它获得一个海明码，如果得到的校验码是001。需要和我们开始得到的正确的校验码（这个不是说我之前写过的码，这里只是举个例子与之前得到的海明码无关）按位进行异或运算，也就是001与000进行异或运算。得到的结果位001就是第一位出现了问题，如果得到010就是第二位出现了问题，如果得到110就是第六位出现了问题。