CRC检验原理及程序实现

CRCCRC 检验原理及程序实现检验原理及程序实现 引言 引言 循环冗余检验 CRC Cyclic Redundancy Check 的检错技术应用较为广泛 由于实际的 通信线路并非是理想的 它不可能将误码率 在一段时间内 传输错误的比特占所传输比 特总数的比率称为误码率 BER 下降到零 因此 为了保证数据传输的可靠性 在计算机 网络传输数据时 必须采用检错措施 目前在数据链路中广泛采用循环冗余检验 CRC 检测 技术 1 循环冗余检验 循环冗余检验 CRC 的原理的原理 利用 CRC 进行检错的过程可简单描述为 在发送端根据要传送的 k 位二进制码序列 以一定的规则产生一个校验用的 n 位监督码 CRC 码 附在原始信息后边 构成一个新的 二进制码序列数共 k n 位 然后发送出去 在接收端 根据信息码和 CRC 码之间所遵循 的规则进行检验 以确定传送中是否出错 这个规则 在差错控制理论中称为 生成多项 式 代数学的一般性算法 在代数编码理论中 将一个码组表示为一个多项式 码组中各码元当作多项式的系数 例如 表示为 1 x6 1 x5 0 x4 0 x3 1 x2 0 x 1 即 x6 x5 x2 1 设编码前的原始信息多项式为 G x G x 的最高幂次加 1 等于 k 生成多项式为 P x P x 的最高幂次等于 r CRC 多项式为 R x 编码后的带 CRC 的信息多项式为 T x 发送方编码方法 将 x 乘以 xr 即对应的二进制码序列左移 r 位 再除以 x 所得 余式即为 R x 用公式表示为 T x xr x R x 接收方解码方法 将 T x 除以 G x 如果余数为 0 则说明传输中无错误发生 否则说 明传输有误 2 循环冗余码的产生及正确性检验的例子 循环冗余码的产生及正确性检验的例子 举例来说 设信息码为 生成多项式为 1101 即 P x x3 x2 1 G x x5 x3 1 计算 CRC 的过程为 xrP x 即左移三位 x x3 x2 1 即 R x 注意到 G x 最高幂次 r 3 得出 CRC 为 001 如果用竖式除法 计算过程为 用异或计算 以 x 为准 x 左移 P x 的最高 次位 r 再除以 P x 本身求余可得一个的位的 CRC 码 1 1 0 1 0 1 商 P 除数 1 1 0 1 Error 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 R 余数 即检验码 因此 T x XrG x R x 即 010 如果传输无误 T x 除以 P x 无余式 回头看一下上面的竖式除法 如果被除数 是 除数是 P 1101 显然就能除尽 总之 在接收端对收到的每一帧经过 CRC 检验后 1 若得出的余数 R 0 则判断这个帧没有差错 就接受 2 若余数 R 不等于 0 则判断这个帧有差错 但无法确定究竟是哪一位或那几位出 现了差错 就丢弃 3 用 用 C 语言程序实现语言程序实现 下面以最常见的 CRC 16 为例说明生成过程 假设发送信息用信息多项式 K x 表示 将 K x 左移 R 位 则可以表示成 K x 2R 这样 K x 的右边就会生成 R 位 这就是检验码 的位置 通过 K x 2R 除以生成多项式 G x 得到的余数就是检验码 实现方法 1 最高幂次为 R 的生成多项式 G x 转换成对应的 R 1 位二进制数 2 码左移 R 位 相当于对应的信息多项式 K x 2R 3 多项式 二进制 对信息码做模 2 除 得到 R 位的余数 4 拼到信息码左移后空出的位置 得到完整的 CRC 码 C 语言源程序代码 include void main unsigned int g k r l n b c d e p i s j cont register s1 printf 以下数据一十六进制计数方式输入 n printf 请输入生成码的值 n scanf d printf 请输入信息码的值 n scanf d unsigned int m w 0 测量生成码的长度 r m g do m 1 w while m 0 r w unsigned int m w 0 测量信息码的长度 n m k do m 1 w while m 0 n w k n 1 取被除数信息码的高 r 1 位 即和生成码的位数相同 do s i g 被除数信息码与生成码异或运算 p r c 0 统计余数 s 高位零的个数 保存到 c for j 0 j p 1 if s1c else break if c l cont break 余数 s 高位零的个数高于信息码没有被除的位数 跳出循环 不再做异 或运算 s n 1 c 取信息码 K 的从右端开始的 n r 1 r c n 1 c 的 C 位 d 0 c e b s s e 取 s 的高位与信息码没被除的高位合成被除数 i s cont c while cont l s s k 将最后余数