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

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

65
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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’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/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
6 Huỳnh Văn Kha 9/30/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
7 Huỳnh Văn Kha 9/30/2010 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 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/2010 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ý 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
9 Huỳnh Văn Kha 9/30/2010 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 • 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/2010 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 … … … … … … … … 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
11 Huỳnh Văn Kha 9/30/2010 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, 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í)
12 Huỳnh Văn Kha 9/30/2010 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 • 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
13 Huỳnh Văn Kha 9/30/2010 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 … … … … … … … … 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
14 Huỳnh Văn Kha 9/30/2010 Chứng minh • 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 đó
15 Huỳnh Văn Kha 9/30/2010 Chứng minh • Vậy • 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
16 Huỳnh Văn Kha 9/30/2010 Ví dụ x1 0.3 x1 0.3 x1 0.3 x2 0.25 x2 0.25 x2 0.25 x3 0.2 x3 0.2 x4,56 0.25 x4 0.1 x5,6 0.15 x3 0.2 x5 0.1 x4 0.1 x6 0.05 x3,456 0.45 x1,2 0.55 x1 0.3 x3,456 0.45 x2 0.25
17 Huỳnh Văn Kha 9/30/2010 x1,2 0 x3,456 1 x1 00 x1 00 x1 00 x3,456 1 x1 00 x2 01 x2 01 x2 01 x2 01 x4,56 10 x3 11 x3 11 x3 11 x5,6 100 x4 101 x4 101 x5 1000 x6 1001
18 Huỳnh Văn Kha 9/30/2010 Bài tập X Xác suất x1 0.3 x2 0.28 x3 0.15 x4 0.1 x5 0.06 x6 0.06 x7 0.05