Giáo trình lý thuyết thông tin | Học viện công nghệ bưu chính viễn thông
Giáo trình lý thuyết thông tin | Học viện công nghệ bưu chính viễn thông Tài liệu gồm 95 trang, giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!
Môn: Lý thuyết thông tin (ELE1319)
Trường: Học viện Công Nghệ Bưu Chính Viễn Thông
Thông tin:
Tác giả:
Tài liệu liên quan:
Preview text:
Giáo trình: Lý thuyết thông tin. M C L C
GI I THI U T NG QUAN.............................................................................................................6 1.
M C ĐÍCH ...........................................................................................................................6 2.
YÊU C U .............................................................................................................................6 3.
N I DUNG C T LÕI...........................................................................................................7 4.
K T TH C TIÊN QUY T ..................................................................................................7 5.
TÀI LI U THAM KH O.....................................................................................................8 6. PH
NG PHÁP H C T P.................................................................................................8 CH
NG 1: GI I THI U ...............................................................................................................9 1.
M c tiêu.................................................................................................................................9 2.
Đ i t ng nghiên c u............................................................................................................9 3.
Mô hình lý thuy t thông tin theo quan đi m Shannon ........................................................10 4. L
ng tin bi t và ch a bi t .................................................................................................10 5. Ví d v l
ng tin bi t và ch a bi t ....................................................................................10 6.
Đ nh lý c s c a kỹ thu t truy n tin ..................................................................................11 7.
Mô t tr ng thái truy n tin có nhi u ....................................................................................11 8.
Minh h a kỹ thu t gi m nhi u.............................................................................................12 9.
Chi phí ph i tr cho kỹ thu t gi m nhi u ............................................................................13 10. Khái ni m v dung l
ng kênh truy n ............................................................................13 11.
V n đ sinh mã ................................................................................................................13 12.
V n đ gi i mã.................................................................................................................13 CH NG 2: Đ ĐO L
NG TIN ...............................................................................................15
BÀI 2.1: ENTROPY .......................................................................................................................15 1.
M c tiêu...............................................................................................................................15 2.
Ví d v entropy ..................................................................................................................15 3. Nh n xét v đ đo l
ng tin ................................................................................................15 4.
Khái ni m entropy ...............................................................................................................16 5.
Entropy c a m t s ki n......................................................................................................16 6.
Entropy c a m t phân ph i .................................................................................................16 7.
Đ nh lý d ng gi i tích c a Entropy......................................................................................16 8.
Ví d minh h a ....................................................................................................................17 9.
Bài toán v cây tìm ki m nh phân-Đ t v n đ ...................................................................17 10.
Bài toán v cây tìm ki m nh phân - Di n gi i................................................................17 11.
Bài t p .............................................................................................................................18
BÀI 2.2: CÁC TÍNH CH T C A ENTROPY .............................................................................19 1.
M c tiêu: .............................................................................................................................19 2.
Các tính ch t c b n c a Entropy........................................................................................19 3.
Minh h a tính ch t 1 và 2....................................................................................................19 4.
Minh h a tính ch t 3 và 4....................................................................................................19 5.
Đ nh lý c c đ i c a entropy ................................................................................................20 6.
Ch ng minh đ nh lý c c đ i c a Entropy............................................................................20 7.
Bài t p .................................................................................................................................21
BÀI 2.3: ENTROPY C A NHI U BI N .....................................................................................22 1.
M c tiêu...............................................................................................................................22 2.
Đ nh nghĩa Entropy c a nhi u bi n.....................................................................................22 3.
Ví d Entropy c a nhi u bi n..............................................................................................22 4.
Đ nh nghĩa Entropy có đi u ki n.........................................................................................22
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 1
Giáo trình: Lý thuyết thông tin. 5.
Ví d Entropy có đi u ki n .................................................................................................23 6.
Quan h gi a H(X,Y) v i H(X) và H(Y) khi X, Y đ c l p.................................................23 7.
Quan h gi a H(X,Y) v i H(X) và H(Y) khi X, Y t
ng quan ..........................................24 8.
Bài t p .................................................................................................................................25
BÀI 2.4: MINH H A CÁC ENTROPY ........................................................................................26 1.
M c tiêu...............................................................................................................................26 2.
Yêu c u c a bài toán ...........................................................................................................26 3.
Xác đ nh các phân ph i ng u nhiên c a bài toán ................................................................26 4.
Minh h a Entropy H(X), H(Y) và H(X,Y)..........................................................................27 5.
Minh h a Entropy H(X/Y) và H(Y/X) ................................................................................27 6.
Minh h a quan h gi a các Entropy....................................................................................27 BAI 2.5: ĐO L
NG TIN (MESURE OF INFORMATION) ......................................................28 1.
M c tiêu...............................................................................................................................28 2.
Đ t v n đ bài toán..............................................................................................................28 3.
Xác đ nh các phân ph i c a bài toán...................................................................................28 4.
Nh n xét d a theo entropy ..................................................................................................28 5.
Đ nh nghĩa l ng tin ...........................................................................................................29 6.
Bài t p .................................................................................................................................29 CH NG 3: SINH MÃ TÁCH Đ
C (Decypherable Coding)...................................................31
BÀI 3.1: KHÁI NI M V MÃ TÁCH Đ
C..............................................................................31 1.
M c tiêu...............................................................................................................................31 2.
Đ t v n đ bài toán sinh mã ................................................................................................31 3.
Khái ni m v b ng mã không tách đ
c .............................................................................32 4. B ng mã tách đ
c..............................................................................................................32 5.
Khái ni m b ng mã t c th i ................................................................................................33 6.
Gi i thu t ki m tra tính tách đ
c c a b ng mã..................................................................33 7.
Bài toán 1- yêu c u..............................................................................................................33 8.
Bài toán 1 - Áp d ng gi i thu t ...........................................................................................34 9.
Bài toán 2 ............................................................................................................................34 10.
Bài t p .............................................................................................................................35
BÀI 3.2: QUAN H GI A MÃ TÁCH Đ
C VÀ Đ DÀI MÃ................................................36 1.
M c tiêu...............................................................................................................................36 2.
Đ nh lý Kraftn(1949)...........................................................................................................36 3.
Đ nh nghĩa cây b c D c k. .................................................................................................36 4.
V n đ sinh mã cho cây b c D c k ....................................................................................37 5.
Ch ng minh đ nh lý Kraft (Đi u ki n c n) .........................................................................37 6.
Ch ng minh đ nh lý Kraft (Đi u ki n đ )...........................................................................38 7.
Ví d minh h a đ nh lý Kraft ..............................................................................................38 8.
Bài t p .................................................................................................................................39
BÀI 3.3: TÍNH T I U C A Đ DÀI MÃ..................................................................................40 1.
M c tiêu...............................................................................................................................40 2.
Đ nh lý Shannon (1948) ......................................................................................................40 3.
B ng mã t i u tuy t đ i .....................................................................................................40 4. B ng mã t i u t
ng đ i....................................................................................................41 5.
Đi u ki n nh n bi t m t b ng mã t i u .............................................................................41 6.
Đ nh lý Huffman .................................................................................................................41 7. Ph
ng pháp sinh mã Huffman...........................................................................................42 8. Minh h a ph
ng pháp sinh mã Huffman ..........................................................................42 9.
Nh n xét tính t i u c a b ng mã Huffman ........................................................................43 10.
Bài t p .............................................................................................................................43
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 2
Giáo trình: Lý thuyết thông tin. CH
NG 4: KÊNH TRUY N ......................................................................................................45
BÀI 4.1: KÊNH TRUY N R I R C KHÔNG NH
...................................................................45 1.
M c tiêu...............................................................................................................................45 2.
Gi i thi u.............................................................................................................................45 3.
Mô hình v t lý .....................................................................................................................45 4.
Mô hình toán h c.................................................................................................................46 5.
Ví d xác đ nh phân ph i đ u nh n.....................................................................................47 6. L
ng tin trên kênh truy n..................................................................................................47 7.
Đ nh nghĩa dung l ng kênh truy n....................................................................................48
BAI 4.2: CÁC D NG KÊNH TRUY N........................................................................................49 1.
M c tiêu...............................................................................................................................49 2. Hi u đ nh lý v dung l
ng kênh truy n,Kênh truy n không m t tin.................................49 3.
Kênh truy n xác đ nh ..........................................................................................................49 4.
Kênh truy n không nhi u ....................................................................................................50 5. Kênh truy n không s d ng đ
c. ......................................................................................50 6.
Kênh truy n đ i x ng..........................................................................................................50 7.
Xây d ng công th c tính dung l
ng kênh truy n đ i x ng ..............................................51 8.
Đ nh lý v dung l ng kênh truy n.....................................................................................52 9.
Bài t p .................................................................................................................................52 BÀI 4.3: L
C Đ GI I MÃ .......................................................................................................53 1.
M c tiêu...............................................................................................................................53 2.
Đ t v n đ bài toán gi i mã.................................................................................................53 3.
Ví d bài toán gi i mã .........................................................................................................53 4.
Các khái ni m c b n c a kỹ thu t truy n tin .....................................................................54 5.
Ví d minh h a các khái ni m c b n .................................................................................54 6.
Các d ng sai s c b n ........................................................................................................55 7. Ph ng pháp xây d ng l
t đ gi i mã t i u....................................................................55 8. Minh h a xây d ng l
c đ gi i mã t i u .........................................................................56 9.
Minh h a cách tính các sai s ..............................................................................................57 10.
Bài t p 1 ..........................................................................................................................58 11.
Bài T p 2 .........................................................................................................................58 CH
NG 5: S A L I...................................................................................................................59
BÀI 5.1: NGUYÊN LÝ KHO NG CÁCH NH NH T HAMMING .........................................59 1.
M c tiêu: .............................................................................................................................59 2.
Kho ng cách Hamming .......................................................................................................59 3.
Kênh truy n đ i x ng nh phân và l
c đ gi i mã t i u..................................................59 4.
Ví d kênh truy n đ i x ng nh phân..................................................................................60 5.
Quan h gi a xác su t gi i mã và kho ng cách Hamming..................................................60 6.
Nguyên lý Hamming ...........................................................................................................60 7.
Bài t p .................................................................................................................................61
BÀI 5.2: B Đ V T S A L I VÀ C N HAMMING ...........................................................62 1.
M c tiêu...............................................................................................................................62 2.
B đ v t s a l i...............................................................................................................62 3.
Ch ng minh và minh h a b đ ..........................................................................................62 4.
C n Hamming. ....................................................................................................................63 5.
Phân các d ng l i.................................................................................................................64 6.
Bài t p .................................................................................................................................64
BÀI 5.3: MÃ KI M TRA CH N L .............................................................................................64 1.
M c tiêu: .............................................................................................................................64 2.
B mã ki m tra ch n l ........................................................................................................65
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 3
Giáo trình: Lý thuyết thông tin. 3. Ph
ng pháp ki m tra ch n l .............................................................................................65 4. Ph
ng pháp sinh mã ki m tra ch n l ...............................................................................66 5.
Ví d sinh mã ki m tra ch n l ............................................................................................66 6.
Đ nh lý quan h gi a đ dài mã n, s bit ki m tra m và s l i t s a e ..............................67 7.
Ví d tìm m nh nh t t n và e...........................................................................................68 8.
Ví d tìm e l n nh t t m và n.............................................................................................68 9.
Bài t p .................................................................................................................................68
BÀI 5.4: NHÓM C NG TÍNH VÀ B T MÃ CH N L .........................................................69 1.
M c tiêu...............................................................................................................................69 2.
Khái ni m nhóm c ng tính. .................................................................................................69 3.
Tính ch t c a b mã ch n l ................................................................................................69 4.
Ví d minh h a ....................................................................................................................70 5. Ph
ng pháp sinh mã ki m tra ch n l nhanh.....................................................................71 6.
Ví d sinh mã ki m tra ch n l nhanh .................................................................................71 7.
Bài t p .................................................................................................................................72 BÀI 5.5: L
C Đ S A L I T I U.........................................................................................73 1.
M c tiêu...............................................................................................................................73 2.
Đ t v n đ ............................................................................................................................73 3.
Đ nh nghĩa Hi p h p ...........................................................................................................73 4. L
c đ s a l i theo các hi p h p ......................................................................................74 5. L
c đ s a l i thong qua b l i.........................................................................................74 6. Ví d minh h a l
c đ s a l i 1 bit...................................................................................74 7. Ví d minh h a l
c đ s a l i 2 bit...................................................................................75 8. Ví d minh h a l
c đ s a l i 3 bit...................................................................................76 9.
Xác su t truy n đúng...........................................................................................................76 10.
Bài t p .............................................................................................................................76
BÀI 5.6: MÃ HAMMING ..............................................................................................................76 1.
M c tiêu...............................................................................................................................76 2.
Mã Hammin.........................................................................................................................77 3.
Tính ch t..............................................................................................................................77 4.
Ví d minh h a ....................................................................................................................77 5.
Bài t p .................................................................................................................................78
BÀI 5.7: THANH GHI LÙI T NG B
C ...................................................................................79 1.
M c tiêu...............................................................................................................................79 2.
Đ t v n đ ............................................................................................................................79 3.
Bi u di n v t lý c a thanh ghi .............................................................................................79 4.
Bi u di n toán h c c a thanh ghi ........................................................................................80 5. Ví d thanh ghi lui t ng b
c .............................................................................................80 6.
Chu kỳ c a thanh ghi...........................................................................................................81 7.
Ví d tìm chu kỳ c a thanh ghi ...........................................................................................81 8.
Bài t p .................................................................................................................................82
BÀI 5.8: MÃ XOAY VÒNG ..........................................................................................................82 1.
M c tiêu...............................................................................................................................82 2.
Ma tr n ki m tra ch n l mã xoay vòng ..............................................................................83 3.
Đ nh nghĩa mã xoay vòng ...................................................................................................83 4. Ph
ng pháp sinh nhanh b mã xoay vòng.........................................................................83 5.
Ví d sinh nhanh b mã xoay vòng.....................................................................................84 6.
Bài t p .................................................................................................................................85
BÀI 5.9: ĐA TH C Đ C TR NG C A THANH GHI ...............................................................86 1.
M c tiêu...............................................................................................................................86
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 4
Giáo trình: Lý thuyết thông tin. 2.
Đ nh nghĩa đa th c đ c tr ng c a thanh ghi .......................................................................86 3.
Quan h gi a chu kỳ n, đa th c đăc tr ng và đa th c (xn + 1)............................................86 4.
Th t c sinh thanh ghi lùi t ng b
c ..................................................................................87 5.
Ví d minh h a ....................................................................................................................87 6.
Bài t p .................................................................................................................................87 Bài 5.10: PH
NG PHÁP SINH MÃ XOAY VÒNG ..................................................................88 1.
M c tiêu...............................................................................................................................88 2.
Đ t v n đ ............................................................................................................................88 3. Ph
ng pháp sinh b ng mã xoay vòng................................................................................88 4.
Ví d minh h a 1 .................................................................................................................89 5.
Ví d minh h a 2 .................................................................................................................89 6.
Ví d minh h a 3 .................................................................................................................90 7.
B ng li t kê m t s đa th c đ c tr ng.................................................................................90 8.
Bài t p .................................................................................................................................90
BÀI T P T NG H P ....................................................................................................................91 1.
M c tiêu...............................................................................................................................91 2.
Bài 1 ....................................................................................................................................91 3.
Bài 2 ....................................................................................................................................91 4.
Bài 3 ....................................................................................................................................92 5.
Bài 4 ....................................................................................................................................93
TÀI LI U THAM KH O...............................................................................................................95
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 5
Giáo trình: Lý thuyết thông tin. GI I THI U T NG QUAN
GIÁO TRÌNH LÝ THUY T THÔNG TIN M C ĐÍCH
Giáo trình này s cung c p cho ng i đ c nh ng kh i ki n th c c b n c a lý thuy t thông tin nh : Đ do l
ng tin (Measure of Information), Sinh mã tách đ c (Decypherable Coding),
Kênh truy n tin r i r c không nh (Discrete Memoryless Channel) và S a l i trên kênh truy n (Error Correcting Codings).
• Liên quan đ n Đ đo l ng tin, giáo trình s trình bày các khái ni m c b n v thông tin,
entropy, m t s công th c, tính ch t, các đ nh lý quan tr ng c a entropy và cách tính l ng tin.
• V Sinh mã tách đ c, giáo trình s gi i thi u đ n ng i h c các v n đ v yêu c u c a
bài toán sinh mã, gi i mã duy nh t, cũng nh mã t c th i và gi i thu t ki m tra mã tách
đ c. Các đ nh lý quan tr ng đ c đ c p trong n i dung này là: Đ nh lý Kraft (1949),
Đ nh lý Shannon (1948) và Đ nh lý sinh mã Huffman.
• V kênh truy n tin r i r c không nh , giáo trình s gi i thi u mô hình kênh truy n theo
2 khía c nh v t lý và toán h c. Các khái ni m v dung l
ng kênh truy n, phân l p kênh truy n, đ nh lý v dung l
ng kênh truy n, cũng nh các khái ni m trong kỹ thu t truy n tin và ph ng pháp xây d ng l c đ gi i mã t i u cũng đ c trình bày trong môn h c này.
• V n đ S a l i (hay x lý mã sai) trên kênh truy n là m t v n đ r t quan tr ng và
đ c quan tâm nhi u trong môn h c này. Các n i dung đ c gi i thi u đ n các b n s là
Nguyên lý Kho ng cách Hamming, các đ nh lý v C n Hamming, ph ng pháp ki m tra ch n l , các l
c đ s a l i, B ng mã Hamming và B ng mã xoay vòng.
H n n a, h u h t các v n đ nêu trên đ u đ c đ a vào n i dung gi ng d y các b c Đ i h c
c a m t s ngành trong đó có ngành Công ngh thông tin. Do đó, đ có m t tài li u ph c v
công tác gi ng d y c a giáo viên cũng nh vi c h c t p và nghiên c u c a sinh viên, chúng tôi
m nh d n biên so n giáo trình này nhằm giúp cho sinh viên có m t tài li u t h c và nghiên c u m t cách hi u qu . YÊU C U
Sau khi h c xong môn này, sinh viên ph i có đ c nh ng kh năng sau:
• Hi u các khái ni m v v thông tin, Entropy, Entropy c a m t phân ph i, Entropy c a
nhi u phân ph i, Entropy có đi u ki n, Đ đo l
ng tin. V n d ng gi i quy t các bài toán v xác đ nh l ng tin.
• Bi t khái ni m v mã tách đ c, mã không tách đ c, b ng mã t i u. Hi u Đ nh lý Kraft
(1949), Đ nh lý Shannon (1948), Đ nh lý sinh mã Huffman và ph ng pháp sinh mã
Huffman. V n d ng đ sinh b ng mã tách đ c t i u, nh n bi t đ c b ng mã nh th
nào là b ng mã t i u và có th v n d ng đ vi t các ch
ng trình sinh mã, gi i mã (hay vi t ch
ng trình nén và gi i nén). T đây, các sinh viên có th t nghiên c u các lo i
b ng mã khác đ v n d ng cho vi c mã hóa và b o m t thông tin m t cách hi u qu .
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 6
Giáo trình: Lý thuyết thông tin.
• Bi t các khái ni m v kênh truy n tin r i r c không nh , dung l ng kênh truy n và phân
l p kênh truy n. Hi u đ nh lý v dung l ng kênh truy n, ph ng pháp xây d ng l c đ
gi i mã t i u và cách tính xác su t truy n sai trên kênh truy n.
• Bi t các khái ni m v kho ng cách Hamming, nguyên lý kho ng cách Hamming, các đ nh lý v C n Hamming, ph
ng pháp ki m tra ch n l , các l c đ s a l i, B ng mã
Hamming và B ng mã xoay vòng.
• V n d ng các ki n th c h c đ c đ thi t k m t h th ng truy n nh n d li u v i quy
trình c b n: mã hóa, gi i mã và b o m t thông tin.
Lý thuy t thông tin cũng là m t trong các môn h c khó c a ngành Công ngh thông tin vì nó
đòi h i ng i h c ph i có ki n th c c b n v toán và xác su t th ng kê. Do đó, đòi h i ng i
h c ph i t b sung các ki n th c c b n v toán và xác su t th ng kê cho mình (n u thi u),
tham gia l p h c đ y đ và làm các bài t p theo yêu c u c a môn h c thì m i ti p thu ki n
th c môn h c m t cách hi u qu . N I DUNG C T LÕI Giáo trình g m 5 ch ng đ
c trình bày trong 45 ti t gi ng cho sinh viên chuyên ngành Công
ngh thông tin, trong đó có kho ng 30 ti t lý thuy t và 15 ti t bài t p mà giáo viên s h ng d n cho sinh viên trên l p. Ch
ng 1: Gi i thi u. Chương này trình bày các nội dung có tính tổng quan về môn học bao
gồm: các đối tượng nghiên cứu, mô hình lý thuyết thông tin theo quan điểm của nhà toán học
Shannon, khái niệm về lượng tin biết và chưa biết, định lý cơ bản của kỹ thuật truyền tin. Ch ng 2: Đ đo l
ng tin. Chương này trình bày các vấn đề cơ bản về entropy, các tính chất
của entropy, entropy của nhiều biến, entropy có điều kiện, các định lý về quan hệ giữa các
entropy và lượng tin của một sự kiện. Ch ng 3: Sinh mã tách đ
c. Nội dung chính của chương này bao gồm các khái niệm về mã
tách được, quan hệ giữa mã tách được và độ dài mã, tính tối ưu của độ dài mã. Ch
ng 4: Kênh truy n. Các nội dung được trình bày trong chương này bao gồm khái niệm về
kênh truyền tin rời rạc không nhớ, các mô hình truyền tin ở khía cạnh vật lý và toán học, dung
lượng trên kênh truyền, phân lớp các kênh truyền. Phương pháp xây dựng lược đồ giải mã tối ưu
và cách tính xác suất truyền sai cũng được giới thiệu trong chương này. Ch
ng 5: S a l i. Chương này trình bày các nội dung cốt lõi sau: khái niệm về khoảng cách
Hamming, nguyên lý khoảng cách nhỏ nhất Hamming, bổ đề về tự sửa lỗi và định lý Cận
Hamming. Chương này cũng giới thiệu về bộ mã kiểm tra chẵn lẻ, phương pháp kiểm tra chẵn lẻ,
lược đồ sửa lỗi tối ưu, mã Hamming và mã xoay vòng. K T TH C TIÊN QUY T
Đ h c t t môn h c này, đòi h i sinh viên ph i nắm v ng các môn h c có liên quan nh : xác su t
th ng kê, đ i s boole (phép toán Modulo 2 và đa th c nh phân). Các môn h c có liên quan và có
th tham kháo thêm nh kỷ thu t s , h đi u hành, m ng máy tính.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 7
Giáo trình: Lý thuyết thông tin. TÀI LI U THAM KH O
1. David J.C. Mackey, Information Theory, Infernce, and Learning Algorithms, CamBridge University Express-2003.
2. G.J.ChaiTin, Algorithmic Information Theory, CamBridge University Express-1992.
3. Sanford Goldman, Information Theory.
4. http://www.inference.phy.cam.ac.uk/mackay/info-theory/course.html.
5. http://en.wikipedia.org/wiki/Information_theory.
6. http://www-2.cs.cmu.edu/~dst/Tutorials/Info-Theory/.
7. http://cscs.umich.edu/~crshalizi/notebooks/information-theory.html.
8. http://www.lecb.ncifcrf.gov/~toms/paper/primer/primer.pdf.
9. http://www.cs.ucl.ac.uk/staff/S.Bhatti/D51-notes/node27.html.
10. http://guest.engelschall.com/~sb/hamming/.
11. http://www2.rad.com/networks/1994/err_con/hamming.htm PH NG PHÁP H C T P
Đ ph c v cho m c tiêu nâng cao kh năng t h c t p và t nghiên c u c a sinh viên, giáo trình này đ
c biên so n cùng v i các giáo trình khác thu c chuyên ngành Công ngh thông tin c a
Khoa Công ngh thông tin và Truy n thông – Đ i H c C n Th theo d án ASVIET002CNTT “Tăng c
ng hi u qu đào t o và năng l c đào t o c a sinh viên khoa Công ngh Thông tin-
Đ i h c C n Th ”. Chúng tôi đã c gắng trình bày giáo trình này m t cách có h th ng các n i dung theo b c c các ch
ng ng v i các kh i ki n th c nêu trên, m i ch ng đ c đ c trình
bày theo b c c c a các bài h c và m i bài h c gi i thi u đ n ng
i h c m t v n đ nào đó trong
s các v n đ c a m t kh i ki n th c t ng ng v i m t ch
ng. Khi h c xong các bài h c c a m t ch ng, ng
i h c s có m t kh i ki n th c c n thi t t
ng ng cho môn h c. N i dung c a các bài h c đ u đ c đ a vào các ví d đ ng
i h c d hi u, tùy theo t ng v n đ mà ng i h c
c n ph i h c và nghiên c u trong th i l
ng t 1 đ n 2 ti t t h c cho m t bài h c trong m t ch
ng. Nh v y, đ h c t t môn h c này, tr c h t sinh viên c n ph i:
• H c đ y đ các môn h c tiên quy t, b sung nh ng ki n th c c b n v toán và xác su t th ng kê (n u thi u).
• H c và nghiên c u kỹ t ng ch ng theo trình t các ch ng đ c trình bày trong giáo trình này. Trong t ng ch ng, h c các bài theo th t đ
c trình bày, sau m i bài ph i làm
bài t p đ y đ (n u có).
• Tham gia l p đ y đ , th o lu n các v n đ t n t i ch a hi u trong quá trình t h c.
• Sau m i ch ng h c, ph i nắm v ng các khái ni m, các đ nh nghĩa, các công th c tính
toán và v n d ng gi i các bài toán có tính ch t t ng h p đ c gi i thi u cu i ch ng.
• V n d ng ki n th c có đ c sau khi h c xong các ch ng đ gi i m t s bài t p t ng h p
cu i giáo trình, t đó giúp cho ng
i h c hi u sâu h n v môn h c và có th gi i quy t các v n đ t ng t trong th c t .
Vi c cho ra đ i m t giáo trình v i nh ng m c đích nh trên là không đ n gi n khi kh năng và kinh nghi m c a ng
i so n còn có h n, nhi u khái ni m, thu t ng dùng trong giáo trình ch a
đ c đ nh nghĩa m t cách chính th ng. Vì v y giáo trình này chắc không tránh kh i nh ng khi m khuy t, r t mong nh n đ
c s góp ý c a các đ ng nghi p và ng i đ c.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 8
Giáo trình: Lý thuyết thông tin. CH NG 1: GI I THI U 1: M c tiêu
Sau khi hoàn t t bài h c này b n có th bi t: - Đ i t ng nghiên c u,
- Mô hình lý thuy t thông tin theo quan đi m Shannon, - Các khái ni m v L ng tin bi t và l ng tin ch a bi t,
- Đ nh lý c s c a kỹ thu t truy n tin, - Khái ni m chung v dung l ng kênh truy n,
- V n đ sinh mã và gi i mã. Đ i t ng nghiên c u
Lý thuy t th ng kê v thông tin đ c xây d ng trên hai h
ng khác nhau b i hai nhà toán h c
Shannon (1948) và Wiener (1949). Lý thuy t thông tin nghiên c u quá trình x lý tín hi u nh sau:
Đ u vào (input): nh n tín hi u t m t lĩnh v c c th , t c là tín hi u xu t hi n theo các ký hi u (symbol) t m t t p h p cho tr
c và theo phân ph i xác su t đã bi t. Tín hi u đ
c truy n đi trên kênh truy n (channel) và có th b nhi u cũng theo m t phân ph i
xác su t nào đó. Kênh truy n có th đ c hi u d i hai nghĩa: D
i nghĩa v t lý: kênh truy n là m t h th ng truy n tín hi u (dây d n, m ch, sóng, ...) và gây nhi u tùy thao ch t l ng c a h th ng. D
i nghĩa toán h c: kênh truy n là các phân ph i xác su t xác đ nh trên l p các tín hi u đang xét
đ u nh n tín hi u (output).
đ u ra (output): d ng l i tín hi u chân th t nh t có th có so v i tín hi u đ u vào.
Shannon xây d ng mô hình lý thuy t thông tin trên c s gi i quy t bài toán: sinh mã đ dài t i
u khi nh n tín hi u đ u vào. Tín t i u đ c xét trên 3 y u t sau:
Phân ph i xác su t c a s xu t hi n c a các tín hi u.
Tính duy nh t c a mã và cho phép t đi u chỉnh mã sai n u có v i đ chính xác cao nh t. Gi i mã
đ ng th i t đ ng đi u chỉnh mã ho c xác đ nh đo n mã truy n sai.
Trong khí đó, Wiener l i nghiên c u ph
ng pháp x lý tín hi u đ u ra: c l ng t i u chu i
tín hi u so v i chính nó khi nh n đ u vào không qua quá trình sinh mã. Nh v y ph ng pháp Wiener đ c áp d ng trong nh ng tr ng h p con ng i không ki m soát đ c quá trình truy n
tín hi u. Môn “x lý tín hi u” đã đ c p đ n v n đ này.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 9
Giáo trình: Lý thuyết thông tin.
Mô hình lý thuy t thông tin theo quan đi m Shannon Lý thuy t thông tin đ
c xét đây theo quan đi m c a Shannon. Đ i t ng nghiên c u là m t h
th ng liên l c truy n tin (communication system) nh s đ d i đây: Ngu n Mã hóa Kênh Gi i mã Nh n Nhi u B ch cái B ch cái Di n gi i:
- Ngu n (source) thông tin còn g i là thông báo c n đ c truy n đ u vào (Input).
- Mã hóa (encode) là b sinh mã. ng v i m t thông báo, b sinh mã s gán cho m t đ i t
ng (object) phù h p v i kỹ thu t truy n tin. Đ i t ng có th là:
o Dãy s ngh phân (Digital) d ng: 01010101, cũng gi ng nh mã máy tính.
o Sóng liên t c (Analog) cũng gi ng nh truy n radio. - Kênh (channel) là ph
ng ti n truy n mã c a thông tin. - Nhi u (noise) đ
c sinh ra do kênh truy n tin. Tùy vào ch t l ng c a kênh truy n mà nhi u nhi u hay ít.
- Gi i mã (decode) đ u ra (output) đ a dãy mã tr v d ng thông báo ban đ u v i xác su t
cao nh t. Sau đó thông báo s đ
c chuy n cho n i nh n. Trong s đ trên, chúng ta quan
tâm đ n 2 kh i mã hóa và gi i mã trong toàn b môn h c. L
ng tin bi t và ch a bi t
M t bi n ng u nhiên (BNN) X luôn mang m t l
ng tin nào đó. N u X ch a x y ra (hay ta ch a
bi t c th thông tin v X) thì l
ng tin c a nó là ch a bi t, trong tr ng h p này X có m t l ng tin ch a bi t. Ng
c l i n u X đã x y ra (hay ta bi t c th thông tin v X) thì l ng tin v bi n
ng u nhiên X coi nh đã bi t hoàn toàn, trong tr ng h p này X có m t l ng tin đã bi t.
N u bi t thông tin c a m t BNN X thông qua BNN Y đã x y ra thì ta có th nói: chúng ta chỉ bi t m t ph n l
ng thông tin c a X đó trên c s bi t Y. Ví d v l
ng tin bi t và ch a bi t Ta xét ví d v m t ng
i t ch c trò ch i may r i khách quan v i vi c tung m t đ ng ti n “có
đ u hình – không có đ u hình”. N u ng i ch i ch n m t không có đ u hình thì thắng khi k t
qu tung đ ng ti n là không có đ u hình, ngu c l i thì thua. Tuy nhiên ng i t ch c ch i có th
“ăn gian” bằng cách s d ng 2 đ ng ti n “Th t- Gi ” khác nhau sau: +
Đ ng ti n lo i 1 (hay đ ng ti n th t): đ ng ch t có 1 m t có đ u hình. +
Đ ng ti n lo i 2 (hay đ ng ti n gi ): đ ng ch t, m i m t đ u có 1 đ u hình. M c dù ng
i t ch c ch i có th “ăn gian” nh ng quá trình trao đ i 2 đ ng ti n cho nhau là ng u nhiêu, v y li u ng
i t ch c ch i có th “ăn gian” hoàn toàn đ c không? Hay l ng tin bi t và
ch a bi t c a s ki n l y m t đ ng ti n t 2 đ ng ti n nói trên đ c hi u nh th nào?
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 10
Giáo trình: Lý thuyết thông tin. Ta th xét m t tr ng h p sau: n u ng
i ch i l y ng u nhiên 1 đ ng ti n và sau đó th c hi n vi c tung đ ng ti n l y đ
c 2 l n. Qua 2 l n tung đ ng ti n, ta đ m đ c s đ u hình xu t hi n.
D a vào s đ u hình xu t hi n, ta có th phán đoán đ c ng i t ch c ch i đã l y đ c đ ng ti n nào.
Ch ng h n: N u s đ u hình đ m đ
c sau 2 l n t ng là 1 thì đ ng ti n đã l y đ c là đ ng ti n th t. Ng c l i n u s đ u hình đ m đ
c là 2 thì đ ng ti n đã l y đ
c có th là th t hay cũng có
th là gi . Nh v y, ta đã nh n đ
c m t ph n thông tin v lo i đ ng ti n qua s đ u hình đ m
đ c sau 2 l n tung. Ta có th tính đ c l ng tin đó bằng bao nhiêu? (Việc tính lượng tin này sẽ
được thảo luận sau). D i đây là m t s b ng phân ph i c a bài toán trên:
G i BNN X v lo i đ ng ti n (X=1 n u l y đ
c đ ng ti n lo i 1 và X=1 n u l y đ c đ ng ti n lo i 2 đ c l y).
Khi đó phân ph i c a X có d ng: X 1 2 P 0.5 0.5
Đ t BNN Y là BNN v s đ u hình đ m đ c sau 2 l n tung. Khi đó ta có th xác đ nh đ c phân
ph i c a Y v i đi u ki n x y ra c a X trong 2 tr ng h p sau.
Phân ph i c a Y khi bi t X=1 có d ng: Y/X=1 0 1 2 P 0.25 0.5 0.25
Phân ph i c a Y khi bi t X=2 có d ng: Y/X=2 0 1 2 P 0 0 1
Đ nh lý c sở c a kỹ thu t truy n tin
Trong “ A New Basic of Information Theory (1954)”, Feinstein đã đ a ra đ nh lý sau: “Trên m t kênh truy n có nhi u, ng
i ta luôn có th th c hi n m t ph
ng pháp truy n sao cho đ t đ c sai
s nh h n sai s cho phép (nh b t kỳ) cho tr c đ i v i kênh truy n.”
Chúng ta s không ch ng minh đ nh lý, thay vào đó, chúng ta s tham kh o đ n các minh h a
gi m nhi u trong các n i dung ti p theo c a bài h c.
Mô t tr ng thái truy n tin có nhi u Gi s , m t thông báo đ
c truy n đi trên m t kênh truy n nh phân r i r c. Thông báo c n truy n đ
c mã hóa thành dãy s nh phân (0,1) và có đ dài đ
c tính theo đ n v bit. Gi s 1
bit truy n trên kênh nhi u v i xác su t 1/4 (hay tính trung bình c truy n 4 bit thì có th nhi u 1 bit). ¾ đúng
Ta có s đ tr ng thái truy n tin sau: 0 0 ¼ Ngu n Mã hóa Truy n t ng bit ¼ 1 1 ¾ đúng Biên so n: T ạ
S. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 11
Giáo trình: Lý thuyết thông tin.
Minh h a kỹ thu t gi m nhi u
Trong kỹ thu t truy n tin, ng
i ta có th làm gi m sai l m khi nh n tin bằng cách truy n l p l i 1 bit v i s l l n.
Ví d : truy n l p l i 3 cho 1 bit c n truy n (xác su t nhi u 1 bit bằng 1/4). Khi nh n 3 bit li n nhau cu i k nh đ
c xem nh là 1 bit. Giá tr c a bit này đ
c hi u là 0 (hay 1) n u bit 0 (bit 1)
có s l n xu t hi n nhi u h n trong dãy 3 bit nh n đ
c li n nhau (hay gi i mã theo nguyên tắc đa s ). Ta c n ch ng minh v i ph
ng pháp truy n này thì xác su t truy n sai th t s < 1/4 (xác su t nhi u cho tr c c a kênh truy n). S đ truy n tin: Bit truy n Tuy n l p 3 l n Nh n 3 bit Gi i mã 0 000 000 0 000 001 0 000 010 0 000 100 0 000 101 1 000 011 1 000 110 1 000 111 1 1 111 000 0 111 001 0 111 010 0 111 100 0 111 011 1 111 110 1 111 111 1 111 111 1 Th t v y:
Gi s Xi xác đ nh giá tr đúng hay sai c a bit th i nh n đ
c cu i kênh truy n v i Xi =1 n u bit th i nh n đ
c là sai và Xi =0 n u bit th i nh n đ
c là đúng. Theo gi thi t ban đ u c a
kênh truy n thì phân ph i xác su t c a Xi có d ng Bernoulli b(1/4): Xi 1 0 P 3/4 1/4
G i Y ={X1 + X2 + X3 } là t ng s bit nh n sai sau 3 l n truy n l p cho 1 bit. Trong tr ng h p
này Y tuân theo phân ph i Nh th c B(p,n), v i p=1/4 (xác su t truy n sai m t bit) và q =3/4 (xác su t truy n đúng 1 bit): Y ~ B(i,n) hay
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 12
Giáo trình: Lý thuyết thông tin. i i n−i p Y (
= i) = C .p q n Trong đó: i n! C = n i ( ! n−i)!
V y truy n sai khi Y ∈ {2, 3} có xác xu t là:
Psai= P(y≥2) = P(Y=2) + P(Y=3) = B(2,3) + B(2,3) 2 1 2 3 1 3 1 3 3 0 10 1 Hay
Psai = (C ( ) .( ) ) + (C ( ) ( ) ) = < (đpcm). 3 4 4 3 4 4 64 4
Chi phí ph i tr cho kỹ thu t gi m nhi u
Theo cách th c l p l i nh trên, ta có th gi m sai l m bao nhiêu cũng đ c (l p càng nhi u thì
sai càng ít), nh ng th i gian truy n cũng tăng lên và chi phí truy n cũng s tăng theo. Hay ta có th hi u nh sau:
L p càng nhi u l n 1 bit => th i gian truy n càng nhi u => chi phí càng tăng. Khái ni m v dung l ng kênh truy n
Ví d trên cho chúng ta th y c n ph i xác đ nh m t thông s cho truy n tin đ đ m b o sai s ch p nh n đ
c và đ ng th i t c đ truy n cũng không quá ch m. Khái ni m “dung l
ng” kênh truy n là khái ni m r t c b n c a lý thuy t truy n tin và là m t đ i l
ng v t lý đ ng th i cũng là đ i l
ng toán h c (có đ n v là bit). Nó cho phép xác đ nh t c đ
truy n t i đa c a m i kênh truy n. Do đó, d a vào dung l ng kênh truy n, ng i ta có th chỉ ra
t c đ truy n tin đ ng th i v i m t ph
ng pháp truy n có sai s cho phép. V n đ sinh mã
T kỹ thu t truy n tin trên cho ta th y quá trình sinh mã và gi i mã đ c mô t nh sau: m t đ n v thông tin nh n đ c đ u vào s đ
c gán cho m t ký hi u trong b ký hi u sinh mã. M t ký hi u mã đ
c gán n l n l p l i (d a vào dung l
ng c a kênh truy n, ta có th xác đ nh đ c n).
Thi t b sinh mã (Coding device/ Encoder) s th c hi n quá trình sinh mã.
Nh v y, m t đ n v thông tin t ngu n phát tin s đ
c thi t b sinh mã gán cho m t dãy n ký
hi u mã. Dãy ký hi u mã c a 1 đ n v thông tin đ
c g i là m t t mã (Code word). Trong tr ng h p t ng quát, ng
i ta có th gán m t kh i ký t mã cho m t kh i thông tin nào đó và đ c g i là m t t mã. V n đ gi i mã
cu i kênh truy n, m t thi t b gi i mã (Decoding device/ Decoder) s th c hi n quá trình ng c
l i nh sau: ki m tra dãy ký hi u mã đ quy t đ nh gi i mã v m t t mã và đ a nó v d ng kh i tin ban đ u. Ví d : Kh i tin ban đ u : 01010101
Kh i ký hi u mã đ u truy n (l p 3 l n): 000111000111000111000111. Kh i ký hi u mã đ u nh n : 001110100111011001000111 Kh i tin nh n đ c cu i cùng
: 01011001 (sai 2 bit so v i kh i tin ban đ u)
Do đó làm sao đ đua kh i tin nh n đ
c v kh i tin ban đ u 01010101, đây chính là công vi c c a b gi i mã (Decoder).
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 13
Giáo trình: Lý thuyết thông tin.
M t v n đ quan tr ng c n l u ý là ph i đ ng b gi a t c đ n p thông tin (phát tín hi u) v i t c
đ truy n tin. N u t c đ n p thông tin bằng ho c l n h n so v i t c đ truy n tin c a kênh, thì
c n ph i gi m t c đ n p thông tin sao cho nh h n t c đ truy n tin.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 14
Giáo trình: Lý thuyết thông tin. CH NG 2: Đ ĐO L NG TIN
M c tiêu: trình bày các khái ni m v đ đo l
ng tin ch a bi t và đã bi t v m t bi n ng u nhiên X. Tính toán các l
ng tin này thông qua đ nh nghĩa và các tính ch t c a Entropy t m t hay nhi u bi n ng u nhiên. BÀI 2.1: ENTROPY M c tiêu
Sau khi hoàn t t bài h c này b n có th : - Hi u đ c các khái ni m Entropy,
- Bi t Entropy c a m t s ki n và Entropy c a m t phân ph i,
- Hi u Đ nh lý d ng gi i tích c a Entropy,
- Bi t Bài toán v cây tìm ki m nh phân và
- Làm ki n th c c s đ hi u và h c t t các bài h c ti p theo. Ví d v entropy Tr
c h t, ta c n tìm hi u m t ví d v khái ni m đ do c a m t l ng tin d a vào các s ki n
hay các phân ph i xác su t ng u nhiên nh sau:
Xét 2 BNN X và Y có phân ph i sau:
X={1, 2, 3, 4, 5} có phân ph i đ u hay p(X=i) = 1/5.
Y={1, 2} cũng có phân ph i đ u hay p(Y=i) = 1/2.
B n thân X và Y đ u mang m t l
ng tin và thông tin v X và Y ch a bi t do chúng là ng u
nhiên. Do đó, X hay Y đ u có m t l
ng tin không chắc chắn và l
ng tin chắc chắn, t ng c a 2 l
ng tin này là không đ i và th c t nó bằng bao nhiêu thì ta ch a th bi t. L ng tin không chắc chắn c a X (hay Y) đ c g i là Entropy. Tuy nhiên, n u X và Y có t
ng quan nhau thì X cũng có m t ph n l ng tin không chắc chắn thông qua l
ng tin đã bi t c a Y (hay thông tin v Y đã đ c bi t). Trong tr ng h p này, m t ph n l
ng tin không chắc chắn c a thông qua l ng tin đã bi t c a Y đ c g i là Entropy có đi u ki n. Nh n xét v đ đo l ng tin
Rõ ràng, ta c n ph i xây d ng m t đ i l
ng toán h c r t c th đ có th đo đ c l ng tin ch a
bi t t m t bi n ng u nhiên. M t cách tr c quan, l ng tin đó ph i th hi n đ c các v n đ sau:
M t s ki n có xác su t càng nh thì s ki n đó ít x y ra, cũng có nghĩa là tính không chắc chắn càng l n. N u đo l
ng tin c a nó thì nó cho m t l ng tin không bi t càng l n.
M t t p h p các s ki n ng u nhiên (hay Bi n ng u nhiên) càng nhi u s ki n có phân ph i càng
đ u thì tính không chắc chắn càng l n. N u đo l ng tin c a nó thì s đ c l ng tin không bi t càng l n. Hay l
ng tin chắc chắn càng nh .
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 15
Giáo trình: Lý thuyết thông tin.
M t phân ph i xác su t càng l ch nhi u (có xác xu t r t nh và r t l n) thì tính không chắc chắn
càng ít và do đó s có m t l
ng tin ch a bi t càng nh so v i phân ph i xác su t đ u hay l ng
tin chắc chắn c a nó càng cao. Khái ni m entropy
Trong ti ng vi t ta ch a có t t ng đ
ng v i t Entropy, tuy nhiên chúng ta có th t m hi u hi u thoáng qua tr
c khi đi vào đ nh nghĩa ch c ch v m t toán h c c a Entropy nh sau: Entropy là m t đ i l ng toán h c dùng đ đo l ng tin không chắc (hay l ng ng u nhiên) c a
m t s ki n hay c a phân ph i ng u nhiên cho tr
c. Hay m t s tài li u ti ng anh g i là Uncertainty Measure. Entropy c a m t s ki n
Gi s có m t s ki n A có xác su t xu t hi n là p. Khi đó, ta nói A có m t l ng không chắc chắn đ
c đo b i hàm s h(p) v i p ⊆ [0,1]. Hàm h(p) đ c g i là Entropy n u nó tho 2 tiêu đ toán h c sau:
Tiên đ 01: h(p) là hàm liên t c không âm và đ n đi u gi m.
Tiên đ 02: n u A và B là hai s ki n đ c l p nhau, có xác su t xu t hi n l n l t là pA và pB. Khi
đó, p(A,B) = pA.pB nh ng h(A,B) = h(pA) + h(pB).
Entropy c a m t phân ph i
Xét bi n ng u nhiên X có phân ph i: X x1 x2 x3 … xM P p1 p2 p3 … pM
N u g i Ai là s ki n X=xi, (i=1,2,3,..) thì Entropy c a Ai là: h(Ai)= h(pi)
G i Y=h(X) là hàm ng u nhiên c a X và nh n các giá tr là dãy các Entropy c a các s ki n X=xi,
t c là Y=h(X)={h(p1), h(p2), …, h(pn)}.
V y, Entropy c a X chính là kỳ v ng toán h c c a Y=h(X) có d ng:
H(X)=H(p1, p2, p3, …,pn) = p1h(p1)+ p2h(p2)+…+pnh(pn). T ng quát: n H ( X ) = p h( p ) ∑ i i i 1 =
Đ nh lý d ng gi i tích c a Entropy M Đ nh lý: Hàm H(X) = H(p = 1, p2,...,pM) C p log( p ) ∑ i i i 1 = C = const >0 C s logarithm là b t kỳ. B đ : h(p)=-Clog(p). Tr
ng h p C=1 và c s logarithm = 2 thì đ n v tính là bit.
Khi đó: h(p)=-log2(p) (đvt: bit) và
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 16
Giáo trình: Lý thuyết thông tin. M H(X) = H(p p , ,..., p ) = − p log ( p ) ∑ 1 2 M i 2 i i 1 = Qui
c trong cách vi t: log(pi)= log2(pi) Ví d minh h a
N u s ki n A có xác su t xu t hi n là 1/2 thì h(A)=h(1/2)= -log(1/2) = 1 (bit)
Xét BNN X có phân ph i sau: X x1 x2 x3 P 1/2 1/4 1/4
H(X) = H(1/2, 1/4, 1/4) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit)
Bài toán v cây tìm ki m nh phân-Đ t v n đ Gi s , tìm 1 trong 5 ng i có tên bi t tr
c s xu t hi n theo phân ph i sau: X x1 x2 x3 x4 x5 P 0,2 0,3 0,2 0,15 0,15 Trong đó: x1, …x5 l n l t là tên c a 5 ng
i mà ta c n nh n ra v i cách xác đ nh tên bằng câu h i đúng sai (yes/no). S đ d
i đây minh h a cách xác đ nh tên c a m t ng i: x1 Yes X=x 1? X=x1/x2? Yes No x2 No x3 Yes X=x3? x4 Yes X=x4? No No x5
Bài toán v cây tìm ki m nh phân - Di n gi i Theo s đ trên:
Đ tìm x1, x2, x3 v i xác su t t ng ng là 0.2, 0.3, 0.2 ta chỉ c n t n 2 câu h i.
Đ tìm x4, x5 v i xác su t t ng ng 0.15, 0.15 thì ta c n 3 câu h i. V y:
S câu h i trung bình là: 2 x (0,2+0,3+0,2) + 3 x (0,15+0,15) = 2.3
M t khác: Entropy c a X: H(X)= H(0.2, 0.3, 0.2, 0.15, 0.15)=2.27.
Ta luôn có s câu h i trung bình luôn ≥ H(X) (theo đ nh lý Shannon s trình bày sau). Vì s câu h i trung bình trong tr
ng h p này x p sỉ H(X) nên đây là s câu h i trung bình t i u đ tìm ra tên chính xác c a m t ng
i. Do đó, s đ tìm ki m trên là s đ t i u.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 17
Giáo trình: Lý thuyết thông tin.
Sinh viên t cho thêm 1 hay 2 s đ tìm ki m khác và t di n gi i t ng t - xem nh bài t p. Bài t p
Tính H(X) v i phân ph i sau: X x1 x2 x3 P 1/3 1/3 1/3
Tính H(Y) v i phân ph i sau: Y x1 x2 x3 x4 P 1/6 2/6 1/6 2/6
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 18
Giáo trình: Lý thuyết thông tin.
BÀI 2.2: CÁC TÍNH CH T C A ENTROPY M c tiêu:
Sau khi hoàn t t bài h c này b n có th :
- Hi u các tính ch t c b n c a Entropy,
- Hi u đ nh lý c c đ i c a Entropy,
- V n d ng gi i m t s bài toán v Entropy,
- Làm c s đ v n d ng gi i quy t các bài toán tính dung l ng kênh truy n.
Các tính ch t c b n c a Entropy
Xét bi n ng u nhiên X = {x1, x2, …, xM}. Entropy c a bi n ng u nhiên X có các tính ch t: 1 1 1. Hàm s f(M) = H( ,…, ) đ n đi u tăng. M M 2. Hàm s f(ML) = f(M)+f(L).
3. H(p1, p2, …, pM) = H(p1 + p2 +…+pr, pr+1+ pr+2+…+ pM) p p + (p + p + …+ p )H( 1 ,..., r ) 1 2 r ∑r r p p i= i ∑ 1 i 1 = i p p + (p + p +… p )H( r 1 + ,..., M ) r 1 + + r+2 M ∑M M p p i=r+ i ∑ 1 i=r 1 + i
4. H(p, 1-p) là hàm liên t c theo P.
Minh h a tính ch t 1 và 2 Minh h a tính ch t 1: Trong tr
ng h p bi n ng u nhiên X có phân ph i đ u Entropy c a X nh sau : ⎛ 1 1 1 ⎞ 1 1 1 1 1 1 1 1
H ( X ) = H ⎜ , , L , ⎟ = − log − log ,..., − log = − M log M M M m M M M M M M M ⎝ ⎠ 1 => H(X) = − log
= log M là hàm đ n đi u tăng M Minh h a tính ch t 2: Trong tr
ng h p 2 bi n ng u nhiên X, Y đ c l p có phân ph i đ u v i BNN X có M s ki n và BNN Y có L s ki n. G i f(M), f(L) l n l
t là Entropy c a X, c a Y. Theo tính ch t 2 c a Entropy ta có f(ML)=f(M)+f(L)
Minh h a tính ch t 3 và 4 Minh h a tính ch t 3:
Xét con xúc sắc có 6 m t v i xác su t xu t hi n các m t đ c cho trong b ng sau: X x1 x2 x3 x4 x5 x6 P 10% 20% 25% 25% 15% 5%
Ta có th gom các s ki n x1, x2, x3 l i thành m t s ki n m i là x123 có xác su t xu t hi n
là 55%, gom s ki n x5 và x6 l i thành s ki n x56 có xác su t 20%.
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 19
Giáo trình: Lý thuyết thông tin. Ta đ
c m t nhi n ng u nhiên m i X* có phân ph i sau: X* x123 x4 X56 P 55% 25% 20%
Đ n đây các b n có th áp d ng công th c đ tính, so sánh các Entropy và nh n xét tính
ch t 3. Ph n này xem nh bài t p cho sinh viên. Minh h a tính ch t 4:
Đ hi u tính ch t th 4, ta xét d ng đ th c a hàm s H(p, 1-p ):
Rõ ràng H(p, 1-p) là m t hàm liên t c theo p.
Đ nh lý c c đ i c a entropy
Đ nh lý: H(p1, p2, …,pM)≤ log(M)
Trong đó: đ ng th c x y ra khi và chỉ khi p1=…= pM= 1/M
B đ : cho 2 b {p1, p2, …,pM} và {q1, q2,…,qM} là các b s d ng b t kỳ và ∑M M p q i = ∑ i i=1 i=1 M M
Khi đó, ta có H(p1, p2, …,pM)= − p log p log 2 ≤ − p q (*) ∑ ∑ i i i 2 i i=1 i=1
Đ ng th c x y ra khi pi=qi v i ∀i=1,..,M.
Ch ng minh đ nh lý c c đ i c a Entropy Ch ng minh b đ :
Theo toán h c ta luôn có th ch ng minh đ
c ln(x)≤ x-1 v i x>0 và đ ng th c đúng khi x=1.
Đ t x= qi/pi Suy ra ln(qi/pi)≤ qi/pi –1 (và đ ng th c đúng khi qi=pi v i m i i). M M ⇔ q p ln ∑ i q p i ≤ ( p
∑ i − )i =1−1= 0 i 1 = i i 1 = M M ⇔ − p ln p ≤ − p q ln ( ∑ ∑ i i i đ ng th c x y ra khi q i i=pi). (1) i=1 i=1
Theo toán h c ta có lnx = log2x / log2e (2) M M T (1) và (2), ta có − p log p ≤ − p q log ( ∑ ∑ i i i đ ng th c x y ra khi q i i=pi.) i=1 i=1 Ch ng minh đ nh lý: Đ 1 t qi , i ∀ M T b đ , ta có: M M M − ∑ 1 p log p p log log M p log M i 2 i ≤ −∑ i 2 = 1 1 M 2 ∑ i = 2 i= i= i=1
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 20