Tham khảo tài liệu 'bài toán mã trường hợp kênh không bị nhiễu - phần 4', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 7 2 2010 Chương 2 Bài toán mã trường hợp kênh không bị nhiễu Xây dựng bộ mã tối ưu Huỳnh Văn Kha 7 2 2010 Bổ đề 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ổ đề 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ố 1 7 2 2010 3 Huỳnh Văn Kha 7 2 2010 Chứng minh bổ đề 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 1 n 2 . n M là các độ dài từ mã của C Theo định lý 1 i l Theo định lý 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 7 2 2010 Bổ đề 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 Pị pỉ 1 . pỉ r thì nỉ nỉ i . nỉ 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 2 7 2 2010 5 Huỳnh Văn Kha 7 2 2010 Bổ đề 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 6 Huỳnh Văn Kha 7 2 2010 Ví dụ Xét bộ mã nhị phân sau X Từ mã x1 0 x2 100 x3 101 x4 1101 x5 1110 Bộ mã này không tối ưu
