- Chæång IV -
Chæång 4
Maî hoïa nguäön
Hãû thäúng thäng tin âæåüc sæí duûng âãø truyãön tin tæïc tæì nguäön tin âãún nháûn tin. Nguäön tin sinh
ra tin dæåïi nhiãöu daûng khaïc nhau, vê duû ám thanh trong hãû thäúng radio, tên hiãûu video trong
hãû thäúng vä tuyãún truyãön hçnh...
Tin naìy coï thãø âæåüc âæa træûc tiãúp vaìo kãnh âãø truyãön âi, nhæng trong thæûc tãú, tin naìy thæåìng
âæåüc biãún âäøi räöi âæa vaìo kãnh truyãön. Vê duû nhæ tin laì vàn baín tiãúng Anh, nguäön tin coï
khoaíng 40 kyï tæû (symbol) khaïc nhau, gäöm caïc máùu tæû alphabet, con säú, dáúu cháúm cáu...Vãö
nguyãn tàõc ta coï thãø duìng 40 daûng soïng âiãûn aïp khaïc nhau âãø biãøu thë 40 kyï tæû naìy. Tuy
nhiãn thæûc tãú thç phæång phaïp naìy khäng phuì håüp, quaï khoï thæûc hiãûn hay tháûm chê khäng thãø
âæåüc, vç:
- Kãnh truyãön khäng phuì håüp vãö màût váût lyï âãø coï thãø mang nhiãöu kyï tæû khaïc nhau nhæ
váûy.
- Daíi táön âoìi hoíi seî ráút räüng.
- Viãûc læu træî hay xæí lyï tên hiãûu træåïc khi truyãön ráút khoï, trong khi nãúu chuyãøn sang nhë
phán thç moüi viãûc seî dãù daìng hån nhiãöu.
Váûy ta tháúy cáön phaíi thay âäøi daûng cuía tin khaïc âi so våïi daûng ban âáöu do nguäön cung cáúp.
Cäng viãûc thay âäøi daûng naìy âæåüc goüi laì maî hoïa (encoding).
Cå såí lyï thuyãút cuía maî hoïa laì lyï thuyãút tin (information theory). Lyï thuyãút tin liãn quan âãún
viãûc biãøu diãùn tin bàòng caïc kyï tæû, âæa ra giåïi haûn lyï thuyãút cho viãûc thæûc hiãûn hãû thäúng thäng
tin, cho pheïp âaïnh giaï hiãûu suáút cuía hãû thäúng thæûc tãú. Nãön taíng cuía lyï thuyãút tin do Hartley
vaì Nyquist âæa ra tæì nhæîng nàm 1920 vaì âæåüc Shannon hoaìn chènh vaì täøng kãút vaìo nàm
1948. Âáy laì mäüt lyï thuyãút phæïc taûp, pháön âáöu cuía chæång naìy daình âãø trçnh baìy nhæîng váún
âãö cå baín nháút cuía lyï thuyãút tin.
Vãö caïc muûc âêch cuía maî hoïa, ta coï thãø toïm tàõt nhæ sau:
-
Âënh daûng, âãø chuyãøn tin tæì daûng gäúc tæû nhiãn sang daûng chuáøn vê duû sang daûng säú
PCM.
-
Maî hoïa âæåìng, âãø âaím baío daûng soïng cuía kyï tæû truyãön âi phuì håüp våïi caïc âàûc âiãøm cuía
kãnh truyãön.
-
Maî hoïa nguäön (source encoding), nhàòm giaím säú kyï tæû trung bçnh yãu cáöu âãø truyãön baín
tin.
-
Máût maî hoïa (encryption), âãø maî hoïa baín tin bàòng mäüt khoïa máût maî nhàòm traïnh sæû thám
nháûp traïi pheïp, âaím baío âäü an toaìn cho thäng tin.
- Maî hoïa kãnh truyãön (channel encoding), cho pheïp bãn thu coï thãø phaït hiãûn, kãø caí sæía
- 81 -
- Chæång IV -
âæåüc caïc läùi trong baín tin thu âãø tàng âäü tin cáûy cuía thäng tin.
Pháön âënh daûng vaì maî hoïa âæåìng âaî âæåüc xeït âãún trong chæång III. Do nhæîng âàûc âiãøm
riãng, pháön máût maî hoïa khäng âæåüc âãö cáûp trong giaïo trçnh naìy. Pháön maî hoaï kãnh truyãön seî
âæåüc trçnh baìy trong chæång sau. Chæång naìy trçnh baìy vãö maî hoïa nguäön, trong âoï táûp trung
vaìo loaûi maî thäúng kã täúi æu. Loaûi maî naìy taûo ra tæì maî coï âäü daìi thay âäøi, trong âoï phäø biãún laì
maî Huffman, bao gäöm maî Huffman cå såí (basic Huffman) vaì maî Huffman âäüng (dynamic
Huffman). Pháön cuäúi chæång seî giåïi thiãûu så læåüc vãö maî hoïa fax (facsimile)
4.1 Lyï thuyãút tin
4.1.1 Âo tin tæïc
Âãø âaïnh giaï âënh læåüng cho tin tæïc, ngæåìi ta âæa ra khaïi niãûm læåüng tin (information content).
Læåüng tin liãn quan âãún giaï trë cuía tin, hay noïi caïch khaïc laì khaí nàng dæû âoaïn âæåüc
(predictability) cuía tin: mäüt tin coï khaí nàng âoaïn træåïc caìng nhiãöu thç caìng chæïa êt tin. Vê duû,
baín tin vãö tyí säú tráûn boïng Manchester United - Bradford Academicals laì 7 - 0 chæïa ráút êt tin
nhæng kãút quaí ngæåüc laûi thç gáy cháún âäüng, vaì do âoï chæïa ráút nhiãöu tin. Váûy xaïc suáút caìng
cao thç baín tin caìng chæïa êt tin vaì ngæåüc laûi. Ta coï thãø viãút:
p (baín tin) = 1 khäng mang tin
p (baín tin) = 0 mang mäüt læåüng tin vä haûn.
Tæì nháûn xeït trãn, ta tháúy tin caìng coï yï nghéa khi noï caìng hiãúm gàûp, nãn âäü låïn cuía noï phaíi tyí
lãû nghëch våïi xaïc suáút xuáút hiãûn cuía tin.
Xeït nguäön tin X råìi raûc sinh ra caïc tin i våïi xaïc suáút laì p(i), læåüng tin cuía tin i phaíi laì mäüt
haìm coï caïc âàûc âiãøm sau:
- Tyí lãû nghëch våïi xaïc suáút xuáút hiãûn p(i), hay âoï laì haìm f(1/p(i)).
- Haìm naìy phaíi laì 0 khi p(i) = 1.
- Nãúu hai tin âäüc láûp thäúng kã laì i vaì j âäöng thåìi xuáút hiãûn, ta coï tin laì (i,j), læåüng tin
chung cuía chuïng phaíi bàòng täøng læåüng tin cuía tæìng tin, nghéa laì:
f(1/p(i,j)) = f(1/p(i)) + f(1/p(j))
Theo luáût nhán xaïc suáút ta coï:
p(i,j) = p(i).p(j)
Do âoï:
f(1/(p(i).p(j))) = f(1/p(i)) + f(1/p(j))
Ta tháúy haìm loga thoaí maîn táút caí caïc yãu cáöu naìy. Váûy haìm log(1/p(i)) âæåüc choün âãø âaïnh
giaï âënh læåüng cho tin. Læåüng tin cuía mäüt tin i âæåüc kyï hiãûu laì I(i). Âënh nghéa læåüng tin cuía
mäüt tin i laì:
)i(plog
)i(p
1
log)i(I −==
- 82 -
- Chæång IV -
Âån vë âo cuía læåüng tin tuyì thuäüc vaìo cå säú cuía loga. Âån vë cuía læåüng tin laì bit, laì nat hay
laì hartley khi cå säú cuía loga láön læåüt laì 2, laì e hay laì 10. Trong âoï cå säú 2 thæåìng âæåüc choün
hån caí. Khi choün cå säú 2 thç læåüng tin cuía tin i laì:
)i(plog
)i(p
1
log)i(I 22 −== (bit)
Váûy coï thãø âënh nghéa bit nhæ sau: bit laì læåüng tin mang trong mäüt kyï tæû coï xaïc suáút xuáút hiãûn
laì p = 0,5.
4.1.2 Entropy cuía nguäön tin
Entropy H âæåüc âënh nghéa laì giaï trë trung bçnh thäúng kã cuía læåüng tin. Âoï laì læåüng tin trung
bçnh chæïa trong mäüt kyï tæû báút kyì cuía nguäön tin.
Xeït mäüt nguäön tin sinh ra M kyï tæû âäüc láûp thäúng kã. Nguäön tin naìy âæåüc goüi laì nguäön råìi raûc
khäng nhåï (discrete memoryless source). Entropy cuía nguäön naìy laìì:
∑
=
=
M
1m 2)m(p
1
log)m(pH (bit/kyï tæû)
trong âoï p (m) laì xaïc suáút choün kyï tæû thæï m.
Lyï thuyãút tin âaî chæïng minh giaï trë låïn nháút cuía entropy laì MlogH 2max
=
, âaût âæåüc khi
caïc kyï tæû âäüc láûp vaì âäöng xaïc suáút (equiprobable), nghéa laì:
M,1m,M/1)m(p =∀=
Âäúi våïi nguäön tin ASCII coï M = 128 thç entropy cæûc âaûi laì:
Hmax = - log2(1/128) = 7 (bit/kyï tæû).
Thæûc tãú thç âiãöu naìy khoï xaíy ra nãn entropy cuía nguäön ASCII laì:
7
)m(p
1
log)m(pH
128
1m 2<= ∑
=
(bit/kyï tæû)
Âäúi våïi nguäön tin nhë phán coï M = 2, nãúu p (1) = 1 vaì p (0) = 1-p thç entropy laì:
p1
1
log)p1(
p
1
logp
)m(p
1
log)m(pH 22
2
1m 2−
−+== ∑
=
(bit/kyï tæû)
4.1.3 Entropy coï âiãöu kiãûn vaì âäü dæ
Âäúi våïi caïc nguäön tin trong âoï viãûc sinh ra kyï tæû sau khäng âäüc láûp thäúng kã våïi caïc kyï tæû
træåïc âoï ( goüi laì nguäön coï nhåï - memory source) thç cäng thæïc entropy trãn khäng âuí täøng
quaït âãø tênh âæåüc entropy chênh xaïc.
Trong træåìng håüp naìy phaíi xeït âãún xaïc suáút coï âiãöu kiãûn (conditional probability). Vê duû våïi
nguäön coï nhåï mäüt kyï tæû, nghéa laì kyï tæû sau âæåüc choün phuû thuäüc vaìo mäüt kyï tæû træåïc âoï,
entropy âæåüc tênh nhæ sau:
- 83 -
- Chæång IV -
∑∑
=
j2
i)ij(p
1
log)i,j(pH (bit/kyï tæû)
åí âáy laì xaïc suáút nguäön choün i vaì j, )i,j(p )ij(p laì xaïc suáút nguäön choün j nãúu træåïc âoï âaî
choün i. Theo âënh lyï Bayes, ta coï:
)ij(p)i(p)i,j(p
=
Váûy:
∑∑
=
j2
i)ij(p
1
log)ij(p)i(pH (bit/kyï tæû)
Sæû khaïc nhau giæîa entropy thæûc sæû cuía nguäön vaì entropy cæûc âaûi goüi laì âäü dæ (redundancy)
cuía nguäön, kyï hiãûu laì r:
∑∑
−=−=
j2
i
2max )ij(p
1
log)ij(p)i(pMlogHHr (bit/kyï tæû)
Âäü dæ tæång âäúi cuía nguäön âæåüc âënh nghéa nhæ sau:
maxmax
max
H
H
1
H
HH
r−=
−
=
4.1.4 Sæû máút maït tin do nhiãùu
Goüi kyï tæû nguäön thæï i âæåüc truyãön âi laì , xaïc suáút xuáút hiãûn laì , læåüng tin cuía
laì :
TX
iTX
i )i(p TX
TX
i )i(I TXTX
)i(p
1
log)i(I
TX
2TXTX = (bit)
Âäúi våïi kãnh khäng nhiãùu (noiseless channel), giaí sæí âiãûn aïp tæång æïng våïi kyï tæû phaït laì
, khi bãn nháûn tin taïch âæåüc thç coï thãø biãút chàõc chàõn kyï tæû phaït åí nguäön laì .
Læåüng tin trong træåìng håüp naìy âæåüc baío toaìn khi truyãön qua kãnh:
RX
v
TX
iRX
vTX
i
)i(p
1
log)i(I)i:v(I
TX
2TXTXTXRXRX == (bit)
Tuy nhiãn, âäúi våïi kãnh coï nhiãùu (noise channel), khi bãn nháûn tin taïch âæåüc âiãûn aïp thç
khäng thãø kãút luáûn chàõc chàõn vãö kyï tæû thæûc phaït åí nguäön. Sæû khäng chàõc chàõn naìy liãn quan
âãún xaïc suáút
RX
v
)vi(p RXTX , âáy laì xaïc suáút phaït kyï tæû thæï i vaì taïch âæåüc âiãûn aïp åí bãn
nháûn (Âäúi våïi kãnh khäng nhiãùu, xaïc suáút naìy laì 1). Âäúi våïi kãnh coï nhiãùu, tin nháûn âæåüc êt
hån tin truyãön âi mäüt læåüng liãn quan âãún âäü khäng chàõc chàõn cuía quyãút âënh. Thæûc tãú, læåüng
tin nháûn âæåüc laì:
RX
v
- 84 -
- Chæång IV -
)i(p
)vi(p
log)i:v(I
TX
RXTX
2TXRXRX = (bit)
Giaí sæí bãn nháûn tin thæûc hiãûn quyãút âënh cæïng, âiãûn aïp chuyãøn âäøi træûc tiãúp thaình kyï tæû
nháûn laì . Trong træåìng håüp naìy, læåüng tin nháûn âæåüc laì:
RX
v
RX
i
)i(p
)ii(p
log)i(I
TX
RXTX
2RXRX = (bit)
Sæû suy giaím læåüng tin trong mäùi kyï tæû do nhiãùu coï nghéa laì entropy nháûn nhoí hån entropy
phaït. Entropy nháûn chênh laì entropy hiãûu quaí (effective entropy) cuía caïc kyï tæû nháûn. Kyï hiãûu
entropy hiãûu quaí laì vaì âæåüc tênh nhæ sau:
eff
H
∑
=
iRXRXRXeff )i(I)i(pH (bit/kyï tæû)
åí âáy laì xaïc suáút thu kyï tæû thæï i. )i(p RX
Sæû khaïc nhau giæîa vaì entropy phaït goüi laì âäü nghi ngåì (equivocation) E:
eff
H
eff
H= H - E (bit/kyï tæû)
Âäü nghi ngåì âæåüc tênh tæì viãûc ta khäng chàõc laì kyï tæû truyãön âi coï giäúng våïi kyï tæû nháûn âæåüc
hay khäng. Sæû khäng chàõc chàõn naìy laì do kãnh truyãön coï nhiãùu nãn coï thãø xem nhiãùu chênh
laì tin ám cäüng vaìo doìng kyï tæû phaït.
Âäü nghi ngåì âæåüc âënh nghéa laì:
)ji(p
1
log)ji(p)j(p
)ji(p
1
log)j,i(pE
RXTX
2
iRXTX
jj
RX
RXTX
2RXTX
i∑∑∑∑==
åí âáy laì xaïc suáút nháûn kyï tæû thæï j, )j(p RX )ji(p RXTX liãn quan âãún xaïc suáút läùi kyï tæû.
4.1.5 Täúc âäü láûp tin cuía nguäön tin
Ngoaìi thäng säú cå baín cuía nguäön laì entropy tuyì thuäüc vaìo cáúu truïc thäúng kã cuía nguäön, coìn
coï mäüt thäng säú khaïc tuyì thuäüc vaìo tênh cháút váût lyï cuía nguäön. Âoï laì täúc âäü thiãút láûp tin
(information rate) cuía nguäön, kyï hiãûu laì R. Thäng säú naìy chè ra sæû hçnh thaình tin nhanh hay
cháûm âãø âæa vaìo kãnh. Vê duû con ngæåìi, do kãút cáúu cuía cå quan phaït ám nãn mäùi giáy chè
phaït ám âæåüc tæì 5 âãún 7 tiãúng, trong khi mäüt thiãút bë âáöu cuäúi säú liãûu coï thãø âaût âãún haìng
ngaìn kyï hiãûu trong mäüt giáy.
Täúc âäü thiãút láûp tin cuía nguäön coï âån vë laì læåüng tin trãn âån vë thåìi gian (træåìng håüp duìng
loga cå säú 2 thç âån vë laì bit/s) vaì âæåüc tênh laì têch cuía entropy våïi säú kyï hiãûu láûp âæåüc trong
mäüt âån vë thåìi gian:
- 85 -