Xem mẫu
Chương 2:
Bài toán mã trường hợp kênh không bị nhiễu
2.3 Định lý cho bài toán mã trong trường hợp kênh không bị nhiễu
2
Huỳnh Văn Kha 9/30/2010
Mở ñầu
• Biến ngẫu nhiên X có các trạng thái x , x , …, x với xác xuất tương ứng p1, p2, …, pM
• Các từ mã cho x , x , …, x là W , W , …, W có độ dài lần lượt là n1, n2, …, nM
• Tập các ký tự mã là {a1, a2, …, aD}
• Ta sẽ xây dựng bộ mã để cực tiểu hóa chiều dài từ mã trung bình
• Đầu tiên là tìm chặn dưới lớn nhất, sau đó tìm cách tiến gần tới chặn dưới đó. Và cuối cùng là xây dựng thuật toán để tìm bộ mã tối ưu
3
Huỳnh Văn Kha 9/30/2010
ðịnh lý 2.4 (ðịnh lý cho bài toán mã trong trường hợp kênh không bị nhiễu)
Gọi
là chiều dài từ mã trung bình của một bộ mã giải được bất kỳ cho biến ngẫu nhiên X. Khi đó:
Dấu bằng xảy ra khi và chỉ khi:
4
Huỳnh Văn Kha 9/30/2010
Chứng minh ñịnh lý 2.4
• Đặt:
Thì các qi có tổng bằng 1. Áp dụng mệnh đề 1.1
5
Huỳnh Văn Kha 9/30/2010
Chứng minh ñịnh lý 2.4
• Dấu bằng trong bất đẳng thức (*) xảy ra khi và chỉ khi:
• Do bộ mã là giải được nên Và ta được
• Tiếp theo, nếu , thì
...
- tailieumienphi.vn
nguon tai.lieu . vn