將 m-Sequence 轉換為 de Bruijn 序列
在他的論文Alternating Step Generator Controlled by de Bruijn Sequence中，CG Günther 在第三頁指出
de Bruijn 序列 (..) 可以很容易地從 m 序列（最大長度 LFSR 序列）中獲得
不幸的是，他在論文中沒有給出這樣做的方法，而我在自己的研究中也找不到這樣的方法。誰能告訴我 Günther 先生的想法？是否有將 m 序列轉換為 de Bruijn 序列的簡單電路？
A de Bruijn 序列，如 NG de Bruijn 的A 組合問題，Proc 中所定義。K.內德。阿卡德。濕，卷。49, pp 758-764, 1946（歸屬於 Ir. K. Posthumus）是
的有序循環 $ 2^n $ 數字 0 或 1，這樣 $ 2^n $ 可能的有序集 $ n $ 該循環的連續數字都是不同的。
給出的例子 $ n=3 $ 是序列
00010111, 產生集合000,001,010,101,011,111,110,100.鑑於此，一個de Bruijn長度序列 $ 2^n $ 從任何長度的 m 序列中獲得 $ 2^n-1 $ （也就是說，LFSR 的循環輸出具有度的原始多項式 $ n $ 從非零狀態開始）通過
0在單個子序列中插入一個 $ n-1 $ 連續0.每條評論更新：我們可以實現一個輸出de Bruijn長度序列的電路 $ 2^n $ 使用 $ n $ D 型觸發器連接為最大長度斐波那契 LFSR $ n $ 階段，通過添加一個額外的 XOR 項等於輸出的 NOR $ n-1 $ 回饋端的觸發器。在下圖中（輸出上面的範例序列），添加的門是 NOR1 和 XOR2。
注0：當階段數 $ n $ 變大，與非門 $ n-1 $ 輸入變得煩人；可以用這個換一個 $ \lceil\log_2(n)\rceil $ - 帶復位的位計數器，計算輸出中連續零的數量，給出一個 $ 1 $ 到達時 $ n-1 $ 連續的零，並輸出額外的異或項。
注 1：本文中使用de Bruijn生成器僅用於 ASG 的控制生成器，決定其他兩個中的哪一個被計時。對於其他兩個生成器中的任何一個也使用de Bruijn生成器是有問題的：請注意，如果控制生成器具有 $ c $ 位，從屬發生器 $ x $ 位，並且都是de Bruijn，從機輸出的總週期是 $ 2^{\max(c,x+1)} $ ， 而不是 $ 2^c\cdot(2^x-1) $ 當slave是一個最大長度的LFSR時。
注 2：如果控制生成器是最大長度的 LFSR 而不是de Bruijn生成器，我不明白為什麼 ASG 的安全性會被削弱，並且兩個從站都具有最大長度的 LFSR，前提是 $ \gcd(2^{c-1}-1,2^x-1) $ 很小[以及 $ \gcd(2^x-1,2^y-1) $ ]， 在哪裡 $ c $ （分別。 $ x $ , $ y $ ) 是控制發生器的位數（分別是控制發生器輸出時計時的從發生器 $ 0 $ ，另一個從發電機）。原始論文暗示另一篇論文（送出給 IEEE Transactions on Information Theory，但我找不到它）涵蓋了最大長度 LFSR 作為控制生成器的情況。這篇關於 ASG 的文章及其一些參考資料似乎也是這種情況。
後期添加：這在軟體中也很容易。認為 $ x^\mathtt n+x^\mathtt k+1 $ 是一個原始的三項式 $ GF(2) $ （合適的常數 $ \mathtt n $ 和 $ \mathtt k $ 可以從Jörg Arndt’s Complete list of original trinomials over GF(2) up to degree 400 獲得）。如果
x至少是一個無符號整數變數 $ \mathtt n $ 位寬，則 C 表達式
x = ((((x>>k)^x)&1)<<(n-1))|(x>>1);很容易實現帶句點的 LFSR $ 2^\mathtt n-1 $ （當從任何正數
x小於 $ 2^\mathtt n $ ）。我們可以將
x = ((((x>>k)^x^!(x>>1))&1)<<(n-1))|(x>>1);其更改為實現帶有句點的 NLFSR $ 2^\mathtt n $ （當從任何非負
x小於 $ 2^\mathtt n $ ).
