Bài toán mã trường hợp kênh không bị nhiễu - Phần 3

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 3, 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ả
Nội dung trích xuất từ tài liệu:
Bài toán mã trường hợp kênh không bị nhiễu - Phần 3 7/2/2010Chương 2:Bài toán mã trư ng h pkênh không b nhi u2.3 Đ nh lý cho bài toán mã trongtrư ng h p kênh không b nhi u 2 7/2/2010 Huỳnh Văn KhaM ñu• Bi n ng u nhiên X có các tr ng thái x1, x2, …, xM v i xác xu t tương ng p1, p2, …, pM• Các t mã cho x1, x2, …, xM là W1, W2, …, WM có đ dài l n lư t là n1, n2, …, nM• T p các ký t mã là {a1, a2, …, aD}• Ta s xây d ng b mã đ c c ti u hóa chi u dài t mã trung bình• Đ u tiên là tìm ch n dư i l n nh t, sau đó tìm cách ti n g n t i ch n dư i đó. Và cu i cùng là xây d ng thu t toán đ tìm b mã t i ưu 1 7/2/2010 3 7/2/2010 Huỳnh Văn Khað nh lý 2.4 (ð nh lý cho bài toán mã trongtrư ng h p kênh không b nhi u)Gilà chi u dài t mã trung bình c a m t b mã gi i đư c b t kỳ cho bi n ng u nhiên X. Khi đó:D u b ng x y ra khi và ch khi: 4 7/2/2010 Huỳnh Văn KhaCh ng minh ñ nh lý 2.4• Đ t:Thì các qi có t ng b ng 1. Áp d ng m nh đ 1.1 2 7/2/2010 5 7/2/2010 Huỳnh Văn KhaCh ng minh ñ nh lý 2.4• D u b ng trong b t đ ng th c (*) x y ra khi và ch khi:• Do b mã là gi i đư c nênVà ta đư c• Ti p theo, n u , thì 6 7/2/2010 Huỳnh Văn KhaCh ng minh ñ nh lý 2.4• Ngư c l i, n u thì t (*) ta đư cNhưngVy , và t (**), ta đư c 3 7/2/2010 7 7/2/2010 Huỳnh Văn KhaB mã t i ưu tuy t ñ i• B mã làm cho d u b ng trong đ nh lý 2.4 x y ra đư c g i là b mã t i ưu tuy t đ i• Ví d X Xác su t T mã x1 1/2 0 x2 1/4 10 x3 1/8 110 x4 1/8 111 8 7/2/2010 Huỳnh Văn KhaB mã t i ưu tuy t ñ i• B mã t i ưu tuy t đ i ph i th a mãn• Trong trư ng h p t ng quát chưa ch c xây d ng đư c b mã t i ưu tuy t đ i, do các ni như trên chưa ch c là s nguyên• Tuy nhiên, ta hoàn toàn có th xây d ng đư c b mã ti n t có chi u dài t mã trung bình g n b ng ch n dư i H(X)/log D như kh ng đ nh c a đ nh lý sau 4 7/2/2010 9 7/2/2010 Huỳnh Văn Khað nh lý 2.5Cho trư c bi n ng u nhiên X, v i đ không ch c ch n là H(X). Khi đó t n t i b mã ti n t cho X, sao cho chi u dài t mã trung bình th a mãn 10 7/2/2010 Huỳnh Văn KhaCh ng minh ñ nh lý 2.5• Ch n ni là s nguyên th a mãn• Khi đó log pi ≥ -ni log D, suy ra• V y theo đ nh lý 2.2 thì t n t i b mã ti n t ng v i các ni ch n như trên 5 7/2/2010 11 7/2/2010 Huỳnh Văn KhaCh ng minh ñ nh lý 2.5• Ti p theo, ta ư c lư ng chi u dài t mã trung bình. Nhân hai v cho pi r i l y t ng theo i ta đư c• Và ta có k t lu n c a đ nh lý 12 ...