- 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ỡ vn 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 nm 1920 vaỡ õổồỹc Shannon hoaỡn chốnh vaỡ tọứng kóỳt vaỡo nm
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 õỷ

hm cọ cạc âàûc âiãøm sau:
- T lãû nghëch våïi xạc sút xút hiãûn p(i), hay âọ l hm f(1/p(i)).
- Hm ny phi l 0 khi p(i) = 1.
- Nãúu hai tin âäüc láûp thäúng kã l i v j âäưng thåìi xút hiãûn, ta cọ tin l (i,j), lỉåüng tin
chung ca chụng phi bàòng täøng lỉåüng tin ca tỉìng tin, nghéa l:
f(1/p(i,j)) = f(1/p(i)) + f(1/p(j))
Theo lût nhán xạc sút ta cọ:
p(i,j) = p(i).p(j)
Do âọ:
f(1/(p(i).p(j))) = f(1/p(i)) + f(1/p(j))
Ta tháúy hm loga tho mn táút c cạc u cáưu ny. Váûy hm log(1/p(i)) âỉåüc chn âãø âạnh
giạ âënh lỉåüng cho tin. Lỉåüng tin ca mäüt tin i âỉåüc k hiãûu l I(i). Âënh nghéa lỉåüng tin ca
mäüt tin i l:
)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)

(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

+==


2
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:

==
j
2
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

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

ọỹ 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
i
RXTX
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

tọỳi õa maỡ kónh cho qua cuợng bũng vồùi lổồỹng tin tọỳi õa maỡ nguọửn coù thóứ thióỳt lỏỷp. Vỏỷy thọng
lổồỹng kónh laỡ:
max0max
HnRC
=
=
(bit/s)
Theo Shannon, nóỳu R < C thỗ coù thóứ maợ hoùa õóứ laỡm cho tọỳc õọỹ lỏỷp tin cuớa nguọửn tióỳp cỏỷn vồùi
thọng lổồỹng kónh:


<

,RC laỡ vọ cuỡng beù
Phổồng phaùp maợ hoùa naỡy õổồỹc goỹi laỡ maợ hoaù thọỳng kó tọỳi ổu.
b) Trổồỡng hồỹp truyóửn tin trong kónh coù nhióựu:
Trong kónh coù nhióựu, lổồỹng tin truyóửn õi bở hao huỷt mọỹt phỏửn do nhióựu nón thọng lổồỹng kónh
bở giaớm õi. Lổồỹng giaớm õi õoù chờnh laỡ lổồỹng tin bở nhióựu phaù huớy trong mọỹt õồn vở thồỡi gian,
õổồỹc tờnh bũng n
0
E. Vỏỷy thọng lổồỹng kónh coù nhióựu laỡ:
)EH(nEnHnR
max00max0

=

=
Theo Shannon, nóỳu R < C thỗ coù thóứ maợ hoùa õóứ tin õổồỹc truyóửn õi trong kónh vồùi xaùc suỏỳt lọựi
beù tuyỡ yù vaỡ nóỳu R > C thỗ khọng thóứ truyóửn tin õi maỡ khọng bở lọựi. Phổồng phaùp maợ hoùa õóứ
giaớm xaùc suỏỳt lọựi õổồỹc goỹi laỡ maợ hoaù õióửu khióứn lọựi.

m mmx →
Phẹp biãún âäøi ngỉåüc lải: iil2i1i
xm mm →
âỉåüc gi l gii m (decoding).
Thäng thỉåìng, säú tin ca ngưn tin ráút låïn nãn säú k hiãûu m khäng thãø bàòng hồûc nhiãưu hån
säú tin.
4.2.2 Cạc tham säú cå bn ca m họa
Táûp M âỉåüc gi l m hiãûu (code), cạc pháưn tỉí
gi l k hiãûu m (symbol), säú k hiãûu m
khạc nhau trong m gi l cå säú ca m. M nhë phán l m cå säú 2, trong âọ m chè cọ 2 k
hiãûu m l 0 v 1.
k
m
Dy liãn tủc cạc k hiãûu m dng âãø m họa mäüt tin ca ngưn âỉåüc gi l tỉì m
(codeword). ÅÍ âáy tỉì m tỉång ỉïng våïi tin
l .
i
x
il2i1i
m mm
Säú k hiãûu m cọ trong mäüt tỉì m âỉåüc gi l âäü di ca tỉì m (codeword length), k hiãûu l
l. Vê dủ tỉì m 00100 cọ âäü di l 5.
Tham säú tiãúp theo l trng lỉåüng tỉì m (codeword weigh), âọ l täøng säú cạc k hiãûu khạc 0
cọ màût trong tỉì mỵ, k hiãûu l w. Vê dủ tỉì m 110001 cọ trng lỉåüng l 3.
Mäüt tham säú nỉỵa l khong cạch m (distance), k hiãûu l d. Âọ l säú k hiãûu cng vë trê
khạc nhau giỉỵa hai tỉì m di bàòng nhau. Vê dủ khong cạch giỉỵa hai tỉì m 110001 v
101000 l 3.

troỹng lổồỹng thay õọứi.
- Dổỷa vaỡo khoaớng caùch maợ giổợa hai tổỡ maợ kóử nhau, ta phỏn ra maợ coù khoaớng caùch
khọng õọứi vaỡ maợ coù khoaớng caùch thay õọứi.
- Dổỷa vaỡo cồ sọỳ cuớa maợ, ta phỏn ra maợ nhở phỏn (maợ cồ sọỳ 2), maợ baùt phỏn (maợ cồ sọỳ
8), maợ hexa (maợ cồ sọỳ 16) Trong õoù maợ nhở phỏn laỡ maợ thọng duỷng nhỏỳt. Chổồng
naỡy ta chố xeùt maợ nhở phỏn.
- Dổỷa vaỡo õọỹ tin cỏỷy, ta phỏn ra maợ coù khaớ nng phaùt hióỷn vaỡ sổớa lọựi vaỡ maợ
khọng coù
khaớ nng phaùt hióỷn vaỡ sổớa lọựi
- Dổỷa vaỡo hióỷu suỏỳt thọng tin, ta phỏn ra maợ tọỳi ổu vaỡ maợ chổa tọỳi ổu.
4.2.4 Caùc phổồng phaùp bióứu dióựn maợ
a) Phổồng phaùp lióỷt kó
ỏy laỡ phổồng phaùp bióứu dióựn maợ õồn giaớn nhỏỳt: chố cỏửn lióỷt kó caùc tin cuớa nguọửn vaỡ caùc tổỡ
maợ tổồng ổùng trong mọỹt baớng.
Vờ duỷ: nguọửn tin coù 8 tin (kyù tổỷ), caùc tin õổồỹc maợ hoùa nhổ baớng 4.1
Phổồng phaùp bióứu dióựn naỡy coù ổu õióứm laỡ cuỷ thóứ, roợ raỡng nhổng õọỳi vồùi caùc bọỹ maợ lồùn thỗ quaù
cọửng kóửnh.

Tin
A B C D E F G H
Tổỡ maợ
000 001 010 011 100 101 110 111
Baớng 4.1 Vờ duỷ vóử baớng maợ
b) Phổồng phaùp ma trỏỷn
Tổỡ vờ duỷ trón, ta thỏỳy: coù nhổợng tổỡ maợ laỡ tọứ hồỹp tuyóỳn tờnh cuớa caùc tổỡ maợ khaùc. Chúng haỷn
nhổ:
ECBH,ECG,EBF,CBD


=

cạc nụt nhạnh âãún nụt lạ.
Hçnh 4.1 l vê dủ vãư mäüt cáy m cho bäü m nhë phán gäưm cạc tỉì m l 00, 01, 10, 1101,
11001.
Mỉïc
11001
11
0
1
1
0
0
1
1
00

1
1
1
0
0
0

1k
1k
mxmxm xmxm)x(f +++++=
−
−
−
−

Vê dủ tỉì m nhë phán 1101001 cọ thãø biãøu diãùn bàòng âa thỉïc: . 1xxx)x(f
356
+++=
4.3 M họa ngưn
Hãû thäúng thäng tin âỉåüc sỉí dủng âãø truưn tin tỉïc tỉì ngưn tin âãún nháûn tin. Ngưn tin cọ ráút
nhiãưu dảng khạc nhau, nhỉng cọ thãø phán thnh hai loải chênh l ngưn liãn tủc (continuous
source) nhỉ ngưn ám thanh, ngưn video v ngưn råìi rảc (discrete source) nhỉ ngưn dỉỵ
liãûu tỉì mạy tênh.
Trong hãû thäúng thäng tin säú, âáưu ra ca ngưn phi âỉåüc chuøn thnh dảng thêch håüp âãø cọ
thãø truưn âi bàòng k thût säú. Theo sỉû phán loải ngưn, ta cọ hai k thût m họa ngưn
chênh l m họa ngưn liãn tủc v m họa ngưn råìi rảc. Näüi dung m họa ngưn liãn tủc
cng tr
ng våïi näüi dung säú hoạ tên hiãûu liãn tủc â xẹt trong chỉång trỉåïc.
Trong pháưn ny, ta xẹt quạ trçnh m họa ngưn råìi rảc (discrete source encoding). Ngưn råìi
rảc l ngưn sinh ra cạc k tỉû våïi mäüt quy lût phán bäú xạc sút no âọ. Âãø cho âån gin, ta
xẹt trỉåìng håüp ngưn khäng nhåï, cạc k tỉû âỉåüc sinh ra âäüc láûp våïi nhau. Thäng thỉåìng, quy
lût phán bäú xạc sút sinh ra cạc k tỉû l khäng âãưu nãn âäü dỉ ca ngưn låïn, entropy ca
ngưn bẹ, täúc âäü láûp tin ca ngưn cn xa måïi âảt âãún thäng lỉåüng kãnh. Lục âọ nhiãûm vủ
ca m họa ngưn råìi rảc l lm cho cáúu trục thäúng kã ca ngưn tråí nãn håüp l bàòng cạch
tàng entropy ca cạc k tỉû dng âãø m họa ngưn.
Ngun tàõc ca m họa ngưn råìi rảc l m họa cạc k tỉû cọ xạc sút sinh ra låïn bàòng cạc tỉì
m ngàõn v m họa cạc k tỉû cọ xạc sút sinh ra bẹ bàòng cạc tỉì m di. Loải m ny gi l

- Chổồng IV -
óứ cho pheùp maợ hoùa õaỷt hióỷu quaớ cao, toaỡn bọỹ lổồỹng tin rióng trong mọựi kyù tổỷ nguọửn phaới
õổồỹc chuyóứn hóỳt sang cho tổỡ maợ tổồng ổùng, hay lổồỹng tin trung bỗnh cuớa tổỡ maợ phaới lồùn hồn
hoỷc bũng lổồỹng tin trung bỗnh cuớa mọỹt kyù tổỷ nguọửn. Lổồỹng tin trung bỗnh cuớa mọỹt kyù tổỷ
nguọửn chờnh laỡ entropy cuớa nguọửn H. Vỏỷy:
HL
ỏy laỡ giồùi haỷn dổồùi cuớa õọỹ daỡi trung bỗnh cuớa tổỡ maợ. Dỏỳu bũng chố xaớy ra khi õọỹ daỡi cuớa mọỹt
tổỡ maợ bỏỳt kyỡ bũng vồùi lổồỹng tin rióng cuớa kyù tổỷ maỡ noù maợ hoùa:
)x(plogl
ii

=

Vỗ l
i
laỡ sọỳ nguyón nón - logp(x
i
) phaới laỡ sọỳ nguyón. Khi õoù õọỹ daỡi trung bỗnh cuớa tổỡ maợ seợ õaỷt
tọỳi thióứu L = L
min
. Ta coù bọỹ maợ thọỳng kó tọỳi ổu. Thổồỡng thỗ - logp(x
i
) khọng phaới laỡ sọỳ
nguyón nón
chố laỡ mọỹt õióửu kióỷn giồùi haỷn. HL
Ta coù thóứ thỏỳy: õóứ õọỹ daỡi tổỡ maợ trung bỗnh nhoớ nhỏỳt khi - logp(x
i
) khọng phaới laỡ sọỳ nguyón
thỗ L phaới thoaớ maợn bỏỳt õúng thổùc sau:
1HLH

Baớn tin
(Tỏỷp kyù tổỷ 2)
Baớn tin
(Tỏỷp kyù tổỷ 1)
Maợ hoùa
Hỗnh 4.2 Chuyóứn õọứi baớn tin giổợa hai tỏỷp kyù tổỷ khaùc nhau

Nóỳu caùc kyù tổỷ nguọửn õổồỹc maợ hoùa thaỡnh tổỡ maợ nhở phỏn thỗ coù mọỹt caùch khaùc õóứ tờnh hióỷu
suỏỳt maợ:
- 91 -
- Chổồng IV -
%100x
l)m(p
H
%100x
L
H
M
1m
m

=
== (bit/sọỳ nhở phỏn)
ồớ õỏy
l
m
laỡ õọỹ daỡi cuớa mọựi tổỡ maợ nhở phỏn vaỡ L laỡ õọỹ daỡi tổỡ maợ trung bỗnh.

1 thỗ chồỡ nhỏỷn thóm mọỹt sọỳ nổợa, rọửi cổù tióỳp
tuỷc nhổ vỏỷy.
Thuỏỷt toaùn giaới maợ (hỗnh 4.3 c) giaớ sổớ bón thu õaợ coù sụn baớng tổỡ maợ vaỡ baớng maợ ASCII tổồng
ổùng. Doỡng bit thu õổồỹc xổớ lyù trong bióỳn DOèNG BIT.ỡ Bióỳn Tặè MAẻ õổồỹc duỡng õóứ lổu caùc bit
vaỡo mọựi tổỡ maợ trong khi caùc tổỡ maợ naỡy õổồỹc hỗnh thaỡnh dỏửn. Nhổ ta thỏỳy tổỡ lổu õọử, mọựi khi tổỡ
- 92 -
- Chổồng IV -
maợ õổồỹc nhỏỷn daỷng, tổỡ maợ ASCII tổồng ổùng õổồỹc vióỳt vaỡo trong bióỳn Bĩ M THU. Thuớ
tuỷc naỡy õổồỹc lỷp laỷi cho õóỳn khi xổớ lyù hóỳt tỏỳt caớ caùc bit. Hỗnh 4.3 b laỡ mọỹt vờ duỷ vóử giaới maợ.

Doỡng bit thu: 0 1 0 0 1 1 1 1 1 0 0 - - - thồỡi gian

Tổỡ maợ: A B A D
t
ron
g
cỏ
y
maợ ?
Taới k
y
ù tổ
ỷ
ASCII vaỡo B
ĩ


M THU
aợ xổớ lyù tỏỳt caớ bit
t
ron
g
DOèNG BIT
Begin
(c)
(b)
(a)
End
Hỗnh 4.3 Thuỏỷt toaùn giaới maợ vaỡ mọỹt vờ duỷ giaới maợ thổỷc tóỳ
(a) Vờ duỷ cỏy maợ (b) Vờ duỷ giaớ i maợ (c) Thuỏỷt toaùn giaới maợ
- 93 -
- Chỉång IV -
4.4 M họa Huffman

=
(bit/k tỉû)
Nhỉ váûy hiãûu sút ca ngưn l:
%85%100x
3
55.2
==η
Nãúu mäùi k tỉû trãn âỉåüc m họa thnh 3 bit thç hiãûu sút m họa s giỉỵ ngun khäng thay
âäøi l 85 %.
M họa Huffman thỉûc hiãûn m họa sỉí dủng êt bit hån cho cạc k tỉû cọ xạc sút xút hiãûn cao
vç chụng âỉåüc truưn âi thỉåìng xun hån v ngỉåüc lải, nhiãưu bit hån cho cạc k tỉû cọ xạc
sút xút hiãûn tháúp nãn cọ thãø tàng âỉåüc hiãûu sút.
Thût toạn m họa Huffman gäưm cạc bỉåïc sau:
(1) Sàõp xãúp cạc k tỉû theo thỉï tỉû xạc sút gim dáưn.
(2) Gạn cho hai k tỉû cọ xạc sút xút hiãûn tháúp nháút våïi hai nhạnh (0) v (1) ca cáy m.
Tỉì hai k tỉû cọ
xạc sút tháúp nháút gim cn mäüt k tỉû våïi xạc sút bàòng täøng ca hai
xạc sút.
(3) Làûp lải tỉì bỉåïc (1) cho âãún khi chè cn lải mäüt k tỉû duy nháút våïi xạc sút l 1.
(4) Duût cáy m âãø tçm ra tỉì m tỉång ỉïng våïi tỉìng k tỉû ca ngưn.
- 94 -
- Chổồng IV -
Hỗnh 4.4 a trỗnh baỡy vờ duỷ vóử maợ hoùa Huffman cho nguọửn tin trón. Nóỳu ta quy ổồùc gaùn cho
nhaùnh õi ra tổỡ kyù hióỷu coù xaùc suỏỳt cao hồn laỡ 1 vaỡ nhaùnh kia laỡ 0, nhaùnh 0 veợ ồớ bón traùi, nhaùnh
1 veợ ồớ bón phaới thỗ ta coù thóứ veợ laỷi cỏy maợ Huffman vổỡa lỏỷp õổồỹc nhổ hỗnh 4.4 b.
(a)
C 0.40 0.40 0.40 0.40 0.40 0.40 0.60(1)
B 0.18 0.18 0.18 0.19 0.23 0.37(1) 0.40(0)
A 0.10 0.10 0.13 0.18 0.19(1) 0.23(0)
F 0.10 0.10 0.10 0.13(1) 0.18(0)

1 1
1 1
0
0 0
0 0
0
0.60 C 0.40
1 0
(b)
Hỗnh 4.4 Vờ duỷ maợ hoùa Huffman
(a) Taỷo cỏy maợ (b) Cỏy maợ

Goỹi troỹng sọỳ cuớa caùc nuùt trong cỏy maợ laỡ xaùc suỏỳt cuớa nuùt õoù, ta nhỏỷn thỏỳy cỏy maợ Huffman
vổỡa lỏỷp laỡ cỏy maợ tọỳi ổu theo nghộa thổù tổỷ troỹng sọỳ cuớa caùc nuùt tng dỏửn theo chióửu tổỡ dổồùi lón
trón vaỡ traùi sang phaới.
Nhỗn vaỡo cỏy maợ, ta thỏỳy kóỳ
t quaớ maợ hoùa Huffman cuớa nguọửn tin trón nhổ sau:
- 95 -
- Chỉång IV -

K tỉû
C B A F G E D H
Tỉì m
0 110 100 1111 1011 1010 11101 11100
Âäü di tỉì m trung bçnh báy giåì l:
L = 1(0.4) + 3(0.18 + 0.10) + 4(0.10 + 0.07 + 0.06) + 5(0.05 + 0.04) = 2.61(bit/k tỉû)
Váûy âäü låüi m họa l:
%7.97%100x
61.2
55.2

nọ nháûn, mäùi tỉì m phạt âỉåüc m họa
theo cng cạch ca bãn thu. Bãn thu tiãún hnh cạc thay âäøi giäúng nhỉ bãn phạt v cọ mäüt
bng sao riãng ca cáy. Nhåì âọ bãn thu s xạc âënh âụng tỉì m tiãúp theo âỉåüc nháûn tu vo
cáúu trục cáy måïi cáûp nháût.
C bãn phạt v bãn thu âãưu bàõt âáưu våïi mäüt cáy m chè cọ mäüt nhạnh trại - nhạnh 0 - v mäüt
- 96 -
- Chỉång IV -
nụt lạ räùng (empty leaf node) - nụt lạ cọ 0 láưn xút hiãûn.
Âãø mä t chi tiãút phỉång phạp ny, ta xẹt vê dủ bn tin truưn âi bàõt âáưu bàòng dy k tỉû:
A B C D C D C . . .
Hçnh 4.5 minh ha cạc bỉåïc láûp cáy m Huffman.
Trỉåïc tiãn, c bãn phạt v bãn thu cng thnh láûp cáy ban âáưu ( mäüt nhạnh 0 v mäüt nụt lạ
räùng e0).
Tiãúp theo, bäü m họa bàõt âáưu âc k tỉû âáưu tiãn trong bn tin - A - v gạn 'A'ï vo nhạnh phi-
nhạnh 1 âáưu tiãn. Vç âáy l láưn xút hiãûn âáưu tiãn ca 'A' nãn nọ âỉåüc truưn âi khäng nẹn
(dảng ASCII). Vç cáy bãn gii m âang räùng nãn nọ nháûn ra dy bit nháûn âỉåüc l mäüt k tỉû
khäng nẹn v nọ
sàõp xãúp k tỉû ny vo trong cáy theo cạch giäúng bãn m họa (hçnh 4.5a).
Våïi mäùi k tỉû tiãúp theo, trỉåïc hãút bäü m họa kiãøm tra xem k tỉû âọ â cọ màût trong cáy m
chỉa. Nãúu cọ räưi thç bäü m họa s gåíi tỉì m theo cạch thäng thỉåìng giäúng nhỉ m Huffman
cå såí, tỉì m âỉåüc xạc âënh båíi vë trê ca k tỉû trong cáy. Nãúu chỉa cọ thç bäü m họa gåíi tỉì
m hiãûn hnh cho nụt lạ räùng - âỉåüc xạc âënh båíi vë trê ca nụt lạ räùng trong cáy, theo sau l
tỉì m khäng nẹn ca k tỉû. Vç bäü gii m cng cọ cáy m y nhỉ váûy nãn nọ cọ thãø suy ra tỉì
dng bit nháûn âỉåü
c âáu l tỉì m cọ nẹn, âáu l nụt lạ räùng våïi k tỉû khäng nẹn theo sau.
Bäü m họa v gii m cáûp nháût vo cáy m dỉûa trãn k tỉû cúi cng âỉåüc phạt/ thu. Nãúu âáy
l k tỉû måïi thç nụt lạ räùng âang täưn tải trong cáy âỉåüc thay bàòng mäüt nụt nhạnh måïi, nụt lạ
räùng âỉåüc gạn bãn nhạnh 0 v k tỉû bãn nhạnh 1 (hçnh 4.5 b).
Nãúu k tỉû â cọ màût trong cáy thç säú láưn xút hiãûn ca nụt lạ tỉång ỉïng tàng lãn 1. Vê dủ hçnh
4.5 e, bäü m họa kiãøm tra v tháúy k tỉû 'C' â cọ màût trong cáy m nãn nọ truưn âi tỉì m

B1
C1
1
e 0
2
0 1
0 1
1 0
0


B1
1 0
2
C1 A1 B1
2


- 99 -
- Chæång IV -

0
0 1
C2
1 0
4
B1 D2
2
A1
1
e 0
0 1
1
0
0 1
C3
5
B1 D2
2
A1
1
e 0
0 1
1
0
0 1
(g) C 11
- 100 -
- Chỉång IV -

1 0

Thỉûc tãú, trong háưu hãút cạc ti liãûu, nhiãưu dng quẹt chè gäưm ton mu tràõ
ng, nhiãưu dng khạc
chỉïa c dy di mu tràõng v dy di mu âen. Vç mạy fax thỉåìng dng våïi mảng cäng cäüng
nãn ITU-T â âỉa ra cạc chøn liãn quan. Âọ l fax nhọm 1, nhọm 2, nhọm 3 v nhọm 4.
Nhọm 1 v nhọm 2 ngy nay ráút êt dng, nhọm 3 dng trong mảng PSTN, nhọm 4 dng trong
mảng hon ton säú ISDN. C nhọm 3 v nhọm 4 âãưu âảt t lãû nẹn khong 10:1. Do váûy âãø
truưn trang A4 våïi fax nhọm 3 chè máút chỉa âáưy 1 phụt, våïi fax nhọm 4 do cọ âỉåìng truưn
täúc âäü cao hån (64kbps) nãn chè máút vi giáy.
Quạ trçnh m họa trỉåïc tiãn l phán têch täøng quạt trang ti liãûu âỉåüc quẹt. Bng m fax âỉåüc
tảo ra dỉûa trãn cå såí
vãư táưn sút xút hiãûn ca mäüt säú pixel tràõng v âen liãn tủc (gi l run
length) trong mäùi dng quẹt. Tỉì m ngàõn hån thç âỉåüc áún âënh cho cạc run length hay xút
hiãûn hån v ngỉåüc lải. Nọi cạch khạc, âáy chênh l m họa Huffman cå såí. Bng m fax cäú
âënh gäưm hai bng m riãng biãût: bng m cúi (termination-codes table) v bng m make-
up (make-up codes table). Bng 4.2 l bng m nhọm 3 v nhọm 4 theo chøn ITU-T.
Bng m cúi dng cho cạc run length tỉì 0 âãún 63 pixel, bỉåïc nhy l 1 pixel. Bng m
make-up dng cho cạc run length tỉì 64 âãún 2560 pixel, bỉåïc nhy l 64 pixel. K thût quẹt
- 101 -
- Chỉång IV -
ngáưm âënh l táút c cạc dng âãưu bàõt âáưu våïi êt nháút l 1 pixel mu tràõng. Theo cạch ny, bãn
thu biãút âỉåüc tỉì m âáưu tiãn ln ln liãn quan âãún pixel mu tràõng.
(a)

Run length tràõng Tỉì m Run length âen Tỉì m
0 00110101 0 0000110111
1 000111 1 010
2 0111 2 11
3 1000 3 10

62 00110011 62 000001100110
1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 bit

| 6W |2B| 9W |2B| 5W | 8B |2W run length

1110 10100 1100 0111 tràõng

11 11 000101 âen

111011101001111000001010111 âáưu ra ca m họa
fax (Huffman)
Hçnh 4.6 Vê dủ m họa fax

TỌM TÀÕT CHỈÅNG
1. Lỉåüng tin l mäüt âải lỉåüng dng âãø âạnh giạ âënh lỉåüng cho tin tỉïc. Lỉåüng tin liãn quan
âãún kh nàng dỉû âoạn âỉåüc ca tin. Lỉåüng tin âỉåüc tênh l logarit ám ca xạc sút xút
hiãûn ca tin. Nãúu cå säú ca liogarit l 2 thç âån vë va lỉåüng tin l bit.
2. Entropy H ca ngưn tin l lỉåüng tin trung bçnh chỉïa trong mäüt k tỉû báút k ca ngưn
tin. Giạ trë låïn nháút ca entropy âảt âỉåüc khi cạc k tỉû âäüc láûp v âäưng xạc sút. Entropy
ca mäüt ngưn tin nhë phán âäüc láûp thäúng kã, xạc sút xút hiãûn ca säú '1' v '0' bàò

tuún tênh; phỉång phạp cáy giụp cho viãûc gii m dãù dng, nhçn vo cáy cọ thãø biãút âỉåüc
mäüt säú âàûc âiãøm ca bäü m; phỉång phạp âa thỉïc thêch håüp våïi cạc m vng, giụp cho
viãûc m họa v gii m m vng dãù d
ng bàòng cạch sỉí dủng cạc phẹp toạn âäúi våïi âa
thỉïc.
11. M họa ngưn nhàòm loải b âäü dỉ trong cạc k tỉû dng âãø m họa, lm cho viãûc truưn
v lỉu trỉỵ thäng tin tråí nãn hiãûu qu hån. Nọi chung thç m họa ngưn phi tha tênh gii
m duy nháút.
12. Ngun tàõc ca m họa ngưn råìi rảc l m họa cạc k tỉû cọ xạc sút sinh ra låïn bàòng
cạc tỉì m ngàõn v m họa cạc k tỉû cọ xạc sút sinh ra bẹ bàòng cạc tỉì m di. Loải m
ny gi l m họ
a thäúng kã.
13. Viãûc truưn tin s tråí nãn kinh tãú hån nãúu m thäúng kã cọ âäü di trung bçnh ca tỉì m l
nh nháút. Loải m nhỉ váûy gi l m thäúng kã täúi ỉu. Âáy cng chênh l m họa nẹn.
14. M Huffman l mäüt loải m thäúng kã täúi ỉu. M Huffman âảt âỉåüc u cáưìu vãư âäü di tỉì
m trung bçnh nh nháút v tho tênh gii m duy nháút. Thãm vo âọ, m Huffman cn
tho tênh gii m tỉïc thåìi, nghéa l khäng cọ tỉì m no trng våïi pháưn âáưu ca tỉì m khạc
di hån nọ.
15. M họa fax - loải m họa dng trong dëch vủ
facsimile - l mäüt ỉïng dủng ca m hoạ
Huffman cå såí. Âáy l loải m tho tênh gii m duy nháút, tỉïc thåìi v khäng cọ täøn hao.
Phỉång phạp m họa ngưn cho phẹp âảt nhỉỵng chè tiãu kinh tãú täút, tuy nhiãn cáưn phi âm
bo chè tiãu truưn tin chênh xạc. Âãø gii quút váún âãư ny cọ mäüt gii phạp l m họa kãnh.
- 104 -