Bài giảng Lý thuyết thông tin: Chương 2.4 - ThS. Huỳnh Văn Kha

Chương 2: Bài toán mã trường hợp kênh không bị nhiễu 2.4 Xây dựng bộ mã tối ưu 2 Huỳnh Văn Kha 9/30/2010 Bổ ñề 2.6 Giả sử bộ mã C là tối ưu trong họ các các bộ mã tiền tố cho phân bố xác suất p1, p2, …, pM; nói cách khác, giả sử không bộ mã tiền tố nào có chiều dài từ mã trung bình nhỏ hơn của C. Khi đó C là tối ưu trong họ các bộ mã giải được Bổ đề 2.6 cho phép ta thay vì tìm bộ mã tối ưu trong tập các bộ mã giải được, ta chỉ cần tìm bộ mã tối ưu trong tập nhỏ hơn, tập các bộ mã tiền tố 3 Huỳnh Văn Kha 9/30/2010 Chứng minh bổ ñề 2.6 • Giả sử tồn tại bộ mã giải được C’ có chiều dài từ mã trung bình nhỏ hơn của C. Gọi n’ , n’ , …, n’ là các độ dài từ mã của C’ • Theo định lý 2.3 • Theo định lý 2.2 thì tồn tại bộ mã tiền tố C’’ với chiều dài từ mã lần lượt là: n’1, n’2, …, n’M • Như vậy có bộ mã tiền tố C’’ có chiều dài từ mã trung bình nhỏ hơn của C (vô lý) 4 Huỳnh Văn Kha 9/30/2010 Bổ ñề 2.7 • Cho C là bộ mã tiền tố nhị phân với chiều dài các từ mã là n1, n2, …, nM. • Giả sử các trạng thái được sắp xếp theo thứ tự giảm dần theo xác suất (nghĩa là p1 ≥ p2 ≥ … ≥ pM) và trong mỗi nhóm có cùng xác suất, các trạng thái được xếp thứ tự tăng dần theo chiều dài từ mã, nghĩa là nếu pi = pi+1 = … = pi+r thì ni ≤ ni+1 ≤ … ≤ ni+r • Nếu C là tối ưu trong họ các bộ mã tiền tố thì C có các tính chất sau: 5 Huỳnh Văn Kha 9/30/2010 Bổ ñề 2.7 a) Trạng thái có xác suất cao thì từ mã tương ứng có độ dài ngắn hơn, nghĩa là pj > pk kéo theo nj ≤ nk b) Hai từ mã của hai trạng thái cuối có độ dài bằng nhau, nghĩa là nM-1 = nM c) Trong số các từ mã có chiều dài nM, có ít nhất hai từ mã giống nhau hoàn toàn, ngoại trừ ký tự cuối cùng của chúng ... - tailieumienphi.vn