关于CRC校验码的计算步骤、模2除法等内容在这里不做过多说明了,本文主要对LFSR电路谈一谈理解。
为简化计算,现假设一个CRC4的生成多项式为:
由多项式可能会得到下面两种形式的电路,区别是红色的连线部分:
两者表现区别见仿真,其中为从高位依次输入,校验结果为,为A电路中D触发器值,为B电路中D触发器值,触发器初值需要为全0。
可以看出B电路在输入所有数据后立刻得出了CRC校验值,而A电路在数据全部输入后还需4个周期才能得到校验值,这是4级D触发器造成的。这个4周期的差别在一定条件下可以消除,当输入数据的前4 bits在第1个时钟前已知时,可以通过对置数来跳过前4个周期。由于A需要已知前几位数据的条件,B电路在设计上是优于A的,下面分析两个电路原理。
电路A
A电路可以分为两个阶段,1 ~ 4时钟周期为数据移入阶段,5 ~ 8时钟周期为模2除法阶段。
上图为初始状态下各D触发器转移情况,可以看出将连续输出4个0电平,这导致在后面4个时钟周期内、先后等于,经过4个周期后,输入数据被依次移入触发器。
模2除法阶段,由于模2除法本质上就是异或,而在生成多项式中做除法的时机是5bit数据第5位为1,在电路中表现为输出为1时进行一次与10101的异或(没有异或电路的、等价于和0异或),各比特对应关系在图中已用颜色标出。
从上图可以看出,将变为0,这表明之后两个周期将不做异或操作(等价于与全0异或保持不变),计算上表现为模2结果前两位为0不够除。
电路B
A电路是一个相对好理解的电路,是对模2除法比较直观的实现。相较于B电路的缺点是在逐位获取输入数据的情况下需要多消耗更多的周期数。产生这一问题的原因在于A电路计算除法需要提供低位数据并直接计算出结果。
B电路认为在接收到输入位时就可以判断其是否需要异或,例如当输入为1并根据多项式可知需要对后2个周期与后4个周期的数据进行异或。因此记录下需要异或的4位情况,当在传入最后一位数据时,电路可以得出记录值与0000异或结果,即CRC4的校验码。
具体情况见下图:
还是从初始状态分析,当输入第一位为1时,由于后几位未知,但根据多项式可以知道后2个周期与后4个周期需要将输入数据与1异或,因此将、置1,可以暂且估计在2个周期与4个周期后置1数据会反馈到处进行异或。
上图输入为0,可以先简单认为此位不需要进行异或。
在这一时刻下,输入为1,但由于之前记录了当前输入需要对1异或,输出的1反馈到了输入端,因此输入的1应该在异或中变为0无法除尽。
给出最后计算结果。
B电路核心是两个异或电路,在例子中均只遇到了3种情况,下面列出其真值表及含义理解:
处异或电路
含义 | ||
---|---|---|
0 | 0 | 输入为0且未被模2除,不需要对后续数据做除法 |
0 | 1 | 输入为1且未被模2除,需要对后续数据做除法 |
1 | 0 | 输入0但被模2除后变为1,需要对后续数据做除法 |
1 | 1 | 输入1但被模2除后变为0,不需要对后续数据做除法 |
处异或电路
含义 | ||
---|---|---|
0 | 0 | 此位不需要做除法 |
0 | 1 | 此位将要做一次除法 |
1 | 0 | 此位将要做一次除法 |
1 | 1 | 此位将要做两次除法,因此相互抵消 |