下面 CRC 校验 多项式 是怎么除的?

yangyi11056   2009-6-25 09:55 楼主


使用公式 :Xr·K(X)=G(X)Q(X)+R(X)( R(X)是Xr·K(X)除以G(X)的余式)
其中 K(X)是信息位 对应的 虚拟多项式,Q(X)是 按着  冗余算法 指定的 多项式, R(X)是Xr·K(X)除以G(X)的余式
这个 公式应该 是对的吧?

以K(X)=X6+X4+X3+1为例(即信息位为1011001),
得到 crc校验的 算法如下:

取r=4,则X4·K(X)=X10+X8+X7+X4(对应代码为0110010000),若G(X)=X4+X3+1(对应代码11001),其由模2除法求余式R(X),
得到 R(X)=X3+X,得到的最后余数为1010,这就是冗余位,这个结果对吗? 如果结果对

X4·K(X) =X10+X8+X7+X4  除以  G(X)=X4+X3+1是 怎么得到  R(X)=X3+X 的?
   

回复评论 (1)

CRC使用的是不借位的除法,其运算规则可以认为是进行了异或运算。

如果信息位为 1011001,取r=4 ,那么我们首先把信息位左移4位,即你所说的得到 1011001 0000,假设校验多项式为G(X)=X4+X3+1(对应代码11001),那么我们用 1011001 0000去除以11001 (注意这里使用的是不借位的除法)那么得到的余数为:1010.

我觉得这个地方你关键是要理解什么是 不借位的除法。如下所示:
                       10110010000
                    11001
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·
                        11110
                     11001
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                       11110
                       11001
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         11100
                         11001
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                           1010 (最终的余数)
点赞  2009-9-3 14:45
电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 京公网安备 11010802033920号
    写回复