Xem mẫu
Chương 2:
Bài toán mã trường hợp kênh không bị nhiễu
2.2 Sự tồn tại của bộ mã tiền tố và giải được
2
Huỳnh Văn Kha 9/30/2010
Mở ñầu
• Cho biến ngẫu nhiên X có các giá trị x , x , …, x Tập các ký tự mã a1, a2, …, aD
• Cho trước các số nguyên dương n1, n2, …, nM • Bài toán đặt ra là: có thể xây dựng bộ mã giải
được sao cho từ mã ứng với xk có chiều dài là nk? • Mã tiền tố có thể giải mã từng bước
• Trong bài toán kênh không bị nhiễu, mã giải được có thể quy về mã tiền tố
• Đầu tiên ta sẽ xét sự tồn tại của bộ mã tiền tố, sau đó mở rộng cho bộ mã giải được
3
Huỳnh Văn Kha 9/30/2010
Ví dụ
• Ví dụ 1:
M = 3, D = 2, n1 = 1, n2 = 2, n3 = 3 Có thể chọn bộ mã {0, 10, 110}
• Ví dụ 2: M = 3, D = 2, n1 = n2 = 1, n3 = 2 Không có bộ mã giải được nào thỏa yêu cầu bài
toán (sẽ chứng minh sau)
• Khi nào có thể xây dựng được bộ mã thỏa yêu cầu, khi nào không?
4
Huỳnh Văn Kha 9/30/2010
ðịnh lý 2.2
Một bộ mã tiền tố với chiều dài các từ mã n1, n2, …, nM là tồn tại khi và chỉ khi
Trong đó D là số các ký tự mã
5
Huỳnh Văn Kha 9/30/2010
Chứng minh ñịnh lý 2.2
• Cây bậc D kích thước k là một hệ thống các điểm và đoạn thẳng
• Mỗi dãy s được tạo thành từ các ký tự trong {0, 1, …, D – 1} có chiều dài không lớn hơn k được biểu diễn bởi một điểm Vs khác nhau
• Nếu dãy t có được do thêm duy nhất một ký tự vào sau s thì nối Vs và Vt bằng một đoạn thẳng
• Các điểm ứng với dãy có chiều dài k gọi là các điểm ngọn của cây kích thước k
...
- tailieumienphi.vn
nguon tai.lieu . vn