- Chæång V -
Chæång 5
Maî hoïa kãnh
Theo quan âiãøm cuía ngaình thäng tin, taìi nguyãn thäng tin chuí yãúu laì cäng suáút, thåìi gian vaì
bàng thäng cuía tên hiãûu. Âäúi våïi mäüt mäi træåìng thäng tin cho træåïc, ba taìi nguyãn naìy coï thãø
máu thuáùn láùn nhau. Viãûc cán âäúi caïc máu thuáùn naìy tuìy vaìo tæìng træåìng håüp cuû thãø. Tuy
nhiãn, nhçn chung thç ta coï thãø âaût âæåüc täúc âäü truyãön säúî liãûu cao nháút trong mäüt bàng thäng
nhoí nháút trong khi giæî cho cháút læåüng truyãön dáùn åí mæïc cháúp nháûn âæåüc. Trong thäng tin säú
thç cháút læåüng truyãön dáùn coï liãn quan máût thiãút våïi xaïc suáút läùi bit Pb taûi âáöu thu.
Âënh lyï vãö thäng læåüng kãnh cuía Shannon- Hartley:
)N/S1(logBC 2
+
=
(bit/s)
âaî chè ra giåïi haûn lyï thuyãút cuía täúc âäü truyãön säú liãûu tæì bäü phaït coï cäng suáút cho træåïc, qua
mäüt kãnh våïi bàng thäng cho træåïc, hoaût âäüng trong mäi træåìng coï nhiãùu âaî biãút. Tuy nhiãn,
âãø thæûc hiãûn âæåüc giåïi haûn lyï thuyãút naìy, ta phaíi tçm âæåüc mäüt phæång phaïp maî hoïa phuì håüp
(theo Shannon thç phæång phaïp naìy coï täön taûi).
Trong thæûc tãú, yãu cáöu cuía viãûc thiãút kãú laì phaíi thæûc hiãûn âæåüc mäüt täúc âäü truyãön säú liãûu yãu
cáöu (thæåìng âæåüc xaïc âënh båíi dëch vuû cung cáúp) trong mäüt bàng thäng haûn chãú cuía mäüt kãnh
truyãön sàôn coï vaì mäüt cäng suáút haûn chãú tuìy æïng duûng cuû thãø. Hån næîa, coìn phaíi âaût âæåüc täúc
âäü naìy våïi mäüt tyí säú BER (Bit Error Rate) vaì thåìi gian trãù cháúp nháûn âæåüc. Nãúu mäüt tuyãún
truyãön dáùn PCM khäng âaût âæåüc tyí säú BER yãu cáöu våïi caïc raìng buäüc naìy thç cáön phaíi sæí
duûng caïc phæång phaïp maî hoïa âiãöu khiãøn läùi (error control coding).
Maî hoïa âiãöu khiãøn läùi, coìn âæåüc goüi laì maî hoïa kãnh (channel encoding) âæåüc sæí duûng âãø
phaït hiãûn vaì sæía caïc kyï tæû hay caïc bit thu bë läùi. Maî hoïa phaït hiãûn läùi (error detection
coding) âæåüc sæí duûng nhæ laì bæåïc âáöu tiãn cuía quaï trçnh sæía läùi bàòng caïch kêch cho âáöu cuäúi
thu phaït ra tên hiãûu yãu cáöu làûp laûi tæû âäüng ARQ (Automatic Repeat reQuest), truyãön theo
hæåïng ngæåüc laûi vãö cho âáöu cuäúi phaït. Nãúu quaï trçnh truyãön laûi thaình cäng thç coi nhæ laì âaî
sæía âæåüc läùi. Nãúu kyî thuáût ARQ khäng thêch håüp, chàóng haûn nhæ khi trãù truyãön dáùn quaï låïn
thç seî sæí duûng kyî thuáût maî hoïa sæía läùi khäng phaín häöi FECC (Forward Error Correction
Coding). Caí maî phaït hiãûn läùi vaì maî sæía läùi âãöu âæa thãm âäü dæ vaìo dæî liãûu phaït, trong âoï âäü
dæ thãm vaìo trong maî sæía läùi nhiãöu hån trong maî phaït hiãûn läùi. Lyï do laì âäúi våïi maî sæía läùi,
âäü dæ thãm vaìo phaíi âuí cho bãn thu khäng chè phaït hiãûn âæåüc läùi maì coìn sæía âæåüc läùi, khäng
cáön phaíi truyãön laûi.
Pháön âáöu cuía chæång naìy seî trçnh baìy täøng quan vãö âiãöu khiãøn läùi aïp duûng trong hãû thäúng
thäng tin säú, bao gäöm giåïi thiãûu vãö caïc phæång phaïp âiãöu khiãøn läùi, phán loaûi caïc maî âiãöu
khiãøn läùi.
Pháön sau cuía chæång táûp trung vaìo caïc loaûi maî âiãöu khiãøn läùi, bao gäöm hai loaûi chênh laì maî
khäúi (block code) vaì maî cháûp (convolutional code).
- 105 -
- Chæång V -
Pháön maî khäúi seî nãu mäüt loaûi maî khäúi âån giaín nháút laì maî kiãøm tra chàôn leí parity.
Pháön maî khäúi tuyãún tênh (linear block code) seî táûp trung trçnh baìy vãö maî voìng (cyclic code)
vaì mäüt loaûi maî voìng âån giaín laì maî Hamming.
Pháön maî cháûp åí cuäúi chæång seî trçnh baìy phæång phaïp duìng så âäö cáy (tree diagram), så âäö
læåïi (trellis diagram) vaì så âäö traûng thaïi (state diagram) âãø minh hoüa cho quaï trçnh maî hoïa
maî cháûp. Pháön giaíi maî maî cháûp trçnh baìy thuáût toaïn Viterbi duìng så âäö læåïi.
Caïc näüi dung vãö maî hoïa âæåüc trçnh baìy åí âáy theo quan âiãøm laì daình cho ngæåìi âaî nàõm âæåüc
lyï thuyãút maî hoïa, chè nãu thuáût toaïn maî hoïa vaì giaíi maî, âæa ra vê duû minh hoüa, chæï khäng
nãu cå såí toaïn hoüc.
5.1 Täøng quan vãö âiãöu khiãøn läùi
5.1.1 Caïc phæång phaïp âiãöu khiãøn läùi
Âaûi læåüng âo läùi thäng thæåìng laì tyí lãû läùi bit BER (Bit Error Rate) hay xaïc suáút läùi bit (Pb). Pb
âån giaín laì xaïc suáút mäüt bit nhë phán báút kyì truyãön âi bë läùi. BER laì tyí säú läùi trung bçnh, âæåüc
tênh laì têch cuía Pb vaì Rb, åí âáy Rb laì täúc âäü bit trong kãnh. Pb âiãøn hçnh trong mäüt hãû thäúng
PCM tuyãún tênh laì 10 -7, trong hãû thäúng PCM neïn phi tuyãún laì 10 -5, trong hãû thäúng ADPCM
laì 10 -4.
Âiãöu khiãøn läùi nhàòm muûc âêch laì laìm giaím tyí lãû läùi trong mäüt hãû thäúng khi tyí lãû naìy låïn quaï
mæïc cho pheïp. Nhçn chung coï nàm phæång phaïp âiãöu khiãøn läùi.
Giaíi phaïp âáöu tiãn vaì dãù tháúy nháút laì tàng cäng suáút phaït, nhæng khäng phaíi luïc naìo cuîng coï
thãø thæûc hiãûn âæåüc. Vê duû nhæ, âäúi våïi mäüt maïy âiãûn thoaûi boí tuïi thç khäng cháúp nháûn khäúi
læåüng cuía pin quaï låïn.
Giaíi phaïp thæï hai, ráút hiãûu quaí trong viãûc chäúng laûi läùi chuìm gáy båíi fading, laì sæí duûng phán
táûp (diversity). Coï ba kiãøu phán táûp chênh laì phán táûp khäng gian, phán táûp táön säú vaì phán táûp
thåìi gian. Caí ba kiãøu phán táûp naìy âãöu âæa thãm âäü dæ vaìo trong dæî liãûu phaït bàòng caïch
truyãön gáúp âäi: qua hai âæåìng, taûi hai táön säú hay vaìo hai thåìi âiãøm khaïc nhau. Trong phán
táûp khäng gian, sæí duûng hai hay nhiãöu antenna âàût taûi nhæîng vë trê âuí xa âãø coï mäüt trong caïc
antenna âoï thu âæåüc tên hiãûu täút nháút, êt bë fading nháút. Phán táûp táön säú sæí duûng hai hay nhiãöu
táön säú khaïc nhau âãø phaït cuìng mäüt tin. Phán táûp táön säú coï thãø laì trong bàng hay ngoaìi bàng
tuìy vaìo khoaíng caïch táön säú giæîa caïc soïng mang. Trong hãû thäúng phán táûp thåìi gian, phaït
cuìng mäüt tin nhæng vaìo hai hay nhiãöu thåìi âiãøm khaïc nhau.
Giaíi phaïp thæï ba laì truyãön song cäng, hay coìn goüi laì kiãøm tra echo (echo checking). ÅÍ âáy,
khi bäü phaït phaït tin âãún bäü thu, tin âæåüc phaït ngæåüc vãö bäü phaït trãn mäüt kãnh häöi tiãúp riãng.
Nãúu tin phaït ngæåüc vãö khaïc våïi tin phaït âi thç biãút laì coï läùi. Phæång phaïp naìy coï khuyãút âiãøm
laì yãu cáöu bàng thäng gáúp âäi so våïi truyãön trãn mäüt hæåïng nãn khäng cháúp nháûn khi cáön táûn
duûng phäø.
Phæång phaïp thæï tæ âãø âäúi phoï våïi BER cao laì yãu cáöu làûp laûi tæû âäüng ARQ (Automatic
Repeat reQuest). Trong hãû thäúng ARQ, maî phaït hiãûn läùi (error detecting code) âæåüc sæí duûng
âãö bãn thu kiãøm tra läùi trong khäúi säú liãûu thu vaì traí låìi cho bãn phaït trãn mäüt kãnh häöi tiãúp.
- 106 -
- Chæång V -
Tên hiãûu traí låìi laì cháúp nháûn ACK (ACKnowledgment) khi säú liãûu thu âuïng vaì khäng cháúp
nháûn NAK (Non - AcKnowledgment) khi säú liãûu thu sai. Nãúu bãn phaït nháûn NAK, bãn phaït
phaíi tiãún haình truyãön laûi khäúi säú liãûu bë läùi. Coï hai kyî thuáût ARQ chênh laì ARQ dæìng vaì âåüi
(stop and wait ARQ) vaì ARQ liãn tuûc (continuous ARQ). Trong hãû thäúng ARQ dæìng vaì âåüi,
sau khi phaït khäúi säú liãûu âi, bãn phaït dæìng laûi vaì chåì nháûn traí låìi tæì bãn thu, räöi tuyì theo traí
låìi âoï laì ACK hay NAK maì bãn phaït phaït khäúi säú liãûu tiãúp theo hay phaït laûi khäúi säú liãûu væìa
räöi. Nãúu thåìi gian chåì quaï thåìi gian quy âënh (goüi laì time-out), bãn phaït coi nhæ laì khäúi säú
liãûu væìa phaït bë läùi vaì váùn tiãún haình phaït laûi. Haûn chãú cuía phæång phaïp naìy laì thåìi gian trãù
truyãön dáùn låïn. Trong hãû thäúng ARQ liãn tuûc, caïc khäúi säú liãûu âãöu mang säú thæï tæû - N - vaì
baín tin traí låìi ACK/NAK cuîng mang säú thæï tæû N tæång æïng. Bãn phaït liãn tuûc phaït âi caïc
khäúi säú liãûu maì khäng chåì nháûn traí låìi tæì bãn thu. Bãn thu kiãøm tra läùi caïc khäúi säú liãûu thu vaì
traí låìi vãö cho bãn phaït baín tin ACK/NAK keìm theo säú thæï tæû cuía khäúi tin tæång æïng. Khi naìo
bãn phaït nháûn traí låìi NAK tæì bãn thu, bãn phaït seî phaït laûi táút caí caïc khäúi säú liãûu kãø tæì khäúi säú
liãûu bë läùi âäúi våïi ARQ luìi laûi N (go-back-N ARQ), hoàûc bãn phaït seî chè phaït laûi khäúi säú liãûu
bë läùi âäúi våïi ARQ choün loüc (selective ARQ). Màûc duì ARQ choün loüc ráút hiãûu quaí trong sæí
duûng bàng thäng nhæng yãu cáöu dung læåüng bäü nhåï låïn hån ARQ luìi laûi N, âàûc biãût trong caïc
kãút näúi täúc âäü cao. ARQ phuì håüp våïi caïc hãû thäúng thäng tin maïy tênh, vç åí âoï coï sàôn kãnh
song cäng âãø bãn thu coï thãø phaït laûi cho bãn phaït baín tin ACK/NAK. Tuy nhiãn, trong caïc
âæåìng truyãön daìi våïi täúc âäü cao, âiãøn hçnh nhæ thäng tin vãû tinh thç ráút khoï thæûc hiãûn ARQ.
Phæång phaïp thæï nàm âãø giaím BER laì thæûc hiãûn maî hoïa sæía läùi khäng phaín häöi FECC
(Forward Error Correction Coding). Trong lëch sæí, viãûc cháúp nháûn sæí duûng räüng raîi FECC
coï trãù hån so våïi caïc phæång phaïp khaïc, båíi vç âäü phæïc taûp vaì giaï caí cuía noï cao hån. Ngaìy
nay, âäü phæïc taûp âaî giaím xuäúng nhåì vaìo sæû gia tàng caïc chip maî hoïa/ giaíi maî VLSI. FECC
låüi duûng sæû khaïc nhau giæîa täúc âäü truyãön dáùn vaì thäng læåüng kãnh âãø giaím xaïc suáút läùi Pb.
Viãûc giaím xaïc suáút läùi bë traí giaï bàòng viãûc tàng thåìi gian trãù truyãön dáùn, do tàng âäü dæ cho âuí
âãø maî coï thãø phaït hiãûn vaì sæía âæåüc läùi vaì do máút thåìi gian kiãøm tra khäúi säú liãûu thu âãø sæía
läùi. Tuy nhiãn, låüi êch cuía FECC coï âæåüc thæåìng nhiãöu hån khuyãút âiãøm vãö âäüì trãù låïn.
Maî khäúi
Maî khäng voìng
Maî Golay RS
Hamming (e=1) e>1
BCH nhë phán
Maî voìng
Maî tuyãún tênh
(Maî nhoïm)
Maî khäng
tuyãún tênh
Maî cháûp
Maî hoïa âiãöu khiãøn läùi
Hçnh 5.1 Phán loaûi maî âiãöu khiãøn läùi
- 107 -
- Chæång V -
5.1.2 Phán loaûi maî âiãöu khiãøn läùi
Nhçn chung, coï thãø phán loaûi maî phaït hiãûn vaì sæía läùi (goüi chung laì maî hoïa kãnh - maî hoïa
âiãöu khiãøn läùi) theo så âäö trong hçnh 5.1.
a) Maî khäúi
Maî khäúi âæåüc âàûc træng båíi hai säú nguyãn n vaì k, vaì mäüt ma tráûn sinh hay âa thæïc sinh.
Hçnh 5.2 minh hoüa mäüt bäü maî hoïa maî khäúi våïi k bit tin vaìo vaì n bit maî hoïa ra. Tæì maî n bit
âæåüc taûo ra duy nháút tæì k bit tin vaì (n-k) laì säú bit kiãøm tra dæ. Tyí lãû maî (coder rate) laì R =
k/n, laì tiãu chuáøn âãø âaïnh giaï âäü dæ cuía maî. Tyí lãû maî thæåìng tæì 1/2 âãún 1. Maî hãû thäúng
(systematic code) laì maî coï màût caïc bit tin cuìng våïi caïc bit dæ trong tæì maî. Trong caïc taìi liãûu
vãö maî hoïa thç coï hai âënh nghéa vãö maî hãû thäúng. Âënh nghéa nghiãm ngàût hån cho ràòng maî coï
tênh hãû thäúng khi k bit tin phaíi nàòm liãn tuûc thaình mäüt khäúi vaì caïc bit dæ phaíi nàòm liãn tuûc
trong mäüt khäúi khaïc. Âënh nghéa êt nghiãm ngàût hån thç chè yãu cáöu trong tæì maî coï màût caïc
bit tin chæï khäng cáön phaíi nàòm liãn tuûc thaình khäúi.
Bäü maî hoïa khäúi n bit
maî hoïa
k
b
it
tin
Tæì maî n bit
(n-k) bit k bit
Pháön tin Pháön dæ
Hçnh 5.2 Maî khäúi hãû thäúng (n, k)
Maî khäúi tuyãún tênh (liear block code) - coìn goüi laì maî nhoïm (group code) - coï caïc tæì maî coï
tæång æïng 1-1 våïi caïc pháön tæí thuäüc nhoïm toaïn hoüc. Maî tuyãún tênh coï chæïa tæì maî gäöm toaìn
säú 0 vaì coï tênh cháút âoïng, chàóng haûn âäúi våïi maî tuyãún tênh nhë phán, våïi hai tæì maî vaì
báút kyì, ta luän coï , cuîng laì mäüt tæì maî. Viãûc coï chæïa tæì maî gäöm toaìn säú
0 vaì tênh cháút âoïng laìm cho viãûc tênh toaïn âäúi våïi maî tuyãún tênh âàûc biãût dãù. Hçnh 5.3 laì mäüt
vê duû âån giaín vãö maî tuyãún tênh. Noï minh hoüa cho tênh cháút âoïng cuía maî. Coï 4 kyï tæû nguäön
laì a, b, c, vaì d, k = 2, n = 5. Âáy laì maî (5, 2)
i
C
j
Ckji CCC =+ k
C
a = 00 00000
b = 01 00111
c = 10 11100
Maî hoï
a
d = 11 11011
c
d
b
,
b
d
c,
d
b
c
=
⊕
=
⊕
=
⊕
Hçnh 5.3 Minh hoüa tênh cháút âoïng cuía maî khäúi tuyãún tênh
Maî voìng (cyclic code) laì mäüt låïp con cuía maî khäúi tuyãún tênh khäng coï tæì maî gäöm toaìn säú 0.
- 108 -
- Chæång V -
Mäüt maî khäúi tuyãún tênh âæåüc goüi laì maî voìng nãúu sau mäüt láön dëch voìng mäüt tæì maî thç cuîng
âæåüc mäüt tæì maî thuäüc cuìng bäü maî. Vê duû caïc tæì maî sau âáy âæåüc goüi laì maî voìng:
1101000, 0110100, 0011010, 1000110, 0001101, 1010001, 0100011.
Maî Golay laì mäüt loaûi maî voìng sæía âæåüc sai nhiãöu läùi. Maî Golay (23, 12) coï khaí nàng sæía
âæåüc 3 läùi cho tæì maî daìi 23 bit. Maî naìy âæåüc Golay phaït minh nàm 1949 vaì âæåüc nhiãöu
chuyãn gia quan tám nghiãn cæïu tåïi cáúu truïc vaì cå chãú giaíi maî. Thæûc tãú âang coï hai phæång
phaïp giaíi maî laì phæång phaïp Kasami vaì giaíi maî tçm kiãúm coï hãû thäúng (systematic search
decoding). Maî Golay (23, 12) âæåüc sæí duûng khaï phäø biãún trong mäüt säú hãû thäúng thäng tin.
Maî BCH nhë phán (binary BCH code) laì mäüt loaûi maî voìng âæåüc Hocquenghem tçm ra nàm
1959, sau âoï âæåüc Bose vaì Chaudhuri tçm ra mäüt caïch âäüc láûp vaìo nàm 1960. Maî BCH coï
thãø sæía âæåüc t läùi trong tæì maî daìi n bit, våïi . Vê duû maî
BCH (15, 7) coï thãø sæía sai täúi âa 2 läùi.
1t2d,mtkn,12n min
m+≥≤−−=
Maî RS âæåüc Reed vaì Solomon giåïi thiãûu láön âáöu tiãn vaìo nàm 1960. Theo lyï thuyãút maî, coï
thãø xem maî RS laì maî BCH khäng nhë phán. Maî RS âæåüc täø chæïc theo kyï tæû. Maî RS taûo
thaình n kyï tæû, mäùi kyï tæû daìi m bit, m tuìy thuäüc vaìo æïng duûng cuû thãø, vê duû m = 8 thç mäùi kyï
tæû chênh laì mäüt byte. Maî RS hoaût âäüng trãn kyï tæû nhiãöu bit chæï khäng phaíi trãn tæìng bit nhæ
caïc maî voìng khaïc. Mäüt âàûc âiãøm quan troüng cuía maî RS laì khaí nàng sæía läùi chuìm. Maî RS coï
thãø sæía sai t läùi, våïi 2
kn
t−
=. ÅÍ âáy n vaì k laì säú kyï tæû maî hoïa vaì säú kyï tæû mang tin chæï
khäng phaíi säú bit. Vê duû maî RS (31, 15) coï 15 kyï tæû vaìo, mäùi kyï tæû 5 bit, tæïc laì 75 bit tin vaì
31 kyï tæû maî hoïa, mäùi kyï tæû 5 bit. Maî naìy coï thãø sæía âæåüc 8 läùi bit âäüc láûp hoàûc 4 läùi chuìm daìi
khäng quaï 5 bit. Maî RS âæåüc duìng räüng raîi trong caïc âáöu CD vaì trong bäü nhåï maïy tênh.
Maî Hamming laì mäüt træåìng håüp riãng âån giaín nháút cuía maî BCH nhë phán. Maî naìy âæåüc
R.W. Hamming âæa ra vaì âæåüc duìng trong mäüt säú hãû thäúng thäng tin. Maî Hamming coï khaí
nàng sæía sai 1 läùi. Quan hãû giæîa n vaì k thoía maîn báút âàóng thæïc: 1n
2
2
n
k
+
≤
b) Maî cháûp
Maî cháûp cuîng âæåüc âàûc træng båíi hai säú nguyãn laì n vaì k nhæ maî khäúi, nhæng n bit ra khoíi
bäü maî hoïa khäng chè phuû thuäüc vaìo k bit vaìo maì coìn phuû thuäüc vaìo K-1 bäü k bit vaìo træåïc
âoï. K âæåüc goüi laì âäü daìi raìng buäüc (constraint length). Maî cháûp (n, k, K) âæåüc xáy dæûng tæì
caïc thanh ghi dëch kK bit. Váûy coï thãø xem maî cháûp laì maî coï nhåï, âoï laì âiãøm khaïc biãût cå baín
cuía maî cháûp so våïi maî khäúi.
Maî cháûp âæåüc Elias âãö xuáút láön âáöu tiãn vaìo nàm 1955. Sau âoï, Wozencraft âæa ra mäüt thuáût
toaïn giaíi maî tæång âäúi hiãûu quaí. Nàm 1963, Massey âæa ra caïch giaíi maî êt hiãûu quaí hån
nhæng dãù thæûc hiãûn. Nàm 1967, Viterbi âaî âæa ra thuáût toaïn giaíi maî täúi æu âæåüc goüi laì thuáût
toaïn Viterbi. Tæì âáy, maî cháûp âæåüc æïng duûng räüng raîi trong ngaình viãùn thäng.
5.1.3 Khaí nàng phaït hiãûn vaì sæía läùi cuía maî khäúi
- 109 -