CRC 校验原理.docVIP

CRC 校验原理校验原理 1 循环校验码 CRC 码 是数据通信领域中最常用的一种差错校验码 其特征是信息字段和校验字段的长度可以任意选定 2 生成 CRC 码的基本原理 任意一个由二进制位串组成的代码都可以 和一个系数仅为 0 和 1 取值的多项式一一对应 例如 代码 1010111 对 应的多项式为 x6 x4 x2 x 1 而多项式为x5 x3 x2 x 1对应的代码 101111 3 CRC 码集选择的原则 若设一个带有 CRC 的码字长度为 N 信息字段 为 K 位 校验字段为 R 位 N K R 则对于 CRC 码集中的任一码字 存在且仅存 在一个 R 次多项式 g x 使得 t x A x g x xRm x r x 其中 m x 为 K 次信息多项式 g x 称为生成多项式 g x g0 g1x 2x2 g R 1 x R 1 gRxR r x 为 R 1 次校验多项式 t x 为编码后的带 CRC 的信息多项式 发送方通过指定的 g x 产生 CRC 码字 接收方则通过该 g x 来验证收到的 CRC 码字 4 CRC 校验码软件生成方法 借助于多项式除法 其余数为校验字段 例如 例如 信息字段代码为 1011001 对应m x x6 x4 x3 1 假设生成多项式为 g x x4 x3 1 则对应 g x 的代码为 11001 xRm x x4m x x10 x8 x7 x4 对应的代码记为 10110010000 采用多项式除法除以 g x 得余数为 1010 即校验字段为 1010 发送方发送方 发出的传输字段为 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1010 信息字段 校验字段 接收方接收方 使用相同的生成码进行校验 接收到的字段 生成码 二进制除法 如果能够除尽 则正确 否则出错 5 CRC 校验码生成示意图 CRC 代数学的一般性算法 在代数编码理论中 将一个码组表示为一个多项式 码组中各码元当作多项式 的系数 例如 1100101 表示为 1 x6 1 x5 0 x4 0 x3 1 x2 0 x 1 即 x6 x5 x2 1 设编码前的原始信息多项式为 m x m x 的最高幂次等于 K 生成多项式为 g x g x 的最高幂次等于 R CRC 多项式为 r x r x 为 R 1 次校验多项式 编码后的带 CRC 的信息多项式为 t x 发送方编码方法 将 m x 乘以xR 即对应的二进制码序列左移 R 位 再除以 g x 所得余式即为 r x 用公式表示为 t x xRm x r x 接收方解码方法 将 t x 除以 g x 如果余数为 0 则说明传输中无错误发生 否则说明传输有误 举例来说 设信息码为 1100 生成多项式为 1011 即 m x x3 x2 g x x3 x 1 则计算 CRC 的过程为 xrm x x3 x3 x2 x6 x5 x3 x2 x x g x x3 x 1 x3 x 1 x3 x 1 即 r x x 注意到 g x 最高幂次 R 3 得出 CRC 为 010 除法 除法是乘法的逆运算 二进制除法和十进制除法也一样 而且更简单 每一位商数不 是 0 就是 1 二进制除法 1 10100010 1001 2 10010011 111 解 1 2 10100010 1001 10010 10010011 111 10101 求二进制除法的商数和余数 111010 101 解 111010 101 所得商数是 1011 余数是 11 二进制除法是乘法的逆运算 规则如下 1 1 1 0 1 0 1 0 不允许 0 0 不允许 2 3 二进制数算术运算二进制数算术运算 二进制数的加 减 乘 除四则运算 在数字系统中是经常遇到的 它们的运算规则与 十进制数很相似 加法运算是最基本的一种运算 利用它的运算规则可以实现其它三种运算 例如 减法运算可以借助改变减数的符号再与被减数相加 乘法运算可视为被乘数的连加 而除法则可视为被除数重复地减去除数 1 二进制加法二进制加法 二进制加法运算的规则可简单描述如下 1 被加数 0 0 1 1 1 加 数 0 1 0 1 1 和 0 1 1 10 11 2 二进制减法二进制减法 这里先介绍无符号数的减法 其规则如下 借 入 被减数 0 1 1 10 减 数 0 0 1 1 差 0 1 0 1 3 二进制乘法二进制乘法 二进制乘法与十进制乘法相同 下面列出了四条规则 4 二进制除法二进制除法 二进制除法与十进制除法相同 5 用带符号位的二进制数实现减法运算用带符号位的二进制数实现减法运算 1 带符号位的二进制数 一个二进制数既可表示为正数 也可表示为负数 其方法是在二进制数之前加一符号位 通常用 表示正数 而用 表示负数 其余数位表示数的大小 例如 5 0101 5 1101 2 补码的概念 补码是负数的一种表示方法 现以人们熟悉的十进制数为例来说明补码的概念 常规减法运算以 10 为模的减法运算 87 87 87 24 24 76 63 163 可见 将减数 24 变为以 10 为模 称为模 10 的补码为 76 然后相加并丢弃进位数 其结果相同 模 10 的补码是这样求得的 模数 10 减 1 作为底数 9 然后将减数的每一位 数码从底数 9 中减去得到相应的数码 然后加 1 便得到补码 在上例中 99 24 1 75 1 76 3 二进制的模 2 补码及减法运算 与模 10 的补码相类似 当二进制形成模 2 的补码时 模数 2 减 1 作为底数 1 然后将减 数的每一位从底减去 得到相应的位的数码 然后加 1 便得到补码 例如 011 的模 2 补 码为 101 实际上 一种简便的方法是将二进制数码中的 0 变为 1 1 变为 0 再加 1 即可 得到模 2 的补码 常规的减法运算 模 2 补码的减法运算 被减数 7 0111 0111 减 数 3 0011 1101 差 4 100 10100 丢弃进位 由上可知 模 2 补码的减法运算与常规运算的结果一致 在此例中还需注意到在运算中 符号参加运算 有关二进制数的四则运算细节 可参阅有关文献 8 9 1 数字电路处理的信号是离散信号 这种信号的有无可以用二进制信息 0 和 1 表示 其 大小也可以用二进制数表示