循环冗余编码

编辑:涕泗网互动百科 时间:2020-01-21 22:35:42
编辑 锁定
本词条缺少概述信息栏名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
循环冗余编码又名多项式编码(polynomial code),也称CRC(Cyclic Redundancy Check).
CRC的工作方法
在发送端产生一个循环冗余码,附加在信息位后面一起发送到接收端,接收端收到的信息按发送端形成循
环冗余码同样的算法进行校验,
若有错,需重发。
2.循环冗余码的产生与码字正确性检验例子。
CRC校验码的算法分析
CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。
其实现步骤如下:
(1) 设待发送的数据块是m位的二进制多项式t(x),(2) 生成多项式为r阶的g(x)。在数据块的末尾添
加r个0,(3) 数据块的长度增加到m+r位,(4) 对应的二进制多项式为 。
(5) 用生成多项式g(x)去除 ,(6) 求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x
)就是t(x)经过生成多项式g(x)编码的CRC校验码。
(7) 用 以模2的方式减去y(x),(8) 得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。
从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽
的m+r位二进制多项式 ,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错
误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。
同时 可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到
的就是原始数据。
为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、
CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。
3.循环冗余码的工作原理
循环冗余码CRC在发送端编码和接收端校验时,都可以利用事先约定的生成多项式G(X)来得到,K位要发送
的信息位可对应于一个(k-1)
次多项式K(X),r位冗余位则对应于一个(r-1)次多项式R(X),由r位冗余位组成的n=k+r位码字则对应于一
个(n-1)次多项式T(X)=Xr*K(X)+R(X)。
1)可检测出所有奇数位错;
2)可检测出所有双比特的错;
3)可检测出所有小于、等于校验位长度的突发错。
词条标签:
计算机术语 计算机学