Berlekamp-Massey 梅西迭代算法 C++ 實現：尋找最短線性移位寄存器

算法背景與問題定義

Berlekamp-Massey 算法（梅西迭代算法）用於解決線性移位寄存器（LFSR）綜合問題：給定長度為 N 的二元序列，求出生成該序列的最短線性移位寄存器，即確定其最小階數 L 及對應的特徵多項式 f(x)。這在密碼學序列分析、編碼理論、通信同步等領域有廣泛應用。

核心數據結構

typedef vector<bool> MyArray;       // 狀態數組，存儲輸入序列
vector<int> l;                      // 各階段 LFSR 階數 L_n
MyArray temp;                       // 臨時多項式係數數組
vector<MyArray> f;                  // 多項式係數序列，f[n] 對應第 n 階段多項式

算法流程詳解

1. 初始化：讀取輸入文件 input.txt，第一項為序列長度 N，第二項為二元序列字符串。初始化 l[0]=0，f[0]=[1]（對應多項式 1）。
2. 迭代主循環（n = 0 到 N-1）：
   • 計算差異值 d_n：d_n = Σ (f[n][i] * a[n-i]) mod 2，i=0..l[n]。
   • 若 d_n == 0：序列與當前多項式匹配，直接繼承 f[n+1]=f[n], l[n+1]=l[n]。
   • 若 d_n != 0 且歷史所有 l[k] == 0：構造新多項式 f[n+1] = 1 + x^{n+1}，階數 l[n+1] = n+1。
   • 若 d_n != 0 且存在歷史 l[m] < l[n]：找到最大的 m 滿足條件，更新多項式 f[n+1] = f[n] + x^{n-m} * f[m]（模 2 加法），階數 l[n+1] = max(l[n], n+1-l[n])。
3. 輸出結果：最終 l[N] 為最小階數，f[N] 為最小多項式係數。結果輸出至控制台及 output.txt。

關鍵代碼片段

do {
    int dn = 0;
    for (int i = 0; i <= l[n]; ++i)
        dn += f[n][i] * a[n-i];
    dn %= 2;

    int isum = 0;
    for (int i = 0; i <= n; ++i) isum += l[i];

    if (dn == 0) {
        f.push_back(f[n]);
        l.push_back(l[n]);
    } else if (!isum) {
        temp.clear();
        for(int i=0; i<n+2; ++i) temp.push_back(0);
        temp[0] = 1; temp[n+1] = 1;
        f.push_back(temp);
        l.push_back(n+1);
    } else {
        int m = 0;
        for (int i = n; i >= 0; --i)
            if (l[i] < l[n]) { m = i; break; }
        temp.clear();
        for (int i = 0; i < n-m; ++i) temp.push_back(0);
        temp.insert(temp.end(), f[m].begin(), f[m].end());
        // 模2加法合成新多項式 ft = temp + f[n]
        vector<bool> ft;
        int len = max(temp.size(), f[n].size());
        ft.insert(ft.begin(), len, 0);
        for (int i=0; i<temp.size(); ++i) ft[i] = temp[i];
        for (int i=0; i<f[n].size(); ++i)
            ft[i] = (ft[i] != f[n][i]); // XOR
        f.push_back(ft);
        l.push_back(max(l[n], n+1-l[n]));
    }
    if (n >= N-1) break;
    ++n;
} while(1);

編譯與運行

代碼遵循標準 C++，包含 <iostream>, <vector>, <fstream> 等頭文件。編譯後執行，需同目錄下存在 input.txt，格式為：

10
1011001010

程序將輸出最小 LFSR 階數 ln 及多項式 f(x)（如 f(x)=1+X^2+X^5）。