标签: 线性反馈移位寄存器

CRC 校验：从原理到实现   CRC 校验，就是循环冗余校验， Cyclic Redundancy Check ，是数据通信领域中最常用的一种差错校验码，用于保障数据的完整性。其特征是信息字段和校验字段的长度可以任意选定，也就是说，不管信息序列（明文序列， plaintext 或者 message ）有多长，只要选定某一种 CRC 校验，最后得到的校验序列（校验和）的长度是一定的。   通常使用的 CRC 校验有 CRC-8 、 CRC-12 ， CRC-16 ， CRC-32 ，后面的数字就表示校验之后校验字段的长度（以 bit 记）。   1、 CRC校验的基本原理——多项式求余运算   所有的 CRC 校验都是基于以下 几个 等式 ，但是发送端和接收端的工作机制的不同会使得下面的等式有一些细微变化。为了便于说明，我们选定这种机制：发送端将校验序列附在明文序列之后发出去，接收端对明文序列和校验序列做校验，结果为 0 说明校验正确 ：   发送端， 或者 接收端： 或者 M 是 明文序列的 多项式， R 是校验 序列的 多项式， r 是校验 序列 多项式的最高次幂（也就是校验字段的长度， CRC-32 对应的 r=32 ，依次类推）。 G 是生成 (Generator) 多项式 ， 对某一种确定的 CRC 校验，其 G 是固定的。   发送端 用 G 对 M 做模运算（求余运算），得到校验序列 R ，将 R 附加到明文序列 M 之后传给接收端；   接收端收到 M+R 的序列后么，也用 G 对 M+R 做模运算，将公式 1 或 2 带入 3 或 4 ，得出结论：如果的到结果为 0 ，说明序列正确，数据完整。   所以， CRC 校验最根本的就是用生成多项式对明文多项式（或者是明文 + 校验序列的多项式）做除法求余计算，而它的实现方法就是用线性反馈移位寄存器（ Liner Feedback Shift Register ， LFSR ）实现多项式的求余计算。   2、 LFSR和多项式取模运算的关系   为什么用 LFSR 就能实现 CRC 校验 / 多项式求余运算呢？我们首先来看一个简单的 LFSR ，每经过一个时钟周期， 3bit 的移位寄存器都会按照异或逻辑由低到高做一次值的更新，左侧串行输入多项式序列 M 。     我们假设寄存器的初始值为（ R2 ， R1 ， R0 ） = （ 0 ， 0 ， 1 ），输入序列一直为 0 ，则寄存器的值（ R2 ， R1 ， R0 ）会按照如下状态机跳转，遍历除 000 外的所有 7 个状态 ，相当于一个状态机 。 再假设 M 输入在时间上展开不是全 0 的，而是以 1 开始后面有若干个 0 ，就对应了不同的多项式序列 x^n ，寄存器剩余的值 就是用 x^3+x+1 除以 多项式序列对应的余数序列。   M 在时间上展开的值 多项式序列 M(x) 寄存器最后的值 / 余数 R(x) 1 1 1 10 x x 100 x^2 x^2 1000 x^3 x+1 10000 x^4 x^2+1 100000 x^5 x^2+x+1 1000000 x^6 x^2+1   如果将这张表延续下去，会看到周期性的效果： x^7 对应的 R(x) 为 1 ，依次类推， x^n 对应的 R(x) 都可以用这张表中的内容来表示，有公式：   又根据伽罗华域的性质， GF(2^m) 域的本原多项式为 P(x) = x^8 + x^4 +x^3 + x^2 + 1 ，将 a 作为 P(x) 的根，则有 a^8=a^4+a^3+a^2+1 ，所以任何多项式 M(x) 都可以用 x^n （ 0=n=255 ）来表示，如下表所示：     所以任何 M(x) 的余数 R(x) 都可以 x^0~x^7 的余数准确的表示，所以用 LFSR 可以实现多项式的取模运算。   举个例子来说明，对 CRC16 而言，其生成多项式 G(x)=x^16+x^15+x^2+1 。如图所示，这是一个根据生成多项式设计的 CRC16 校验逻辑，由初始值为全 0 的 16 位以为寄存器和由 G(x) 确定的异或逻辑组成（只有一个输入的异或门默认为另一个输入为 0 ，也就是输出等于输入）。每经过一个时钟周期，移位寄存器都会按照异或逻辑由低到高做一次值的更新，按照图中所示，用 X 表示输入的值，用 R 表示当前的寄存器值， R ’ 表示前一时钟的寄存器值，有：   R =X^R ’ ^R ’ ， R =R ’ ; R = X^R ’ ^R ’ ; R =R ’ ; R = X^R ’ ;