Chương 3: Thông tin và định lượng thông tin
lượt xem 8
download
Tốc độ lập tin của nguồn và thông lượng kênh rời rạc: Tốc độ lập tin và độ dư của nguồn. Khái niệm thông lượng của kênh. Thông lượng của kênh rời rạc không nhiễu. Thông lượng của kênh rời rạc có nhiễu
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Chương 3: Thông tin và định lượng thông tin
- Cơ s Lý thuy t Truy n tin-2004 Chương 3: Thông tin và đ nh lư ng thông tin Hà Qu c Trung1 1 Khoa Công ngh thông tin Đ i h c Bách khoa Hà n i
- Chương 3: Thông tin và đ nh lư ng thông tin 1 Lư ng tin c a ngu n tin r i r c 2 Entropi c a ngu n r i r c 3 T c đ l p tin c a ngu n và thông lư ng kênh r i r c 4 Entropi c a ngu n và thông lư ng kênh liên t c
- 1. Lư ng tin c a ngu n tin r i r c 1 Lư ng tin c a ngu n tin r i r c Ngu n tin r i r c Bi n đ i ngu n tin r i r c Lư ng tin riêng, lư ng tin tương h , lư ng tin có đi u ki n Tính ch t c a lư ng tin Lư ng tin trung bình 2 Entropi c a ngu n r i r c 3 T c đ l p tin c a ngu n và thông lư ng kênh r i r c 4 Entropi c a ngu n và thông lư ng kênh liên t c Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 3/ 55
- 1.1.Ngu n tin r i r c Ngu n tin r i r c Ngu n tin t o ra m t chu i các bi n ng u nhiên r i r c x1 , x2 , . . . , xn , . . . Ký hi u Ph n t nh nh t ch a thông tin, M t giá tr c a bi n ng u nhiên, Ví d mã morse, 4 ký hi u B ký hi u: t p h p t t c các ký hi u có th (t t c các giá tr có th c a bi n ng u nhiên r i r c), còn g i là b ng ch cái X = {x1 , x2 , . . . , xn } T : T p h p h u h n các ký hi u B t : T p h p t t c các t có th Ngu n đ c trưng b i trư ng xác su t {X , p(x)}, X = {x1 x2 . . . xn ....} Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 4/ 55
- Các lo i ngu n tin r i r c Ngu n r i r c không nh : xác su t xu t hi n c a các ký hi u không ph thu c vào các ký hi u đã xu t hi n trư c đó p(xn |x1 , x2 , . . . xn−1 ) = p(xn ) Ngu n r i r c có nh p(xn |x1 , x2 , . . . xn−1 ) < p(xn ) Ngu n d ng: Xác su t xu t hi n c a các ký t ch ph thu c vào v trí tương quan gi a các ký t , không ph thu c vào v trí so v i g c p(xi , n) = p(xi , n + k)∀k Ngu n d ng Ergodic: Ngu n có các giá tr trung bình t p h p b ng các giá tr trung bình theo th i gian Ngu n có t c đ thông tin đi u khi n đư c (thay đ i) Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 5/ 55
- Các lo i ngu n tin r i r c (Ti p) Ngu n đi n tín Telex Ngu n có t c đ thông tin không đi u khi n đư c (không thay đ i) Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 6/ 55
- Ngu n Markov Ngu n Markov đ nh 1: xác su t c a m t ký hi u ch ph thu c vào ký hi u trư c đó p(xin |xjn−1 , xkn−2 ...) = p(xin |xjn−1 ) T i th i đi m n ngu n có th tr ng thái xj v i xác su t pij = p(xj,n |xi,n−1 ) khi th i đi m n − 1 ngu n đã tr ng L thái xi . Khi đó pij = 1 j=1 Xác su t đ ký hi u th n là xj L p(xjn ) = p(xjn , xin−1 ) = i=1 L L p(xin−1 )p(xjn |xin−1 ) = p(xin−1 )pij i=1 i=1 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 7/ 55
- Ngu n Markov (Ti p) Bi u di n b ng ma tr n p(x1n ) p(x1n−1 ) p11 p12 . . . p1L p(x1n ) p(x1n−1 ) p21 p22 . . . p2L . . . Pn−1 = . . . T = . . . . . . Pn = . . . . . . p(xLn ) p(xLn−1 ) pL1 pL2 . . . pLL Phân b xác su t t i th i đi m n Pn = T T Pn−1 = (T T )n P0 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 8/ 55
- 1.2.Bi n đ i ngu n tin r i r c Bi n đ i c u trúc th ng kê c a ngu n tin r i r c {X , p(x)} → {Y , p(y)} N u không có nhi u, phép bi n đ i là 1-1, ánh x có th bi u di n theo b ng: A → 00 B → 01 C → 10 D → 11 T ng quát, phép bi n đ i bi u di n b ng m t trư ng xác su t {XY , p(X , Y )}, X = {A, B, C, D}, Y = {00, 01, 10, 11} mô t xác su t có th đ có m t đ u vào x và m t đ u ra y đ ng th i p(x, y) Có th s d ng các xác su t có đi u ki n p(y|x) Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 9/ 55
- Ví d : kênh nh phân đ i x ng Y=X Y =X P(Y0 |X0 ) 1 0 P(Y1 |X0 ) 0 1 P(Y1 |X1 ) 1 0 P(Y0 |X1 ) 0 1 T p vào g m 2 ký hi u, T p ra g m hai ký hi u M t phép bi n đ i b t kỳ có th bi u di n b ng b 4 xác su t có đi u ki n (xác su t chuy n đ i): x0 chuy n thành y0 x0 chuy n thành y1 x1 chuy n thành y1 x1 chuy n thành y0 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 10/ 55
- Ví d : kênh nh phân đ i x ng (Ti p) Phân b xác su t c a đ u ra b ng phân b xác su t c a đ u vào và xác su t chuy n đ i: p(x, y) = p(x)p(y|x) Khi g i m t tin x, xác su t đ có tin y đ u ra s là p(x, y) p(y|x) = p(x) Các xác su t này g i là xác su t chuy n đ i, có th dùng đ đ c trưng cho phép bi n đ i Theo công th c v xác su t đ ng th i và có đi u ki n p(x) = (p(x, y)), p(y) = (p(x, y)) Y X p(x)p(y|x) p(x|y) = Y p(x)p(y|x) Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 11/ 55
- Ví d : kênh nh phân đ i x ng (Ti p) T công th c cu i cùng, có th tính đư c xác su t g i tin x khi nh n đư c tin y: Gi i quy t bài toán thu tin p(x): xác su t tiên nghi m, p(x|y) xác su t h u nghi m, s d ng đ xác đ nh các lư ng tin Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 12/ 55
- Ví d M t ngu n tin g m 8 tin U, m i tin là m t ký hi u ui , i = 1 . . . 8 đư c bi n đ i b i m t kênh truy n tin thành t p 8 tin, m i tin g m 3 ký hi u x, y, z, m i ký hi u nh n 2 giá tr 0 ho c 1. Ký hi u x0 = y0 = z0 = 0, x1 = y1 = z1 = 1 Khi nh n tin, nh n l n lư t t ng ký t x, y, z. M i l n nh n đư c m t ký hi u, xác su t h u nghi m c a tin u thay đ i p(u)khi nh n đư c ký hi u Tin u p(u) xyz x1 y0 z1 u0 1/4 x0 y0 z0 0 0 0 u1 1/4 x1 y0 z0 1/2 4/5 0 u2 1/8 x0 y1 z0 0 0 0 u3 1/8 x1 y1 z0 1/4 0 0 u4 1/16 x0 y0 z1 0 0 0 u5 1/16 x1 y0 z1 1/8 1/5 1 u6 1/16 x0 y1 z1 0 0 0 u7 1/16 x1 y1 z1 1/8 0 0 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 13/ 55
- Ví d M t ngu n tin g m 8 tin U, m i tin là m t ký hi u ui , i = 1 . . . 8 đư c bi n đ i b i m t kênh truy n tin thành t p 8 tin, m i tin g m 3 ký hi u x, y, z, m i ký hi u nh n 2 giá tr 0 ho c 1. Ký hi u x0 = y0 = z0 = 0, x1 = y1 = z1 = 1 Khi nh n tin, nh n l n lư t t ng ký t x, y, z. M i l n nh n đư c m t ký hi u, xác su t h u nghi m c a tin u thay đ i p(u)khi nh n đư c ký hi u Tin u p(u) xyz x1 y0 z1 u0 1/4 x0 y0 z0 0 0 0 u1 1/4 x1 y0 z0 1/2 4/5 0 u2 1/8 x0 y1 z0 0 0 0 u3 1/8 x1 y1 z0 1/4 0 0 u4 1/16 x0 y0 z1 0 0 0 u5 1/16 x1 y0 z1 1/8 1/5 1 u6 1/16 x0 y1 z1 0 0 0 u7 1/16 x1 y1 z1 1/8 0 0 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 13/ 55
- Ví d M t ngu n tin g m 8 tin U, m i tin là m t ký hi u ui , i = 1 . . . 8 đư c bi n đ i b i m t kênh truy n tin thành t p 8 tin, m i tin g m 3 ký hi u x, y, z, m i ký hi u nh n 2 giá tr 0 ho c 1. Ký hi u x0 = y0 = z0 = 0, x1 = y1 = z1 = 1 Khi nh n tin, nh n l n lư t t ng ký t x, y, z. M i l n nh n đư c m t ký hi u, xác su t h u nghi m c a tin u thay đ i p(u)khi nh n đư c ký hi u Tin u p(u) xyz x1 y0 z1 u0 1/4 x0 y0 z0 0 0 0 u1 1/4 x1 y0 z0 1/2 4/5 0 u2 1/8 x0 y1 z0 0 0 0 u3 1/8 x1 y1 z0 1/4 0 0 u4 1/16 x0 y0 z1 0 0 0 u5 1/16 x1 y0 z1 1/8 1/5 1 u6 1/16 x0 y1 z1 0 0 0 u7 1/16 x1 y1 z1 1/8 0 0 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 13/ 55
- Ví d M t ngu n tin g m 8 tin U, m i tin là m t ký hi u ui , i = 1 . . . 8 đư c bi n đ i b i m t kênh truy n tin thành t p 8 tin, m i tin g m 3 ký hi u x, y, z, m i ký hi u nh n 2 giá tr 0 ho c 1. Ký hi u x0 = y0 = z0 = 0, x1 = y1 = z1 = 1 Khi nh n tin, nh n l n lư t t ng ký t x, y, z. M i l n nh n đư c m t ký hi u, xác su t h u nghi m c a tin u thay đ i p(u)khi nh n đư c ký hi u Tin u p(u) xyz x1 y0 z1 u0 1/4 x0 y0 z0 0 0 0 u1 1/4 x1 y0 z0 1/2 4/5 0 u2 1/8 x0 y1 z0 0 0 0 u3 1/8 x1 y1 z0 1/4 0 0 u4 1/16 x0 y0 z1 0 0 0 u5 1/16 x1 y0 z1 1/8 1/5 1 u6 1/16 x0 y1 z1 0 0 0 u7 1/16 x1 y1 z1 1/8 0 0 Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 13/ 55
- 1.3.Lư ng tin riêng, lư ng tin tương h , lư ng tin có đi u ki n Lư ng tin c a m i tin xi ∈ X : I(xi ) = −log(p(xi )) g i là lư ng tin riêng c a tin xi Bài toán thu tin Các tin c a ngu n tin X truy n qua m t h th ng bi n đ i thành đ u ra Y . Cho bi t C u trúc th ng kê c a ngu n C u trúc th ng kê c a t p nhi u và phép bi n đ i (cho b ng các xác su t chuy n đ i) V i m i đ u ra y ∈ Y xác đ nh đ u vào x ∈ X đã sinh ra y ∈Y L i gi i Chính xác: không có Xác su t: Xác đ nh đ u vào có kh năng nh t Thông tin: (l c)tách thông tin c a đ u vào ch a trong đ u ra Xác đ nh lư ng thông tin c a m i xi ch a trong yj : lư ng tin tương h =Lư ng tin ban đ u-lư ng tin còn l i ch n ra đ u vào lư ng tin tương h l n nh t Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 14/ 55
- 1.3.Lư ng tin riêng, lư ng tin tương h , lư ng tin có đi u ki n Lư ng tin c a m i tin xi ∈ X : I(xi ) = −log(p(xi )) g i là lư ng tin riêng c a tin xi Bài toán thu tin Các tin c a ngu n tin X truy n qua m t h th ng bi n đ i thành đ u ra Y . Cho bi t C u trúc th ng kê c a ngu n C u trúc th ng kê c a t p nhi u và phép bi n đ i (cho b ng các xác su t chuy n đ i) V i m i đ u ra y ∈ Y xác đ nh đ u vào x ∈ X đã sinh ra y ∈Y L i gi i Chính xác: không có Xác su t: Xác đ nh đ u vào có kh năng nh t Thông tin: (l c)tách thông tin c a đ u vào ch a trong đ u ra Xác đ nh lư ng thông tin c a m i xi ch a trong yj : lư ng tin tương h =Lư ng tin ban đ u-lư ng tin còn l i ch n ra đ u vào lư ng tin tương h l n nh t Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 14/ 55
- 1.3.Lư ng tin riêng, lư ng tin tương h , lư ng tin có đi u ki n Lư ng tin c a m i tin xi ∈ X : I(xi ) = −log(p(xi )) g i là lư ng tin riêng c a tin xi Bài toán thu tin Các tin c a ngu n tin X truy n qua m t h th ng bi n đ i thành đ u ra Y . Cho bi t C u trúc th ng kê c a ngu n C u trúc th ng kê c a t p nhi u và phép bi n đ i (cho b ng các xác su t chuy n đ i) V i m i đ u ra y ∈ Y xác đ nh đ u vào x ∈ X đã sinh ra y ∈Y L i gi i Chính xác: không có Xác su t: Xác đ nh đ u vào có kh năng nh t Thông tin: (l c)tách thông tin c a đ u vào ch a trong đ u ra Xác đ nh lư ng thông tin c a m i xi ch a trong yj : lư ng tin tương h =Lư ng tin ban đ u-lư ng tin còn l i ch n ra đ u vào lư ng tin tương h l n nh t Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 14/ 55
- 1.3.Lư ng tin riêng, lư ng tin tương h , lư ng tin có đi u ki n Lư ng tin c a m i tin xi ∈ X : I(xi ) = −log(p(xi )) g i là lư ng tin riêng c a tin xi Bài toán thu tin Các tin c a ngu n tin X truy n qua m t h th ng bi n đ i thành đ u ra Y . Cho bi t C u trúc th ng kê c a ngu n C u trúc th ng kê c a t p nhi u và phép bi n đ i (cho b ng các xác su t chuy n đ i) V i m i đ u ra y ∈ Y xác đ nh đ u vào x ∈ X đã sinh ra y ∈Y L i gi i Chính xác: không có Xác su t: Xác đ nh đ u vào có kh năng nh t Thông tin: (l c)tách thông tin c a đ u vào ch a trong đ u ra Xác đ nh lư ng thông tin c a m i xi ch a trong yj : lư ng tin tương h =Lư ng tin ban đ u-lư ng tin còn l i ch n ra đ u vào lư ng tin tương h l n nh t Chương 3: Thông tin và đ nh lư ng thông tin 1. Lư ng tin c a ngu n tin r i r c 14/ 55
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng thông tin số Chương 3
37 p | 620 | 244
-
Chương 3: Cảm biến và cơ cấu chấp hành
110 p | 871 | 196
-
Tin học ứng dụng - Chương 3
66 p | 321 | 171
-
Bài giảng hệ thống thông tin VIBA - vệ tinh - chương 1
56 p | 623 | 107
-
Giáo trình - Thông tin di động - Chương 2
32 p | 210 | 79
-
Giáo trình môn điện tử thông tin - Chương 3
13 p | 208 | 52
-
Đồ án bảo dưỡng công nghiệp Hệ thống Servo- Chương 3
43 p | 148 | 42
-
Bài giảng Hệ thống viễn thông: Chương 3 - Trương Thu Hương
190 p | 130 | 25
-
Hệ thống vô tuyến - Chương 3
8 p | 114 | 23
-
Bài giảng Kỹ thuật số - Chương 3: Các cổng logic & Đại số Boolean
27 p | 74 | 7
-
Bài giảng Lý thuyết thông tin: Chương 3.2 - ThS. Huỳnh Văn Kha
15 p | 79 | 7
-
Bài giảng Xử lý số tín hiệu: Chương 3 - PGS.TS Lê Tiến Thường
40 p | 40 | 4
-
Bài giảng Tín hiệu và hệ thống: Chương 3 - Lê Vũ Hà (Bài 1)
29 p | 37 | 3
-
Tập bài giảng Quản trị học (Dùng cho HSSV hệ CĐN &TCCN) - Cao đẳng Cộng đồng Lào Cai
138 p | 24 | 3
-
Bài giảng Xử lý số tín hiệu: Chương 3 - PGS.TS. Phạm Tiến Thường
40 p | 50 | 2
-
Bài giảng Điện tử cho công nghệ thông tin: Chương 5.3 - Đỗ Công Thuần
45 p | 9 | 2
-
Bài giảng Tín hiệu và hệ thống: Chương 3 - Trần Thủy Bình
30 p | 6 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn