Bài giảng Cơ sở Lý thuyết Truyền tin - Chương 3: Thông tin và định lượng thông tin - Hà Quốc Trung

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
1Khoa 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 = {x1x2 . . . 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
thái xi . Khi đó
L∑
j=1
pij = 1
Xác suất để ký hiệu thứ n là xj
p(xjn) =
L∑
i=1
p(xjn, xin−1) =
L∑
i=1
p(xin−1)p(xjn|xin−1) =
L∑
i=1
p(xin−1)pij
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
Pn =

p(x1n)
p(x1n)
. . .
p(xLn)
Pn−1 =

p(x1n−1)
p(x1n−1)
. . .
p(xLn−1)
T =

p11 p12 . . . p1L
p21 p22 . . . p2L
. . . . . . . . . . . .
pL1 pL2 . . . pLL

Phân bố xác suất tại thời điểm n
Pn = T TPn−1 = (T T )nP0
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ằngmộ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(y |x) = p(x , y)
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) =
∑
Y
(p(x , y)),p(y) =
∑
X
(p(x , y))
p(x |y) = p(x)p(y |x)∑
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
Tin u p(u) xyz
p(u)khi nhận được ký hiệu
x1 y0 z1
u0 1/4 x0y0z0 0 0 0
u1 1/4 x1y0z0 1/2 4/5 0
u2 1/8 x0y1z0 0 0 0
u3 1/8 x1y1z0 1/4 0 0
u4 1/16 x0y0z1 0 0 0
u5 1/16 x1y0z1 1/8 1/5 1
u6 1/16 x0y1z1 0 0 0
u7 1/16 x1y1z1 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
Tin u p(u) xyz
p(u)khi nhận được ký hiệu
x1 y0 z1
u0 1/4 x0y0z0 0 0 0
u1 1/4 x1y0z0 1/2 4/5 0
u2 1/8 x0y1z0 0 0 0
u3 1/8 x1y1z0 1/4 0 0
u4 1/16 x0y0z1 0 0 0
u5 1/16 x1y0z1 1/8 1/5 1
u6 1/16 x0y1z1 0 0 0
u7 1/16 x1y1z1 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
Tin u p(u) xyz
p(u)khi nhận được ký hiệu
x1 y0 z1
u0 1/4 x0y0z0 0 0 0
u1 1/4 x1y0z0 1/2 4/5 0
u2 1/8 x0y1z0 0 0 0
u3 1/8 x1y1z0 1/4 0 0
u4 1/16 x0y0z1 0 0 0
u5 1/16 x1y0z1 1/8 1/5 1
u6 1/16 x0y1z1 0 0 0
u7 1/16 x1y1z1 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
Tin u p(u) xyz
p(u)khi nhận được ký hiệu
x1 y0 z1
u0 1/4 x0y0z0 0 0 0
u1 1/4 x1y0z0 1/2 4/5 0
u2 1/8 x0y1z0 0 0 0
u3 1/8 x1y1z0 1/4 0 0
u4 1/16 x0y0z1 0 0 0
u5 1/16 x1y0z1 1/8 1/5 1
u6 1/16 x0y1z1 0 0 0
u7 1/16 x1y1z1 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
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
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ỗ  ... uồn rời rạc 25/ 55
Ví dụ: kênh nhị phân đối xứng
Giả sử p(y0|x0) = p(y1|x1) = pd ,p(y0|x1) = p(y1|x0) =
ps,p(x0) = p,p(x1) = q. Khi đó pd + ps = 1,p + q = 1
Tìm lượng tin tương hỗ trung bình giữa X ,Y?
Sử dụng công thức I(X ;Y ) = H(Y )− H(Y |X )
Tính H(Y)
Tính H(Y|X)
Chương 3: Thông tin và định lượng thông tin 2. Entropi của nguồn rời rạc 25/ 55
Ví dụ: kênh nhị phân đối xứng
Xác định xác suất của các tin đầu ra
p(y) =
∑
X
p(x , y) =
∑
X
p(x)p(y |x)
p(y0) = p(x0)p(y0|x0) + p(x1)p(y0|x1) =
= p(1− ps) + (1− p)ps = p − 2pps + ps
p(y1) = 1− (p − 2pps + ps)
Entropi đầu ra
H(Y ) = −p(y0) logp(y0)− p(y1) logp(y1) =
−(p − 2pps + ps) log(p − 2pps + ps)−
−(1− (p − 2pps + ps)) log(1− (p − 2pps + ps))
Chương 3: Thông tin và định lượng thông tin 2. Entropi của nguồn rời rạc 26/ 55
Ví dụ: kênh nhị phân đối xứng (Tiếp)
Entropi có điều kiện
H(Y |X ) = −
∑
XY
p(x , y) log(p(y |x)) = −
∑
XY
p(x)p(y |x) log(p(y |x))
−{pp(y0|x0) logp(y0|x0) + qp(y1|x1) logp(y1|x1)+
pp(y1|x0) logp(y1|x0) + qp(y0|x1) logp(y0|x1)} =
−{p.pd logpd+(1−p).pd logpd+p.ps logps+(1−p).ps logps} =
−{pd logpd +ps logps} = −(ps logps+(1−ps) log(1−ps))
Lượng tin tương hỗ
I(X ;Y ) = H(Y )− H(Y |X ) =
−(p − 2pps + ps) log(p − 2pps + ps)−
−(1− (p − 2pps + ps)) log(1− (p − 2pps + ps))+
+(ps logps − (1− ps) log(1− ps))
Chương 3: Thông tin và định lượng thông tin 2. Entropi của nguồn rời rạc 27/ 55
Ví dụ: kênh nhị phân đối xứng (Tiếp)
Xét trường hợp p = q = 1/2, H(Y ) = 1
I(X ;Y ) = 1+ (1− ps) log2(1− ps) + ps log2(ps)
Đồ thị theo ps
ps = 0: không có sai số, lượng tin tương hỗ là 1, đạt cực đại
ps = 1: Sai số hoàn toàn, lượng tin tương hỗ là 1, đạt cực đại
ps = 0.5: lượng tin tương hỗ là 0, X ,Y độc lập thống kê, sự
truyền tin bị nhiễu phá hủy hoàn toàn
Chương 3: Thông tin và định lượng thông tin 2. Entropi của nguồn rời rạc 28/ 55
3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc
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
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
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 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 29/ 55
3.1.Tốc độ lập tin và độ dư của nguồn
Tốc độ tạo ra các tin (ký hiệu) của nguồn (vật lí)là hữu hạn
Lượng tin nguồn có thể tạo ra trong một đơn vị thời gian
R = n0H(X )
gọi là tốc độ lập tin của nguồn. Ký hiệu R
Để có tốc độ lập tin lớn với n0 (nguồn vật lí) cố định, cần
H(X ) lớn nhất
Để H(X ) lớn nhất: thay đổi cấu trúc thống kê của nguồn:mã
hóa thống kê
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 30/ 55
Ví dụ (Shannon)
Một nguồn X có 4 ký hiệu và có phân bố xác suất
X = x1, x2, x3, x4
p(x1) = 1/2,p(x2) = 1/4,p(x3) = 1/8,p(x4) = 1/8
Entropi của X là
H(X ) = −
∑
X
p(x) logp(x) = 7/4
Để có Entropi cực đại H(X )max = log2 4 = 2 cần có phân bố
xác suất đều cho các ký hiệu
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 31/ 55
Ví dụ (Shannon) (Tiếp)
Thực hiện liên tiếp hai phép biến đổi. Phép biến đổi thứ nhất
x1 → y0
x2 → y1y0
x3 → y1y1y0
x4 → y1y1y1
Xác suất của y0 và y1 là bằng nhau: (7/8)/(7/4) = 1/2
Biến đổi nguồn tin thu được thành một nguồn có 4 ký hiệu
y0y0 → z1
y1y0 → z2
y0y1 → z3
y1y1 → z4
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 32/ 55
Ví dụ (Shannon) (Tiếp)
Cả hai phép biến đổi đều bảo toàn lượng tin cho mỗi tin
Entropi của nguồn Z là 2, do đó tốc độ lập tin của nguồn Z
sẽ lớn hơn nguồn X
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 33/ 55
3.2.Khái niệm thông lượng của kênh
Lượng tin tối đa kênh cho đi qua trong một đơn vị thời gian
mà không gây sai nhầm. Ký hiệu C
Là tốc độ lập tin tối đa ở đầu ra của kênh
Tốc độ lập tin thường nhỏ hơn nhiều so với thông lượng
R  C
Tận dụng thông lượng của kênh
Tối đa tốc độ lập tin của nguồn cho phù hợp với kênh: Mã hóa
thống kê để có tốc độ lập tin cực đại, gần với thông lượng
(đồng bộ kênh-nguồn)
Cơ sở lý thuyết: định luật Shannon cho kênh không nhiễu
Sử dụng phần còn lại của thông lượng để chống nhiễu (mã
chống nhiễu)
Cơ sở lý thuyết: Định luật Shannon cho kênh có nhiễu
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 34/ 55
3.3.Thông lượng của kênh rời rạc không nhiễu
Kênh không có nhiễu:
Thông tin do nguồn thiết lập được truyền không có sai nhầm
Thông lượng kênh khi đó bằng tốc độ lập tin cực đại
C = Rmax = n0H(X )max(bit/sec)
Để tối ưu hệ thống cần cực đại entropi của nguồn
Tồn tại một phương pháp mã hóa với entropi cực đại?
Giới hạn của tốc độ truyền tin khi đó là bao nhiêu
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 35/ 55
Định lý Shannon cho kênh rời rạc không nhiễu
Giả định
Nguồn có entropi H(bit/ký hiệu)
Kênh có thông lượng C(bit/sec)
Chú ý C = Rmax = n0H(X )max(bit/sec)
Kết luận
1 Có thể mã hóa nguồn để truyền tin với tốc độ trung bình
C
H − (ký hiệu/s), bé tùy ý
2 Không thể truyền tin nhanh hơn CH (ký hiệu/s)
Chứng minh
1 ??? (Bài tập)
2 Hiển nhiên?
Tốc độ lập tin tối đa tiệm cận và có thể bằng với thông lượng
kênh. Phép mã hóa tương ứng gọi là phép mã hóa tối ưu.
Phép mã hóa tối ưu không sử dụng hết thông lượng của
kênh
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 36/ 55
Độ dư của nguồn
Khi tốc độ lập tin của nguồn chưa đạt cực đại, còn khả năng
để tối ưu nguồn. Khả năng này đo bằng độ dư của nguồn
Độ dư của nguồn
H(X )max − H(X )
Độ dư tương đối
rs =
H(X )max − H(X )
H(X )max
= 1− H(X )
H(X )max
Để có thể xây dựng mã chống nhiễu, điều kiện đầu tiên là
phải có độ dư
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 37/ 55
Độ dư của nguồn
Khi tốc độ lập tin của nguồn chưa đạt cực đại, còn khả năng
để tối ưu nguồn. Khả năng này đo bằng độ dư của nguồn
Độ dư của nguồn
H(X )max − H(X )
Độ dư tương đối
rs =
H(X )max − H(X )
H(X )max
= 1− H(X )
H(X )max
Để có thể xây dựng mã chống nhiễu, điều kiện đầu tiên là
phải có độ dư
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 38/ 55
3.4.Thông lượng của kênh rời rạc có nhiễu
Xét kênh không nhớ, có nhiễu
Các tin nhận được bị sai lệch
Nếu vẫn phân biệt được các tin đầu vào: không có sai nhầm
Nếu các tin đầu vào bị lẫn nhau ở đầu ra (nhiều tin đầu vào
cho một tin đầu ra): giảm độ chính xác truyền tin
Xuất hiện sai số truyền tin, đo bằng bit/s
Xét hệ thống gồm đầu vào X = {xi , i = 1 . . .m}, đầu ra
Y = {yj , j = 1 . . .n}. Do kênh có nhiễu, nên phép biến đổi
giữa X và Y được biểu diễn bằng ma trận xác suất chuyển
đổi p(yj |xi)
Lượng tin tương hỗ khi đó có thể tính theo
I(X ;Y ) = H(X )− H(X |Y )
I(X ;Y ) = H(Y )− H(Y |X )
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 39/ 55
3.4.Thông lượng của kênh rời rạc có nhiễu (Tiếp)
Tốc độ lập tin ở đầu ra của kênh
R = n0I(X ;Y ) = n0(H(X )− H(X |Y ))(bit/sec)
Trong đó n0H(X |Y )(bit/sec) là lương tin bị nhiễu phá hủy
trong một đơn vị thời gian
Khi các thông số của kênh đã xác định, muốn nâng cao tốc
độ lập tin đầu ra, cần phải tăng entropi bằng cách thay đổi
phương pháp mã hóa. Thông lượng kênh chính là tốc độ lập
tin tối đa ở đầu ra kênh:
C = Rmax = n0I(X ;Y )max = n0(H(X )−H(X |Y ))max(bit/sec)
Nếu xem giải thông của kênh∆f = n0 thì thông lượng kênh
có nhiễu là
C = ∆f (H(X )− H(X |Y ))max(bit/sec)
đảm bảo truyền tin không có sai nhầm
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 40/ 55
Định lý Shannon cho kênh có nhiễu
Với nguồn tin có tốc độ lập tin R, kênh tin có thông lượng C,
có thể truyền tin với độ chính xác tối đa là bao nhiêu?
Định lý
1 Với kênh rời rạc có thông lượng C, tốc độ lập tin của nguồn là
R < C có thể có phương pháp mã hóa để truyền tin với một
độ sai nhầm bé tùy ý.
2 Nếu R > C có thể mã hóa nguồn với sai số R − C + ,  bé
tùy ý.
3 Không tồn tại cách mã hóa với sai số nhỏ hơn R − C
Ýnghĩa
Nếu R < C phần dư của nguồn được dùng để bổ sung các
thông tin chống nhiễu. Cần truyền lượng tin lớn hơn so với
lươợng tin cần truyền.
NếuR > C, phần thông tin không được truyền đi sẽ trở thành
sai số (tối thiểu). Tồn tại cách mã hóa để có(tiệm cận) sai số
tổi thiểu
Chương 3: Thông tin và định lượng thông tin 3. Tốc độ lập tin của nguồn và thông lượng kênh rời rạc 41/ 55
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
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
Entropi của nguồn liên tục
Thông lượng kênh liên tục
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 42/ 55
4.1.Entropi của nguồn liên tục
Nguồn liên tục là một quá trình ngẫu nhiên liên tục. Để có
thể nghiên cứu, xem xét nguồn liên tục cần rời rạc hóa
nguồn liên tục
Với điều kiện nguồn có phổ hữu hạn, có thời gian tồn tại hữu
hạn, nguồn liên tục có thể được lấy mẫu với tần số 2∆f tại
các điểm {ti}, i = 1 . . .n
Mỗi một thể hiện của nguồn liên tục là một hàm x(t) theo
thời gian, được đặc trưng bởi n giá trị tức thời {xi}, i = 1 . . .n
Tính chất thống kê của nguồn đặc trưng bởi phân bố xác
suất đồng thời
p(x1, x2 . . . , xn)
Với nguồn dừng, phân bố xác suất này không phụ thuộc thời
gian
p(xti ) = p(xti+τ )
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 43/ 55
4.1.Entropi của nguồn liên tục (Tiếp)
Nguồn đặc trưng bằng một phân bố xác suất chung p(x)
Entropi của nguồn liên tục dừng
H(X ) = −
∫ ∞
−∞
p(x) logp(x)dx
Entropi của nguồn không dừng
−
∞∫
−∞
. . .
∞∫
−∞
p(xt1 , xt2 . . . xtn) logp(xt1 , xt2 . . . xtn)dx1dx2 . . .dxn
Tốc độ lập tin của nguồn
R = n0H(X ) = 2∆fH(X )
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 44/ 55
Entropi có điều kiện, Lượng tin tương hỗ
Entropi có điều kiện
H(X |Y ) = −
∞∫
∞
∞∫
−∞
p(x , y) logp(x |y)
H(Y |X ) = −
∞∫
∞
∞∫
−∞
p(x , y) logp(y |x)
Lượng tin tương hỗ
I(X ;Y ) = −
∞∫
∞
∞∫
−∞
p(x , y) log
p(x |y)
p(x)
dxdy
I(X ;Y ) = −
∞∫
∞
∞∫
−∞
p(x , y) log
p(y |x)
p(y)
dxdy
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 45/ 55
Quan hệ giữa lượng tin tương hỗ, lượng tin đồng thời và
Entropi
H(X ;Y ) = H(X )− H(Y |X ) = H(Y ) + H(X |Y )
H(XY ) = H(X ) + H(Y |X ), H(XY ) = H(Y ) + H(X |Y )
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 46/ 55
Ví dụ 1: Entropi của nguồn có công suất cực đại hạn
chế
Với công suất cực đại hạn chế bởi Pmax , x(t) biến đổi trong
phạm vi xmin ∼ xmax , xmin = −
√
Pmax , xmax =
√
Pmax
(Không chứng minh)Phân bố đều sẽ cho Entropi cực đại
p(x) =
1
2
√
Pmax
=
1
2xmax
H(X ) = −
xmax∫
xmin
1
2xmax
log
1
2xmax
dx = log(2xmax)
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 47/ 55
Ví dụ 2: Entropi của nguồn có công suất trung bình hữu
hạn
Công suất trung bình hữu hạn
∞∫
∞
x2p(x)dx = P2av
Entropy cực đại khi p(x) là phân bố gauss chuẩn
p(x) =
1√
2piPav
e
x2
2Pav
và có giá trị là
H(X ) = H(X )max =
∞∫
∞
p(x)[
x2
2Pav
+ ln
√
2piPav ]dx
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 48/ 55
Ví dụ 2: Entropi của nguồn có công suất trung bình hữu
hạn (Tiếp)
=
1
2Pav
∞∫
∞
x2p(x)dx + ln
√
2piPav
∞∫
∞
p(x)dx
=
1
2
+ ln
√
2piPav = ln
√
2piePav
Các nguồn nhiễu trắng có phân bố gauss chuẩn. Tốc độ lập
nhiễu
R = 2∆fH(N) = 2∆f ln
√
2piePN = ∆f ln 2piePN =
Để có thể có entropi lớn nhất, cần mã hóa thông tin sử dụng
các tín hiệu có phân bố chuẩn (giống nhiễu trắng): mã hóa
giả nhiễu
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 49/ 55
4.2.Thông lượng kênh liên tục
Xét kênh truyền tin có nhiễu cộng. Tín hiệu đầu ra là
y(t) = x(t) + n(t), x ∈ X , y ∈ Y ,n ∈ N
giả thiết X và N độc lập thống kê
Vậy
H(X ,Y ) = H(X ,X + N) = H(X ,N) = H(X ) + H(N)
Độ bất định của đầu ra bằng tổng độ bất định đầu vào và
nhiễu
Mặt khác
H(X ,Y ) = H(X ) + H(Y |X )
Vậy H(N) = H(Y |X )
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 50/ 55
4.2.Thông lượng kênh liên tục (Tiếp)
Tốc độ lập tin
R = n0[H(Y )− H(Y |X )] = 2∆f [H(Y )− H(N)]
Thông lượng kênh bằng tốc độ lập tin cực đại đầu ra
C = Rmax
Cần có H(Y ) cực đại để có thông lượng cực đại
Các tin của Y gồm hai thành phần từ X và N. Phụ thuộc vào
các hạn chế của X ,N có thể xác định qui luật phân bố của X
để thông lượng kênh cực đại
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 51/ 55
Trường hợp công suất trung bình hạn chế
Công suất trung bình đầu ra
PY = PX + PN
Để H(Y ) cực đại, Y có phân bố chuẩn. Nhiễu có quá trình
phân bố chuẩn, vậy X phải có quá trình phân bố chuẩn. Khi
đó
H(Y ) = H(Y )max = ln
√
2pie(PX + PN),H(N) = ln
√
2piePN
C = Rmax = 2∆f (H(Y )− H(N)) = ∆f (1+ PXPN )
gọi là công thức Shannon
Vậy muốn tăng thông lượng của kênh cần tăng giải thông∆f
hoặc tăng công suất tín hiệu
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 52/ 55
Trường hợp công suất trung bình hạn chế (Tiếp)
Giải thông không thể tăng vô hạn. Khi giải thông tăng, công
suất nhiễu cũng tăng
PN = ∆fN20
Khi đó
C = ∆f log2(1+
PS
∆f
N20 )
Giới hạn của thông lượng
lim
∆f→∞
(C) =
PX
N20
log2 e = 1.443
PX
N20
Các hệ thống truyền tin trong thực tế còn cách rất xa giới
hạn trên
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 53/ 55
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
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
Khái niệm entropi
Tính chất của Entropi
Entropi đồng thời và có điều kiện
3 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
4 Entropi của nguồn và thông lượng kênh liên tục
Entropi của nguồn liên tục
Thông lượng kênh liên tục
Chương 3: Thông tin và định lượng thông tin 4. Entropi của nguồn và thông lượng kênh liên tục 54/ 55