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

Chương 2.4 trang bị cho người học những hiểu biết cơ bản về xây dựng bộ mã tối ưu. Thông qua bài giảng này người học có thể hiểu được định lý Huffman, biết phương pháp sinh mã Huffman, vận dụng phương pháp sinh mã Huffman để sinh mã Huffman cho một thông báo,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết thông tin: Chương 2.4 - ThS. Huỳnh Văn KhaChương 2:Bài toán mã trường hợpkênh không bị nhiễu2.4 Xây dựng bộ mã tối ưu 2 Huỳnh Văn Kha 9/30/2010Bổ ñề 2.6Giả 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 đượcBổ đề 2.6 cho phép ta thay vì tìm bộ mã tối ưutrong 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/2010Chứ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’1, n’2, …, n’M 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/2010Bổ ñề 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/2010Bổ ñề 2.7a) 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 ≤ nkb) Hai từ mã của hai trạng thái cuối có độ dài bằng nhau, nghĩa là nM-1 = nMc) 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 9/30/2010Ví 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 7 Huỳnh Văn Kha 9/30/2010Chứng minh bổ ñề 2.7• Chứng minh a): Nếu pj > pk nhưng nj > nk thì chỉ cần đổi các từ mã ở vị trí thứ j và k cho nhau ta sẽ được bộ mã C’ có chiều dài từ mã trung bình nhỏ hơn. Thật vậy:• Chứng minh b): Chú ý rằng nM-1 ≤ nM. Nếu nM > nM-1, chỉ cần bỏ đi ký tự cuối của từ mã thứ M thì ta được bộ mã tiền tố tốt hơn 8 Huỳnh Văn Kha 9/30/2010Chứng minh bổ ñề 2.7• Chứng minh c): Giả sử ngược lại, mọi cặp từ mã độ dài nM đều có ít nhất một ký tự mã (không là ký tự cuối) khác nhau. Khi đó chỉ cần bỏ đi ký tự mã cuối cùng của một trong các từ mã đó, ta sẽ được bộ mã (vẫn là tiền tố) tốt hơnChú ý: Để đơn giản ta chỉ nói về cách xây dựng bộ mã tiền tố nhị phân tối ưu. Cách xây dựng bộ mã với nhiều ký tự mã hơn có thể xem trong tài liệu tham khảo 9 Huỳnh Văn Kha 9/30/2010Xây dựng bộ mã tối ưu (Huffman)• Sắp xếp các xi theo thứ tự xác suất tăng dần• Ghép hai trạng thái xM-1 và xM thành một trạng thái, gọi là xM,M-1, với xác suất pM + pM-1• Giả sử ta xây dựng được bộ mã tiền tố tối ưu C2 cho tập trạng thái mới• Xây dựng C1 cho tập trạng thái ban đầu như sau: ▫ Các từ mã cho x1, x2, …, xM-2 vẫn như trong C2 ▫ Từ mã cho xM-1 và xM được tạo thành bằng cách thêm lần lượt 0, 1 vào từ mã của xM,M-1 trong C2 10 Huỳnh Văn Kha 9/30/2010Xây dựng bộ mã tối ưu (Huffman)X p C1 n X p C2 nx1 p1 W1 n1 x1 p1 W1 n1x2 p2 W2 n2 x2 p2 W2 n2 … … … …… … … … xM,M-1 pM+pM-1 WM,M-1 nM,M-1 … … ...