CRC32的计算方法
答案:2 悬赏:80 手机版
解决时间 2021-03-27 18:38
- 提问者网友：藍了天白赴美
- 2021-03-27 10:52
CRC32的计算方法
最佳答案
- 五星知识达人网友：往事隔山水
- 2021-03-27 11:34
CRC 算法是以 GF(2) 多项式算术为数学基础的，GF(2) 多项式中只有一个变量 x ，其系数也只有 0 和 1 ，比如：
1 *x^6 + 0*x^5 + 1*x^4 + 0*x^3 + 0*x^2 +1*x^1 + 1*x^0
= x^6 + x^4 + x + 1
加减运算不考虑进位和退位。说白了就是下面的运算规则：
0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0
看看这个规则，其实就是一个异或运算。
每个生成多项式的系数只能是 0 或 1 ，因此我们可以把它转化为二进制形式表示， 比如 g(x)=x^4 + x + 1 ，那么g(x) 对应的二进制形式就是 10011 ， 于是我们就把 GF(2) 多项式的除法转换成了二进制形式，和普通除法没有区别，只是加减运算没有进位和退位。
比如基于上述规则计算 11010/1001 ，那么商是 11 ，余数就是 101 ，简单吧。
CRC 校验的基本过程
采用 CRC 校验时，发送方和接收方用同一个生成多项式 g(x) ， g(x) 是一个 GF(2) 多项式，并且 g(x) 的首位和最后一位的系数必须为 1 。
CRC 的处理方法是：发送方用发送数据的二进制多项式 t(x) 除以 g(x) ，得到余数 y(x) 作为 CRC 校验码。校验时，以计算的校正结果是否为 0 为据，判断数据帧是否出错。设生成多项式是 r 阶的（最高位是 x^r ）具体步骤如下面的描述。
发送方：
1 ）在发送的 m 位数据的二进制多项式 t(x) 后添加 r 个 0 ，扩张到 m+ r 位，以容纳 r 位的校验码，追加 0 后的二进制多项式为 T(x) ；
2 ）用 T(x) 除以生成多项式 g(x) ，得到 r 位的余数 y(x) ，它就是 CRC 校验码；
3 ）把 y(x) 追加到 t(x) 后面，此时的数据 s(x) 就是包含了 CRC 校验码的待发送字符串；由于 s(x) = t(x) y(x) ，因此 s(x) 肯定能被 g(x) 除尽。
接收方：
1 ）接收数据 n(x) ，这个 n(x) 就是包含了 CRC 校验码的 m+r 位数据；
2 ）计算 n(x) 除以 g(x) ，如果余数为 0 则表示传输过程没有错误，否则表示有错误。从 n(x) 去掉尾部的 r 位数据，得到的就是原始数据。
生成多项式可不是随意选择的，数学上的东西就免了，以下是一些标准的 CRC 算法的生成多项式：
原始的 CRC 校验算法
根据多项式除法，我们就可以得到原始的 CRC 校验算法。假设生成多项式 g(x) 是 r 阶的，原始数据存放在 data中，长度为 len 个 bit ， reg 是 r+1 位的变量。 以 CRC-4 为例，生成多项式 g(x)=x^4 + x + 1 ，对应了一个 5bits 的二进制数字 10011 ，那么 reg 就是 5 bits 。
reg[1] 表明 reg 的最低位， reg[r+1] 是 reg 的最高位。
通过反复的移位和进行除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：
改进一小步——从 r+1 到 r
由于最后只需要 r 位的余数，所以我们可以尝试构造一个 r 位的 reg ，初值为 0 ，数据 data 依次移入 reg[1] ，同时把reg[r] 移出 reg 。
根据上面的算法可以知道，只有当移出的数据为 1 时， reg 才和 g(x) 进行 XOR 运算；于是可以使用下面的算法：
1 *x^6 + 0*x^5 + 1*x^4 + 0*x^3 + 0*x^2 +1*x^1 + 1*x^0
= x^6 + x^4 + x + 1
加减运算不考虑进位和退位。说白了就是下面的运算规则：
0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0
看看这个规则，其实就是一个异或运算。
每个生成多项式的系数只能是 0 或 1 ，因此我们可以把它转化为二进制形式表示， 比如 g(x)=x^4 + x + 1 ，那么g(x) 对应的二进制形式就是 10011 ， 于是我们就把 GF(2) 多项式的除法转换成了二进制形式，和普通除法没有区别，只是加减运算没有进位和退位。
比如基于上述规则计算 11010/1001 ，那么商是 11 ，余数就是 101 ，简单吧。
CRC 校验的基本过程
采用 CRC 校验时，发送方和接收方用同一个生成多项式 g(x) ， g(x) 是一个 GF(2) 多项式，并且 g(x) 的首位和最后一位的系数必须为 1 。
CRC 的处理方法是：发送方用发送数据的二进制多项式 t(x) 除以 g(x) ，得到余数 y(x) 作为 CRC 校验码。校验时，以计算的校正结果是否为 0 为据，判断数据帧是否出错。设生成多项式是 r 阶的（最高位是 x^r ）具体步骤如下面的描述。
发送方：
1 ）在发送的 m 位数据的二进制多项式 t(x) 后添加 r 个 0 ，扩张到 m+ r 位，以容纳 r 位的校验码，追加 0 后的二进制多项式为 T(x) ；
2 ）用 T(x) 除以生成多项式 g(x) ，得到 r 位的余数 y(x) ，它就是 CRC 校验码；
3 ）把 y(x) 追加到 t(x) 后面，此时的数据 s(x) 就是包含了 CRC 校验码的待发送字符串；由于 s(x) = t(x) y(x) ，因此 s(x) 肯定能被 g(x) 除尽。
接收方：
1 ）接收数据 n(x) ，这个 n(x) 就是包含了 CRC 校验码的 m+r 位数据；
2 ）计算 n(x) 除以 g(x) ，如果余数为 0 则表示传输过程没有错误，否则表示有错误。从 n(x) 去掉尾部的 r 位数据，得到的就是原始数据。
生成多项式可不是随意选择的，数学上的东西就免了，以下是一些标准的 CRC 算法的生成多项式：
原始的 CRC 校验算法
根据多项式除法，我们就可以得到原始的 CRC 校验算法。假设生成多项式 g(x) 是 r 阶的，原始数据存放在 data中，长度为 len 个 bit ， reg 是 r+1 位的变量。 以 CRC-4 为例，生成多项式 g(x)=x^4 + x + 1 ，对应了一个 5bits 的二进制数字 10011 ，那么 reg 就是 5 bits 。
reg[1] 表明 reg 的最低位， reg[r+1] 是 reg 的最高位。
通过反复的移位和进行除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：
改进一小步——从 r+1 到 r
由于最后只需要 r 位的余数，所以我们可以尝试构造一个 r 位的 reg ，初值为 0 ，数据 data 依次移入 reg[1] ，同时把reg[r] 移出 reg 。
根据上面的算法可以知道，只有当移出的数据为 1 时， reg 才和 g(x) 进行 XOR 运算；于是可以使用下面的算法：
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯