用于CRC计算的LFSR电路理解

关于CRC校验码的计算步骤、模2除法等内容在这里不做过多说明了,本文主要对LFSR电路谈一谈理解。

为简化计算,现假设一个CRC4的生成多项式为:
G\left(x\right)=x^{4}+x^{2}+1
由多项式可能会得到下面两种形式的电路,区别是红色的连线部分:

两者表现区别见仿真,其中data\_in1011从高位依次输入,校验结果为1101xa为A电路中D触发器值,xb为B电路中D触发器值,触发器初值需要为全0。

可以看出B电路在输入所有数据后立刻得出了CRC校验值,而A电路在数据全部输入后还需4个周期才能得到校验值,这是4级D触发器造成的。这个4周期的差别在一定条件下可以消除,当输入数据的前4 bits在第1个时钟前已知时,可以通过对x_{0},..,x_{3}置数来跳过前4个周期。由于A需要已知前几位数据的条件,B电路在设计上是优于A的,下面分析两个电路原理。

电路A

A电路可以分为两个阶段,1 ~ 4时钟周期为数据移入阶段,5 ~ 8时钟周期为模2除法阶段。

上图为初始状态下各D触发器转移情况,可以看出x_{3}将连续输出4个0电平,这导致在后面4个时钟周期内x_{2} = x_{1}x_{0}先后等于1011,经过4个周期后,输入数据被依次移入触发器。

模2除法阶段,由于模2除法本质上就是异或,而在生成多项式x^{4}+x^{2}+1中做除法的时机是5bit数据第5位为1,在电路中表现为x_{3}输出为1时进行一次与10101的异或(没有异或电路的x_{1}x_{3}等价于和0异或),各比特对应关系在图中已用颜色标出。
从上图可以看出x_{2}x_{3}将变为0,这表明之后两个周期将不做异或操作(等价于与全0异或保持不变),计算上表现为模2结果前两位为0不够除。

电路B

A电路是一个相对好理解的电路,是对模2除法比较直观的实现。相较于B电路的缺点是在逐位获取输入数据的情况下需要多消耗更多的周期数。产生这一问题的原因在于A电路计算除法需要提供低位数据并直接计算出结果。

B电路认为在接收到输入位时就可以判断其是否需要异或,例如当输入为1并根据多项式x^{4}+x^{2}+1可知需要对后2个周期与后4个周期的数据进行异或。因此记录下需要异或的4位情况,当在传入最后一位数据时,电路可以得出记录值与0000异或结果,即CRC4的校验码。

具体情况见下图:

还是从初始状态分析,当输入第一位为1时,由于后几位未知,但根据多项式可以知道后2个周期与后4个周期需要将输入数据与1异或,因此将x_{2}x_{0}置1,可以暂且估计在2个周期与4个周期后置1数据会反馈到x_{0}处进行异或。

上图输入为0,可以先简单认为此位不需要进行异或。

在这一时刻下,输入为1,但由于之前记录了当前输入需要对1异或,x_{3}输出的1反馈到了输入端,因此输入的1应该在异或中变为0无法除尽。

给出最后计算结果。

B电路核心是两个异或电路,在例子中均只遇到了3种情况,下面列出其真值表及含义理解:

x_{0}处异或电路

x_{3} data\_in 含义
0 0 输入为0且未被模2除,不需要对后续数据做除法
0 1 输入为1且未被模2除,需要对后续数据做除法
1 0 输入0但被模2除后变为1,需要对后续数据做除法
1 1 输入1但被模2除后变为0,不需要对后续数据做除法

x_{2}处异或电路

D_{x0} x_{1} 含义
0 0 此位不需要做除法
0 1 此位将要做一次除法
1 0 此位将要做一次除法
1 1 此位将要做两次除法,因此相互抵消
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1/3 考前复习 考试说明 填空题,8道,共16分 选择题,7道,共14分 解答题,7道,共70分 往年真题及答案...
    Du1in9阅读 8,373评论 2 61
  • 零. 课程要点: 了解基础逻辑电路 C语言中的各类运算 判断溢出与数据舍入 如果没学过基础逻辑电路,应该是有专门的...
    KPlayer阅读 3,181评论 0 2
  • 16宿命:用概率思维提高你的胜算 以前的我是风险厌恶者,不喜欢去冒险,但是人生放弃了冒险,也就放弃了无数的可能。 ...
    yichen大刀阅读 6,088评论 0 4
  • 公元:2019年11月28日19时42分农历:二零一九年 十一月 初三日 戌时干支:己亥乙亥己巳甲戌当月节气:立冬...
    石放阅读 6,907评论 0 2
  • 今天上午陪老妈看病,下午健身房跑步,晚上想想今天还没有断舍离,马上做,衣架和旁边的的布衣架,一看乱乱,又想想自己是...
    影子3623253阅读 2,927评论 3 8