在每對連續項之間插入固定長度的零的修改 LFSR 序列的線性複雜度是多少
有一個已刪除的問題問；
我們知道，如果 $ n $ 在 LFSR 中序列的每對連續項之間插入零（變數已更改 $ x $ 至 $ x^n $ ) 那麼線性複雜度（產生給定序列的最短 LFSR）將是 $ n $ 倍於原來的。
我的問題是：在新序列中，週期是多少（假設原始序列的周期是 $ p $ )
這個時期很容易回答；
讓 $ m $ 是一個序列輸出 $ L $ 位最大LFSR。那麼我們知道序列的周期 $ m $ 是 $ 2^L-1 $
讓 $ m’ $ 是修改後的序列 $ m $ 使得對於每兩個連續的元素 $ n $ 插入零。一個例子 $ n=3 $
m = 1 1 0 1 1 0 1 m' = 1000100000001000100000001000很明顯，這段時間 $ m’ $ 是 $ (2^L-1)\cdot n $ . 可以用反駁來證明這一點；如果週期較小，則刪除添加的零以找到較小的周期 $ m $ .
那麼線性複雜度呢？
我看不到這個的一般規則。我的例子已經是倍數的反例；使用~~SageMath 程式碼~~線上執行；
[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1 [1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0] has x^8 + x^4 + 1並且對於 $ n=1 $ 案子;
[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1 [1,0,1,0,0,0,1,0,1,0,0,0,1,0] has x^4 + x^2 + 1 [1,1,0,1,1,1,1,1] has x^4 + x^3 [1,0,1,0,0,0,1,0,1,0,1,0,1,0] has x^7 + x^5線上性複雜度的範圍內是否有工作或結果 $ m’ $ 相關 $ L $ 和 $ n $ ?
沒有本質上不是組合的一般下限/上限。
如果你有一個序列 $ S=(s_0,s_1,\ldots,s_{N-1}) $ 有期限 $ N $ 在有限域上 $ \mathbb{F}_q $ 線性複雜度有兩種相關的形式化 $ L(S) $ 的序列。第一個是經典
$$ L(S)=N-\deg(\gcd(S^N(x),x^N-1)),\tag{1} $$
在哪裡 $ S^N(x)=s_0+s_1x+\cdots+s_{N-1} x^{N-1}. $
現在，對於 $ q=2, $ 這是我們感興趣的， $ x^N-1 $ 有一個規範的因式分解為 $$ x^N-1=\prod_{t=1}^h f_t(x)\quad with\quad f_t(x)=\prod_{j \in C_t} (x-\alpha^j) $$ 在哪裡 $ \alpha $ 是秩序的一個要素 $ N $ 在 $ \mathbb{F}_{q’} $ 它被定義為包含該順序元素的最小擴展欄位。那麼 (1) 中的 gcd 的度可以寫成以分圓陪集為模的基數之和 $ N. $
如果你插入 $ k-1 $ 每個符號之間的零，對於 $ k\geq 2, $ 獲得一個新的序列 $ S’ $ 期間 $ kN, $ 很容易看出新的線性複雜度是 $$ L(S’)=kN-\deg(\gcd(S^N(x^k),x^{kN}-1))\tag{1} $$
可以使用有限域值（非複值）DFT 進行相關表徵。首先，您需要在有限域中有足夠的點 $ GF(q’) $ 您將在其上定義 DFT 以使其一對一，因此 $ q’\geq N $ 是需要的。對於導致 DFT 的算術運算有意義， $ \mathbb{F}q $ 必須是 $ \mathbb{F}{q’}. $
如果你能找到 $ \mathbb{F}_{q’} $ 這樣 $ \gcd(q’,N)=1, $ 您可以定義序列的 DFT 向量 $ S $ 作為
$$ A=[a_0,\ldots,a_{N-1}] $$ 在哪裡 $$ a_j=\sum_{i=0}^{N-1} s_j \alpha^{ij},\quad j=0,\ldots,N-1 $$ 所有算術都在 $ \mathbb{F}_{q’}. $
編碼理論文獻中稱為Blahut 定理的關係指出，線性複雜度 $ L(S) $ 等於漢明權重（超過 $ \mathbb{F}_{q’} $ ) 的 DFT 向量 $ A. $
注意：此答案的一些代數細節可以在例如 Lidl 和 Niederreiter 的有限域簡介一書中找到。