Thuật toán Berlekamp–Massey

Thuật toán Berlekamp–Massey là một thuật toán tìm bộ ghi dịch hồi tiếp tuyến tính (LFSR) ngắn nhất sinh ra một dãy nhị phân cho trước. Thuật toán cũng tìm ra đa thức nhỏ nhất của một quan hệ truy toán tuyến tính trên một trường bất kì.^[1]

Elwyn Berlekamp phát minh ra thuật toán này để giải mã mã Bose–Chaudhuri–Hocquenghem (BCH).^[2]^[3] James Massey phát hiện ra ứng dụng của nó cho bộ ghi dịch hồi tiếp tuyến tính và đơn giản hóa thuật toán.^[4]^[5] Massey gọi thuật toán là Thuật toán Tổng hợp LFSR (Thuật toán Lặp Berlekamp) (Massey 1969, tr. 124), nhưng ngày nay nó được gọi là thuật toán Berlekamp–Massey.

Mô tả thuật toán sửa

Thuật toán Berlekamp–Massey là một phương pháp giải hệ các phương trình tuyến tính mô tả trong thuật toán giải mã Peterson cho mã Reed–Solomon, có thể tóm tắt như sau:

S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.

Dưới đây, C(x) là một trường hợp nhất định của Λ(x). Đa thức định vị lỗi C(x) cho L lỗi được định nghĩa là:

C(x)=C_{L}\ x^{L}+C_{L-1}\ x^{L-1}+\cdots +C_{2}\ x^{2}+C_{1}\ x+1

hay viết ngược lại:

C(x)=1+C_{1}\ x+C_{2}\ x^{2}+\cdots +C_{L-1}\ x^{L-1}+C_{L}\ x^{L}.

Mục tiêu của thuật toán là tìm bậc L nhỏ nhất và đa thức C(x) sao cho:

S_{n}+C_{1}\ S_{n-1}+\cdots +C_{L}\ S_{n-L}=0

với mọi giá trị hội chứng S đã cho, n = L to (N-1).

Thuật toán hoạt động như sau. Khởi tạo C(x) bằng 1, L là giả định số lượng lỗi hiện tại, khởi tạo bằng 0. N là số giá trị hội chứng. n là biến lặp chính và là chỉ số của giá trị hội chứng từ 0 đến (N-1). B(x) lưu giá trị cũ cuối cùng của C(x) mỗi lần L thay đổi, và được khởi tạo bằng 1. b lưu giá trị cũ cuối cùng của độ sai lệch d (giải thích ở dưới) mỗi lần L thay đổi, và được khởi tạo bằng 1. m là số lần lặp từ lần cuối L, B(x), và b thay đổi và được khởi tạo bằng 1.

Trong mỗi lần lặp, thuật toán tính một giá trị sai lệch d. Ở lần lặp thứ k giá trị đó là:

d=S_{k}+C_{1}\ S_{k-1}+\cdots +C_{L}\ S_{k-L}.

Nếu d bằng 0, thuật toán giả sử rằng C(x) và L hiện tại vẫn đúng, tăng m, và tiếp tục.

Nếu d khác 0, thuật toán thay đổi C(x) sao cho khi tính lại thì d bằng 0:

C(x)=C(x)\ -\ (d/b)\ x^{m}\ B(x).

Thừa số x^m dịch B(x) đi m vị trí nên nó nhận giá trị ứng với b. Nếu lần cuối cùng L thay đổi là ở lần lặp thứ j, thì m = k - j, và giá trị sai lệch tính lại sẽ là:

d=S_{k}+C_{1}\ S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}\ S_{j-1}+\cdots ).

Vì vậy, giá trị sai lệch mới là:

d=d-(d/b)b=d-d=0.\

Thuật toán cũng tăng giá trị L (số lỗi) nếu cần. Nếu L đúng bằng số lỗi thì trong quá trình lặp, tất cả các giá trị sai lệch sẽ trở thành 0 trước khi n lớn hơn hoặc bằng (2 L). Nếu giả thiết này không đúng, thuật toán tăng L và cập nhật giá trị B(x), b, tăng L, và khởi tạo lại m = 1. Công thức L = (n + 1 - L) giới hạn giá trị L nhỏ hơn hoặc bằng số giá trị hội chứng đã cho, và cũng giải quyết trường hợp tăng L nhiều hơn 1.

Thuật toán cho trường nhị phân sửa

Dưới đây là thuật toán Berlekamp–Massey cho trường hợp đặc biệt phổ biến là trường hữu hạn F₂ và GF(2). Các phần tử của trường là 0 và 1. Trong trường này, các toán tử + và − là tương đương và trở thành toán tử hoặc loại trừ XOR. Toán tử nhân * trở thành toán tử lôgic AND. Phép chia trở thành toán tử đồng nhất (nghĩa là phép chia chỉ được định nghĩa cho giá trị 1, và x/1 = x).

Đặt $s_{0},s_{1},s_{2}\cdots s_{n-1}$ là các bit dữ liệu vào (các giá trị hội chứng).
Khởi tạo hai mảng $b$ và $c$ độ dài $n$ bằng không, ngoại trừ $b_{0}\leftarrow 1,c_{0}\leftarrow 1$
Gán $L\leftarrow 0,m\leftarrow -1$ .
Lặp $N=0$ với bước tăng 1 chừng nào $N<n$ :
- Đặt $d$ bằng $s_{N}+c_{1}s_{N-1}+c_{2}s_{N-2}+\cdots +c_{L}s_{N-L}$ .
- Nếu $d=0$ , thì $c$ hiện tại đã thỏa mãn mọi điều kiện từ $N-L$ đến $N$ .
- Nếu không:
  - Gán $t$ bằng $c$ .
  - Gán $c_{N-m}\leftarrow c_{N-m}\oplus b_{0},c_{N-m+1}\leftarrow c_{N-m+1}\oplus b_{1},\dots$ cho tới $c_{n-1}\leftarrow c_{n-1}\oplus b_{n-N+m-1}$ (trong đó $\oplus$ là toán tử hoặc loại trừ).
  - Nếu $L\leq {\frac {N}{2}}$ , gán $L\leftarrow N+1-L$ , gán $m\leftarrow N$ , và gán $b\leftarrow t$ ; nếu không, giữ nguyên giá trị của $L$ , $m$ và $b$ .

Sau khi thuật toán thực hiện xong, $L$ là chiều dài của LFSR ngắn nhất sinh ra dữ liệu vào, và ta có $c_{L}s_{a}+c_{L-1}s_{a+1}+c_{L-2}s_{a+2}+\cdots =0$ với mọi $a$ .

Mã Java cho trường hợp trường nhị phân sửa

Mã ví dụ dưới đây là cho trường hợp trường nhị phân.

    public static int runTest(int[] array) {
        final int N = array.length;
        int[] b = new int[N];
        int[] c = new int[N];
        int[] t = new int[N];
        b[0] = 1;
        c[0] = 1;
        int l = 0;
        int m = -1;
        for (int n = 0; n < N; n++) {
            int d = 0;
            for (int i = 0; i <= l; i++) {
                d ^= c[i] * array[n - i];
            }
            if (d == 1) {
                System.arraycopy(c, 0, t, 0, N);
                int N_M = n − m;
                for (int j = 0; j < N − N_M; j++) {
                    c[N_M + j] ^= b[j];
                }
                if (l <= n / 2) {
                    l = n + 1 - l;
                    m = n;
                    System.arraycopy(t, 0, b, 0, N);
                }
            }
        }
        return l;
    }

Thuật toán Berlekamp–Massey cho trường bất kì sửa

Thuật toán dưới đây là từ Massey (1969, tr. 124).

  polynomial(field K) s(x) =... /* Các hệ số s_j; Dãy kết quả của LFSR (các giá trị hội chứng) dưới dạng đa thức bậc N-1 */
  /* đa thức lời giải */
  polynomial(field K) C(x) = 1;  /* Các hệ số c_j */
  polynomial(field K) B(x) = 1;
  int L = 0;
  int m = 1;
  field K b = 1;
  int n;
  for (n = 0; n < N; n++)
    {
      /* Tính giá trị sai lệch */
      field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};
      if (d == 0)
        {
          /* Giá trị c hiện tại vẫn đúng */
          m = m + 1;
        }
      else if (2 * L <= n)
        {
          /* Bản sao của C(x) */
          polynomial(field K) T(x) = C(x);
          C(x) = C(x) - d b^{-1} x^m B(x);
          L = n + 1 - L;
          B(x) = T(x);
          b = d;
          m = 1;
        }
      else
        {
          C(x) = C(x) - d b^{-1} x^m B(x);
          m = m + 1;
        }
    }
  return L;

Xem thêm sửa

Thuật toán Reeds–Sloane, mở rộng ra dãy các số nguyên mod n
Thuật toán Berlekamp–Welch
NLFSR, bộ ghi dịch hồi tiếp phi tuyến

Tham khảo sửa

Reeds, J. A.; Sloane, N. J. A. (1985), “Shift-Register Synthesis (Modulo n)” (PDF), SIAM Journal on Computing, 14 (3): 505–513, doi:10.1137/0214038, Bản gốc (PDF) lưu trữ ngày 29 tháng 8 năm 2012, truy cập ngày 15 tháng 4 năm 2012

^ Thuật toán Berlekamp–Massey đòi hỏi tất cả các phần tử khác không đều có nghịch đảo nhân. (Reeds & Sloane 1985, tr. 2) Reeds và Sloane mở rộng thuật toán này để giải quyết được cả trường hợp vành.
^ Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy
^ Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory, Laguna Hills, CA: Aegean Park Press, ISBN 0894120638 Đã bỏ qua tham số không rõ |ed= (trợ giúp). Nhà xuất bản cũ McGraw-Hill, New York, NY.
^ Massey, J. L. (1969), “Shift-register synthesis and BCH decoding” (PDF), IEEE Trans. Information Theory, IT-15 (1): 122–127
^ Ben Atti, Nadia; Diaz-Toca, Gema M.; Lombardi, Henri, The Berlekamp–Massey Algorithm revisited

Liên kết ngoài sửa

Thuật toán Berlekamp–Massey Lưu trữ 2012-07-16 tại Wayback Machine ở PlanetMath.(tiếng Anh)
Weisstein, Eric W., "Berlekamp–Massey Algorithm" từ MathWorld.(tiếng Anh)
Thư viện lập trình cho trường hợp GF(2) trong Mathematica.
Applet mô tả thuật toán Berlekamp–Massey.(tiếng Đức)
Máy tính trực tuyến Berlekamp-Massey cho GF(2) Lưu trữ 2012-03-09 tại Wayback Machine.(tiếng Anh)

[1] Thuật toán Berlekamp–Massey đòi hỏi tất cả các phần tử khác không đều có nghịch đảo nhân. (Reeds & Sloane 1985, tr. 2) Reeds và Sloane mở rộng thuật toán này để giải quyết được cả trường hợp vành.

[2] Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy

[3] Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory, Laguna Hills, CA: Aegean Park Press, ISBN 0894120638 Đã bỏ qua tham số không rõ |ed= (trợ giúp). Nhà xuất bản cũ McGraw-Hill, New York, NY.

[4] Massey, J. L. (1969), “Shift-register synthesis and BCH decoding” (PDF), IEEE Trans. Information Theory, IT-15 (1): 122–127

[5] Ben Atti, Nadia; Diaz-Toca, Gema M.; Lombardi, Henri, The Berlekamp–Massey Algorithm revisited

[1]

[2]

[3]

[4]

[5]