[發(fā)明專利]非線性反饋移位寄存器

在審

• 申請?zhí)枺?/td>: 202080059362.1
• 申請日: 2020-08-13
• 公開（公告）號: CN114270774A
• 公開（公告）日: 2022-04-01
• 發(fā)明（設計）人: A·約翰遜
• 申請（專利權）人: 國際商業(yè)機器公司
• 主分類號: H04L9/26
• 分類號: H04L9/26;H04L9/06;G06F7/58
• 代理公司: 中國貿(mào)促會專利商標事務所有限公司 11038
• 代理人: 劉倜

本發(fā)明提供一種使用非線性反饋移位寄存器(NLFSR)生成n級至少接近最大長度的偽隨機序列的方法和系統(tǒng)，其中最大長度為2ⁿ?1。該方法可以包括：在最大長度線性反饋移位寄存器中選擇n個抽頭，其中n需要兩個以上抽頭；以及針對所選擇的n級寄存器，使用僅第一邏輯門和第二邏輯門的反饋邏輯運算生成偽隨機序列。兩個合適的非端抽頭是用于第一邏輯門的輸入，第一邏輯門的輸出和端抽頭是用于第二邏輯門的輸入，并且第二邏輯門的輸出用作對n級寄存器的第一級的反饋。

背景技術

本發(fā)明涉及反饋移位(shift)寄存器，更具體地，涉及具有最大或接近最大長度序列的非線性反饋移位寄存器。

在數(shù)字電子電路領域中，線性反饋移位寄存器(LFSR)是用于生成2ⁿ-1個偽隨機比特序列的裝置。LFSR具有包括密碼術的許多應用，例如其中它們被用于密鑰流生成器、數(shù)據(jù)壓縮、錯誤檢測和校正等。

LFSR是移位寄存器，其輸入位是其先前狀態(tài)的線性函數(shù)。最常用的單個位的線性函數(shù)是異或(XOR)，并且移位寄存器具有由整個移位寄存器值的一些位的XOR驅動的輸入位。LFSR的硬件和軟件實現(xiàn)方式都是常見的。

影響下一狀態(tài)的比特位置稱為抽頭(taps)。LFSR的最右位稱為輸出位。在Fibonacci LFSR中，抽頭與輸出比特順序異或，然后反饋到最左邊的比特中。最右邊位置中的比特序列被稱為輸出流。最大長度LFSR產(chǎn)生n序列，因為它循環(huán)通過移位寄存器內(nèi)所有可能的2ⁿ-1個狀態(tài)，除了所有位為零的狀態(tài)之外。還有可能使用XNOR，從而產(chǎn)生等效多項式計數(shù)器。

在LFSR中用于反饋的抽頭的布置可以在有限域算術中表示為多項式模2，其中，多項式的系數(shù)必須是1或0，稱為反饋多項式。

具有最大時段的LFSR可以使用二進制字段上的原語生成器多項式來構造。如果對應的反饋多項式是原語(其中抽頭的數(shù)量是偶數(shù)，并且抽頭的集合是集合互質(setwiseco-prime))，則LFSR是最大長度。

下面是顯示用于n高達24位的反饋多項式的表，可從該反饋多項式構造最大長度的LFSR。對于給定的LFSR長度，可以有一個以上的最大長度抽頭序列。

多項式中的“+1”不對應于抽頭；它對應于第一位的輸入。項的冪(powers)與從左側計數(shù)的抽頭位相關。具有四個項加一的LFSR需要四個抽頭并且因此需要三個XOR門。

現(xiàn)在參考圖1，示出了示例8級LFSR 100。寄存器的8位101-108被示為從1-8編號，其中第8位是最右輸出位108。在所示實施例中，根據(jù)多項式x⁸+x⁶+x⁵+x⁴+1，示出的8位寄存器具有從4、5、6和8位的抽頭。每個抽頭使用XOR門111、112、113提供線性反饋。反饋120被輸入到第一比特101。

調適為頂部-底部混合LFSR產(chǎn)生器，其中頂部LFSR分接頭與最后分接頭異或，且將結果饋送到頂部分接頭之后的級中。底部抽頭與最后抽頭異或，并且結果被饋送到移位寄存器的第一級。頂部-底部混合LFSR發(fā)生器可以用于將4個抽頭減少到3個抽頭(兩個XOR)，如下：

{8，7，-6}

{12，9，-4}

{13，12，-11}

{14，13，-11}

{16，14，-7}

{19，18，-11}

{24，23，-19}

其中，第一數(shù)量是級的數(shù)量，第二數(shù)量是頂部LFSR抽頭，并且第三數(shù)量(指示為負數(shù))是底部LFSR抽頭。