Không rõ chính xác "mã thời gian nhất định" là gì, nhưng tôi sẽ hiểu nó có nghĩa là một chuỗi có độ dài hữu hạn $s_0, s_1, \ldots, s_{N-1}$ của $N$ chút ít. Bản thân chuỗi có thể được tạo ra hoặc không bởi một LFSR -- chúng tôi không biết -- nhưng chúng tôi muốn tìm một LFSR (Fibonacci) tạo ra chuỗi.
Hãy thiết lập sân khấu một chút. Một Fibonacci LFSR có độ dài $n$
là một mảng của $n$ bit có giá trị ban đầu
$$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ và các giá trị liên tiếp
$$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\
\downarrow\
(s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\
\downarrow\
(s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\
\downarrow\
\cdots \quad \cdots$$
trong đó nội dung mảng dịch chuyển sang trái ở mỗi bước (chu kỳ đồng hồ)
để các bit rơi xuống
ngoài cùng bên trái (LFSR đầu ra) là chuỗi đã cho, trong khi
các bit được hiển thị dưới dạng vào LFSR bên phải
là đang được tính toán như một kết hợp tuyến tính (còn gọi là tổng độc quyền-HOẶC) của một số của LFSR
nội dung ở bước trước. Đặc biệt, đối với $i \geq 0$,
các chuyển đổi trạng thái có thể được thể hiện như
$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\
\downarrow\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad {\Large{\oplus}}_{j=0}^ {n-1}c_{n-j} s_{i+j}\biggr),$$
ở đâu $c_i$có giá trị $0$ hoặc $1$, sao cho tuyến tính sự phối hợp
$c_ns_i\oplus c_{n-1}s_{i+1} \oplus \cdots \oplus c_1s_{i+n-1}$ của trước
Nội dung LFSR đang được cho ăn trở lại vào đầu bên phải của LFSR
như $s_{n+i}$ thực sự là tổng Exclusive-OR của một vài bit đã chọn của nội dung trước đó (những nội dung tương ứng $c_i$ có giá trị $1$).
Do đó, thanh ghi dịch chuyển phản hồi tuyến tính tên được khởi tạo thành LFSR.
Với mô tả ở trên, một câu trả lời cho câu hỏi về LFSR là tầm thường theo một nghĩa nào đó: một $N$ giai đoạn LFSR với hệ số phản hồi $(c_N,c_{N-1}, \cdots, c_1) = (1,0,0,\cdots, 0)$ và tải ban đầu $\big(s_0, s_1, \ldots, s_{N-1}\big)$ sẽ tạo ra sự lặp lại vô tận
$$s_0, s_1, \ldots, s_{N-1},s_0, s_1, \ldots, s_{N-1}, s_0, s_1, \ldots, s_{N-1}, \cdots$$
của mã thời gian nhất định
$s_0, s_1, \ldots, s_{N-1}$ cho sự vĩnh hằng. Ngoài ra, không tí nào sự lựa chọn khác của $(c_N,c_{N-1}, \cdots, c_1)$ sẽ lấp đầy thanh ghi ca bằng thứ khác, nhưng thứ đầu tiên $N$ bit ra vẫn sẽ được $s_0, s_1, \ldots, s_{N-1}$ và những gì tiếp theo sau đó sẽ khác. Đây rõ ràng không phải là điều chúng tôi muốn, và vì vậy chúng tôi tìm kiếm một tiêu chí tốt hơn: tìm ngắn nhất LFSR (và tải ban đầu của nó) sẽ tạo ra $s_0, s_1, \ldots, s_{N-1}$, và đó chính xác là những gì thuật toán Berlekamp-Massey tìm thấy.
Thuật toán Berlekamp-Massey là một quá trình lặp đi lặp lại bao gồm việc tìm LFSR ngắn nhất tạo ra LFSR đầu tiên $t$ chút ít
$s_0, s_1, \ldots s_{t-1}$ và kiểm tra xem LFSR
tìm thấy $s_t$ một cách chính xác. Nếu vậy, $s_{t+1}$ được kiểm tra,
trong khi nếu không, $c_i$được cập nhật để
LFSR sửa đổi tạo ra $s_t$. Thông thường, nhưng không phải luôn luôn, độ dài của LFSR tăng lên. Quá trình lặp lại tiếp tục cho đến bit khả dụng cuối cùng $s_{N-1}$ đã được xử lý, do đó khi thuật toán Berlekamp-Massey kết thúc, LFSR được tổng hợp sẽ tạo ra toàn bộ chuỗi $s_0, s_1, \ldots, s_{N-1}$ ở đầu ra của nó. Nếu LFSR tổng hợp có $n\leq N$ các giai đoạn, sau đó tải ban đầu của nó là
$\big(s_0, s_1, \ldots, s_{n-1}\big)$ (cái nào đầu tiên $n$ bit đầu ra) và LFSR tính toán chính xác $s_n, s_{n+1}, \cdots, s_{N-1}$ (tức là phần còn lại của dãy đã cho). Độ dài của LFSR được tổng hợp bởi thuật toán Berlekamp-Massey được đảm bảo là tối thiểu: không LFSR tạo ra $s_0, s_1, \ldots, s_{N-1}$ có thể có ngắn hơn chiều dài. Tuy nhiên, có không tuyên bố rằng $n$ đảm bảo nhỏ hơn $N$; rất có thể các giải pháp tầm thường được mô tả ở trên là các giải pháp tối thiểu. Thật vậy, tôi lập luận rằng đây thực sự là trường hợp cho phần lớn trình tự; LFSR có chiều dài $N$. Lý thuyết phức tạp Kolmogorov nói rằng chương trình ngắn nhất để in ra hầu hết các chuỗi có độ dài $N$ có chiều dài $N+c$, hay nói một cách thông tục, đối với hầu hết các chuỗi, người ta có thể làm tốt hơn một chút so với việc chỉ lưu trữ chuỗi và in ra; các "$c$" chỉ là độ dài của lệnh "In chuỗi sau". Trong ngữ cảnh của các thanh ghi dịch chuyển, đối với hầu hết các chuỗi độ dài $N$, thanh ghi dịch chuyển ngắn nhất có đầu ra là một chuỗi độ dài nhất định $N$ chỉ là thanh ghi thay đổi độ dài $N$ được khởi tạo theo trình tự đã cho. Phản hồi là gì (nếu có bất kỳ phản hồi nào) không liên quan.
- Nếu trình tự thực sự được tạo ra bởi một
$n$-giai đoạn LFSR như mô tả ở trên, trong đó $n \leq \frac N2$, sau đó là Berlekamp-Massey
thuật toán tìm tất cả $n$ hệ số $c_i$ sau đó
kiểm tra $s_0, s_1, \ldots, s_{2n-1}$. Tất nhiên, tải ban đầu của LFSR tổng hợp chỉ là $\big(s_0, s_1, \ldots, s_{n-1}\big)$. Từ đây
điểm trở đi, thuật toán Berlekamp-Massey có thể
tiếp tục kiểm tra phần còn lại của dãy (nếu vậy
mong muốn) nhưng không cần cập nhật $c_i$'S
bởi vì mỗi lần kiểm tra biểu tượng tiếp theo chỉ báo cáo
trở lại rằng mọi thứ đều ổn; LFSR hiện tại cũng tạo ra bit tiếp theo. Tuy nhiên, nói chung, nhà giải mã có không ý tưởng về việc liệu mã thời gian có được tạo bởi LFSR hay không; nó chỉ đơn thuần là một chuỗi các $N$ các bit không rõ nguồn gốc, và vì mục đích của nhà giải mã, tất cả các $N$ bit phải được kiểm tra để tìm ra LFSR ngắn nhất có thể tạo ra $s_0, s_1, \ldots, s_{N-1}$. Nếu các bit bổ sung $s_N, s_{N+1}, \ldots$ có sẵn, thì không có gì đảm bảo rằng LFSR được tìm thấy sau khi kiểm tra $N$ bit cũng sẽ tạo ra các bit bổ sung này. Trên thực tế, toàn bộ ý tưởng đằng sau thuật toán Berlekamp-Massey là nếu thử nghiệm "Liệu LFSR hiện tại cũng tạo ra $s_n$?" không thành công, thuật toán sẽ tổng hợp LFSR đã sửa đổi từ LFSR hiện tại để LFSR đã sửa đổi tạo ra $s_0, s_1, \ldots, s_{n-1},s_n$. Trong quá trình này, các chiều dài của LFSR có thể (hoặc có thể không) tăng lên.
- Nếu trình tự thực sự được tạo ra bởi một
$n$-giai đoạn LFSR như mô tả ở trên, trong đó $\frac N2 < n \leq N$, sau đó thuật toán Berlekamp-Massey tìm LFSR ngắn nhất tạo ra $s_0, s_1, \ldots, s_{N-1}$. Nó có thể, hoặc có thể không, tạo ra các giá trị giống nhau cho $s_N, s_{N+1}, \cdots, s_{2n-1}$ như LFSR thực tế làm.
Với suy nghĩ dài dòng ở trên, chúng ta hãy giải quyết các câu hỏi của OP. Trong tiêu đề, OP yêu cầu
Những công cụ nào có sẵn để thiết kế ngược một LFSR bên cạnh BMA?
Vâng, các thuật toán Euclide mở rộng đối với đa thức, ước chung lớn nhất có thể được sử dụng, nhưng theo một nghĩa nào đó, nó tương đương với thuật toán Berlekamp-Massey; nó có thể được xem như xử lý trình tự theo thứ tự ngược lại $s_{N-1}, s_{N-2}, \cdots, s_1, s_0$ so với thứ tự $s_0, s_1, \cdots, s_{N-2}, s_{N-1}$ được sử dụng bởi thuật toán Berlekamp-Massey.
Trong phần nội dung của câu hỏi, OP phàn nàn
mã này dường như có độ phức tạp tuyến tính là 110, điều này không thực tế theo bất kỳ cách nào.Nó cũng không thể được xây dựng lại với đa thức bất khả quy 110 bit mà BMA tìm thấy. Chỉ một vài bit đầu tiên như mong đợi và sau đó các bit dường như bị lật.
Có khả năng vấn đề này là do sai sót trong quá trình thực hiện BMA. "Không thực tế theo bất kỳ cách nào" cho thấy rằng có lẽ không đủ bộ nhớ được phân bổ để lưu trữ các đa thức khác nhau được sử dụng nội bộ trong BMA hoặc bộ đệm bị tràn, v.v. Như @kodlu chỉ ra, nếu mã thời gian có độ dài $220$ bit, sau đó kiểm tra tất cả $220$ bit có thể dẫn đến LFSR có độ dài $110$. Mặt khác, như đã thảo luận ở trên, nếu mã thời gian có độ dài $110$ hoặc nhiều hơn (có thể $128$ chút ít $= 16$ byte?), BMA cũng có thể tổng hợp một LFSR có độ dài $110$. Cuối cùng, tôi không có lời giải thích nào ngoài lỗi lập trình viên đối với quan sát của OP rằng trong đầu ra LFSR được tổng hợp, "một vài bit đầu tiên" là chính xác nhưng phần còn lại bị lật.
có ai có manh mối trong những điều kiện mà BMA phát hiện một đa thức dài như vậy không?
Xem tài liệu phía trên đường đứt nét trong câu trả lời này.
