Bài giảng Lý thuyết thông tin - Chương 3: Kênh rời rạc không phụ thuộc thời gian (Phần 1)

Chương 3: Kênh rời rạc không phụ thuộc thời gian 3.1 Kênh và dung lượng kênh Kênh truyền thông • Kênh truyền thông là thiết bị hoạt động trên input để cung cấp output • Thông tin chuyển qua kênh là một dãy các ký tự. 9/30/2010 2 Huỳnh Văn Kha Nếu các ký tự này thuộc vềmột tập hữu hạn thì ta gọi là kênh rời rạc • Trong trường hợp tổng quát, phân phối xác suất của output không những phụ thuộc vào việc input nào được truyền qua kênh, mà còn phụ thuộc vào trạng thái của kênh tại thời điểm input được truyền Kênh rời rạc không phụ thuộc thời gian • Nếu phân phối output của kênh không phụ thuộc vào trạng thái của kênh tại thời điểm input được truyền, thì kênh được là không phụ thuộc thời 9/30/2010Huỳnh Văn Kha 3 gian. Trong chương này kênh có nghĩa là kênh rời rạc không phụ thuộc thời gian • Có thể đặc trưng kênh rời rạc không phụ thuộc thời gian bằng ma trận các xác suất có điều kiện, gọi là ma trận kênh Ma trận kênh • Ký hiệu các ký tự input là: x1, x2, , xM • Ký hiệu các ký tự output là: y1, y2, , yL • Đặt aij = p(yj|xi) thì ma trận [aij] được gọi là ma trận kênh • Input là biến ngẫu nhiên nên output cũng vậy 9/30/2010Huỳnh Văn Kha 4 • Biết trước các xác suất của input là: p(x1), p(x2), , p(xM), thì sẽ biết các xác suất của output và các xác suất đồng thời của input và output Dung lượng kênh • Với một kênh cho trước, biết input X sẽ tính được H(X), H(Y), H(X,Y), H(X|Y), H(Y|X) • Ta định nghĩa thông tin xử lý bởi kênh là lượng 9/30/2010Huỳnh Văn Kha 5 I(X|Y) = H(X) – H(X|Y) • Chú ý: I(X|Y) = I(Y|X) = H(Y) – H(Y|X) = H(X) + H(Y) – H(X,Y) • Thông tin xử lý bởi kênh phụ thuộc vào phân phối xác suất của input. Dung lượng kênh được định nghĩa là: Một số kênh ñặc biệt 1. Một kênh là lossless nếu H(X|Y) = 0 với mọi input 2. Một kênh là deterministic nếu H(Y|X) = 0 với 9/30/2010Huỳnh Văn Kha 6 mọi input 3. Một kênh là noiseless nếu nó vừa là lossless vừa là deterministic 4. Một kênh là useless nếu I(X|Y) = 0 với mọi input Kênh ñối xứng (symmetric) • Kênh là đối xứng nếu mỗi dòng của ma trận kênh đều cùng một tập các con số p’1, p’2, , p’L và mỗi cột của ma trận kênh cũng đều cùng một tập các 9/30/2010Huỳnh Văn Kha 7 con số q’1, q’2, , q’M • Ví dụ 1/3 1/3 1/6 1/6 1/6 1/6 1/3 1/3 y1 y2 y3 y4 x1 x2 1/2 1/3 1/6 1/6 1/2 1/3 1/3 1/6 1/2 y1 y2 y3 x1 x2 x3 Kênh nhị phân ñối xứng 9/30/2010Huỳnh Văn Kha 8 0 01 – β β 1 1 1 – β β 1 – β β β 1 – β [p(yj|xi)] = Tính chất kênh ñối xứng • Do tập các p’ mỗi hàng đều như nhau nên 9/30/2010Huỳnh Văn Kha 9 j H(Y|X=xi) không phụ thuộc i và ta có: • Vậy H(Y|X) không phụ thuộc phân phối xác suất input mà chỉ phụ thuộc vào các p(yj|xi) của kênh Dung lượng kênh ñối xứng I(X|Y) = H(Y) – H(Y|X) • Do H(Y|X) không phụ thuộc X nên cực đại H(Y) sẽ làm cực đại I(X|Y) 9/30/2010Huỳnh Văn Kha 10 • H(Y) đạt cực đại là log L khi và chỉ khi Y có phân phối đồng xác suất • Nhận xét rằng, nếu X có phân phối đồng xác suất thì Y cũng đồng xác suất, thật vậy: Dung lượng kênh ñối xứng • Như vậy khi input là đồng xác suất thì thông tin xử lý bởi kênh đối xứng là cực đại • Dung lượng kênh đối xứng là: 9/30/2010Huỳnh Văn Kha 11 • Ví dụ, kênh nhị phân đối xứng có dung lượng là: CBSC = 1 – H(β, 1 – β) Tính dung lượng kênh (tổng quát) • Người ta chứng minh được rằng luôn tồn tại phân phối input để I(X|Y) đạt max • Tính dung lượng kênh trong trường hợp tổng 9/30/2010Huỳnh Văn Kha 12 quát là bài toán phức tạp, và người ta thường sử dụng các phương pháp số để tính • Dựa vào tính chất I(X|Y) là hàm lồi theo phân phối xác suất của X, sử dụng phương pháp giải tích người ta tìm được công thức để tính dung lượng kênh trong trường hợp đặc biệt như sau ðịnh lý 3.1 Giả sửma trận kênh Π của kênh rời rạc không phụ thuộc thời gian là ma trận vuông khả nghịch. 9/30/2010Huỳnh Văn Kha 13 Gọi qij là các phần tử hàng i cột j của ma trận Π-1. Giả sử rằng với mỗi k = 1, 2, , M, ta có: ðịnh lý 3.1 Thì khi đó dung lượng kênh là: 9/30/2010Huỳnh Văn Kha 14 Và phân phối xác suất input để lượng thông tin xử lý bởi kênh đạt max như trên là