tailieunhanh - LÝ THUYẾT THÔNG TIN - CÁC TÍNH CHẤT CỦA ENTROPY - KS. DƯƠNG VĂN HIẾU - 3

Giải ra x1, còn lại 0. Nhận tiếp 0 - 00 - Giải ra x1, còn lại 0. Nhận tiếp 1 - 01 - Giải ra x2. Nhận tiếp 01 - Giải ra x2. Nhận tiếp 00 - Giải ra x1, còn lại 0. Nhận tiếp 1 - 01 - Giải ra x2. Kết quả dãy thông báo là: x1x2x1x1x1x2x2x1x2. Kết luận: Bảng mã tách được là bảng mã mà trong đó không tồn lại từ mã này là mã khóa từ mã khác, tuy nhiên vẫn có thể tồn tại từ mã này là tiền tố (phần đầu) của. | Giáo trình Lý thuyết thông tin. Nhận tiếp 0 - 00 Nhận tiếp 0 - 00 Nhận tiếp 1 - 01 Nhận tiếp 01 Nhận tiếp 00 Nhận tiếp 1 - 01 Kết quả dãy thông báo là x1x2x1x1x1x2x2x1x2. - Giải ra x15 còn lại 0 - Giải ra xb còn lại 0 - Giải ra x2. - Giải ra x2. - Giải ra x1 còn lại 0. - Giải ra x2. Kết luận Bảng mã tách được là bảng mã mà trong đó không tồn lại từ mã này là mã khóa từ mã khác tuy nhiên vẫn có thể tồn tại từ mã này là tiền tố phần đầu của từ mã kia. Khái niệm bảng mã tức thời Bảng mã tức thời là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được dãy các từ mã ws và khi giải mã dãy các từ mã ws thì ta chỉ nhận được một thông báo duy nhất là Msg ban đầu. Abramson đã chứng minh được kết quả sau Bảng mã tức thời là bảng mã không tồn tại từ mã này là tiền tố của từ mã khác. Ví dụ 1 Bảng mã W w1 10 w2 101 w3 100 không phải bảng mã tức thời vì w1 là tiền tố của w2 và w3. Ví dụ 2 Bảng mã W w1 0 w2 100 w3 101 w4 11 là bảng mã tức thời vì không tồn tại từ mã này là tiền tố của từ mã khác. Giải thuật kiểm tra tính tách được của bảng mã Thủ tục sau đây do Sardinas 1960 Patterson 1963 và Abramson 1963 đưa ra nhằm kiểm tra xem một bảng mã nào đó có phải là bảng mã tách được bảng mã cho phép giải mã duy nhất hay không. Input Bảng mã W Output Kết luận bảng mã tách được hay không tách được. Giải thuật Bước khởi tạo Gán tập hợp S0 W. Bước 1 xác định tập hợp S1 từ S0 - Khởi tạo S1 - Với V wi Wj e So ta xét nếu wi WjA wj là tiền tố của wi hoặc Wj wi A wi là tiền tố của Wj thì thêm A phần hậu tố vào S1. Bước k xác định tập hợp Sk k 2 từ tập hợp S0 và Sk-1 - Khởi tạo Sk - Với V wiG S0 và V vj eSk-b ta xét nếu wi vjA vj là tiền tố của Wi hoặc vj wi A Wi là tiền tố của vj thì thêm A phần hậu tố vào Sk. Điều kiện để dừng vòng lặp Nếu Sk thì dừng và kết luận bảng mã tách được k 1 . Nếu tồn tại từ mã wi trong Sk hay Sk oS0 0 thì dừng và kết luận bảng mã không tách được. Nếu Sk St k thì dừng và kết luận bảng mã tách được k 1 . Bài toán 1- yêu cầu Biên soạn TS. L ê Quy ết Thắng ThS. Phan Tấn