Trang 142
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
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 143
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 = {x
1
, , x
K
}, mt bng kí
hiu đu ra (ngun nhn)
Y = {y
1
, , y
J
}, và mt s phân b xác
sut có điu kin
p(y
j
| x
k

N
n
knjnkNkjNj
xypxxyyp
1
11
)|(}|{ LK
p(y
J
| x
K
) p(y
2
| x
K
)p(y
1
| x
K
)x
K

p(y
J
| x
2
) p(y
2
| x
2

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
k
kjkj
xypxpyp
1
)|()()(
Trang 146
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 x
k
nào đã đc phát phát đi khi nhn đc 
đu nhn mt kí hiu y
j
nào đó?
̈ Ví d
̈ Cho ngun X = {x
1
, x
2
} vi các xác sut ln lt là p(x
1

| y
1
), nh vy chúng ta có th khng đnh đc
kí hiu
x
2
có kh nng đc phát đi hn x
1
?
∑∑
==
×
×
=
×
==
K
i
iji
kjk
K
i
ji
kjk
j
jk
jk
xypxp
xypxp
yxp

yxp
5
3
)|(
12
=
yxp
Trang 148
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Ví d (tt)
̈  ý, trong công thc ca p(x
i
| y
j
) có cha tha s p(x
i
), nên
p(x
i
| y
j
) đã bnh hng bi xác sut l p(x
i
).
̈ 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(x
i
| y
j

11
=
=
==
xp
yxp
xp
yxp
Trang 149
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Lng tin có điu kin I(x
k
| y
j
)
̈ nh ngha
I(y
j
| x
k
) = –log p(y
j
| x
k
)
I(x
k
| y
j
) = –log p(x

s có hai kh nng và
y
j
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(y
j
| x
k
) = 1/2 ch xy ra khi kênh truyn có nhiu.
Trang 150
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Lng tin có điu kin I(x
k
| y
j
)
̈ 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 x
k
bên nhn s có mt tp các y
j
có kh nng đc
nhn.
̈ Ngc li khi nhn đc y
j
bên phát s có mt tp các x

| y
j
)
̈ Nu p(x
k
| y
j
) = 1 có ngha là nu y
j
đã nhn đc thì chc chn
x
k
đã đc phát đi, điu này có ngha là lng tin ca x
k
đã
đc truyn nguyên vn thông qua kênh, do đó I(x
k
, y
j
) = I(x
k
).
)(
)(
)(
)(
j
kj
k
jk

kjkjk
xypxypxyIxypxYI
11
)|(log)|()|()|()|(
∑
=
−==
J
j
K
k
jkjkj
J
j
jj
yxpyxpypyXIypYXI
111
)|(log)|()()|()()|(
−=
K
k
J
j
jkjk
yxpyxp
11
)|(log),(
−=
K
k

11
)|(log),()|( yx
Trang 154
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Chng minh
̈ Ly tng trên nhng cp (k, j) mà p(x
k
, y
j
) ≠ 0. Vì vy
+−=−
K
k
J
j
K
k
kkjkjk
xpxpyxpyxpHH
11 1
)(ln)()|(ln),()()|( xyx
−=
K
k
J
j
jk
k
jk
yxp

yxpypxp ),()()(
[
]
01)()( ≤−=
∑
∑
kj
jk
ypxp
Trang 155
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Chng minh (tt)
̈ Du “=” xy ra ⇔ p(x
k
) = p(x
k
| y
j
) đi vi tt c các cp (k, j)
mà
p(x
k
, y
j
) ≠ 0 đng thi tng p(x
k
)p(y
j
) trên tt c nhng cp
này bng 1.

xypxpyxp )|(log)(log),(
[
]
∑
∑∑
−−=
kj
kjkj
k
kk
xypyypxpxp )|(log),()(log)(
)|()( xyx HH
+
=
Trang 157
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Lng tin tng h trung bình
̈ 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)
∑
∑
=
kj
jkjk
yxIyxpYXI ),(),(),(
=
kj
k
jk
jk

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
p
1
’, , p
J
’vàmi ct cha cùng tp các s q
1
’, , q
K
’.
̈ Ví d
1 – εε
0 ≤ε≤1
ε1 – ε
[p(y
j
| x
k
)] =
0,30,20,5
0,20,50,3
0,50,30,2
[p(y
j
| x
k
)] =
k = 20,20,20,30,3

K
k
J
j
kjkjk
xypxypxp
11
)|(log)|()(
−=
K
k
J
j
jjk
ppxp
11
''
log)(
∑
=
−=
J
j
jj
pp
1
''
log
Trang 160
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin

y
1
x
1
x
2
x
m
x
m+1
y
2
x
K
y
J
Trang 161
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 p

) p(y
j
)
Vì vy đu vào và đu ra đc lp nhau bt chp s phân b xác
sut ca đu vào.
̈ iu kin cn
Gi s các dòng ca ma trn không ging nhau ⇒∃mt ct
chng hn
j
0
mà có các phn t không ging nhau.
Gi s
p(y
j0
| x
k0
) là phn t ln nht trong ct này. Xét s phân
b đng nht (đng xác sut)  đu vào (đu phát), chúng ta có
====
K
k
K
k
K
k
jkjkjkjkj
pxppxypxpyxpyp
11 1
''
)()|()(),()(

K
k
kjkjkjkj
xypxyp
K
xypxpyp
11
00000
)|()|(
1
)|()()(
Trang 164
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
S nhp nhng (equivocation)
và tc đ truyn tin
̈ Xét mt kênh nh phân đi xng vi xác sut chéo ε. Gi s
rng ti đu vào P(0) = P(1) = 1/2, tc đ sinh thông tin  đu
phát là
H(x) = 1 bit/kí hiu.
̈ Mt thit b đc gi là b quan sát, nhn mi cp kí hiu
vào/ra
(x, y) và sinh ra mt kí hiu z
̈ z = 0
nu x = y, z = 1 nu x ≠ y
Kênh
B quan sát
…x
(2)
x
(1)

z
(1)
z
(2)
đã đc to sn.
̈ Tc đ truyn thông tin trên kênh, thng kí hiu là R, là bng
tc đ sinh thông tin H(x) tr tc đ sinh thông tin b sung
H(z).
R = H(x) – H(z)
Trang 166
Lý thuyt Thông tin - Khoa Công Ngh Thông Tin
Ví d
̈ Chng hn, nu d liu đu vào đc sinh  tc đ 1000 kí
hiu/giây
và ε = 0,01, chúng ta có
H(x) = 1 → tc đ d liu đu vào = 1000 bits/giây
H(z) = 0,081
→ tc đ d liu b sung = 81 bits/giây
R = 0,919
→ tc đ truyn thông tin = 919 bits/giây
̈
Mt ngi có th lý lun rng trong mt dãy dài, vì ε = 0,01,
ngha là ch 1% s bit đc truyn b li, và vì vy tc đ
truyn thông tin phi là
990 bits/giây.
̈ Câu tr li là rng kin thc v s bit b li không đ đ xây
dng li d liu, mà chúng ta cn phi bit thêm v v trí li
na, và vì lý do này nên tc đ truyn thông tin là thc s bng
mt giá tr thp hn là
919 bits/giây.