Các phép truy hồi tuyến tính hai chiều phức tạp hơn một chút về mặt đại số.
Khái niệm tương ứng với độ phức tạp tuyến tính theo một nghĩa nào đó sẽ là mức độ $(n,m)$ của đa thức sinh bậc nhỏ nhất có dạng
$$
x^{n}y^m- \sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} x^i y^j
$$
tương ứng với sự lặp lại tuyến tính 2D
$$
s_{t+n,t'+m}=\sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} s_{t+i, t'+j}
$$
ở đâu $t,t'$ là các chỉ số trong hai chiều.
Sakata đã tổng quát hóa thuật toán Berlekamp Massey (BMA) thành 2, rồi thành N chiều; Nhìn thấy đây (hình như được công bố rộng rãi). Từ bản tóm tắt:
Chúng tôi trình bày một thuật toán để tìm một tập hợp tối thiểu các quan hệ tuần hoàn tuyến tính hai chiều có khả năng tạo ra một mảng hai chiều hữu hạn được chỉ định. Đây là phần mở rộng hai chiều của thuật toán Berlekamp-Massey để tổng hợp thanh ghi dịch chuyển phản hồi tuyến tính ngắn nhất có khả năng tạo ra một chuỗi hữu hạn nhất định. Độ phức tạp của tính toán cho một mảng kích thước $n$ Là $O(n^2)$ theo một số giả định hợp lý. Hơn nữa, chúng tôi làm rõ một số mối quan hệ giữa thuật toán của chúng tôi và cơ sở Gröbner của các lý tưởng đa thức hai biến, trong đó các đa thức tương ứng một đối một với quan hệ tuần hoàn tuyến tính.
Lý do chúng phức tạp là (lên đến một số vẫy tay) cho một trường hữu hạn $\mathbb{F}$ vành đa thức một biến $\mathbb{F}[x]$ tất cả các lý tưởng là chính (có một trình tạo đa thức duy nhất). Vì vậy, để BMA hoạt động, chỉ cần tìm một máy phát có mức độ tối thiểu là đủ. Trong nhiều biến, không phải tất cả các iđêan của $\mathbb{F}[x_1,\ldots,x_n]$ là hiệu trưởng.
Định nghĩa của hai bậc biến đổi và thứ tự bậc của các thuật ngữ là một vấn đề khác, nhưng điều đó có thể được thực hiện thông qua thứ tự từ điển chẳng hạn.
