Bài giảng Chương 2: Bài toán mã trường hợp kênh không bị nhiễu

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 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ó 9/30/2010Huỳnh Văn Kha 2 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ố 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’1, n’2, , n’M là các độ dài từmã của C’ • Theo định lý 2.3 9/30/2010 3 Huỳnh Văn Kha • 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ý) 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ự 9/30/2010 4 Huỳnh Văn Kha 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: 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 9/30/2010 5 Huỳnh Văn Kha 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 Ví dụ • Xét bộmã nhị phân sau X Từmã 9/30/2010 6 Huỳnh Văn Kha • Bộmã này không tối ưu x1 0 x2 100 x3 101 x4 1101 x5 1110 Chứ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 9/30/2010 7 Huỳnh Văn Kha 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 Chứ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ý 9/30/2010 8 Huỳnh Văn Kha 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ơn Chú ý: Để đơ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 Xâ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 9/30/2010 9 Huỳnh Văn Kha • 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 Xây dựng bộ mã tối ưu (Huffman) X p C1 n X p C2 n x1 p1 W1 n1 x1 p1 W1 n1 x2 p2 W2 n2 x2 p2 W2 n2 9/30/2010 10 Huỳnh Văn Kha xM,M-1 pM+pM-1 WM,M-1 nM,M-1 xM-2 pM-2 WM-2 nM-2 xM-1 pM-1 [WM,M-1 0] nM-1 xM-2 pM-2 WM-2 nM-2 xM pM [WM,M-1 1] nM Chứng minh • Ta sẽ chứng tỏ C1 là bộmã tối ưu • Giả sử C1 không tối ưu. Gọi C1’ là bộmã tiền tố tối ưu với các từmã W’1, W’2, , W’M có độ dài n’1, 9/30/2010 11 Huỳnh Văn Kha n’2, , n’M • Theo bổ đề 2.7 b) n’M-1 = n’M • Theo bổ đề 2.7 c), có ít nhất một cặp từmã độ dài nM chỉ khác nhau ở ký tự cuối cùng • Không mất tính tổng quát, giả sửW’M-1, W’M là một cặp từmã như vậy (nếu cần thiết, đổi vị trí) Chứng minh • Ghép xM, xM-1 thành xM,M-1 và xây dựng bộmã C’2 như sau • Các từmã cho x1, , xM-2 vẫn như trong C’1 9/30/2010 12 Huỳnh Văn Kha • Từmã cho xM,M-1 chính là W’M (hay W’M-1) bỏ đi ký tự cuối (gọi là U’) • Ta sẽ chứng minh C’2 có chiều dài từmã trung bình nhỏ hơn chiều dài từmã trung bình của C2 • Và do đó trái với giả thiết tối ưu của C2 Chứng minh X p C’1 n X p C’2 n x1 p1 W’1 n’1 x1 p1 W’1 n1 x2 p2 W'2 n’2 x2 p2 W’2 n2 9/30/2010 13 Huỳnh Văn Kha xM,M-1 pM+pM-1 U’ n’M-1 = n’M-1-1 xM-2 pM-2 W’M-2 n’M-2 xM-1 pM-1 W’M-1 n’M-1 xM-2 pM-2 W’M-2 n’M-2 xM pM W’M n’M=n’M-1 Chứng minh 9/30/2010 14 Huỳnh Văn Kha • C’1 có chiều dài từmã trung bình nhỏ hơn C1 • Theo cách xây dựng C1 thì nM = nM-1 do đó Chứng minh • Vậy 9/30/2010Huỳnh Văn Kha 15 • Do nM-1-1 = nM,M-1, nên vế phải chính là độ dài từ mã trung bình của C2 và ta có điều cần chứng minh Ví dụ x1 0.3 x2 0.25 x3 0.2 9/30/2010Huỳnh Văn Kha 16 x1 0.3 x2 0.25 x 0.2 x1 0.3 x2 0.25 x 0.25 x4 0.1 x5 0.1 x6 0.05 3 x5,6 0.15 x4 0.1 4,56 x3 0.2 x3,456 0.45 x1 0.3 x2 0.25 x1,2 0.55 x3,456 0.45 9/30/2010Huỳnh Văn Kha 17 x1,2 0 x3,456 1 x3,456 1 x1 00 x 01 x1 00 x2 01 x 10 x1 00 x2 01 x 11 x1 00 x2 01 x 112 4,56 x3 11 3 x5,6 100 x4 101 3 x4 101 x5 1000 x6 1001 Bài tập X Xác suất x1 0.3 x 0.28 9/30/2010Huỳnh Văn Kha 18 2 x3 0.15 x4 0.1 x5 0.06 x6 0.06 x7 0.05