Xem mẫu
Chương 2:
Bài toán mã trường hợp kênh không bị nhiễu
2.1 Tính giải được của một bộ mã
2
Huỳnh Văn Kha 9/30/2010
Giới thiệu bài toán mã
• Biến ngẫu nhiên X nhận các giá trị x , x , … , x (gọi là các trạng thái của X) với xác suất tương ứng p1, p2, …., pM
• Dãy hữu hạn các giá trị của X gọi là mẫu tin (message)
• Tập hợp {a , a , …, a } gọi là tập các ký tự mã (code character)
• Mỗi x tương ứng với một dãy hữu hạn các ký tự mã gọi là từ mã (character word)
• Tập các từ mã gọi là bộ mã (code)
3
Huỳnh Văn Kha 9/30/2010
Giới thiệu bài toán mã
• Giả sử các từ mã là khác nhau
• Mẫu tin do biến X sinh ra được mã hóa thành một dãy các từ mã
• Mục tiêu của bài toán là cực tiểu hóa chiều dài trung bình của mã
• Chiều dài của từ mã ứng với xi là ni, i = 1, 2, …, M. Mục tiêu là cực tiểu hóa:
4
Huỳnh Văn Kha 9/30/2010
Mã tiền tố và mã giải ñược
• Xét bộ mã nhị phân
x1 0 x2 010 x3 01 x4 10
• Dãy 010 có thể tương ứng với một trong ba mẩu tin: x2, x3x1, x1x4. Nên không thể giải mã
• Cần có một số giới hạn trên các từ mã của 1 bộ mã
5
Huỳnh Văn Kha 9/30/2010
Mã tiền tố và mã giải ñược
• Bộ mã gọi là giải được nếu mỗi dãy hữu hạn các từ mã đều tương ứng với nhiều nhất một mẫu tin
• Dãy A gọi là tiền tố của dãy B nếu dãy B có thể được viết dưới dạng AC, với C là một dãy nào đó
• Bộ mã tiền tố là bộ mã có tính chất: không từ mã nào là tiền tố của từ mã khác
• Bộ mã tiền tố là giải được, nhưng bộ mã giải được chưa chắc là bộ mã tiền tố
• Bộ mã tiền tố có thể được giải mã từng bước
...
- tailieumienphi.vn
nguon tai.lieu . vn