使用線性反饋移位寄存器生成偽隨機數

線性反饋移位寄存器與完全描述它們的多項式一起引入。應用說明描述了如何實現它們以及可用于改善所生成數字的統(tǒng)計特性的技術。

介紹

LFSR（線性反饋移位寄存器）提供了一種在微控制器上快速生成非序列數字列表的簡單方法。生成偽隨機數只需要右移操作和 XOR 操作。圖 1 顯示了一個 5 位 LFSR。圖 2 顯示了 C 語言的 LFSR 實現，圖 3 顯示了 8051 匯編中的 16 位 LFSR 實現。

LFSR和多項式

LFSR 完全由其多項式指定。例如，6千-次多項式與每個項存在用方程 x 表示6+ x5+ x4+ x3+ x2+ x + 1。有 2 個(6 - 1)= 32 個這種大小的不同可能多項式。與數字一樣，一些多項式是素數或原始數。我們對原始多項式感興趣，因為它們會在移位時為我們提供最大長度周期。n 次的最大長度多項式將有 2n- 1個不同的州。每個班次后都會轉換到新狀態(tài)。因此，6千-次多項式將有 31 種不同的狀態(tài)。1 到 31 之間的每個數字在重復之前都會出現在移位寄存器中。在基元 6 的情況下千-次多項式，只有六個。表 1 列出了所有基元 6千-次多項式及其各自的多項式掩碼。多項式掩碼是通過采用多項式的二進制表示并截斷最右側的位來創(chuàng)建的。掩碼用于實現多項式的代碼中。實現 n 的多項式掩碼需要 n 位千-次多項式。

每個基元多項式都有奇數項，這意味著基元多項式的每個掩碼都有一個偶數 1 位。每個原始多項式還定義了第二個原始多項式，即它的對偶?？梢酝ㄟ^從每項的多項式次數中減去指數來找到對偶。例如，給定 6千-次多項式，x6+ x + 1，它的對偶是 x6-6+ x6-1+ x6-0，等于 x6+ x5+ 1.在表 1 中，多項式 1 和 2、3 和 4、5 和 6 是彼此的對偶。

表 2 列出了每個不同大小多項式的周期以及每個大小存在的基元多項式的數量。表 3 列出了每個不同大小的多項式的一個多項式掩碼。它還顯示了當 LFSR 初始化為 1 時，LFSR 在連續(xù)班次后將保持的前四個值。此表應有助于確保實現正確。

LFSR的結構

LFSR 的值永遠不會為零，因為歸零的 LFSR 的每個偏移都會將其保留為零。LFSR 必須初始化，即種子，為非零值。當 LFSR 保持 1 并移動一次時，其值將始終為多項式掩碼的值。當寄存器除最高有效位外全部為零時，接下來的幾個偏移將顯示高位偏移到零填充的低位。例如，任何具有基元多項式的 8 位移位寄存器最終將生成序列 0x80、0x40、0x20、0x10、8、4、2、1，然后生成多項式掩碼。

使用 LFSR 生成偽隨機數

一般來說，基本的LFSR不會產生非常好的隨機數。通過選擇較大的LFSR并使用較低的位作為隨機數，可以改進更好的數字序列。例如，如果您有一個 10 位 LFSR 并且想要一個 8 位數字，則可以將寄存器底部的 8 位作為您的號碼。使用此方法，您將看到每個 8 位數字四次和零，三次，然后 LFSR 完成一個周期并重復。這解決了得到零的問題，但數字仍然沒有表現出非常好的統(tǒng)計特性。相反，您可以將 LFSR 的子集用于隨機數，以增加數字的排列并改善 LFSR 輸出的隨機屬性。

在獲得隨機數之前多次移動LFSR也可以改善其統(tǒng)計特性。將LFSR移動其周期的一個因子將使總周期長度減少該因子。表2列出了各期間的因素。

LFSR 相對較短的周期可以通過將兩個或多個不同大小的 LFSR 的值異或相處來解決。這些異或LFSR的新周期將是周期的LCM（最小公倍數）。例如，基元 4 位和基元 6 位 LFSR 的 LCM 是 LCM（15， 63），即 315。以這種方式加入 LFSR 時，請確保僅使用最小位數的 LFSR;使用少于此量是更好的做法。對于 4 位和 6 位 LFSR，不應使用超過底部的 4 位。在圖 2 中，底部的 16 位用于 32 位和 31 位 LFSR。 請注意，對兩個相同大小的 LFSR 進行異或運算不會增加周期。

LFSR的不可預測性可以通過用反饋項對一點“熵”進行異或來增加。這樣做時應該小心——加上熵位，LFSR 到所有零的可能性很小。如果定期添加熵，LFSR 的歸零將自行校正。這種與反饋項進行異或的方法就是CRC（循環(huán)冗余校驗）的計算方式。

多項式不是生而相等的。有些多項式肯定會比其他多項式更好。表 2 列出了可用于最大 31 位大小的基元多項式的數量。嘗試不同的多項式，直到找到滿足您需求的多項式。表3中給出的掩模是隨機選擇的。

可以使用NIST的統(tǒng)計測試套件進行更廣泛的測試。NIST還有幾本出版物描述了隨機數測試和對其他測試軟件的引用。

圖1.LFSR 的簡化繪圖。

圖2.實現 LFSR 的 C 代碼。

圖3.8051匯編代碼，用于實現掩碼為0D295h的16位LFSR。

審核編輯：郭婷