Bài giảng Lý thuyết thông tin - Chương 4: Mã sửa sai (Phần 3)
14 trang
3680
Bạn đang xem tài liệu "Bài giảng Lý thuyết thông tin - Chương 4: Mã sửa sai (Phần 3)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_ly_thuyet_thong_tin_chuong_4_ma_sua_sai_phan_3.pdf
Nội dung text: Bài giảng Lý thuyết thông tin - Chương 4: Mã sửa sai (Phần 3)
- Ch ươ ng 4: Mã s a sai 4.3 Ch n trên và d ư i cho kh năng s a sai c a b mã ki m tra ch n l
- 2 Hu ỳnh V ăn Kha 9/30/2010 Kh năng s a sai • Nh ư đã bi t, s t mã tăng s làm gi m kh năng s a sai c a b mã. Ta s c g ng đ nh l ư ng m i liên h này. • Trong ph n này, ta gi i quy t bài tốn sau: c n ch n ma tr n ki m tra ch n l nh ư th nào đ b mã thu đ ư c s a sai đ ư c e bit tr l i. • Xét tr ư ng h p e = 1 . Ta xây d ng b mã s a sai đư c 1 bit. • N u bit sai v trí th j thì vector hi u ch nh tươ ng ng là c t th j c a ma tr n ch n l .
- 3 Hu ỳnh V ăn Kha 9/30/2010 Kh năng s a sai • Ta ch n ma tr n ch n l sao cho n c t c a nĩ khác nhau đơi m t (và khác 0). • Khi đĩ m i dãy sai m t bit đ u cĩ các vector hi u ch nh khác nhau. Do đĩ m i l i sai 1 bit đ u s a sai đ ư c. • Ví d , n u n = 7, k = 4 , ta cĩ th ch n ma tr n ch n l nh ư sau:
- 4 Hu ỳnh V ăn Kha 9/30/2010 ð nh lý 4.9 B mã ki m tra ch n l xác đ nh b i ma tr n A s s a sai đ ư c e bit tr l i n u và ch n u m i t p 2e c t c a A đ u đ c l p tuy n tính. Ch ứng minh: Theo đ nh lý 4.8, m i l i sai khơng quá e bit s đư c làm đúng n u và ch n u các m u sai ≤ e bit cĩ các vector hi u ch nh phân bi t nhau. Nghĩa là n u và ch n u khơng cĩ t h p tuy n tính c a e (ho c ít hơn) c t nào trong A b ng v i m t t h p tuy n tính khác (cũng c a e c t (ho c ít h ơn) trong A). Đi u này t ươ ng đ ươ ng v i m i t p 2e c t c a A đ u ph i đ c l p tuy n tính.
- 5 Hu ỳnh V ăn Kha 9/30/2010 Ví d • Cĩ th th y m i t p g m 4 c t c a A là đ c l p tuy n tính. B mã ng v i A cĩ th s a sai 2 bit • Tuy nhiên: c(r1)+ c(r8)+ c(r9)= c(r3)+ c(r4)+ c(r6) • Do đĩ các dãy sai ba c t 1, 8, 9 và các dãy sai ba c t 3, 4, 6 cĩ cùng vector hi u ch nh • Nh ư v y sai 3 bit ch ưa ch c s a đ ư c.
- 6 Hu ỳnh V ăn Kha 9/30/2010 Ch n trên và d ư i cho kh năng s a sai c a b mã ki m tra ch n l • Gi s ta c n xây d ng b mã ki m tra ch n l s a sai đ ư c e bit (chi u dài t mã n c đ nh) • V n đ đ t ra là c n bao nhiêu bit ki m tra đ xây d ng b mã nh ư v y • Ta mu n càng ít bit ki m tra càng t t. Do s bit ki m tra càng ít thì s bit thơng tin càng l n và ta cĩ càng nhi u t mã • T ng quát thì khơng th xác đ nh chính xác s bit ki m tra c c ti u. Nh ưng ta cĩ th ư c l ư ng ch n dư i và ch n trên nh ư các đ nh lý sau
- 7 Hu ỳnh V ăn Kha 9/30/2010 ð nh lý 4.10 (Ch n d ư i Hamming cho s bit ki m tra ) S bit ki m tra trong m t b mã ch n l s a sai đư c e bit c n th a: Trong đĩ: n = chi u dài t mã m = s bit ki m tra = n k
- 8 Hu ỳnh V ăn Kha 9/30/2010 Ch ng minh đ nh lý 4.10 • Đ b mã ki m tra ch n l s a sai đ ư c e bit tr l i thì các l i sai e bit ho c ít h ơn cĩ các vector hi u ch nh khác nhau đơi m t. • N u t mã cĩ chi u dài n thì s l i sai đúng i bit là t h p ch p i c a n. • S các vector hi u ch nh là 2m. • Do đĩ đ các vector hi u ch nh là duy nh t cho m i l i sai e bit tr l i thì:
- 9 Hu ỳnh V ăn Kha 9/30/2010 Chú ý • Ch n d ư i Hamming cho s bit ki m tra chính là ch n trên Hamming cho s t mã (đ nh lý 4.3) • Ch n d ư i Hamming là đi u ki n c n nh ưng khơng đ cho vi c xây d ng b mã ki m tra ch n l s a sai đ ư c e bit. • Nĩi cách khác, n u g i m0 là s nguyên nh nh t th a đ nh lý 4.10 (v i n và e cho tr ư c) thì cĩ th khơng cĩ b mã nào s a sai đ ư c e bit mà ch s d ng cĩ m0 bit ki m tra. • Ví d v i n = 10, e = 2 ta cĩ m0 = 6. Tuy nhiên khơng cĩ b mã ch n l nào s a sai đ ư c 2 bit mà s d ng ít h ơn 7 bit ki m tra
- 10 Hu ỳnh V ăn Kha 9/30/2010 ð nh lý 4.11 (Đi u ki n Varsharmov Gilbert Sacks) M t b mã ki m tra ch n l s a sai đ ư c e bit v i chi u dài t mã là n cĩ th xây d ng đ ư c n u s bit ki m tra m th a đi u ki n: Đây là ch n trên cho s bit ki m tra c n thi t cho vi c x y d ng b mã ch n l s a sai e bit
- 11 Hu ỳnh V ăn Kha 9/30/2010 Chú ý • Đi u ki n trong đ nh lý 4.11 là đi u ki n đ nh ưng khơng c n. • Nĩi cách khác, c đ nh n và e, g i m1 là s nguyên dươ ng nh nh t th a đ nh lý 4.11. Thì theo đ nh lý 4.11 cĩ th xây d ng b mã s a sai e bit s d ng m1 bit ki m tra. Tuy nhiên, trong m t s tr ư ng h p, ta cũng cĩ th xây d ng b mã s a sai e bit mà ch s d ng ít h ơn m1 bit ki m tra. • Ví d v i n = 10, e = 2 , ta cĩ m1 = 8 . Tuy nhiên ta cĩ th xây d ng b mã s a sai 2 bit mà ch s d ng 7 bit ki m tra nh ư ví d sau đ nh lý 4.9
- 12 Hu ỳnh V ăn Kha 9/30/2010 Ch ng minh đ nh lý 4.11 • Ta s xây d ng b mã th a yêu c u b ng cách ch ra các c t c(r1), c(r2), , c(rn) c a ma tr n ch n l tươ ng ng. • Các c t này c n ph i th a đi u ki n: m i t p g m 2e c t đ u đ c l p tuy n tính. • Đ u tiên, ch n c(r1) khác 0 tùy ý • Ch n c(r2) sao cho c(r2) ≠ 0, c(r2) ≠ c(r1) • Ch n c(r3) sao cho c(r3) ≠ 0, c(r3) ≠ c(r1), c(r3) ≠ c(r2), c(r3) ≠ c(r1)+ c(r2)
- 13 Hu ỳnh V ăn Kha 9/30/2010 Ch ng minh đ nh lý 4.11 • Gi s đã ch n đ ư c c(r1), c(r2), , c(rn 1), ta ch n c(rn) th a:
- 14 Hu ỳnh V ăn Kha 9/30/2010 Ch ng minh đ nh lý 4.11 • S các t h p nĩi trên, khơng v ư t quá: (Chú ý: khơng nh t thi t t t c các t h p nĩi trên phân bi t nhau, do đĩ s t h p cĩ th nh hơn) • Nh ư v y, n u t ng trên ≤ 2m thì hi n nhiên ta ch n đ ư c c(rn). Và do đĩ đ nh lý đ ư c ch ng minh.
