Berlekamp-Massey 建構最小 LFSR
給定序列 0010001111（或任何其他，不是作業，而是考試練習），你如何使用 Berlekamp-Massey 算法來構造最小 LFSR？
我已經閱讀了幾個關於 Berlekamp-Massey 工作原理的定義，但我錯過了一些實際展示所使用算法的簡單範例。
嘗試使用以下http://en.wikipedia.org/wiki/Berlekamp-Massey#The_algorithm_for_the_binary_field這是我得到多遠（或多短）：
- 讓 $ s_0, s_1, \dots, s_9 $ 是位 0,0,1,0,0,0,1,1,1,1。
- 設長度為 10 的數組 b 和 c 為： b = {1,0,0,0,0,0,0,0,0,0}, c = {1,0,0,0,0 ,0,0,0,0,0}
- 令 L = 0, m = -1
- 迭代 10 次：
迭代 0：
$$ d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9} $$ 在第一次迭代 (0) 中，我遇到了問題。這些負下標變數是什麼？
我正在使用維基百科上的公式，即：
$$ d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L} $$ 這個公式有問題嗎？在第 3 步之前，算法狀態 L = 0，因此最後一項為：
$$ c_Ls_{N-L} $$ 如果按字面意思理解就沒有直覺意義嗎？我假設這個 s 變數的下標應該不斷減少，而對於 c 它應該不斷增加？如果按照公式說明，這些將只是 0？
但無論如何，負 s 變數存在這個問題。
負索引沒有問題，即使是第一次（或第零次，取決於您要如何計算它們）迭代。
數量 $ d $ 稱為差異。在此期間 $ N $ -第一次迭代， $ d $ 是之間的區別 $ s_N $ ， 這 $ N $ -您正在為其查找 LFSR 的給定序列的第 位，以及由您迄今為止合成的 LFSR 計算的位。如果 $ d=0 $ , LFSR 產生的位與給定序列中的位相同，因此目前的LFSR，保證產生 $ s_0, s_1, \ldots, s_{N-1} $ ，不需要改變：它正在生產 $ s_N $ 還。另一方面，如果 $ d \neq 0 $ , 那麼目前的 LFSR 需要更新, 也就是你需要找到最短的 LFSR 產生的不僅僅是 $ s_0, s_1, \ldots, s_{N-1} $ 但也 $ s_N $ . 如何做到這一點是 Berlekamp-Massey 算法的關鍵。請注意，很容易找到將產生 的LFSR $ s_0, s_1, \ldots, s_{N} $ : 訣竅在於找到最短的LFSR。
以此為背景，以及進一步的資訊 $ L $ 是目前LFSR中階段數的上限，考慮差異計算
$$ d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L} $$ 這真的應該表示為 $$ d = c_0s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L} $$ 但更簡單的版本有效，因為 $ c_0 = 1 $ 總是（見初始化）。現在，我們從 $ c_0 = 1 $ 和所有其他 $ c_i = 0 $ ，也就是說，一個平凡的 LFSR，沒有階段會產生 $ 0 $ 如果你要求的話，s 永遠。在第一次計算時 $ L=0 $ 和 $ N=0 $ ， 我們有 $$ d = c_0 s_0 = s_0. $$ 如果您想使用完整的表格 $$ d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9} $$ 沒關係，只要你記得 $ c_1=c_2=\cdots=c_9 = 0 $ ，以及您選擇賦予的值 $ s_{-1}, s_{-2}, \ldots, s_{-9} $ 完全不影響計算。但更實際的是，你應該注意到 $ L=0 $ 和 $ N=0 $ , 所以這個術語 $ c_Ls_{N-L} $ 這對你來說毫無意義只是 $ c_0s_{0-0}=c_0s_0=s_0 $ ，應該是這樣的。 在表格中
$$ d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L} $$ 正確解釋，你永遠不會用完比特，因為 $ c_{L+1}, c_{L+2}, \ldots $ 都保證是 $ 0 $ 和 $ L $ 上限為 $ N $ 所以 $ s_{N-L} $ 可以達到 $ s_0 $ ，給定序列的前導位，但僅此而已。
上沒有負下標 $ s $ （或者 $ c $ ) 我們需要擔心的。