CRC逻辑电路设计

CRC逻辑电路设计

前导课程分析了CRC根据生成多项式进行二进制除法求余，而且是模2求余。根据模2除的原理以及除法竖式的计算过程，可以进行逻辑电路设计，也可以通过Verilog等描述语言进行RTL设计成IP核的方式应用在FPGA与IC设计领域，当然也可以通过软件的方式实现（如C语言）。下面将分析设计过程。

1. 逻辑电路推导步骤

观察除法竖式的计算过程，将分为如下几步的推导过程，计算竖式如图1所示，

图1 CRC 模2除竖式

• 被除数左移

除数为b=X⁴+X³+1，是5位2进制数11001，被除数a=X¹¹ +0+  X⁹+X⁸ +0+0+ X⁵+X⁴  +0+   X² + 0  + 0 =>a=1011_0011_0100，在逻辑电路上可以通过移位寄存器的方式实现，寄存器的个数应与余数的位数相同（比除数少一位），寄存器的初始值设为0，如图2所示： 可以使用q0 – q3; 或者 q4- q1。

图2 移位寄存器

• 余数计算

在寄存器的移位工程中，由于寄存器的个数与余数的位数相同，因此只有最高位为1时，被除数与除数才会进行减法运算，如图1的第一步。实际上由于CRC的除数最高位都为1（X⁴ + X³ + 1 = 11001），因此只有被除数的最高位（不为零）移到Q3时才会做减法运算(这里我们使用{q[3:0]  , data_in}计算)，DATA_IN 也作为计算因子，根据移位寄存器的移位过程确定计算过程,输入数据（被除数）为 a=1011_0011_0100 ； 除数为 b=X⁴+X³+1， 11001

1. 1. 初始数据Q3 Q2 Q1 Q0 DATA_IN= 00001，
   2. 移位Q3 Q2 Q1 Q0 DATA_IN= 00010，
   3. 移位Q3 Q2 Q1 Q0 DATA_IN= 00101，
   4. 移位Q3 Q2 Q1 Q0 DATA_IN= 01011，
   5. 移位Q3 Q2 Q1 Q0 DATA_IN=10110，—>减法计算，如图2，图3所示

图2 移位计算

 

图3 多项式减法计算

可以看出减法运算完全可以用异或运算替代，因此图2，图3可以写成如下逻辑表达式：( 10110 ^ 11001), 串行输入的data_in 数据锁存后 异或的公式：

R4 = Q4 ^ b4;

R3 = Q3 ^ b3;

R2 = Q2 ^ b2;

R1 = Q1 ^ b1;

R0 = Q0 ^ b0;

由于R4的结果为0，因此该项不作为余数的一部分，真正的余数为R3R2R1R0。但例中除数b2,b1为0（x⁴ + x³ +1 = 11001）， 因此结果可以理解为，余数为寄存器输出与除数中的位为1的做异或运算，除数为0的位保持被除数部分原值输出，逻辑电路可以更新如图4，

R4 = Q4 ^ b4;

R3 = Q3 ^ b3;

R2 = Q2 ^ b2;

R1 = Q1 ^ b1;

R0 = Q0 ^ b0;

=

R4 = 1 ^ 1 = 0;

R3 = Q3 ^ b3;

R2 = Q2 ^ 0 = Q2;

R1 = Q1 ^ 0 = Q1;

R0 = Q0 ^ b0;

图4，CRC 余数计算输出为R3 – R0

• 更新被除数

从图2，图3的计算过程还可以看出，新的一轮计算是余数与被除数的新的一位参与左移形成新的被除数，即新的被除数应为Q4 Q3 Q2 Q1 Q0 = R3 R2 R1 R0 DATA_IN左移一位的结果，但是是否与除数相减求余决定于Q4是否为1，如果Q4不为1，则寄存器继续移位，直到Q4为1。

因此可以充分利用寄存器的特点，将余数与左移结合在一起更新被除数，也就是更新移位寄存器。

• • 被除数更新如下，

a = X¹¹ + 0    +  X⁹  +X⁸  + 0  + 0   +   X⁵ + X⁴  + 0    +  X² + 0 + 0

a = R3  + R2 + R1  +R0  + 0  + X⁵+  X⁴  + 0    + X²  +   0  + 0  (一直移位到 q4 等于1)

其中,移位锁存后的结构，计算公式如下：

R3 = Q3^b3=Q4;

R2 = Q2^b2=Q3;

R1 = Q1^b1=Q2;

R0 = Q0^b0=Q1;

DATA_IN=0; （新数据）

• • 移位计算余数

如果Q4为1，计算过程与上面的步骤相同，如果Q4为0，余数为移位后低四位数据，被除数为移位后的5位数据，即余数和被除数都不进行异或运算，仅使用移位后的数据。可见余数更新和被除数更新都受最高位Q4的控制，Q4=0使用移位后的原数据，Q4=1使用移位后与除数中为1的位异或的运算结果。但是Q4的逻辑也是异或逻辑。

图5   移位计算余数

根据上面的分析，更新逻辑图如图6

图6， 输出反馈

图6中由于，Q4=1,以及b3, b0都为1时更新余数和被除数，与就是更新移位寄存器的值，但我们知道本例中由于生成多项式已经确定，b3,b0必为1，因此上图中的两个与门可以DATA_OUT 直连的方式实现。如图7，

图7  电路化简

• 电路优化

从图7的电路可以看出，Q4的结果最终被移出并丢弃，Q0仅起到新数据锁存的作用，R3,R0是组合逻辑输出，对时序收敛不利，因此可以将运算超前一位，并删除Q4，最终的余数比图7滞后一个时钟输出。如图8所示。

图8  优化后的电路

• 完善电路，

将移位寄存器加上清0控制端，就可以控制控制CRC的启动计算了。如图9所示。

图9  完善电路-复位电路

图9利用了输出反馈到移位寄存器的输入，是典型的线性反馈移位寄存器LFSR的使用。根据以上推到及设计步骤，可以画出CRC5，CRC8，CRC12，CRC16，CRC32等不同生成多项式生成CRC的逻辑电路。

由于CRC5，CRC8，CRC12，CRC16，CRC32逻辑电路的步骤与上面的设计步骤类似，这里不再一一画出逻辑电路，后续文章中会以verilog HDL描述语言给出RTL的设计。