可参考链接:https://blog.csdn.net/weixin_43914604/article/details/104183321
https://blog.csdn.net/weixin_43914604/article/details/104864783
思维导图
差错从何而来
- 由噪声引起
-
(1)关于数据链路层和物理层的编码区别
(2)冗余编码
1.奇偶校验码
实现原理: 在原编码中加一个校验位,则
原编码就变成了校验码
,它的码距为2,可以检查出奇数位错误,但不能检查出偶数位错误,增加的冗余位为奇偶校验位,一般校验位设置在原编码的最左边或最右边。- 奇校验码:整个校验码(信息位+校验位)中1的个数位奇数
-
怎么通过奇偶校验码判断数据是正确还是错误呢?
首先在计算机中,我们就要约定好,数据是采用奇校验还是偶校验,下面分奇校验和偶校验来说明一下奇偶校验如何检查在计算机传输数据的过程中数据是否正确。
(1)奇校验
假设我们的原始编码是
10110111
,因为我们规定计算机采用奇校验
,所以我们在原编码最左边多加了一个校验位,并置为1,那么原编码就变成了奇校验码,有奇数(7)个1。传输过程中奇数个数据改变
:在传输过程中有奇数个数位值发生了改变
,那么我们通过奇校验运算
,可以发现现在变成了6个1,和奇校验码相比有3个数位值发生了改变,奇校验码不再有奇数个1,而是变成了偶数个1,可以判断我们的数据发生了改变,可以检查出错误。传输过程中有偶数个数据改变
:在传输过程中有偶数个数位值发生了改变
,那么我们通过奇校验运算
,可以发现现在变成了7个1,和原奇校验码7个1一样,都是奇数,这时我们便无法通过奇校验运算判断数据是否发生了改变,即无法检查出偶数个错误
。
(2)偶校验
假设我们的原始编码是
10110111
,因为我们规定计算机采用偶校验
,所以我们在原编码最左边多加了一个校验位,并置为0,那么原编码就变成了偶校验码,有偶数(6)个1。传输过程中奇数个数据改变
:在传输过程中有奇数个数位值发生了改变
,那么我们通过偶校验运算
,可以发现现在变成了5个1,和偶校验码相比有3个数位值发生了改变,偶校验码不再有偶数个1,而是变成了奇数个1,可以判断我们的数据发生了改变,可以检查出错误。传输过程中有偶数个数据改变
:在传输过程中有偶数个数位值发生了改变
,那么我们通过偶校验运算
,可以发现现在变成了6个1,和原偶校验码6个1一样,都是偶数,这时我们便无法通过偶校验运算判断数据是否发生了改变,即无法检查出偶数个错误
。
为什么无法检查出偶数个错误?
通过上述奇偶校验两种方式校验数据,可以比较得出奇偶校验可以检测出奇数个错误而无法检查出偶数个错误,也无法纠正错误,无法定位错误位置。
-
2.循环冗余校验(CRC)码
什么是CRC码?
基本思想:校验码中的一种。在K位信息位后拼接R位检验位,组成CRC码,这种编码也称(N,R)码
- 特点:可以发现错误,定位错误位置,自动纠正错误。
可检测出所有奇数位错,所有双比特的错和所有小于、等于校验位长度的突发错
- 结构:
原码如何编码生成CRC码?
- 首先,发送端和接受端会有一个生成多项式G(x)约定,生成多项式G(x)的最高次幂为
R
。任意一个二进制数码都可用一个系数为0或1的多项式与之对应。比如:二进制数码 1101 对应的G(x)=1X+1X+0X+1X= X+X+1 - 在发送端,将要传送的K位二进制信息码左移R位,将它与生成多项式G(x)所对应的的二进制数码进行
模2除法
,产生余数,生成一个R位检验码,并附在信息码后,构成一个新的二进制码(CRC)码,共K+R位。模2运算:分为模2加、模2减、模2乘、模2除,不考虑
进位
和借位
。
一题搞懂CRC码生成与校验
例题: 设生成多项式G(x)=X+X+1 ,信息码为 101001 ,求对应的CRC码 。
- 分析:校验位长度:R=3 , 信息码长度:K=6 , CRC码长度:N=R+K= 9
-
(1)信息码左移R位
-
(2)模2除法得余数
方法:发送端用移位后的信息码 101001000 除以G(x)所对应的二进制数码 1101 求余数,余数除得够就写1,不够就写0,直到余数小于 1101 ,余数即为校验位的数值。
- 图中即为具体计算步骤,得到最后的结果CRC码为:101001 001,然后发送端将CRC码101001 001发送给接收端。
-
(3)如何检错和纠正错误?
接收端收到CRC码后,用生成的CRC码除以生成多项式G(x)所对应的的二进制数码,若余数为0,则信息码在传输过程中没有产生错误,数据正确。
- 若接受到的CRC码为CCCCCCCCC= 101001011,除以G(x)所对应的二进制码1101得到余数为010,不为0,说明数据在传输过程中产生错误。010=2说明C2出错,将C2取反即可纠正错误。