Bài 9 Kênh rời rạc không nhớ Lượng tin tương hỗ

Chia sẻ: đỗ Hữu Thọ | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

81
lượt xem 3
download

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

Một hướng giải quyết như sau: để gởi 0 chúng ta gởi chuỗi 3 kí hiệu 0 và tương tự để gởi 1 chúng ta gởi 3 kí hiệu 1.

Chủ đề:

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

Lưu

Nội dung Text: Bài 9 Kênh rời rạc không nhớ Lượng tin tương hỗ

Bài 9 Kênh rời rạc không nhớ Lượng tin tương hỗ 9.1 Kênh rời rạc không nhớ và ma trận kênh 9.2 Entropy điều kiện và lượng tin tương hỗ 9.3 Một số loại kênh 9.4 Sự nhập nhằng (equivocation) và tốc độ truyền tin 9.5 Dung lượng kênh Trang 142 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Kênh rời rạc không nhớ và ma trận kênh Định nghĩa Một kênh rời rạc không nhớ (DMC) được định nghĩa bằng một bảng kí hiệu đầu vào (nguồn phát) X = {x1, ..., xK}, một bảng kí hiệu đầu ra (nguồn nhận) Y = {y1, ..., yJ}, và một sự phân bố xác suất có điều kiện p(yj | xk), với 1 ≤ k ≤ K, 1 ≤ j ≤ J. X p(yj | xk) Y xk yj Bảng kí hiệu đầu ra không nhất thiết giống bảng kí hiệu đầu vào. Điều này có nghĩa là bên nhận có thể nhận những kí hiệu mà không giống với những kí hiệu mà bên phát phát đi. Trang 143 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Nhận xét Thuật ngữ không nhớ (memoryless) suy ra rằng N p{ y j1 K y jN | x k1 L x kN } = ∏ p( y jn | xkn ) với N bất kỳ. n =1 Một kênh rời rạc không nhớ thường được biểu diễn dưới dạng một ma trận kênh [p(yj | xk)] có kích thước K × J. y1 y2 yJ x1 p(y1 | x1) p(y2 | x1) ... p(yJ | x1) x2 p(y1 | x2) p(y2 | x2) ... p(yJ | x2) ... ... ... ... ... xK p(y1 | xK) p(y2 | xK) ... p(yJ | xK) Trang 144 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Nhận xét (tt) Chúng ta thấy, ma trận kênh chính là cái mà biểu diễn tính chất tạp nhiễu của kênh truyền. Chú ý, nếu chúng ta biết sự phân bố xác suất trên X thì sự phân bố xác suất của Y sẽ được xác định như sau K p( y j ) = ∑ p( xk ) p( y j | xk ) k =1 Trang 145 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Entropy điều kiện và lượng tin tương hỗ Xét bài toán truyền tin sau Cho biết cấu trúc thống kê của nguồn X và ma trận kênh. Hãy xác định kí hiệu xk nào đã được phát phát đi khi nhận được ở đầu nhận một kí hiệu yj nào đó? Ví dụ Cho nguồn X = {x1, x2} với các xác suất lần lượt là p(x1) = 1/4, p(x2) = 3/4, nguồn Y = {y1, y2} và ma trận kênh là y1 y2 x1 4/5 1/5 x2 2/5 3/5 Nếu nhận được y1 thì xk nào có khả năng đã được phát đi? Trang 146 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ p( xk , y j ) p( xk ) × p( y j | xk ) p( xk ) × p( y j | xk ) p( xk | y j ) = = = p( y j ) K K ∑ p ( xi , y j ) ∑ p ( xi ) × p ( y j | xi ) i =1 i =1 p ( x1 ) p ( y1 | x1 ) 3 p ( x1 | y1 ) = p ( x 2 | y1 ) = p ( x1 ) p( y1 | x1 ) + p ( x 2 ) p ( y1 | x 2 ) 5 (1 / 4) × (4 / 5) 2 = = (1 / 4) × (4 / 5) + (3 / 4) × (2 / 5) 5 p(x1 | y1) < p(x2 | y1), như vậy chúng ta có thể khẳng định được kí hiệu x2 có khả năng được phát đi hơn x1? Trang 147 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Ví dụ (tt) Để ý, trong công thức của p(xi | yj) có chứa thừa số p(xi), nên p(xi | yj) đã bị ảnh hưởng bởi xác suất lề p(xi). Vì vậy để công bằng trong việc so sánh chúng ta phải dựa trên tỉ số p(xi | yj)/p(xi) cái mà không bị ảnh hưởng nhiều bởi p(xi). p ( x1 | y1 ) 2 / 5 8 = = p ( x1 ) 1/ 4 5 p ( x 2 | y1 ) 3 / 5 4 = = p( x2 ) 3/ 4 5 Như vậy thực sự kí hiệu x1 mới có khả năng được phát đi hơn kí hiệu x2. Từ xác suất điều kiện chúng ta giới thiệu khái niệm lượng tin có điều kiện. Trang 148 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Lượng tin có điều kiện I(xk | yj) Định nghĩa I(yj | xk) = –log p(yj | xk) I(xk | yj) = –log p(xk | yj) p(yj | xk) → 1 thì I(yj | xk) → 0 và ngược lại. Nếu khi phát đi xk và biết chắc yj sẽ nhận được thì ở phía nhận chúng ta không cần tốn thêm thông tin gì để giải thích. Nếu p(yj | xk) = 1/2 (I(yj | xk) = 1 bit) thì khi phát đi xk bên nhận sẽ có hai khả năng và yj chỉ là một trong hai khả năng đó, có nghĩa là bên nhận cần thêm thông tin (cần thêm 1 bit) để biết chính xác đó là khả năng nào. Xác suất p(yj | xk) = 1/2 chỉ xảy ra khi kênh truyền có nhiễu. Trang 149 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Lượng tin có điều kiện I(xk | yj) Vì vậy lượng tin có điều kiện còn được gọi là lượng tin bị mất đi do nhiễu. Khi phát đi xk bên nhận sẽ có một tập các yj có khả năng được nhận. Ngược lại khi nhận được yj bên phát sẽ có một tập các xk có khả năng được phát. Để đo mức độ “quan hệ” giữa xk với yj chúng ta giới thiệu khái niệm lượng tin tương hỗ. Trang 150 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Lượng tin tương hỗ Định nghĩa Lượng tin tương hỗ giữa hai tin là lượng tin của của tin này được chứa trong tin kia và ngược lại. Bằng công thức Lượng tin tương hỗ = Lượng tin riêng – Lượng tin bị mất đi I(xk, yj) = I(xk) – I(xk | yj) = I(yj) – I(xk | yj) p( x k |y j ) p( y j|x k ) = log = log p( x k ) p( y j ) Nếu p(xk | yj) = 1 có nghĩa là nếu yj đã nhận được thì chắc chắn xk đã được phát đi, điều này có nghĩa là lượng tin của xk đã được truyền nguyên vẹn thông qua kênh, do đó I(xk, yj) = I(xk). Trang 151 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Lượng tin có điều kiện trung bình K K I(X | y j ) = ∑ p(xk | y j )I (xk | y j ) = − ∑ p(xk | y j ) log p(xk | y j ) k =1 k =1 J J I (Y | xk ) = ∑ p( y j | xk )I ( y j | xk ) = − ∑ p( y j | xk ) log p( y j | xk ) j =1 j =1 J J K I(X | Y) = ∑ p( y j )I ( X | y j ) = − ∑ p( y j ) ∑ p(xk | y j ) log p(xk | y j ) j =1 j =1 k =1 K J = − ∑ ∑ p( xk , y j ) log p( xk | y j ) k = 1 j =1 K J I (Y | X ) = − ∑ ∑ p( xk , y j ) log p( y j | xk ) k =1 j =1 Trang 152 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Entropy điều kiện Định nghĩa Xét hai biến ngẫu nhiên x và y với phân bố xác suất đồng thời p(xk, yj), k = 1, ..., K , j = 1, ..., J. Entropy điều kiện của x đã cho y được định nghĩa là K J H (x | y ) = − ∑ ∑ p( xk , y j ) log p( xk | y j ) k =1 j =1 H(x | y) có thể được diễn dịch như là độ bất ngờ trung bình về x sau khi đã biết y. Định lý 9.1 H(x | y) ≤ H(x), dấu “=” xảy ra ⇔ x và y là độc lập. Trang 153 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Chứng minh K J K H (x | y) − H (x) = − ∑∑ p(xk , y j ) ln p(xk | y j ) + ∑ p(xk ) ln p(xk ) k =1 j =1 k =1 K J p(xk ) = − ∑∑ p(xk , y j ) ln k =1 j =1 p(xk | y j ) Lấy tổng trên những cặp (k, j) mà p(xk, yj) ≠ 0. Vì vậy ⎡ p( xk ) ⎤ H (x | y) − H (x) = ∑∑ p( xk , y j )⎢ − 1⎥ k j ⎢⎣ p( xk | y j ) ⎥⎦ = ∑ ∑ p( xk ) p( y j ) − p( xk , y j ) k j [ = ∑∑ p( x k ) p( y j ) − 1 ≤ 0 ] k j Trang 154 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Chứng minh (tt) Dấu “=” xảy ra ⇔ p(xk) = p(xk | yj) đối với tất cả các cặp (k, j) mà p(xk, yj) ≠ 0 đồng thời tổng p(xk)p(yj) trên tất cả những cặp này bằng 1. Điều kiện thứ hai tương đương với điều kiện p(xk)p(yj) = 0 bất kỳ khi nào mà p(xk, yj) = 0. Cả hai điều kiện này cuối cùng tương đương với điều kiện là x và y độc lập. Định lý 9.2 H(x, y) = H(x) + H(y | x) = H(y) + H(x | y) Trang 155 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Chứng minh H (x, y) = − ∑∑ p( xk , y j ) log p( xk , y j ) k j [ = − ∑∑ p( xk , y j ) log p( xk ) + log p( y j | xk ) ] k j = − ∑ p( xk )[log p( xk )] − ∑∑ p( y j , y k ) log p( y j | xk ) k k j = H ( x) + H ( y | x) Phần thứ hai chứng minh hoàn toàn tương tự. Kết hợp hai định lý trên chúng ta suy ra rằng H(x, y) ≤ H(x) + H(y) dấu “=” xảy ra ⇔ x, y là độc lập. Trang 156 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Lượng tin tương hỗ trung bình I ( X , Y ) = ∑∑ p( xk , y j ) I ( xk , y j ) k j p( xk | y j ) = ∑∑ p ( x k , y j ) log k j p( xk ) p( y j | xk ) = ∑∑ p ( xk , y j ) log k j p( y j ) p( xk , y j ) = ∑∑ p ( xk , y j ) log k j p( xk ) p( y j ) Nếu biểu diễn theo entropy thì chúng ta có I(x, y) = H(x) – H(x | y) = H(y) – H(y | x) Trang 157 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Một số loại kênh rời rạc không nhớ Kênh đối xứng (Symmetric channel) Là kênh mà mỗi dòng của ma trận kênh chứa cùng tập các số p1’, ..., pJ’ và mỗi cột chứa cùng tập các số q1’, ..., qK’. Ví dụ j=1 2 3 4 0,2 0,2 0,3 0,3 k = 1 [p(yj | xk)] = 0,3 0,3 0,2 0,2 k = 2 Các ma trận biểu 0,2 0,3 0,5 diễn [p(yj | xk)] = 0,3 0,5 0,2 các kênh đối xứng 0,5 0,2 0,3 Kênh đối xứng nhị 1–ε ε phân (binary [p(yj | xk)] = 0≤ε≤1 ε 1–ε symmetric channel – Trang 158 BSC). Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Nhận xét Kênh đối xứng thì H(y | x) độc lập với sự phân bố xác suất của nguồn phát và được xác định duy nhất bằng ma trận kênh. Chứng minh K J H (y | x) = − ∑ ∑ p ( x k , y j ) log p ( y j | x k ) k =1 j =1 K J = − ∑ p ( x k ) ∑ p ( y j | x k ) log p ( y j | x k ) k =1 j =1 K J = − ∑ p ( x k ) ∑ p 'j log p 'j k =1 j =1 J = − ∑ p 'j log p 'j j =1 Trang 159 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Kênh không mất (Lossless channel) Cạnh nối giữa xk và yj nghĩa là p(yj | xk) ≠ 0. Trong kênh không mất đầu ra xác định duy nhất đầu vào, vì vậy H(x | y) = 0. x1 x1 xK y1 y2 ym ym+1 yJ Kênh đơn định (Deterministic channel) x1 x2 xm xm+1 xK y1 y2 yJ Trong kênh này đầu vào xác định duy nhất đầu ra, vì vậy H(y | x) = 0 Trang 160 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin
Kênh vô dụng (Useless channel) Một kênh là vô dụng nếu và chỉ nếu x và y là độc lập với mọi sự phân bố xác suất của đầu vào (nguồn phát). Đối với một kênh vô dụng thì H(x | y) = H(x), tức là kiến thức về đầu ra không làm giảm độ bất ngờ về đầu vào. Vì vậy, đối với mục đích xác định đơn định đầu vào, chúng ta có thể phớt lờ đầu ra hoàn toàn. Bây giờ chúng ta sẽ chứng minh rằng. Một kênh rời rạc không nhớ là vô dụng nếu và chỉ nếu ma trận kênh của nó có các dòng giống nhau. Chứng minh Điều kiện đủ Giả sử ma trận có các dòng giống nhau p1’, ..., pJ’. Thì đối với mọi đầu ra yj Trang 161 Lý thuyết Thông tin - Khoa Công Nghệ Thông Tin