LÝ THUYẾT THÔNG TIN
Bùi Văn Thành

Tháng 7 năm 2013
1
Trường Đại Học Công Nghệ Thông Tin
KHOA M
KHOA M
Ạ
Ạ
NG & TRUY
NG & TRUY
Ề
Ề
N THÔNG
N THÔNG
CHƯƠNG 3
Lượng tin,
Entropi nguồn rời rạc
2
3.1 MốI LIÊN Hệ CủA LƯợNG TIN
VÀ LÝ THUYếT XÁC SUấT

Sự tiếp xúc của con người với ngoại vật, nhận thức được
ngoại vật là thông qua thông tin tiếp thu được.
•
Một tin đối với người nhận có 2 phần, hay 2 nội dung:
1.
Độ bất ngờ của tin: rất liên quan đến các vấn đề cơ bản của hệ
thống truyền tin. Ví dụ: một tin càng bất ngờ, sự xuất hiện của
nó càng hiếm, thì rõ ràng thời gian nó chiếm trong một hệ

= (x
1
,…, x
n
) là một ký hiệu a
i
bất kỳ
thuộc nguồn A được gửi đi ở thời điểm t
k
. Tin x
(k)
có dạng: x
(k)
với
xác suất xuất hiện p(x
(k)
).
o
Thực hiện phép biến đổi tổng quát trong một hệ thống truyền tin
là phép biến đổi có cấu trúc thống kê của nguồn, ie, biến đổi cấu
trúc thống kê của tập tin ở đầu vào khâu hệ thống trở thành một tập
tin mới với một cấu trúc thống kê mong muốn ở đầu ra.
{A,p(a)} {B,p(b)} ,  quy luật biến đổi
o
{A,p(a)}: nguồn vào với bộ chữ A, có phân bố xác suất p(a)
o
{B,p(b)}: nguồn ra với bộ chữ B, có phân bố xác suất p(b)
4

3.2 LƯỢNG TIN RIÊNG, LƯỢNG TIN TƯƠNG HỖ,


Y
y
j

Yy
j

Y
y
j

Để giải quyết vấn đề, phải qua hai bước:
1.
Tính các lượng tin về một tin bất kỳ chứa trong tin nhận
được, lượng tin đó gọi là lượng tin tương hỗ giữa x
i
và y
i
.

Muốn xác định lượng tin tương hỗ ta phải tìm lượng tin ban đầu có
trong x
i
, sau khi thực hiện quá trình truyền tin ta tìm lượng tin còn
lại trong x
i
, hiệu hai lượng tin này cho ta thấy lượng tin đã truyền từ
x
i

yxI 
)(
)|(
log)|()(),(
i
ji
jiiji
xp
yxp
yxIxIyxI 







j
jijji
yxpypyxp )|()(/)|(log
TÍNH CHẤT CỦA LƯỢNG TIN
7
 Tính chất 1: I(x
i
) ≥ 0
 Tính chất 2: I(x
i
) ≥ I(x
i
,y

8
 Lượng tin trung bình: là lượng tin tức trung bình chứa trong
một ký hiệu bất kỳ của nguồn đã cho:
 Lượng tin tương hỗ trung bình:
Lượng tin riêng trung bình có điều kiện:
Quan hệ giữa các lượng tin trung bình:
)(
)/(
log),(),(
;
xp
yxp
yxpYXI
YyXx






XY
yxpyxpXIYXH )/(log),()()/(
)(log)()()()(
i
Aa
i
Aa
ii
apapaIapAI
ii

Hãy cho biết lượng tin riêng của mỗi tin và lượng tin trung bình của
nguồn này trong đơn vị bits.
Giải: Lượng tin riêng của mỗi tin là
p(u
0
) p(u
1
) p(u
2
) p(u
3
) p(u
4
) p(u
5
) p(u
6
) p(u
7
)
1/4 1/4 1/8 1/8 1/16 1/16 1/16 1/16
I(u
0
) I(u
1
) I(u
2
) I(u
3
) I(u

+ n
0
: số ký hiệu được lặp trong một đơn vị thời gian
Ví dụ: Cho nguồn tin với xác suất tương ứng là:
Nếu có một tin gồm các ký hiệu: . Để có H(x) cực đại
phải có xác suất các ký hiệu bằng nhau bằng 1/8


4321
,,, xxxxX

8/1)(;8/1)(;4/1)(;2/1)(
4321
 xpxpxpxp
8/7)(

XH
31212411
xxxxxxxx
VÍ Dụ (TT):
Muốn vậy ta mã hoá nguồn X trên thành nguồn Ynhư sau:
Ta được dãy các ký hiệu của tin :
Nguồn này có :
Mã hoá nguồn này thành nguồn Z với các ký hiệu sau:
Ta được dãy các ký hiệu của tin :
Xác suất các ký hiệu của nguồn bằng nhau và bằng 1/4 nên:
Vậy bằng phép mã hoá nguồn X thành nguồn Z ta có thể nâng Entropi
của nguồn X là H(x) = 7/8 thành Entropi H(z) = 2 mà vẫn đảm bảo
lượng tin trong các bản tin được bảo toàn và có cùng giá trị là 14
(bit)

3231441
zzzzzzz
24log)(


ZH
THÔNG LƯ
ợ
NG KÊNH
TRUYềN
13
Thông lượng của kênh C là lượng thông tin tối đa kênh cho qua đi
trong một đơn vị thời gian mà không gây sai nhầm (C(bps)).
Thông thường R < C, để R tiến tới gần C ta dùng phép mã hoá
thống kê tối ưu (sao cho R=C) để tăng Entrôpi.
Thông lượng kênh rời rạc không nhiễu:
C = R
max
= n
0
. H(X)
max
(bps)
R
max
tốc độ lập tin đầu vào, lượng tin này nhận được nguyên vẹn ở đầu ra
Nếu kênh có R < C thì ta có thể mã hoá để tăng R sao cho: C – R < , 
nhỏ tuỳ ý.
Độ dư của nguồn:
Độ dư tương đối của nguồn:

0
[H(X)-H(X/Y)] (bps)

Tốc độ lập tin cực đại trong kênh có nhiễu:
C = R
max
= n
0
[H(X)-H(X/Y)]
max
(bps)

Độ dư tương đối còn có thể được xác định theo công thức:

Hiệu quả sử dụng kênh:
14
C
R
r
c
 1
cc
r


1

3.4 ENTROPI CủA NGUồN RờI RạC

Khái niệm: Khi ta nhận được một tin ta sẽ nhận được một

(
Y
X
H
)|( XYH
Xx

Yy







YyXx
YyXx
xypyxpXYH
yxpyxpYXH
;
;
)|(log).()|(
)|(log).()|(
)|()(),(
)|()(),(
YXHYHYXH
XYHXHYXH




Xx
xp
)( xp
)(xp
m
2
log
mXH log)(

LƯ
ợ
NG TIN TƯƠNG H
ỗ
TRUNG BÌNH V
À
ENTROPI
Vậy:
Suy ra:
Nếu X,Y độc lập thống kê :
Và ta cũng chứng minh được:
18



YyXxYyXx
xpyxpyxp
xp
yxp
yxpYXI
;;

)|()( XYHYH

V
Í
D
ụ
:

Cho sơ đồ truyền tin:
Biết :
+ Tính Entropi đầu vào của kênh:
+ Tính Entropi đầu ra:
19
)|(
00
xyp
)|(
01
xyp
)|(
10
xyp
)|(
11
xyp
0
x
0
y
1

xypxpxypxpyp
583,0)|()()|()()(
1110101
 xypxpxypxpyp
98,0))(log)()(log)(()(
1100
 ypypypypYH
Tính H(X,Y):
Áp dụng công thức:
+ Tính:
20



YyXx
xypxypYXH
;
)(log)(),(
17,0)|()()(
00000


xypxpyxp
08,0)|()()(
01010


xypxpyxp
25,0)|()()(
10101