差错编码简介

提示：以下是本篇文章正文内容

🍒差错编码原理

传输中的差错是由于噪声引起的

(1)由于线路本身电气特性所产生的随机噪声(热噪声)，是信道固有的，随机存在的 解决办法:提高信噪比来减少或避免干扰, (对传感器下手)

(2)外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因 解决办法:通常利用编码技术来解决。

差错编码基本原理： D→DR，其中R为差错检测与纠正比特（冗余比特） 冗余编码：在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错

这里的R的D的一种映射关系，一般是线性的，一般当收到的D’与D相同，通过映射产生的R’ 才会与R相同，通过比较R与R’可以检测差错

注：差错编码不能保证100%可靠

差错编码可分为检错码与纠错码

对于检错码，如果编码集的汉明距离ds=r+1，则该差错编码可以检测r位的差错

汉明距离是求两个等长字符串之间对应位置的不同字符的个数 码字A为 10001001 码字B为 10110011 那么不同的字符数为4，汉明距离就是4 在一个码组集合中，任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。最小汉明距离越大，码组越具有抗干扰能力

编码集 {0000,0101,1010,1111} 的汉明距离ds=2，可以100%检测1比特差错

对于纠错码，如果编码集的汉明距离ds=2r+1，则该差错编码可以纠正r位的差错 编码集 {000000,010101,101010,111111} 的汉明距离ds=3， 可以纠正1比特差错，如100010纠正为101010。

🍇奇偶校验码

1比特校验位: 检测奇数位差错 实现原理： 在原编码中加一个校验位，则原编码就变成了校验码，可以检查出奇数位错误，但不能检查出偶数位错误，增加的冗余位为奇偶校验位，一般校验位设置在原编码的最左边或最右边

奇校验码：整个校验码（信息位+校验位）中1的个数位奇数 偶校验码：整个校验码（信息位+校验位）中1的个数位偶数

二维奇偶校验: 检测奇数位差错、部分偶数位差错，纠正同一行/列的奇数位错

🍓Internet校验和(Checksum)

TCP/UDP都是采用的这种方式检测差错

发送端: (1)将“数据” (校验内容)划分为16位的二进制“整数”序列

(2)求和(sum)：补码求和(最高位进位的“1”，返回最低位继续加）

(3)校验和(Checksum)： sum的反码

(4)放入分组(UDP、 TCP、 IP)的校验和字段

接收端: 与发送端相同算法计算 计算得到的"checksum"： 为16位全0（或sum为16位全1）：无错 否则：有错

🍉循环冗余校验码(CRC)

基本思想：校验码中的一种。在K位信息位后拼接R位检验位，组成CRC码，这种编码也称(N,R)码

特点：可以发现错误，定位错误位置，自动纠正错误。可检测出所有奇数位错，所有双比特的错和所有小于、等于校验位长度的突发错

CRC是检错能力更强大的差错编码，将数据比特(D),视为一个二进制数，选择一个r+1位的比特模式 (生成比特模式,G) 目标：选择r位的CRC比特， R，满足：

刚好可以被G整除(模2) 接收端检错：利用G除，余式全0，无错；否则，有错！ 可以检测所有突发长度小于r+1位差错。

原码编码生成CRC码 (1)发送端和接受端会有一个生成多项式G(x)约定,生成多项式G(x)的最高次幂为R 任意一个二进制数码都可用一个系数为0或1的多项式与之对应 二进制数码 1101 对应的G(x)=1X3+1X2+0X1+1X0= X3+X2+1

(2)在发送端，将要传送的K位二进制信息码左移R位，将它与生成多项式G(x)所对应的的二进制数码进行模2除法，产生余数，生成一个R位检验码，并附在信息码后，构成一个新的二进制码（CRC）码，共K+R位 注：模2运算：分为模2加、模2减、模2乘、模2除，不考虑进位和借位

示例： 设生成多项式G(x)=X3+X2+1 ,信息码为 101001 ，求对应的CRC码

分析：校验位长度：R=3 , 信息码长度：K=6 , CRC码长度：N=R+K= 9 生成多项式对应二进制码：1101

1.信息码左移R位：发送端将原信息码左移R位，低位补0：101001 000

2.模2除法得余数：发送端用移位后的信息码 101001000 除以G(x)所对应的二进制数码 1101 求余数，余数除得够就写1，不够就写0，直到余数小于 1101 ，余数即为校验位的数值

得到最后的结果CRC码为：101001 001，然后发送端将CRC码101001 001发送给接收端

接收端收到CRC码后，用生成的CRC码除以生成多项式G(x)所对应的的二进制数码，若余数为0，则信息码在传输过程中没有产生错误，数据正确

若接受到的CRC码为C9C8C7C6C5C4C3C2C1= 101001011,除以G(x)所对应的二进制码1101得到余数为010，不为0，说明数据在传输过程中产生错误。010=2（10）说明C2出错，将C2取反即可纠正错误

这种检测方式广泛应用于实际网络 (以太网， 802.11 WiFi， ATM)