反饋移位暫存器

ai表示二值（0，1）存儲單元，ai的個數n稱為反饋移位暫存器的級。在某一時刻，這些級構成該反饋移位暫存器的一個狀態，共有2^n個可能狀態，每一個狀態對應於域GF（2）上的一個n維向量，用（a₁,a₂,a₃,…a_n）表示。在主時鐘周期的周期區間上，每一級存儲器ai都將內容向下一級ai-1傳遞，並根據暫存器的當前狀態f（a1,a2,a3,…an）作為an的下一時間內容，即從一個狀態轉移到下一個狀態。其中函式f（a1,a2,a3,…an）稱為該反饋移位暫存器的反饋函式。

基本介紹

• 中文名：線性反饋移位暫存器
• 外文名：linear feedback shift register
• 簡稱： LFSR
• 類型：非線性、線性反饋移位暫存器

英文名

： linear feedback shift register simu-lated （簡稱： LFSR）

介紹

線性和非線性反饋移位暫存器

如果反饋函式f（a₁,a₂,a₃,…a_n）是a₁,a₂,a₃,…a_n 的線性函式函式，則該反饋移位暫存器是線性反饋移位暫存器，用LFSR表示，比如：f（a₁,a₂,a₃,…a_n）=k_na₁⊕k_n-1a₂⊕….⊕k₂a_n-1⊕k₁a_n,其中係數k_i∈{0，1}（i=1,2,3,…,n）。

相應的如果反饋函式f（a₁,a₂,a₃,…a_n）是a₁,a₂,a₃,…a_n 的非線性函式函式，則該反饋移位暫存器是非線性反饋移位暫存器。

性質

移位暫存器序列

反饋函式f（a₁,a₂,a₃,…a_n）為n元布爾函式。在時鐘脈衝時，如果反饋移位暫存器的狀態為s_i=(a_i,…..a_i+n-1)則

a_i+n=f(a_i,a_i+1,...,a_i+n-1), (2.1)

這個a_i+n 又是移位暫存器的輸入。在a_i+n的驅動下，移位暫存器的各個數據向前推進一位，使狀態變為s_i+1=(a_i+1,…..a_i+n)，同時，整個移位暫存器的輸出為a_i。由此得到的一系列數據：a₁,a₂,a₃,…,a_n,…。該序列稱為滿足關係式（2.1）的一個反饋移位暫存器序列。

例如，線性反饋移位暫存器設f（a₁,a₂,a₃,…a_n）=c_na₁⊕c_n-1a₂⊕….⊕c₂a_n-1⊕c₁a_n,

輸出序列{a_i}滿足a_n+i= c_na_i⊕c_n-1a_i+1⊕….⊕c₂a_n-2+i⊕c₁a_n-1+i,其中i為非負整數。則該序列{a_i}稱為該反饋移位暫存器序列。

m序列

對於一個n級反饋移位暫存器來說，最多可以有2ⁿ個狀態，對於一個線性反饋移位暫存器來說，全“0”狀態不會轉入其他狀態，所以線性移位暫存器的序列的最長周期為2ⁿ-1。當n級線性移位暫存器產生的序列{a_i}的周期為T=2ⁿ-1時，稱{a_i}為n級m序列。

已經證明，n級m序列{ai}具有以下性質：

在一個周期內，0，1出現次數分別為2^n-1-1次和2^n-1次；

在一個周期圈內，總遊程（是指一個元素連續出現的次數）數為2^n-1，對1≤i≤n-2，長度為i的遊程有2^n-i-1個，且0，1遊程各半，長為n-1的0遊程1個長為n的1遊程1個；

所以可以看出，該序列滿足Golomb的三個公設，具有良好的隨機特性。

當反饋函式f（a₁,a₂,a₃,…a_n）為非線性函式時，便構成非線性移位暫存器，其輸出序列為非線性序列。輸出序列的周期最大可達2ⁿ，並稱周期達到最大值的非線性移位暫存器序列為m序列。在m序列的一個周期內，0和1的個數是相同的。在一個周期圈內，總遊程數為2^n-1，對1≤i≤n-2，長度為i的遊程有2^n-i-1個，且0，1遊程各半，長為n-1的遊程不存在，長度為n的0遊程和1遊程各一個。

特徵多項式

對於線性反饋移位暫存器的輸出序列{a_i}滿足遞推關係a_n+i= c_na_i⊕c_n-1a_i+1⊕….⊕c₂a_n-2+i⊕c₁a_n-1+i,對於任意i≥1成立。其中c₀=1，成為該線性移位暫存器或者該遞推關係的特徵多項式，當c_n≠0時，線性移位暫存器是非奇異的，有時也稱非奇異的線性移位暫存器是非退化的。