TAILIEUCHUNG - tài liệu Lý thuyết Thông tin

Định lý : Bộ mã vòng (n,k) có thể dò được tất cả các mẫu sai nhỏ hơn hoặc bằng (n-k) bit. (kể cả độ dài sai vòng). • Chứng minh: • Bổ đề: “Nếu bộ mã vòng (n,k) có khả năng phát hiện được đa thức gây sai e(x) thì sẽ phát hiện được tất cả các đa thức gây sai ei(x) là đa thức dịch chuyển vòng i bit của e(x) (i=1,n-1)”. | Phương pháp giải mã vòng Meggitt Giáo viên thực hiện Lê Thị Thanh Chứng minh định lý Meggitt UM Với quy ước u1 x là quay vòng trái của u x . u x uoxn 1 u-jX1 1 2 . un_i u1 x Ũ- Xn 1 u2xn 2 . u x u0 u1 x mod g x xs x mod g x X. u x mod g x mod g x u1 x mod g x x mod g x u-iX 1 u2xn 2 . un1x Uq mod g x uoxn u-iX 1 . u x mod g x u0 xn 1 mod g x 0 Định lý Meggitt Giả sử s x là syndrome của u x uoxn 1 u-iX 2 . Un-- thì syndrome của u1 x là s1 x được tính theo công thức sau s1 x xs x mod g x Khả năng sửa sai của bộ mã vòng n k Độ dài sai Khả năng dò sai Xác suất không dò được sai của các mẫu sai Xác suất không dò được sai của bộ mã vòng 1 Độ dài sai Độ dài sai Giả sử e 0 . 6 - 0 - . j ei 1 . j_i 6j 6j i en-l 00 . 0 1 ei 1. ếpl 00 . 0 Khi đó độ dài sai được định nghĩa là khoảng cách từ bit i tới bit j độ dài sai j - i 1 Khả năng dò sai 1 3 UM Định lý Bộ mã vòng n k có thể dò được tất cả các mẫu sai nhỏ hơn hoặc bằng n-k bit. kể cả độ dài sai vòng . Chứng minh Bổ đề Nếu bộ mã vòng n k có khả năng phát hiện được đa thức gây sai e x thì sẽ phát hiện được tất cả các đa thức gây sai e x là đa thức dịch chuyển vòng i bit của e x 1 1 n-1 . Độ dài sai vòng giả sử e ege . 6 eoel ei-1 ei ei 1 ej-i ej ej i en-l eoe. . ej_1 10 0. 01 ej 1 .e Độ dài sai vòng được định nghĩa là khoảng cách vòng từ bit e đến bit 6j. độ dài sai vòng n - j - 1 - i - 1 1 n -j i 1 Khả năng dò sai 2 3 UM Giả sử e x là đa thức gây sai không phát hiện được e x cũng là đa thức ma mâu thuẫn . Do đó ta chỉ cần chứng minh định lý với độ dài sai tuyệt đối. Giả sử e x E x .x với 0 i n-1 vector sai ứng với E x có độ dài n-k bậc của E x n-k-1 Để phát hiện được sai trong mã vòng thì phải chứng minh rằng e x không phai từ mã tức là e x không chia hết cho g x . 2 Khả năng dò sai 3 3 Nhận xét E x có bậc nhỏ hơn g x E x 0 E x không chia hết cho g x . Mặt khác vì hệ số tự do của g x là khác không nên X sẽ không chức một thừa số nào của g x .

• Kĩ thuật Viễn thông
• Khả năng dò sai
• Độ dài sai
• Thiết kế mạch giải mã
• Hoạt động mạch
• giải mã Meggitt
• Định lý Meggitt