LFSR 用於大周期的小數
我想使用 LFSR 生成一些隨機數。但是，LFSR 輸出取決於抽頭的數量，因此在很長一段時間內，我使用大量（相對）位數。這導致數字與週期一樣大。例如，我想使用 16 位 LFSR 來生成隨機的 5 位數字。什麼是減少位數但仍確保單個數字不會重複並且序列不會變短的正確方法？
$$ Edit: $$ 對於 5 級，我使用多項式 x^5+x^3+1 和以下程式碼：
lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0x0014u);對於 n = 16，我使用多項式 x^16 + x^14 + x^13 + x^11 + 1
lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xB400u);這些有問題嗎？
提取任何 $ m\le n $ 從一個狀態位 $ n $ -bit LFSR 仍然會導致一個序列 $ m $ - 帶句點的位字 $ 2^n-1 $ , 假設狀態 $ n $ -bit LFSR 不為零，它生成的多項式是原始的。證明草圖：由具有原始回饋多項式的LFSR的一個基本性質，它的周期有 $ 2^n-1 $ 不包括全零狀態的狀態。因此，任何位都有周期 $ 2^n-1 $ 和 $ 2^{n-1} $ 一個和 $ 2^{n-1}-1 $ 零。
此外，該序列與 $ m $ - 週期的位序列 $ 2^n-1 $ 可以是：每個 $ 2^m $ 達到值 $ 2^{n-m} $ 次，除了 $ 0 $ 達到 $ 2^{n-m}-1 $ 次。事實上，這太均勻分佈了，不可能是隨機的。
因此，取（比如說）最大長度的 16 位 LFSR 的低 5 位將產生一個週期為 65535 的序列，在此期間，32 個值中的每一個都將達到 2048 次，除了 0 達到 2047 次。然而，這甚至不會產生一個可以通過的非加密 RNG：如果 LFSR 使用 Fibonacci 構造，則任何輸出的 4 位直接來自先前的輸出，並且使用 Galois 構造的情況幾乎沒有好轉（或根本沒有，取決於多項式）。例如，在更新的問題中使用 16 位生成器（根據我喜歡的約定，使用多項式 $ x^{16}+x^5+x^3+x^2+1 $ 而不是它的反射 $ x^{16}+x^{14}+x^{13}+x^{11}+1 $ )
#include <stdio.h> int main(void){ unsigned x = 1, j = 128, y; // initial sate, number of outputs, output do { y = x&31; printf("%02X%c", y, --j&15?' ':'\n'); x = x>>1 ^ 0xB400&-(x&1); } while(j); return 0;}我們得到這個：
01 00 00 00 00 00 00 10 08 14 1A 0D 16 0B 05 02 01 00 10 08 04 02 11 08 14 0A 05 02 11 18 0C 16 1B 1D 1E 0F 17 1B 0D 16 0B 15 1A 0D 16 0B 05 02 11 08 04 12 19 1C 1E 0F 17 0B 05 12 19 1C 0E 17 1B 1D 0E 07 03 01 10 18 1C 0E 17 1B 1D 1E 0F 07 13 09 14 0A 05 12 19 1C 0E 07 13 19 1C 1E 1F 1F 1F 1F 1F 0F 07 13 09 14 1A 1D 0E 07 03 01 10 18 1C 1E 1F 0F 07 13 09 04 12 09 14 0A 15 1A 1D 1E很明顯，任何輸出的右十六進制數字始終是前一個輸出右移 1。
一種可能的解決方案是逐步執行 LFSR $ m $ 每個輸出的時間 $ m $ 位，每一步收集 1 位。一個問題是，當 $ \gcd(m,2^n-1)\ne 1 $ 該時間段因該因素而減少（並且均勻分佈的證明不再有效）。
相反，我以前建議輸出
y = ((0x6D9B*x+0xDB75)&0xFFFF)>>11. 它確實改善了一些事情，但y = x&31仍然存在一些問題：兩個連續輸出的分佈很差。類似的東西y = 0x6D9B*x, y = (y<<4 ^ y)*0xDB75, y = (y<<2 ^ y)>>11 & 31進一步改進了事情，同時可證明保持週期和均勻分佈（因為直到>>11 & 31步驟，從低 16 位x到低 16 位的轉換y是一個映射）。注意：即使通過使用更複雜的輸出轉換來完善這一點，無論如何，生成的序列在密碼學上並不強，並且如果沒有更多的狀態位就無法做到這一點。
我將在@fgrieu 的回答中添加一些值得考慮的要點。
週期的輸出序列 $ 2^n-1 $ 從一個 $ n $ -bit 最大長度 LFSR 的特性是它包含以（接近）正確比例的零和一的*執行。*特別是，有一個執行 $ n $ 連續的（沒有執行 $ n $ 連續的零，但有一個執行 $ n-1 $ 連續的零。所以，考慮一下如果你正在使用會發生什麼 $ m $ 從 LFSR 內容中提取的連續位。由於連續的一（或零）的長序列正在通過這些 $ m $ 職位，你的 $ m $ -bit 隨機數生成器會卡在 $ 111\cdots 1 $ （或者 $ 000\cdots 0 $ ) 狀態為 $ n-m $
連續的時鐘週期（ $ n-m-1 $ 連續的時鐘週期） 。LFSR 輸出還包含較短的執行 $ k $ 位，並且對於 $ k > m $ ，這些較短的執行也會導致 $ m $ -bit 隨機數生成器停留在相同的狀態 $ k-m $ 連續的時鐘週期。所以，雖然你在全球範圍內 $ m $ -bit 隨機數生成器將具有良好的分佈，每個 $ 2^m-1 $ 出現的非零隨機數 $ 2^{n-m} $ 次和 $ 000\cdots 0 $ 發生 $ 2^{n-m}-1 $ 有時，當地人的行為根本不好，與 $ 000\cdots 00 $ 和 $ 111\cdots 1 $ 連續發生好幾次，不只是一次，而是在許多不同的地方發生 $ 2^n - 1 $ .
參考：
A. Lempel 和 H. Greenberger，“具有最佳漢明相關特性的序列族”，IEEE Trans。通知。理論，卷。IT-20，1974 年 1 月。
DV Sarwate 和 MB Pursley，“跳頻多址通信的跳頻模式”，IEEE 國際通信會議：會議記錄，卷。1，1978 年。
DV Sarwate，“Reed-Solomon 碼和擴頻多址通信的序列設計”，Reed-Solomon 碼及其應用，（SB Wicker 和 VK Bhargava，編輯），IEEE 出版社，1994 年。