循环冗余校验

"冗余"为什么能检验?

• 数据传输过程中不能保证所有的位数都是正确的,由于电磁干扰会产生错误,假设传输过程中最多只有1位是传输错误的,并且不需要检验出具体哪一位出现错误,只需要考虑检验数据存在错误即可

不添加校验码

• 最简单的情况是发送方只发送了一位数据,接收正确为1,接收错误为0
  
• 接收方接收到1,可能是发送发送1,被正确接收或者是发送方发送0,出现错误
• 接收方接收到0,可能是发送发送0,被正确接收或者是发送方发送1,出现错误
• 怎么进行判断数据传输错误? 增加一位不含信息的数据进行辅助校验
  

添加校验码

• 发送方想要发送1,此时添加一位校验位1,发送方会发送11
• 接收方接收到10,01都表示出现错误
  
  

循环如何进行检验?

• 前面知道校验的可行性,将发送1位数据扩展到n位如何进行考虑检验?
• 不恰当的想法:发送一个数据的时候,发送两遍,第一遍表示数据,第二遍进行检验,但是这样在发送大量数据的时候,会浪费很多空间
  

模2除法

• 首先取与除数相同的位数,看首位是不是够减,够减写1,不够减写0
  
  

检验方法

• 事先通过网络协议规定好一个除数(比如11001),通过待校验的数据除以除数,用得到的余数进行校验;余数为0表示传输正确,余数不为0表示传输错误

例题

CRC计算示例1

CRC keywords

• 信息码 - 校验的码值,原编码 101001
• 生成多项式 - G(x) = x^3+x2+1
• 校验位 - 是CRC的长度,根据G(x)最高次幂确定,这里最高位为3,所以校验位是3
• 多项式对应的二进制数 - 多项式会生成一个二进制数,将其中的每一项,从高次到低次进行排列,将每一项的系数进行提取,就是多项式的二进制数
  
• 余数 - 经过除法取模之后得到数,作为真正的校验位

求解过程

• 找到CRC keywords
• 余数 - 联合校验位对于信息码进行拼接,拼接三位校验位(用0补充),对多项式二进制数进行除法运算
  
• 这里得到的余数是1,真正的余数是001
• CRC校验码就是(信息码+余数):101001001

CRC 计算实例2

• 知道多项式二进制数10011和信息码10101011,求CRC?
• 反推出多项式,得到校验位是4
  
• 进行拼接,比较,异或运算
  

参考视频:https://www.bilibili.com/video/BV1tZ4y117Lj/?spm_id_from=333.337.search-card.all.click&vd_source=96e5e43be309416df48eb06a75ad2f96