校验码及其计算
- 2025-12-31 03:27:19
码距：
一个编码系统的码距是整个编码系统中任意两个码字的最小距离，（可以理解为传输形式是几位码距就是几）
例：若我想要传输两个二进制数A=1，B=0；
当码距是1时的传输形式为A=1;B=0；
当码距是2时的传输形式为A=11;B=00；
当码距是3时的传输形式为A=111;B=000；
由上可见，（通讯链路相对靠谱一般只会错一位不会错多位）
当码距为1时，则会用一位数1直接传输，即用1,0来传输若A,B，若通讯链路出现故障将1传输成0输出，此时根本无法判断最初传输的是A还是B，甚至根本无法判断传输是否出错。
检错：
当码距为2时，则会用两位数传递，即用A=11来传输A=1，用B=00来传输B=0，若通讯链路出现故障将11传输成10输出，此时可以判断通讯链路出现故障，即可以检错，但是仍无法判断是将A=11中的11传输成了10，还是将B中的00传输成了10，此时可以判断传输出错但是无法判断哪里出错无法纠正。
纠错：
当码距为3时，则会用三位数传递，即用A=111来传输A=1，用B=000来传输B=0，若通讯链路出现故障将111传输成110输出，此时可以判断通讯链路出现故障，即可以检错，且可以明确判断是将111传输成了110，进而可以将110纠正为111保持结果正确，即纠错。
码距与检错、纠错的关系：
检错：
在一个码组内为了可以将a位二进制的误码检错，要求最小的码距应该是 d>=a+1
即若需将1位二进制误码检错则需要码距为d=1+1=2
纠错：
在一个码组内为了可以将b位二进制误码纠错要求最小码距应该是 d>=2b+1
即若需将1位二进制误码纠错则需要码距为d=2*1+1=3
循环校验码CRC
特点：
只能进行检错不能进行纠错的编码
模2除法：
例题：
CRC编码编译过程：
首先看多项式，将多项式对应的二进制数求得，并明确其位数，设其位数位a位；
在原始报文后面缀上（多项式对应的二进制位数-1）个0，即（a-1）个0；
然后用原始报文后缀（a-1）个0做被除数，多项式对应二进制数做除数进行模2除法；
将模2除法所得的余数自右向左取（a-1）位，取代原来的（a-1）个0后缀到原始报文，得CRC编码；
校验：
将得到的CRC编码做被除数，将多项式对应的二进制数做除数进行模2除法，若余数为0则说明传输正确，若不为0则说明传输出错。
海明校验码
特点：
可以检错也可以纠错，海明校验码是奇偶校验码的一种扩充。
公式：
>=x+r+1 ，x表示所求信息的二进制位数，r表示校验码位数（r 是满足公式的最小正数）
例子：
求信息1011的海明码
二进制位数4位，即x=4，已知需满足>=x+r+1即当 r=3 时有 8>=8，所以有3个校验位。
校验位位置：
校验位的位置是固定的，，，，......
如果有2位校验位那么就分别放在第 ，；位上
如果有3位校验位那么就分别放在 第，，；位上
校验位数值计算：
由上可知，信息1011有4位，则有3个校验码，校验码分别在第1，2，4位上，所以信息只能放在第3，5，6，7位上如图所示：
第7位第6位第5位第4位第3位第2位第1位位数1011信息位r2r1r0校验位
首先用 相加表示出信息位所在的位置，然后根据校验码所在的位置，对应找到各信息位，用信息位上的二进制数进行异或运算
信息位分别是3，5，6，7位：
第3位的位置可以表示为：3=+
第5位的位置可以表示为：5=+
第6位的位置可以表示为：6=+
第7位的位置可以表示为：7=++
已知3个校验码分别在第1，2，4位上，也就是第，，；位上
r0 对应在 位上，则上面有 的是第 7，5，3位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r0 = 111=1
r1 对应在 位上，则上面有 的是第 7，6，3位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r1= 101=0
r2 对应在 位上，则上面有 的是第 7，6，5位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r2= 101=0
所以三位校验位的值是001
第7位第6位第5位第4位第3位第2位第1位位数1011信息位001校验位
正确的海明校验码是1010 101
若传输过程中出错，假定只有一位出错；
错误示例1
例如：
接收到为1110 101
7位海明码根据公式 >=x+r+1 可知有3位校验位，且位置固定，则很容易知道校验码是001
那么剩余的就是信息位，信息位是1111
根据上述求校验码的方式重求校验码：
r0 对应在 位上，则上面有 的是第 7，5，3位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r0 = 111=1
r1 对应在 位上，则上面有 的是第 7，6，3位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r1= 111=1
r2 对应在 位上，则上面有 的是第 7，6，5位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r2= 111=1
得此时得校验码是111
将新得到的校验码各位分别于原校验码取异或
r2r1r0位置001原校验码取异或运算111新校验码110结果110对应的十进制是6则表示第6位出错，将第6位取反就能得到原来正确的信息
接收到为1110 101第6位取反1010 101即正确的海明码
错误示例2
例如：
接收到的
接收到为1010 100
7位海明码根据公式 >=x+r+1 可知有3位校验位，且位置固定，则很容易知道校验码是000
那么剩余的就是信息位，信息位是1011
根据上述求校验码的方式重求校验码：
r0 对应在 位上，则上面有 的是第 7，5，3位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r0 = 111=1
r1 对应在 位上，则上面有 的是第 7，6，3位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r1= 101=0
r2 对应在 位上，则上面有 的是第 7，6，5位，将这3位上的数值自左向右取异或运算（相同同取0不同取1）
r2= 101=0
得此时得校验码是100
将新得到的校验码各位分别与原校验码取异或
r2r1r0位置000原校验码取异或运算001新校验码001结果001对应的十进制是1则表示第1位出错，将第1位取反就能得到原来正确的信息
接收到为1010 100第1位取反1010 101即正确的海明码。
