Chương 3: Thông tin và định lượng thông tin

Chia sẻ: Nguyen Ngoc Yen | Ngày: | Loại File: PDF | Số trang:82

Thêm vào BST

Báo xấu

77
lượt xem 9
download

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

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

Chủ đề:

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

Lưu

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