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

yangyi11056

下面 CRC 校验 多项式 是怎么除的？ [复制链接]

使用公式 ：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 的？
   

HHY55

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 (最终的余数)