用于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 此位将要做两次除法,因此相互抵消
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,332评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,508评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,812评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,607评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,728评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,919评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,071评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,802评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,256评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,576评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,712评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,389评论 4 332
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,032评论 3 316
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,798评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,026评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,473评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,606评论 2 350

推荐阅读更多精彩内容

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