當前位置:網站首頁>【電子技術】什麼是LFSR?

【電子技術】什麼是LFSR?

2022-01-27 19:34:56 那麼菜

目錄

0 前言

1 數學基礎

1.1 邏輯异或

1.2 模2乘法 和 模2除法

 2 線性反饋移比特寄存器LFSR

3  抽頭和特征多項式

 4  階線性反饋移比特寄存器實例


0 前言

線性反饋移比特寄存器: (Linear Feedback Shift Register,LFSR)和循環冗餘碼(Cyclic Redundancy Check,CRC)是微控制器中常用的底層原理。LFSR用於生成偽隨機數,後者用於生成檢錯碼。他們的數學原理都是一樣的。

1 數學基礎


1.1 邏輯异或


异或運算使用符號⊕或者nor錶示,真值錶如下
F = A ⊕ B

A    B    F
0    0    0
0    1    1
1    0    1
1    1    0
异或運算可以有3種理解方式:

1 相同得0,不同得1

2 二進制加法,只留模2的餘數,拋弃進比特(模2加法)

3 二進制减法,大數减小數,不借比特(模2减法)
 

1.2 模2乘法 和 模2除法

兩個二進制數的模2乘法是指在乘法豎式運算中需要做加法的地方都使用异或運算。

模2乘法1010 * 101=100010,下圖紅框中,1⊕0⊕1=0,沒有進比特:

兩個二進制數的模2除法是指在除法豎式運算中需要做减法的地方都使用异或運算。

模2除法10000 / 101=1011,下圖紅框中,0⊕1=1,沒有借比特:

在這裏插入圖片描述

 2 線性反饋移比特寄存器LFSR

以斐波那契(外部LFSR)為例,有n個二進制寄存器R0-Rn-1,每個寄存器值為01。

在這裏插入圖片描述

3  抽頭和特征多項式

f(Rn-1, … R1, R0) = (Rn-1*gn)⊕(Rn-2*gn-1)⊕…⊕(R0*g1)*g0 可以用多項式錶示為:

G(x)=gnxn+gn-1xn-1+…+g1x+g0

G(x)稱為LFSR的特征多項式。

影響線性反饋寄存器下一個狀態的 gi = 0 或1叫做抽頭,抽頭的設定會决定線性反饋寄存器存儲的結果 (Rn-1, … R1, R0) 的變化規律。

通常N比特的線性反饋寄存器最多有 2'N 個不同的狀態。但是如果出現初值為N個0的情况,線性反饋寄存器陷入死循環,要排除掉。所以N比特線性反饋寄存器能產生最長的不重複序列為 2'N-1。

抽頭的比特置會影響LSFR的最大輸出狀態的個數
例如:3比特的抽頭為(g3, g2, g1, g0) = (1, 1, 0, 1)會產生7個狀態(多項式對應為:G(x)=x3+x2+1)
若抽頭為(g3, g2, g1, g0) = (1, 0, 1, 1),會產生2個狀態(多項式對應為:x3+x+1)。

使最大輸出序列長度為2N-1的不可約多項式稱為LFSR的本原多項式,本原多項式產生的寄存器序列為M序列。

當N比特下,本原多項式不是唯一的。下錶為不同的比特下的本原多項式:
在這裏插入圖片描述

 在這裏插入圖片描述

 4  階線性反饋移比特寄存器實例

在這裏插入圖片描述

上圖為3階線性反饋移比特寄存器:
抽頭為(g3, g2, g1, g0) = (1, 1, 0, 1)
多項式對應為:G(x)=x3+x2+1
線性反饋函數R0 = f(R2, R1, R0) = R1⊕R2
初始值為SEED = (R2, R1, R0) = (1, 0, 1)

3階線性反饋移比特寄存器周期為7:

通過設定seed和抽頭,LFSR最多可產生2N-1個序列,這些序列之間看似是隨機產生的之所以稱之為偽隨機,是因為這些數是通過具體的關系式產生,最終會實現循環。 

版權聲明
本文為[那麼菜]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271934557323.html

隨機推薦