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

介紹

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

LFSR和多項(xiàng)式

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

每個(gè)基元多項(xiàng)式都有奇數(shù)項(xiàng)，這意味著基元多項(xiàng)式的每個(gè)掩碼都有一個(gè)偶數(shù) 1 位。每個(gè)原始多項(xiàng)式還定義了第二個(gè)原始多項(xiàng)式，即它的對(duì)偶。可以通過從每項(xiàng)的多項(xiàng)式次數(shù)中減去指數(shù)來找到對(duì)偶。例如，給定 6千-次多項(xiàng)式，x6+ x + 1，它的對(duì)偶是 x6-6+ x6-1+ x6-0，等于 x6+ x5+ 1.在表 1 中，多項(xiàng)式 1 和 2、3 和 4、5 和 6 是彼此的對(duì)偶。

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

LFSR的結(jié)構(gòu)

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

使用 LFSR 生成偽隨機(jī)數(shù)

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

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

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

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

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

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

圖1.LFSR 的簡化繪圖。

圖2.實(shí)現(xiàn) LFSR 的 C 代碼。

圖3.8051匯編代碼，用于實(shí)現(xiàn)掩碼為0D295h的16位LFSR。

審核編輯：郭婷