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

Chia sẻ: Nguyen Uyen | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

56
lượt xem 4
download

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

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 4', 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ả

Chủ đề:

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

Lưu

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

7/2/2010 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 7/2/2010 Huỳnh Văn Kha 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 1
7/2/2010 3 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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: 2
7/2/2010 5 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 3
7/2/2010 7 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 4
7/2/2010 9 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 5
7/2/2010 11 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 6
7/2/2010 13 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 đó 7
7/2/2010 15 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 8
7/2/2010 17 7/2/2010 Huỳnh Văn Kha 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 7/2/2010 Huỳnh Văn Kha 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 9