Rueppel 的自計時 LFSR 範例

考慮以下 Rueppels 論文的摘錄，標題為When Shift Registers Clock Themself ：

他的例子包括 $ C(D) = 1 + D + D^2 + D^3 + D^4 + D^5 $ 作為原始連接多項式。然而，這個多項式不是不可約的，更不用說原始的了，因為它可以被分解為 $ (1+D)(1+D+D^2)^2 $ 超過 $ \text{GF}(2) $ .

我錯過了什麼？

文章中有錯別字。原始多項式必須是$$ x^5 + x^4 + x^3 + x^2 + 1 $$

---

查看是否存在錯誤的最簡單方法是編碼！

有一個幾乎不錯的pylfsr庫。該庫還以它們的格式列出了原始多項式。

L.get_fpolyList(m=5)

• $$ 5, 2 $$
• $$ 5, 4, 2, 1 $$
• $$ 5, 4, 3, 2 $$

該列表也已驗證。

• $ x^5 + x^2 + 1 $
• $ x^5 + x^4 + x^2 + x^1 + 1 $
• $ x^5 + x^4 + x^3 + x^2 + 1 $

我創建了一個 python 程序來測試這些。幸運的是，我在第一次嘗試時就找到了它！

import numpy as np
from pylfsr import LFSR

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
   print(L.state[-1], end=",")
   if L.outbit == 0:
       L.next()
   else :
       L.next()
       L.next()
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1")  

它產生輸出

5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
State        :  [1 1 1 1 1]
Count        :  0
Output bit   :  -1
feedback bit :  -1
1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,

1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

感謝Nikesh Bajaj指出更好地使用該庫（參見其他庫）。

所以文章有錯別字。原始多項式必須是$$ x^5 + x^4 + x^3 + x^2 + 1 $$

回答為什麼-1？[更新：修復 pylfsr ]

LFSR 的輸出確實是初始狀態的最後一位，但如果沒有執行時鐘週期（L.next()），則沒有輸出位。-1 被有意地用來表明 LSFR 沒有經過任何時鐘。

列印行應該在結尾而不是開始。

import numpy as np
from pylfsr import LFSR

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
   if L.outbit == 0:
       L.next()
   else :
       L.next()
       L.next()
   print(L.outbit, end=",")
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1") 

輸出：

5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
State        :  [1 1 1 1 1]
Count        :  0
Output bit   :  -1
feedback bit :  -1
1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,

1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

由於時鐘考慮，這是輸出序列的移位版本。產生準確響應的替代程式碼在這裡

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
   print(L.state[-1], end=",")
   if L.outbit == 0:
       L.next()
   else :
       L.next()
       L.next()
   #
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1") 

產生：

5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
State        :  [1 1 1 1 1]
Count        :  0
Output bit   :  -1
feedback bit :  -1
1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,

1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

更新

感謝@kelalaka 指出。我已經在更新 version=1.0.5 的pylfsr中解決了這個問題，並帶有一個附加參數counter_start_zero，它用 -1 初始化輸出位，直到第一個時鐘通過。因此，您的原始程式碼通過在檢查第一個輸出之前設置counter_start_zero=False或執行 L.next() 來產生預期的答案。看這裡詳細

所以是的，文章中有一個錯字，x^5+x^4+x^3+x^2+1 是正確的原始多項式，也可以通過三個屬性（1）平衡（2）執行長度（ 3) 自相關

引用自：https://crypto.stackexchange.com/questions/51865