tailieunhanh - [Viễn Thông] Giáo Trình: Lý Thuyết Thông Tin phần 5

Bảng mã tối ưu tương đối Định lý: Bảng mã được gọi là tối ưu tương đối khi: H(X ) H (X ) ≤n | Giáo trình Lý thuyết thông tin. W wi w2 w3 w4 là bảng mã tối ưu tuyệt đối vì thỏa điều kiện H X log Bảng mã tối ưu tương đối Định lý Bảng mã được gọi là tối ưu tương đối khi n H 1 log2 D log2 D Điều kiện nhận biết một bảng mã tối ưu Định lý với D 2 - Xác suất pi càng lớn thì độ dài ni của từ mã wi càng nhỏ. - Giả sử p1 p2 . pM. Nếu pi pi 1 pi r thì ni ni 1 ni r thì 2 từ mã tương ứng với 2 giá trị có xác suất nhỏ nhất có độ dài mã bằng nhau nM-1 nM. - Trong các từ mã có độ dài bằng nhau và cùng bằng nM dài nhất thì tồn tại ít nhất 2 từ mã wM-1 và wM có M-1 ký tự đầu giống nhau và ký tự thứ M khác nhau. Ví dụ xét bảng mã W w1 0 w2 100 w3 101 w4 1101 ws 1110 Bảng mã trên không phải là bảng mã tối ưu vì 2 từ mã w4 w5 có độ dài lớn nhất 4 ký tự nhưng 3 ký tự đầu khác nhau. Ghi chú D 2 được xét tương tự. Định lý Huffman Định lý Giả sử X có phân phối xác suất với thứ tự giảm dần sau X x1 x2 . xM P p1 p2 pM Giả sử bảng mã của X là W w15 w2 . wM-1 wM . Đặt xM-1 M xM-1 xM có xác suất là pM-1 M pM-1 pM. và X x1 x2 . xM-1 M có phân phối sau X x1 x2 x M-2 x M-1 M P P1 p2 p M-2 p M-1 M Giả sử W w15 w2 . wM-2 x M-1 M là bảng mã tối ưu của X . Khi đó - wm-1 w m-1 m 0 . - wM w M-1 M 1 . Biên soạn TS. L ê Quy ết Thắng ThS. Phan Tấn Tài Ks. Dương Văn Hiếu. 41 Giáo trình Lý thuyết thông tin. Phương pháp sinh mã Huffman Giả sử X có phân phối xác suất với thứ tự giảm dần sau X x1 x2 xM P p1 p2 pM Thủ tục lùi D 2 Khởi tạo Đặt M0 M Bước 1 - Đặt XM0-1 M0 xm0-1 XM0 có xác suất Pm0-1 M0 PM0-1 PMịí - Sắp xếp lại theo tứ tự giảm dần của xác suất ta nhận được dãy phân phối mới có M0-1 Phần tử như sau P1 p2 L Pm0-1 m0 Bước 2 Lặp lại bước 1 với sự lưu vết WM 0-1 WM 0 -1 M 0 0 11 11 -1M0 1 Giảm M0 M0 M0-1 vòng lặp kết thúc khi M0 2 Chú ý trong trường hợp tổng quát vong lặp kết thúc khi M0 D. Thủ tục tiến Đi ngược lại so với thủ tục lùi đồng thời xác định từ mã ở mỗi bước từ sự lưu vết ở thủ tục lùi. Minh họa phương pháp sinh mã Huffman Ví dụ 1 sinh bảng mã nhị phân Huffman cho X có phân phối