Menu Close

CRC逻辑电路设计

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

1. 逻辑电路推导步骤

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

%title插图%num

图1 CRC 模2除竖式

  • 被除数左移

除数为b=X4+X3+1,是5位2进制数11001,被除数a=X11 +0+  X9+X8 +0+0+ X5+X +0+   X2 =>a=1011001101,在逻辑电路上可以通过移位寄存器的方式实现,寄存器的个数应与余数的位数相同(比除数少一位),寄存器的初始值设为0,如图2

%title插图%num

图2 移位寄存器

  • 余数计算

在寄存器的移位工程中,由于寄存器的个数与余数的位时相同,因此只有最高位为1时,被除数与除数才会进行减法运算,如图1的第一步。实际上由于CRC的除数最高位都为1,因此只有被除数的最高位(不为零)的移到Q3时才会做减法运算,DATA_IN 也作为计算因子,根据移位寄存器的移位过程确定计算过程

      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所示

%title插图%num

图2 移位计算

 

%title插图%num

图3 多项式减法计算

可以看出减法运算完全可以用异或运算替代,因此图2,图3可以写成如下逻辑表达式:

R4=Q4^B4;

R3=Q3^b3;

R2=Q2^b2;

R1=Q1^b1;

R0=Q0^b0;

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

%title插图%num

图4,CRC 余数

  • 更新被除数

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

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

    • 被除数更新如下,

a=X11 +0+  X9+X8 +0+0+ X5+X +0+   X2

a= R4+R3+R2+R0+0+X5+X4+0+X2

其中,

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的逻辑也是异或逻辑。

%title插图%num

图5   移位计算余数

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

%title插图%num

图6, 输出反馈

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

%title插图%num

图7  电路化简

  • 电路优化

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

%title插图%num

图8  优化后的电路

  • 完善电路,

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

%title插图%num

图9  完善电路

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

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

Posted in FPGA, FPGA, 教材与教案, 文章, 资料区

1 Comment

发表评论

相关链接