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

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

Thêm vào BST

Báo xấu

68
lượt xem 3
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 1', 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 1

7/2/2010 Chương 2: Bài toán mã trư ng h p kênh không b nhi u 2.1 Tính gi i đư c c a m t b mã 2 7/2/2010 Huỳnh Văn Kha Gi i thi u bài toán mã • Bi n ng u nhiên X nh n các giá tr x1, x2, … , xM (g i là các tr ng thái c a X) v i xác su t tương ng p1, p2, …., pM • Dãy h u h n các giá tr c a X g i là m u tin (message) • T p h p {a1, a2, …, aD} g i là t p các ký t mã (code character) • M i xi tương ng v i m t dãy h u h n các ký t mã g i là t mã (character word) • T p các t mã g i là b mã (code) 1
7/2/2010 3 7/2/2010 Huỳnh Văn Kha Gi i thi u bài toán mã • Gi s các t mã là khác nhau • M u tin do bi n X sinh ra đư c mã hóa thành m t dãy các t mã • M c tiêu c a bài toán là c c ti u hóa chi u dài trung bình c a mã • Chi u dài c a t mã ng v i xi là ni, i = 1, 2, …, M. M c tiêu là c c ti u hóa: 4 7/2/2010 Huỳnh Văn Kha Mã ti n t và mã gi i ñư c • Xét b mã nh phân x1 0 x2 010 x3 01 x4 10 • Dãy 010 có th tương ng v i m t trong ba m u tin: x2, x3x1, x1x4. Nên không th gi i mã • C n có m t s gi i h n trên các t mã c a 1 b mã 2
7/2/2010 5 7/2/2010 Huỳnh Văn Kha Mã ti n t và mã gi i ñư c • B mã g i là gi i đư c n u m i dãy h u h n các t mã đ u tương ng v i nhi u nh t m t m u tin • Dãy A g i là ti n t c a dãy B n u dãy B có th đư c vi t dư i d ng AC, v i C là m t dãy nào đó • B mã ti n t là b mã có tính ch t: không t mã nào là ti n t c a t mã khác • B mã ti n t là gi i đư c, nhưng b mã gi i đư c chưa ch c là b mã ti n t • B mã ti n t có th đư c gi i mã t ng bư c 6 7/2/2010 Huỳnh Văn Kha Mã ti n t và mã gi i ñư c • B mã sau là b mã ti n t x1 0 x2 100 x3 101 x4 11 • B mã sau là gi i đư c nhưng không là ti n t x1 0 x2 01 3
7/2/2010 7 7/2/2010 Huỳnh Văn Kha Gi i thu t ki m tra tính gi i ñư c • G i S0 là t p các t mã ban đ u • Xét t t c các c p t mã trong S0. N u có các t mã Wi, Wj sao cho Wj = WiA, cho h u t A vào t p S1 • Gi s có t p Sn-1 (n>1). N u có W trong S0 và A trong Sn-1 sao cho A=WB, cho B vào Sn. N u có W’ trong So và A’ trong Sn-1 sao cho W’=A’B’, cho B’ vào Sn • Đ nh lý 2.1: M t b mã là gi i đư c n u và ch n u không t p nào trong các t p S1, S2, S3, … ch a b t kỳ t mã nào 8 7/2/2010 Huỳnh Văn Kha Thu t toán ki m tra tính gi i ñư c x1 a x2 c x3 ad x4 abb x5 bad x6 deb x7 bbcde 4
7/2/2010 9 7/2/2010 Huỳnh Văn Kha Thu t toán ki m tra tính gi i ñư c S0 S1 S2 S3 S4 S5 S6 S7 a d eb de b ad d eb c bb cde bcde ad • Sn r ng v i m i n>7 abb • ad thu c S5 nên b mã là không bad gi i đư c • abbcdebad có th gi i mã thành deb x1x7x5 ho c x4x2x6x3 bbcde 10 7/2/2010 Huỳnh Văn Kha Tìm dãy mã không gi i ñư c • Dãy các ký t mã có th đ i di n cho 2 m u tin đư c g i là dãy mã không gi i đư c • Ta s không ch ng minh đ nh lý 2.1 nhưng s ch ra cách tìm dãy mã không gi i đư c • Gi s Sn ch a t mã W. Ti n hành ngư c l i, ta tìm đư c dãy: A0, W0, A1, W1, …, An, Wn 5
7/2/2010 11 7/2/2010 Huỳnh Văn Kha Tìm dãy mã không gi i ñư c • A0, W0, W1, …, Wn là các t mã, Ai ε Si (i = 1, 2, …, n), W0 = A0A1, An = Wn • V i m i i = 1, 2, …, n-1 thì ho c Ai = WiAi+1 ho c Wi = AiAi+1 • Ví d trên, ta có: A5 = ad ε S5 A4 = b ε S4 A3 = de ε S3 W5 = ad W4 = bad W3= deb A2 = cde ε S2 A1 = bb ε S1 A0 = a W2 = c W1 = bbcde W0 = abb 12 7/2/2010 Huỳnh Văn Kha Tìm dãy mã không gi i ñư c • Ta xây d ng hai dãy, m t dãy b t đ u v i A0W1, dãy kia b t đ u v i W0 • N u Ai = WiAi+1, thêm Wi+1 vào cu i dãy ch a Wi • N u Wi = AiAi+1, thêm Wi+1 vào cu i dãy không ch a Wi • Ti p t c như v y đ n Wn • Ngư i ta ch ng minh đư c r ng hai dãy t o thành như trên là m t, và chính là dãy mã không gi i đư c c n tìm 6
7/2/2010 13 7/2/2010 Huỳnh Văn Kha Tìm dãy mã không gi i ñư c • A0W1 = abbcde W0 = abb • W1 = A1A2 thêm W2 vào W0 • A0W1 = abbcde W0W2 = abbc • A2 = W2A3 thêm W3 vào W0W2 • A0W1 = abbcde W0W2W3 = abbcdeb • W3 = A3A4 thêm W4 vào A0W1 • A0W1W4 = abbcdebad W0W2W3 = abbcdeb • W4 = A4A5 thêm W5 vào W0W2W3 • A0W1W4 = abbcdebad W0W2W3W5 = abbcdebad 14 7/2/2010 Huỳnh Văn Kha • Chú ý: Ta thêm các Wi vào các dãy ng n hơn x1 abc 010 x2 abcd 0001 x3 e 0110 x4 dba 1100 x5 bace 00011 x6 ceac 00110 x7 ceab 11110 x8 eabd 101011 7