🛅線性反饋移位寄存器

1696868916147

線性反饋移位寄存器（Linear Feedback Shift Register，LFSR）作為線性驅動部分來生成偽隨機碼，是數學意義上的最優解，自相關函數除主峰外具有最大平坦。

LFSR 引入#

若干個寄存器排列成一行，每個寄存器存儲著一個二進制數。移位寄存器每次將最右端（末端）的數字輸出，然後整體向右移動移位。同時具有一個反饋函數，以寄存器中已有的某些序列作為反饋函數的輸入，將反饋函數的輸出填充到移位寄存器的最左端，這樣的，擁有反饋函數的移位寄存器稱為反饋移位寄存器。

反饋函數#

LFSR 的反饋函數就是簡單地對移位寄存器中的某些位進行異或，並將異或的結果填充到 LFSR 的最左端。對於 LFSR 中每一位的數據，可以參與異或，也可以不參與異或。其中，我們把參與異或的位稱為抽頭。

b_{n+1} = c_1b_1 \oplus c_2b_2 \oplus \ldots \oplus c_nb_n

級數#

LFSR 的級數就是其中寄存器的個數，一個 $n$ 級的 LFSR 最多可以存儲 $2^n-1$ 種狀態，因為全零的狀態反饋值始終是全零。至於為什麼最多能夠遍歷 $2^n-1$ 種狀態，將在之後介紹。一個 $n$ 級的 LFSR 的最大周期就是 $2^n-1$ ，我們將周期為 $2^n-1$ 的 LFSR 所生成的序列稱為 $m$ 序列。

特徵多項式#

由上述式子可以得到一個 LFSR 的遞推關係式，則這個遞推關係可以對應這一個特徵多項式

f(x) = c_nx^n + c_{n-1} + \ldots + c_2x^2 + c_1x + 1

這裡的 $c_i$ 與之前的定義相同，表示是否抽頭。最終得到的特徵多項式只保留抽頭位次項，並加一。可以理解為一個 LFSR 的不同特徵多項式對應著不同的反饋函數。

本原多項式#

首先給出一個結論

$n$ 級 LFSR 能夠產生 $m$ 序列的充要條件為其特徵多項式為本原多項式

接下來以此引入不可約多項式和本原多項式。

Irreducible Polynomial. 一個多項式在指定域上不能分解，則稱為不可約多項式，即不能等於次數更小的多項式的乘積。

LFSR 中採用的有限域為 $GF(2^n)$ ，指多項式的係數要小於 2，即為 0 或 1，多項式的最高次數不能夠大於或等於 $n$ 。如 $GF(2^3)$ 中的多項式為 $0, 1, x, x+1$ 。

Primitive Polynomial. 本原多項式本身就是一種不可約多項式，但是需要滿足以下三個條件：對於 $n$ 次的本原多項式 $F(x)$

$F(x)$ 是不可約的，不能再分解多項式

$F(x)$ 可整除 $x^p+1$ ，其中 $p = 2^n-1$

$F(x)$ 不能整除 $x^q+1$ ，其中 $q<p$

由本原多項式可以得到生成 $m$ 序列的反饋函數，如 $n=10$ 時本原多項式為

F(x) = x^{10} + x^3 + 1

則反饋函數就表示為 [0,0,1,0,0,0,0,0,0,1] ，意味著第 3 位寄存器和第 10 位寄存器中的值做異或得到的輸出賦值給最左端的寄存器，實現移位反饋。

MATLAB 中 primpoly 函數可以查看任意次數的本原多項式

$m$ 序列的性質#

$m$ 序列實際上就是我們稱呼的偽隨機碼或者擴頻碼。

均衡性#

在 $m$ 序列的一個周期中，0 和 1 的數目基本相等，1 的個數會比 0 多一個。

移位相加性#

一個 $m$ 序列 $m_1$ 與其經過任意延遲移位產生的另一序列 $m_2$ 模 2 相加（異或），得到的仍是 $m_1$ 的某次延遲移位序列 $m_3$ 。

自相關性#

由於 1 的個數始終比 0 多一個，因此在做自相關的過程中，始終會得到一個 -1 的值，這與完全的隨機信號有著很大的區別。

R(\tau) = \left\{ \begin{align*} &1, &\tau = 0\\ &-\frac{1}{N}, &\mathrm{else} \end{align*}\right.

遊程分布#

$m$ 序列中取值相同的相繼元素合稱為一個 “遊程”，遊程中元素的個數稱為遊程長度。 $n$ 位 LFSR 生成的 $m$ 序列中，總共由 $2^{n-1}$ 個遊程，其中長度為 1 的遊程佔總遊程數的 1/2，長度為 2 遊程佔總遊程數的 1/4，長度為 k 的遊程佔總遊程數的 $2^{-k}$ ，且長度為 k 的遊程中，連 0 和連 1 的遊程數各佔一半。遊程分布具有很好的均衡性。

如序列 1000010010110011111000110111010 中，遊程總數為 $2^{5-1}=16$ ，各個長度的遊程分布如下：

長度為 1 的遊程數目為 8，其中 4 個 1 遊程和 4 個 0 遊程
長度為 2 的遊程數目為 4，其中 2 個 11 遊程和 2 個 00 遊程
長度為 3 的遊程數目為 2，其中 1 個 111 遊程和 1 個 000 遊程
長度為 4 的連 0 遊程數目為 1
長度為 5 的連 1 遊程數目為 1

附錄#

由於時間原因，之前有關本原多項式的生成和證明有所省略，未來有時間可以在其他文獻中進行查閱