Tham gia Đăng nhập
Điểm:0
neolith avatar Crypto

Thuật toán Berlekamp-Massey có thể phát hiện sai LFSR không?

lá cờ cn
neolith

Có thể nào BMA phát hiện một đa thức bất khả quy từ một chuỗi không được tạo bởi LFSR không? Tôi đang cung cấp một chuỗi vào BMA với giả định rằng nó được tạo bởi LFSR. Nó phát hiện một đa thức có độ dài nhất định, nhưng không thể xây dựng lại chuỗi từ đa thức đó. Tôi không muốn cho rằng việc triển khai BMA có lỗi. Nếu câu hỏi trên không thể được trả lời có trong mọi trường hợp, thì việc thực hiện phải không chính xác.

52
1 + 0
lsr
Điểm:4
kodlu avatar Crypto
lá cờ sa
kodlu

Không.

Cho một dãy dài tùy ý $(x_1,\ldots,x_t,\ldots)$ xem xét các phân khúc ban đầu của nó.

Dãy bất kỳ (hữu hạn) $$x^{(n)}:=(x_1,\ldots,x_n)$$có thể được tạo ra bởi một LFSR tuần hoàn có cùng độ dài. Chỉ cần xoay vòng các bit, không có vòi.

BMA sẽ phát hiện điều này nếu không tồn tại LFSR ngắn hơn tạo ra $x^{(n)}$. Và sẽ hội tụ để phát hiện chính xác LFSR ngắn nhất tạo ra duy nhất $x^{(n)}$ nếu bạn cung cấp cho nó gấp đôi số bit ban đầu $x^{(2n)}.$

Sửa mã của bạn.

0 + 1
neolith avatar
lá cờ cn
neolith
Cảm ơn. Ít nhất bây giờ tôi không phải làm việc trên các giả định
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.