22计算机考研交流总QQ群：1032995316
课程咨询微信号｜容嬷嬷（csky-rmm）
哈哈，大家好啊！你们的小燕子她带着满满的知识又来啦，大家准备好接受的洗礼了吗！话不多说，我们开始讲课吧。
知识点讲解
世界上没有十全十美的事情，当然我们的通信链路也是，在传输过程中可能会出现错误。
问：为什么传输过程会出错？
答：因为噪声。一方面是由于线路本身电气特性所产生的随机噪声，这种噪声是信道固有的，通过提高提高噪声比来减少干扰（从传感器上改造）；另一方面是外界因素造成的冲击噪声，通常我们会采用编码技术来解决，这也是我们本节课主要讨论研究的方向。问：差错有哪些分类？
答：位错和帧错
问：编码技术（针对位错）有哪些分类？
答：检错编码和纠错编码。检错编码我们会讲到奇偶校验法和循环冗余（CRC）校验，纠错编码我们会讲到海明码。
差错编码：接收端发现信息错误时，将错误信息过滤，并通知发送方重发（简单来说就是只能发现错误）
纠错编码：接收端不仅能发现错误，而且能发现错误比特位置并纠正错误（简单来说就是可以发现错误并纠正错误）
检错编码->奇偶校验
奇校验：1位校验位 + n-1位数据 -> n位数中“1”的个数为奇数
偶校验：1位校验位 + n-1位数据 -> n位数中“1”的个数为偶数
奇偶校验的特点：只能发现奇数个错误，发现错误的概率为50%
比如数据110110，采用偶校验得到0110110
1位出错：0010110 -> “1”为奇数，检验出错误
2位出错：0000110 -> “1”为偶数，无法检验
3位出错：0001110 -> “1”为奇数，检验出错误
4位出错：0001010 -> “1”为偶数，无法检验
下面用个例子来加深理解：
字符S的ASCII码编码从低到高依次为1100101.采用奇校验在下述收到的传输后的字符中，错误不能被检验出来的是（）
A. 11000011
B. 11001010
C. 11001100
D. 11010011
答案解析：D
奇校验，也就是数据位+校验位，“1”的个数为奇数，如果接收方收到的信息“1”的个数为偶数，则可以判断传输过程中信息出错。
题中数据位有7位，加上校验位一共8位，所以四个选项的长度均为8。
A、B、C中，“1”共有4个（偶数个），说明传输中出现了位错，D中“1”的个数为5（奇数个），可能没出错也可能有偶数个位出错，无法判断。（这道题有个取巧的方式，就是除了D其他选项的“1”都为4，嘿嘿知道了吧）
检错编码->循环冗余CRC
按照小燕子的经验，循环冗余最重要的就是这个“余”。小燕子先用我们熟悉的十进制给大家举个例子：
CRC原理：
发送端通过原始数据计算出校验码，并把数据和校验码一起发送出去，接收方收到数据后，如果发现自己使用原始数据计算出来的校验码≠收到的校验码，则可以判断数据出错
CRC工作流程：
1. 发送端最终发送数据为：原始数据+FCS帧检验序列
2. FCS/冗余码为原始数据除以生成多项式的余数
3. 接收端收到数据后除以生成多项式，若余数为0，则接收的数据正确，反之则证明数据在传输过程中出现了错误假如我们要发送的数据为1101 0110 11，生成多项式为 10011 ，那我们最终发送的数据为？
计算冗余码：
1. 在原始数据后加0 -> 生成多项式的阶为r，则加r个0（或多项式位数-1）
10011表示成多项式为：x+x+x，即 r=4。
要注意的是，如果题目中给你x+x+x，要转化为1x+0x+0x+1x+0x+1x，从而得出多项式100101。
2. 模2除 -> 小技巧：二进制里面的加减就是异或
综上，我们需要发送的数据为1101 0110 111110
注意：“可靠传输”是指发送端发什么，接收端就收什么，但CRC只能实现无比特差错传输，错误的数据会被丢弃，并没有实现可靠传输
检错编码->海明码
海明码原理：
牵一发而动全身，也就是一个比特错误，会对作用于它的校验码都产生影响
海明码特点：
发现双比特错误，纠正单比特错误
海明码工作流程：
确定校验码数 -> 确定校验码位置和数值 -> 检错并纠错
下面便通过一个例子1010给大家详细介绍海明码：
1）确定校验码数
n为原始数据位数，k为校验码位数，n和k需要满足：
2-1≥n+k (海明不等式)
现在n=4，满足不等式的最小k=3，所以1010（D1D2D3D4）的校验码为P1P2P3，数据一共7位。
2）确定校验码位置和数值
校验位必须放在2的次方位置上：
P1-> 2的0次方
P2-> 2的1次方
P3-> 2的2次方
二进制：数据位的二进制。二进制长度由数据位的最高位决定，比如最高位为7（111），则二进制用3位表示,若最高位为10（1010），二进制位用4位表示。
数据位：原始数据+校验位的总位数
P1的二进制值为001，它作用的数据位的特点是：二进制值第一位为1的原始数据，如图所示：
P2的二进制值为010,它作用的数据位的特点是：二进制值第二位为1的原始数据，如图所示：
P3的二进制值为100,它作用的数据位的特点是：二进制值第三位为1的原始数据，如图所示：
通过异或为0求出校验位（ “1”的个数为奇数异或为1，“1”的个数为偶数异或为0）：
3）检错并纠错
上步我们求出了发送的海明码为1011010若我们在传输过程中第5位发生了错误，从1011010 变为了 1011110
按照刚才的方法，将所有要校验的位进行异或运算：
思维导图巩固
今天的课程就到此结束啦，大家都学会了吗？奉上今天的思维导图，好好消化哦！今天讲的内容都是计算，一定一定一定一定要亲手做一两道题！！！
习题巩固
对于10位要传输的数据，如果采用海明码校验，那么需要增加的冗余信息位数是（）
A. 3
B. 4
C. 5
D. 6
答案解析：B
2-1≥n+k，n为数据位数10，求出最小的k=4。
交流群
▲ 22计算机考研交流总QQ群：1032995316
▲ 南航计算机/软件考研交流QQ群（有学校资料）：1138098949
▲ 西南大学计算机/软件考研交流QQ群（有学校资料）：1128814897
▲咨询：容嬷嬷微信(csky-rmm)
微信公众号：冯强计算机与软工考研
