Giáo trình Kĩ thuật thông tin số - Chương 5: Mã hóa kênh
- Chæång V -
Chæång
5
Ma hoa kãnh
Theo quan âiãm cua nganh thäng tin, tai nguyãn thäng tin chu yãu la cäng suát, thåi gian va
bàng thäng cua tên hiãu. Âäi våi mät mäi træång thäng tin cho træåc, ba tai nguyãn nay co thã
máu thuán lán nhau. Viãc cán âäi cac máu thuán nay tuy vao tæng træång håp cu thã. Tuy
nhiãn, nhçn chung thç ta co thã âat âæå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 xac suát läi bit Pb tai âáu thu.
Âënh ly vã thäng læång kãnh cua Shannon- Hartley:
C = Blog (1+ S/ N) (bit/s)
2
âa chè ra giåi han ly thuyãt cua täc âä truyãn sä liãu tæ bä phat co cäng suát cho træåc, qua
mät kãnh våi bàng thäng cho træåc, hoat âäng trong mäi træång co nhiãu âa biãt. Tuy nhiãn,
âã thæc hiãn âæåc giåi han ly thuyãt nay, ta phai tçm âæåc mät phæång phap ma hoa phu håp
(theo Shannon thç phæång phap nay co tän tai).
Trong thæc tã, yãu cáu cua viãc thiãt kã la phai thæc hiãn âæåc mät täc âä truyãn sä liãu yãu
cáu (thæång âæåc xac âënh båi dëch vu cung cáp) trong mät bàng thäng han chã cua mät kãnh
truyãn sàn co va mät cäng suát han chã tuy æng dung cu thã. Hån næa, con phai âat âæåc täc
âä nay 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 âat âæåc ty sä BER yãu cáu våi cac rang buäc nay thç cán phai sæ
dung cac phæång phap ma hoa âiãu khiãn läi (error control coding).
Ma hoa âiãu khiãn läi, con âæåc goi la ma hoa kãnh (channel encoding) âæåc sæ dung âã
phat hiãn va sæa cac ky tæ hay cac bit thu bë läi. Ma hoa phat hiãn läi (error detection
coding) âæåc sæ dung nhæ la bæåc âáu tiãn cua qua trçnh sæa läi bàng cach kêch cho âáu cuäi
thu phat ra tên hiãu yãu cáu làp lai tæ âäng ARQ (Automatic Repeat reQuest), truyãn theo
hæång ngæåc lai vã cho âáu cuäi phat. Nãu qua trçnh truyãn lai thanh 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 han nhæ khi trã truyãn dán qua lån
thç se sæ dung ky thuát ma hoa sæa läi khäng phan häi FECC (Forward Error Correction
Coding). Ca ma phat hiãn läi va ma sæa läi âãu âæa thãm âä dæ vao dæ liãu phat, trong âo âä
dæ thãm vao trong ma sæa läi nhiãu hån trong ma phat hiãn läi. Ly do la âäi våi ma sæa läi,
âä dæ thãm vao phai âu cho bãn thu khäng chè phat hiãn âæåc läi ma con sæa âæåc läi, khäng
cán phai truyãn lai.
Phán âáu cua chæång nay se trçnh bay täng quan vã âiãu khiãn läi ap dung trong hã thäng
thäng tin sä, bao gäm giåi thiãu vã cac phæång phap âiãu khiãn läi, phán loai cac ma âiãu
khiãn läi.
Phán sau cua chæång táp trung vao cac loai ma âiãu khiãn läi, bao gäm hai loai 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 loai ma khäi âån gian 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 bay vã ma vong (cyclic code)
va mät loai ma vong âån gian la ma Hamming.
Phán ma cháp å cuäi chæång se trçnh bay phæång phap dung så âä cáy (tree diagram), så âä
læåi (trellis diagram) va så âä trang thai (state diagram) âã minh hoa cho qua trçnh ma hoa
ma cháp. Phán giai ma ma cháp trçnh bay thuát toan Viterbi dung så âä læåi.
Cac näi dung vã ma hoa âæåc trçnh bay å âáy theo quan âiãm la danh cho ngæåi âa nàm âæåc
ly thuyãt ma hoa, chè nãu thuát toan ma hoa va giai ma, âæa ra vê du minh hoa, chæ khäng
nãu cå så toan hoc.
5.1 Täng quan vã âiãu khiãn läi
5.1.1 Cac phæång phap âiãu khiãn läi
Âai læång âo läi thäng thæång la ty lã läi bit BER (Bit Error Rate) hay xac suát läi bit (Pb). Pb
âån gian la xac 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 cua 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 nen phi tuyãn la 10 -5, trong hã thäng ADPCM
la 10 -4.
Âiãu khiãn läi nhàm muc âêch la lam giam ty lã läi trong mät hã thäng khi ty lã nay lån qua
mæc cho phep. Nhçn chung co nàm phæång phap âiãu khiãn läi.
Giai phap âáu tiãn va dã tháy nhát la tàng cäng suát phat, nhæng khäng phai luc nao cung co
thã thæc hiãn âæåc. Vê du nhæ, âäi våi mät may âiãn thoai bo tui thç khäng cháp nhán khäi
læång cua pin qua lån.
Giai phap thæ hai, rát hiãu qua trong viãc chäng lai läi chum gáy båi fading, la sæ dung 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 nay âãu âæa thãm âä dæ vao trong dæ liãu phat bàng cach
truyãn gáp âäi: qua hai âæång, tai hai tán sä hay vao hai thåi âiãm khac nhau. Trong phán
táp khäng gian, sæ dung hai hay nhiãu antenna âàt tai nhæng vë trê âu xa âã co mät trong cac
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æ dung hai hay nhiãu
tán sä khac nhau âã phat cung mät tin. Phán táp tán sä co thã la trong bàng hay ngoai bàng
tuy vao khoang cach tán sä giæa cac song mang. Trong hã thäng phán táp thåi gian, phat
cung mät tin nhæng vao hai hay nhiãu thåi âiãm khac nhau.
Giai phap thæ ba la truyãn song cäng, hay con goi la kiãm tra echo (echo checking). Å âáy,
khi bä phat phat tin âãn bä thu, tin âæåc phat ngæåc vã bä phat trãn mät kãnh häi tiãp riãng.
Nãu tin phat ngæåc vã khac våi tin phat âi thç biãt la co läi. Phæång phap nay 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
dung phä.
Phæång phap thæ tæ âã âäi pho våi BER cao la yãu cáu làp lai tæ âäng ARQ (Automatic
Repeat reQuest). Trong hã thäng ARQ, ma phat hiãn läi (error detecting code) âæåc sæ dung
âã bãn thu kiãm tra läi trong khäi sä liãu thu va tra låi cho bãn phat 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 âung va khäng cháp
nhán NAK (Non - AcKnowledgment) khi sä liãu thu sai. Nãu bãn phat nhán NAK, bãn phat
phai tiãn hanh truyãn lai 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 tuc (continuous ARQ). Trong hã thäng ARQ dæng va âåi,
sau khi phat khäi sä liãu âi, bãn phat dæng lai 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 phat phat khäi sä liãu tiãp theo hay phat lai khäi sä liãu væa
räi. Nãu thåi gian chå qua thåi gian quy âënh (goi la time-out), bãn phat coi nhæ la khäi sä
liãu væa phat bë läi va ván tiãn hanh phat lai. Han chã cua phæång phap nay la thåi gian trã
truyãn dán lån. Trong hã thäng ARQ liãn tuc, cac khäi sä liãu âãu mang sä thæ tæ - N - va
ban tin tra låi ACK/NAK cung mang sä thæ tæ N tæång æng. Bãn phat liãn tuc phat âi cac
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 cac khäi sä liãu thu va
tra låi vã cho bãn phat ban tin ACK/NAK kem theo sä thæ tæ cua khäi tin tæång æng. Khi nao
bãn phat nhán tra låi NAK tæ bãn thu, bãn phat se phat lai tát ca cac khäi sä liãu kã tæ khäi sä
liãu bë läi âäi våi ARQ lui lai N (go-back-N ARQ), hoàc bãn phat se chè phat lai khäi sä liãu
bë läi âäi våi ARQ chon loc (selective ARQ). Màc du ARQ chon loc rát hiãu qua trong sæ
dung bàng thäng nhæng yãu cáu dung læång bä nhå lån hån ARQ lui lai N, âàc biãt trong cac
kãt näi täc âä cao. ARQ phu håp våi cac hã thäng thäng tin may tênh, vç å âo co sàn kãnh
song cäng âã bãn thu co thã phat lai cho bãn phat ban tin ACK/NAK. Tuy nhiãn, trong cac
âæång truyãn dai 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 phap thæ nàm âã giam BER la thæc hiãn ma hoa sæa läi khäng phan häi FECC
(Forward Error Correction Coding). Trong lëch sæ, viãc cháp nhán sæ dung räng rai FECC
co trã hån so våi cac phæång phap khac, båi vç âä phæc tap va gia ca cua no cao hån. Ngay
nay, âä phæc tap âa giam xuäng nhå vao sæ gia tàng cac chip ma hoa/ giai ma VLSI. FECC
låi dung sæ khac nhau giæa täc âä truyãn dán va thäng læång kãnh âã giam xac suát läi Pb.
Viãc giam xac 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ã phat 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 cua FECC co âæåc thæång nhiãu hån khuyãt âiãm vã âä trã lån.
Ma hoa âiãu khiãn läi
Ma khäi
Ma cháp
Ma khäng
tuyãn tênh
Ma tuyãn tênh
(Ma nhom)
Ma khäng vong
Ma vong
Ma Golay RS
BCH nhë phán
Hamming (e=1) e>1
Hçnh 5.1 Phán loai ma âiãu khiãn läi
- 107 -
- Chæång V -
5.1.2 Phán loai ma âiãu khiãn läi
Nhçn chung, co thã phán loai ma phat hiãn va sæa läi (goi chung la ma hoa kãnh - ma hoa
â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 hoa mät bä ma hoa ma khäi våi k bit tin vao va n bit ma hoa ra. Tæ ma n bit
âæåc tao 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 âã âanh gia âä dæ cua ma. Ty lã ma thæång tæ 1/2 âãn 1. Ma hã thäng
(systematic code) la ma co màt cac bit tin cung våi cac bit dæ trong tæ ma. Trong cac tai liãu
vã ma hoa 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 phai nàm liãn tuc thanh mät khäi va cac bit dæ phai nàm liãn tuc
trong mät khäi khac. Âënh nghéa êt nghiãm ngàt hån thç chè yãu cáu trong tæ ma co màt cac
bit tin chæ khäng cán phai nàm liãn tuc thanh khäi.
k
bit
tin
n bit
Bä ma hoa khäi
ma hoa
k bit
(n-k) bit
Phán tin
Phán dæ
Tæ ma n bit
Hçnh 5.2 Ma khäi hã thäng (n, k)
Ma khäi tuyãn tênh (liear block code) - con goi la ma nhom (group code) - co cac tæ ma co
tæång æng 1-1 våi cac phán tæ thuäc nhom toan hoc. Ma tuyãn tênh co chæa tæ ma gäm toan
sä 0 va co tênh chát âong, chàng han âäi våi ma tuyãn tênh nhë phán, våi hai tæ ma C va
i
C bát ky, ta luän co C + C = C , C cung la mät tæ ma. Viãc co chæa tæ ma gäm toan sä
j
i
j
k
k
0 va tênh chát âong lam cho viãc tênh toan âäi våi ma tuyãn tênh âàc biãt dã. Hçnh 5.3 la mät
vê du âån gian vã ma tuyãn tênh. No minh hoa cho tênh chát âong cua ma. Co 4 ky tæ nguän
la a, b, c, va d, k = 2, n = 5. Âáy la ma (5, 2)
a = 00
b = 01
c = 10
d = 11
00000
00111
11100
11011
Ma hoa
c ⊕ b = d, c ⊕ d = b, b ⊕ d = c
Hçnh 5.3 Minh hoa tênh chát âong cua ma khäi tuyãn tênh
Ma vong (cyclic code) la mät låp con cua ma khäi tuyãn tênh khäng co tæ ma gäm toan sä 0.
- 108 -
- Chæång V -
Mät ma khäi tuyãn tênh âæåc goi la ma vong nãu sau mät lán dëch vong mät tæ ma thç cung
âæåc mät tæ ma thuäc cung bä ma. Vê du cac tæ ma sau âáy âæåc goi la ma vong:
1101000, 0110100, 0011010, 1000110, 0001101, 1010001, 0100011.
Ma Golay la mät loai ma vong 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 dai 23 bit. Ma nay âæåc Golay phat minh nàm 1949 va âæåc nhiãu
chuyãn gia quan tám nghiãn cæu tåi cáu truc va cå chã giai ma. Thæc tã âang co hai phæång
phap giai ma la phæång phap Kasami va giai ma tçm kiãm co hã thäng (systematic search
decoding). Ma Golay (23, 12) âæåc sæ dung 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 loai ma vong âæåc Hocquenghem tçm ra nàm
1959, sau âo âæåc Bose va Chaudhuri tçm ra mät cach âäc láp vao nàm 1960. Ma BCH co
thã sæa âæåc t läi trong tæ ma dai n bit, våi n = 2m −1,n − k ≤ mt,d ≥ 2t +1. Vê du ma
min
BCH (15, 7) co thã sæa sai täi âa 2 läi.
Ma RS âæåc Reed va Solomon giåi thiãu lán âáu tiãn vao 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 tao
thanh n ky tæ, mäi ky tæ dai m bit, m tuy thuäc vao æng dung cu thã, vê du m = 8 thç mäi ky
tæ chênh la mät byte. Ma RS hoat âäng trãn ky tæ nhiãu bit chæ khäng phai trãn tæng bit nhæ
cac ma vong khac. Mät âàc âiãm quan trong cua ma RS la kha nàng sæa läi chum. Ma RS co
n − k
thã sæa sai t läi, våi t =
. Å âáy n va k la sä ky tæ ma hoa va sä ky tæ mang tin chæ
2
khäng phai sä bit. Vê du ma RS (31, 15) co 15 ky tæ vao, mäi ky tæ 5 bit, tæc la 75 bit tin va
31 ky tæ ma hoa, mäi ky tæ 5 bit. Ma nay co thã sæa âæåc 8 läi bit âäc láp hoàc 4 läi chum dai
khäng qua 5 bit. Ma RS âæåc dung räng rai trong cac âáu CD va trong bä nhå may tênh.
Ma Hamming la mät træång håp riãng âån gian nhát cua ma BCH nhë phán. Ma nay âæåc
R.W. Hamming âæa ra va âæåc dung trong mät sä hã thäng thäng tin. Ma Hamming co kha
2n
nàng sæa sai 1 läi. Quan hã giæa n va k thoa man bát âàng thæc: 2k ≤
n +1
b) Ma cháp
Ma cháp cung âæåc âàc træng båi hai sä nguyãn la n va k nhæ ma khäi, nhæng n bit ra khoi
bä ma hoa khäng chè phu thuäc vao k bit vao ma con phu thuäc vao K-1 bä k bit vao træåc
âo. K âæåc goi la âä dai rang buäc (constraint length). Ma cháp (n, k, K) âæåc xáy dæng tæ
cac thanh ghi dëch kK bit. Váy co thã xem ma cháp la ma co nhå, âo la âiãm khac biãt cå ban
cua ma cháp so våi ma khäi.
Ma cháp âæåc Elias âã xuát lán âáu tiãn vao nàm 1955. Sau âo, Wozencraft âæa ra mät thuát
toan giai ma tæång âäi hiãu qua. Nàm 1963, Massey âæa ra cach giai ma êt hiãu qua hån
nhæng dã thæc hiãn. Nàm 1967, Viterbi âa âæa ra thuát toan giai ma täi æu âæåc goi la thuát
toan Viterbi. Tæ âáy, ma cháp âæåc æng dung räng rai trong nganh viãn thäng.
5.1.3 Kha nàng phat hiãn va sæa läi cua ma khäi
- 109 -
- Chæång V -
a) Mäi quan hã giæa khoang cach Hamming va kha nàng phat hiãn va sæa läi
Ly thuyãt ma âa chæng minh ràng: khoang cach Hamming giæa cac tæ ma trong mät bä ma co
liãn quan âãn kha nàng phat hiãn sai va sæa sai cua bä ma âo, cu thã la:
d ≥ r + s +1
trong âo d la khoang cach Hamming, r la sä läi phat hiãn âæåc, s la sä läi sæa âæåc, s ≤ r .
Ta kiãm tra âiãu nay qua mät vê du minh hoa sau âáy:
Gia sæ ta co bä ma âãu M. M co 8 tæ ma nhæ sau:
Ky tæ
A
B
C
D
E
F
G
H
Tæ ma
000
001
010
011
100
101
110
111
Tæ M, ta láp bä ma M1 co khoang cach Hamming âãu la 2. Nãu chon tæ ma B (001) lam tæ
ma xuát phat thç bä ma M1 bao gäm 4 tæ ma sau:
Ky tæ
B
C
E
H
Tæ ma
001
010
100
111
Goi 4 tæ ma trãn la tæ ma dung va 4 tæ ma con lai la tæ ma cám.
Trong træång håp sai 1 läi, ro rang cac tæ ma dung âæåc truyãn âi se chuyãn thanh cac tæ ma
cám bãn thu. Cu thã la B (001) chuyãn thanh F (101), D (011), A (000); C chuyãn thanh
G(110), A (000), D (011); E chuyãn thanh A (000), G (110), F (101); H chuyãn thanh D
(011), F (101), G (110). Luc nay co thã dã dang phat hiãn âæåc läi. Nãu bãn thu nhán âæåc tæ
ma la A, co thã kãt luán la tæ ma truyãn âi bë läi nhæng khäng thã kãt luán âæåc tæ ma nao (B,
C hay E) âa truyãn âi. Noi cach khac, khi sä træång håp sai nhiãu hån sä tæ ma cám thç
khäng thã phat hiãn âæåc läi. Trong træång håp sai 2 läi, ta tháy tæ ma dung nay se chuyãn
thanh tæ ma dung khac nãn khäng thã phat hiãn âæåc läi.
Tæ M, ta láp bä ma M2 co khoang cach Hamming âãu la 3. Nãu chon tæ ma B (001) lam tæ
ma xuát phat thç bä ma M2 bao gäm 2 tæ ma sau:
Ky tæ
B
G
Tæ ma
001
110
Trong træång håp sai 1 läi, ro rang cac tæ ma dung âæåc truyãn âi se chuyãn thanh cac tæ ma
cám bãn thu. Cu thã la B (001) chuyãn thanh F (101), D (011), A (000); G chuyãn thanh
C(010), E (100), H (111). Luc nay co thã dã dang phat hiãn âæåc läi va do sä træång håp sai
- 110 -
- Chæång V -
khäng trung nhau va bàng sä tæ ma cám nãn co thã sæa âæåc läi. Trong træång håp sai 2 läi,
ta tháy tæ ma dung chuyãn thanh tæ ma cám nhæng trung våi tæ ma cám trong træång håp sai
1 läi chè phat hiãn âæåc läi chæ khäng sæa âæåc läi.
Tom lai, tæ vê du trãn ta co thã kãt luán: nãu khoang cach Hamming la 2 thç co kha nàng phat
hiãn âæåc 1 läi, nãu khoang cach Hamming la 3 thç co kha nàng phat hiãn va sæa âæåc 1 läi
va phat hiãn âæåc 2 läi. Âiãu nay hoan toan âung chæng minh trãn vã mäi quan hã giæa
khoang cach Hamming va kha nàng phat hiãn va sæa läi cua ma.
Cung qua vê du trãn vã bä ma M2 ta tháy ràng: våi sä læång tæ ma trong bä ma la 2 thæc sæ
trong mäi tæ ma chè co 1 bit tin. Nhæng å âáy chiãu dai tæ ma la 3. Nhæ váy trong 3 bit âo co
2 bit dæ. "Dæ" å âáy hiãu theo nghéa la khäng mang tin nhæng âæåc thãm vao nhàm muc âêch
kiãm tra läi. Phán sau ta se xet täng quat vã mäi quan hã giæa âä dai täng cäng cua tæ ma va
sä bit tin.
b) Mäi quan hã giæa âä dai täng cäng cua tæ ma va sä bit tin
Âã tçm ra mäi quan hã giæa âä dai täng cäng cua tæ ma va sä bit tin, træåc hãt ta âæa ra khai
niãm vector läi e. Vector läi la vector biãu diãn vë trê cac bit läi xuát hiãn trong tæ ma thu, qui
æåc bit khäng läi âæåc biãu diãn la 0 va bit läi âæåc biãu diãn la 1.
Vê du tæ ma phat la 1110010 va tæ ma thu la 1100110. Luc nay vector läi la e = 0010100
Goi âä dai täng cäng cua tæ ma la: n; suy ra sä tæ ma täng cäng la: 2n
Goi sä bit tin trong tæ ma la : k; suy ra sä tæ ma dung la: 2k
Váy sä tæ ma cám la: 2n - 2k
Goi E la sä læång vector läi, ta co:
E = E + E + E + ... + E
n
1
2
3
Å âáy Ei la vector läi biãu diãn træång håp sai i läi.
E = Ci =
n!
i
n
i!(n − i)!
Våi mäi tæ ma dung truyãn âi thç täi âa co thã xay ra E træång håp läi. Váy våi sä tæ ma dung
la 2k thç täi âa co thã xay ra Ex2k træång håp läi. Âã co thã phat hiãn va sæa hãt tát ca cac läi
nay thç yãu cáu mäi træång håp sai phai chuyãn tæ ma dung sang mät tæ ma cám khac nhau,
noi cach khac, sä træång håp sai khäng âæåc væåt qua sä læång tæ ma cám, nghéa la:
Ex2k ≤ 2n − 2k .
Trong træång håp sai 1 läi, ta co:
E = E = n
1
Váy quan hã giæa n va k phai thoa man bát âàng thæc sau:
- 111 -
- Chæång V -
2n
2k ≤
n +1
5.2Ma khäi
5.2.1 Ma kiãm tra chàn le (parity)
Âáy la loai ma khäi âån gian nhát. Ma nay âæåc dung phä biãn trong truyãn sä liãu dang
ASCII. Våi phæång phap nay, mäi ky tæ træåc khi truyãn âi âæåc thãm vao mät bit chàn le,
goi la bit parity (P). Bit P âæåc tênh toan dæa vao ky tæ phat sao cho täng sä bit 1 trong ky tæ
(kã ca bit P) la sä chàn nãu parity la loai chàn ( even parity) va la sä le nãu parity la loai le
(odd parity). Dung ma parity le se tranh âæåc træång håp truyãn tæ ma gäm toan sä 0, tuy
nhiãn, ma parity chàn lai âæåc dung phä biãn hån.
Hçnh 5.4 la mät vê du minh hoa cho ma kiãm tra chàn le. Bit parity chàn la 1, bit parity le la
0 våi ky tæ 1001001. Ty lã ma la 7/8, mät mæc dæ rát tháp.
B0 B1 B2 B3 B4 B5 B6
1 0 0 1 0 0 1 P
P chàn = 1
P le = 0
R = k/n = 7/8
7 bit tin
1bit
kiãm tra
Hçnh 5.4 Vê du ma parity
B6
B5
B4
B3
B2
B1
B0
P chàn
P le
Hçnh 5.5 Mach tênh toan bit parity
- 112 -
- Chæång V -
Khi nhán ky tæ, bãn thu se thæc hiãn tênh toan bit parity tæång tæ nhæ bãn phat va so sanh.
Nãu chung bàng nhau thç kãt luán khäng co läi, nãu khac nhau thç kãt luán co läi.
Mach tênh toan bit parity cho ca bãn phat va bãn thu âån gian la táp cac cäng XOR nhæ trãn
hçnh 5.5.
Báy giå ta xet âãn kha nàng phat hiãn läi cua ma parity. Gia sæ dung P chàn, cac tæ ma mang
tin la 7 bit tæ 0000000 âãn 1111111, cac tæ ma liãn tiãp trong bä ma nay se la:
0000000
0000001
0000010
0
1
1
..................
Ta tháy khoang cach Hamming cua bä ma nay la 2. Váy theo ly thuyãt ma, ma nay chè phat
hiãn âæåc 1 läi. Tuy nhiãn, thæc tã ma nay phat hiãn âæåc tát ca cac läi âån hay cac läi xuát
hiãn våi sä läi le, khäng phat hiãn âæåc cac läi xuát hiãn våi sä läi chàn.
5.2.2 Ma kiãm tra täng khäi BCC(Block sum Check Character)
Khi truyãn âi mät khäi ky tæ, mät ky tæ trong khäi co thã bë läi, va vç váy coi nhæ khäi âo bë
läi. Xac suát khäi ky tæ bë läi goi la xac suát läi khäi (block error rate). Khi truyãn âi khäi ky
tæ, ta co thã cai thiãn kha nàng kha nàng phat hiãn läi cua ma parity bàng cach khäng chè
thãm bit P cho riãng tæng ky tæ âån le ma con thãm táp cac bit P tênh trãn ca mät khäi hoan
chènh.
Våi phæång phap nay, mäi ky tæ trong khäi âæåc thãm vao mät bit P, goi la bit parity hang
(row parity), mäi vë trê cua bit trong khäi âæåc thãm mät bit P goi la bit parity cät (column
parity). Táp cac bit parity cät tao thanh ky tæ kiãm tra täng khäi BCC.
Hçnh 5.6 trçnh bay mät vê du dung parity chàn cho hang va parity le cho cät.
B0
B1
B2
B3
B4
B5
B6
P
Cac
bit
Näi
1
0
1
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
1
0
1
1
0
1
0
dung
khung
Parity
hang
1
1
BCC =
Bit P cho BCC
Cac
bit
parity
cät
Hçnh 5.6 Vê du kiãm tra täng modulo-2
- 113 -
- Chæång V -
Qua vê du trãn ta tháy màc du hai bit läi trong mät ky tæ khäng âæåc phat hiãn nhå bit parity
hang nhæng se âæåc phat hiãn nhå bit parity cät. Ma nay khäng phat hiãn âæåc hai bit läi
trong cung ky tæ xay ra å cung cät vao cung thåi âiãm (vê du nhæ cac bit läi xuát hiãn å cac
vë trê nhæ âanh dáu trong hçnh). Tuy nhiãn, kha nàng nay rát êt xay ra nãn ma kiãm tra täng âa
cai thiãn âæåc kha nàng phat hiãn läi cua ma parity âån. Nãu xay ra läi âån thç càn cæ vao bit
P hang va P cät thu sai khac so våi P hang va P cät tênh, ta co thã xac âënh âæåc vë trê bit läi,
do âo co thã sæa läi.
Phæång phap kiãm tra täng thæång âæåc dung trong træång håp sä liãu truyãn âi la mät mang
ky tæ ASCII.
Phæång phap nay co mät biãn thã la sæ dung täng bu 1 âã tênh BCC thay cho täng modulo-2.
Trong phæång phap måi nay, xem cac ky tæ trong khäi cán truyãn nhæ la cac sä nhë phán
khäng dáu. Træåc hãt, cäng cac sä nay lai dung thuát toan bu 1, sau âo âao ngæåc kãt qua lai
tao thanh BCC. Bãn thu tiãn hanh tênh täng bu 1 cua tát ca cac ky tæ trong khäi (kã ca BCC),
nãu khäng co läi xuát hiãn thç kãt qua phai bàng 0. Læu y ràng, våi thuát toan bu 1, bit nhå
cuäi cung âæåc quay vong räi cäng vao täng âang co cho nãn sä 0 se âæåc biãu diãn hoàc la
toan sä 0 hoàc la toan sä 1.
Phæång phap måi nay âæåc trçnh bay qua vê du trãn hçnh 5.7. Tæ vê du ta tháy phæång phap
måi nay phat hiãn läi tät hån phæång phap täng modulo-2.
Bãn phat
0 1 1 1 0 0 1
Bãn thu
0 1 1 1 0 0 1
1 0 0 0 1 1 0
0 0 0 0 0 1 1
1 0 0 1 1 1 1
1 0 1 0 0 0 1 = täng bu 1
0
1 0 0 0 1 1 0
0 0 0 0 0 1 1
1 0 0 1 1 1 1
1
0 1 0 1 1 0 1
1
1 1 1 1 1 1 0
1 0 1 0 0 1 0
Âao bit
1
1 1 1 1 1 1 1 = sä 0 trong sä bu 1
0 1 0 1 1 0 1 = BCC
Hçnh 5.7 Vê du kiãm tra täng bu 1
Ma kiãm tra täng bu 1 thæång âæåc tênh toan bàng phán mãm, dung âã kiãm tra läi cho cac
ban tin giao thæc qua internet.
5.2.3 Ma khäi tuyãn tênh
a) Vê du vã ma khäi tuyãn tênh
Hçnh 5.8 minh hoa mät mach tao ma khäi tuyãn tênh (4, 7) gäm 4 bit tin (I1 âãn I4) va 3
bit kiãm tra chàn le (P1 âãn P3).
- 112 -
- Chæång V -
Gia sæ dung parity chàn, mäi quan hã giæa cac bit tin va bit kiãm tra la:
P = I ⊕ I ⊕ I
4
1
1
3
P = I ⊕ I ⊕ I
2
1
2
4
3
P = I ⊕ I ⊕ I
3
1
2
Nãu cac bit tin la I1 = 1, I2 = 0, I3 = 1, I4 = 1, cac bit P tênh âæåc se la P1 = 1, P2 = 0 va P3 = 0.
I1
I2
I3
I4
P1
P2
P3
Hçnh 5.8 Mach tao ma khäi (4, 7)
Ta co thã viãt lai quan hã giæa cac bit tin va bit kiãm tra trong vê du trãn nhæ sau:
P =1xI ⊕ 0xI ⊕1xI ⊕1xI
1
1
2
3
4
4
4
P =1xI ⊕1xI ⊕ 0xI ⊕1xI
1
1
2
3
P =1xI ⊕1xI ⊕1xI ⊕ 0xI
1
1
2
3
Tæ cac phæång trçnh quan hã nay, ta rut ra ma trán kiãm tra H nhæ sau:
1011:10 0
⎡
⎤
⎥
⎥
⎢
H = 1101:010
⎢
⎣
⎢
⎥
1110:0 01
⎦
Phán bãn trai cua âæång chám chám la cac hã sä cua cac bit tin I1 âãn I4, phán bãn phai
âæång chám chám la ma trán 3x3 co âæång cheo la 1 (ma trán âån vë).
b) Ma trán sinh (generator matrix)
Ma trán sinh, ky hiãu la G, la mät ma trán 4 x 7, âæåc tao ra bàng cach kãt håp mät ma trán
âån vë 4 x 4 våi ma trán hoan vë cua ma trán bãn trai âæång chám chám cua H. Trong vê du
trãn, ma trán sinh la:
10 0 0:111
⎡
⎤
⎥
⎢
⎢
⎢
010 0:011
⎥
G =
⎥
0 010:101
⎢
⎣
⎥
0 0 01:110
⎦
Nhå ma trán sinh G, ta co thã tênh toan âæåc tæ ma bàng cach nhán vector hang m biãu diãn
- 113 -
- Chæång V -
cho tæ ma mang tin våi G. Trong vê du trãn, day mang tin la 1011, tæ ma khäi tuyãn tênh (4,7)
âæåc tao ra la:
1000111
⎡
⎤
⎥
⎥
⎥
⎢
0100011
0010101
0001110
⎢
[
1011
]
=
[
1011100
]
⎢
⎢
⎥
⎦
⎣
Ta nhán tháy ma trán kãt qua chênh la vector biãu diãn cho tæ ma khäi (4, 7) gäm co hai
phán: 4 bit bãn trai la 4 bit tin I1 âãn I4, 3 bit bãn phai chênh la 3 bit kiãm tra P1 âãn P3.
Theo cach láp ma nay, ta nhán tháy khoang cach Hamming täi thiãu la 3, do âo ma nay sæa
sai âæåc 1 läi.
c) Bang syndrome âã giai ma sæa läi
Syndrome la mät tæ ma âäc láp våi tæ ma phat va chè phu thuäc vao day thu bë läi, ky hiãu
vector syndrome la s. Bang syndrome la táp håp tát ca cac syndrome co thã co. Goi c la
vector biãu diãn cho tæ ma khäi (n, k) . Ta co quan hã:
m x G = c
Goi e la vector läi va r la tæ ma thu, ta co:
r = c ⊕ e
Syndrome âæåc tênh nhæ sau:
s = r x HT = (c ⊕ e) x HT = c x HT ⊕ e x HT = 0 ⊕ e x HT = e x HT
Bang syndrome âæåc tênh sàn våi gia thiãt la truyãn âi tæ ma gäm toan bit 0. Vê du bang
syndrome trong træång håp sai 1 läi nhæ hçnh 5.9:
Vector läi Syndrome
0000000 000
1000000 111
0100000 011
0010000 101
0001000 110
0000100 100
0000010 010
0000001 001
Hçnh 5.9 Bang syndrome hoan chènh cho tát ca cac läi âån
Nhçn vao bang hçnh 5.9 ta tháy: khi khäng co läi syndrome la 0, khi co läi syndrome khac 0
- 114 -
- Chæång V -
va cac syndrome khäng giäng nhau nãn co thã càn cæ vao syndrome âã biãt vë trê bit läi, tæ
âo sæa âæåc läi. Vê du trãn, gia sæ thu âæåc tæ ma 1011101, tæ ma âung sæa âæåc se la c nhæ
sau:
r =
[
1011101
]
111
⎡
⎤
⎥
⎥
⎥
⎥
⎢
011
⎢
⎢
101
⎢
s =
[
1011101
]
110 =
[
001
]
⇒ c =
[
1011100
]
⎢
⎥
⎥
⎥
⎥
⎢
100
⎢
⎢
010
001
⎢
⎣
⎥
⎦
Træång håp xuát hiãn läi chum, ngæåi ta sæ dung ky thuát tao loan (interleaving): xao trän
thæ tæ cac bit tin trong ban tin ma hoa træåc khi phat va sàp xãp lai sau khi thu, âã tach chum
läi thanh cac läi âån räi måi âæa âãn bä giai ma.
5.3Ma vong
5.3.1 Âàc âiãm cua ma vong
Nhæ âa giåi thiãu å trãn (5.1.2), ma vong la mät låp con cua ma khäi tuyãn tênh. Ma vong co
cac âàc âiãm sau:
-
-
Cáu truc toan hoc cua ma vong cho phep kha nàng sæa läi cao.
Co thã thæc hiãn ma vong dã dang bàng phán cæng, bàng cac thanh ghi dëch va cac cäng
XOR
-
-
-
Dëch vong mät tæ ma cung âæåc mät tæ ma thuäc cung bä ma.
Co thã biãu diãn ma vong bàng âa thæc
Co thã tao ra tæ ma vong bàng cach nhán modulo-2 vector mang tin våi âa thæc sinh. Luc
nay ma vong âæåc goi la ma vong khäng hã thäng
5.3.2 Ma kiãm tra âä dæ vong CRC (Cyclic Redundancy Check)
Ma CRC la mät loai ma vong âæåc sæ dung räng rai trãn cac kãnh truyãn näi tiãp bit âã phat
hiãn läi (khäng sæa läi). Trong CRC, mät táp bit kiãm tra âæåc tênh toan cho mäi khung tin
dæa vao näi dung khung, sau âo âæåc gàn thãm vao âuäi khung âã truyãn âi. Bãn thu thæc
hiãn tênh toan tæång tæ nhæ bãn phat âã phat hiãn läi. Cac bit kiãm tra goi la day kiãm tra
khung FCS (Frame Check Sequence). Thuát toan cu thã nhæ sau:
a) Tênh toan tao ma CRC bãn phat va kiãm tra läi bãn thu
Goi M(x) la âa thæc tin bác k-1, G(x) la âa thæc sinh bác r
- 115 -
- Chæång V -
Thæc hiãn phep chia M(x)xr cho G(x), se âæåc:
M(x) xr
G(x)
R(x)
G(x)
= Q(x) +
, våi Q(x) la thæång sä va R(x) la sä dæ
Tæ âáy suy ra:
M(x)xr + R(x)
= Q(x)
G(x)
Âàt T(x) = M(x)xr + R(x) la âa thæc biãu diãn cho tæ ma CRC phat. Ro rang la nãu
khäng co läi xuát hiãn thç bãn thu, sau khi chia tæ ma thu cho âa thæc sinh ta se âæåc phán dæ
la 0.
b) Vê du
Vê du cán truyãn âi mät khung tin 8 bit 11100110 qua âæång truyãn sä liãu, sæ dung ma CRC
âã phat hiãn läi, âa thæc sinh sæ dung la 11001.
Tæ ma CRC âæåc tao ra nhæ hçnh 5.10 sau:
1 1 1 0 0 1 1 0 0 0 0 0
1 1 0 0 1
1 1 0 0 1
⊕
1 0 1 1 0 1 1 0
0 0 1 0 1 1 1
⊕
1 1 0 0 1
1 1 1 0 0
⊕
1 1 0 0 1
0 0 1 0 1 0 0
⊕
1 1 0 0 1
0 1 1 0 1 0
⊕
1 1 0 0 1
0 0 0 1 1 0
Dæ (FCS)
Hçnh 5.10 Vê du tao ma CRC
Sau khi thæc hiãn tênh toan nhæ trãn, ta tçm âæåc tæ ma CRC la: 11100110 0110, trong âo 8
bit âáu la 8 bit tin va 4 bit sau la 4 bit kiãm tra.
Gia sæ tai bãn thu, ta thu âæåc tæ ma: 111001101111. Hçnh 5.11 trçnh bay viãc thæc hiãn
phep chia âa thæc thu cho âa thæc sinh nhæ trãn.
- 116 -
- Chæång V -
1 1 1 0 0 1 1 0 1 1 1 1
1 1 0 0 1
1 1 0 0 1
⊕
1 0 1 1 0 1 1 0
0 0 1 0 1 1 1
⊕
1 1 0 0 1
1 1 1 0 0
⊕
1 1 0 0 1
0 0 1 0 1 1 1
⊕
1 1 0 0 1
0 1 1 1 0 1
⊕
1 1 0 0 1
0 0 1 0 0 1
Dæ ≠ 0nãn phat hiãn âæåc läi
Hçnh 5.11 Vê du giai ma CRC va phat hiãn läi
Viãc læa chon âa thæc sinh rát quan trong vç no xac âënh cac kiãu läi co thã phat hiãn. Mät âa
thæc sinh bác r co êt nhát 3 sä 1 se phat hiãn âæåc tát ca cac läi âån, tát ca cac läi âäi, tát ca
cac läi xay ra våi sä le, tát ca cac läi chum ngàn hån r va háu hãt cac läi chum dai hån hoàc
bàng r. Sau âáy la mät vai âa thæc sinh thæång dung trong thæc tã:
CRC - 16: G(x) = x16 + x15 + x2 + 1
CRC - CCITT: G(x) = x16 + x12 + x5 + 1
CRC - 32: G(x) = x32 + x26 + x23 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
CRC - 16 va CRC - CCITT âæåc dung räng rai trong WAN, CRC - 32 âæåc dung trong háu
hãt cac LAN. Kha nàng tæ sæa läi cua CRC tháp nhæng kha nàng phat hiãn läi rát cao nãn
thæång âæåc dung kãt håp våi ARQ âã sæa läi.
c) Mach thæc hiãn ma CRC
Hçnh 5.12 trçnh bay så âä thæc hiãn CRC bãn phat.
Ta xet cu thã vê du trãn. Sä bit trong FCS la 4 nãn cán mät thanh ghi dëch 4 bit (goi la thanh
ghi FCS) âã biãu diãn x3, x2, x1 va x0 trong âa thæc sinh (goi la cac bit têch cæc - active bit).
Våi âa thæc sinh nay thç cac sä x3 va x0 la 1 con x2 va x1 la 0. Trang thai måi cua x1 va x2 âæåc
thay bàng trang thai træåc âo cua x0 va x1. Trang thai måi cua x0 va x3 âæåc xac âënh båi trang
thai cua âæång phan häi âa XOR våi sä træåc âo.
Mach hoat âäng nhæ sau: træåc tiãn xoa thanh ghi dëch FCS va nap song song 8 bit âáu tiãn
trong khung tin vao thanh ghi vao song song - ra näi tiãp PISO (Parallel Input - Serial
Output). Tên hiãu âiãu khiãn phan häi la 1. Theo täc âä cua âäng hä phat TxC, cac bit nay
âæåc dëch ra âæång truyãn lán læåt tæ msb âãn lsb. Cung luc nay, dong bit nay âæåc XOR våi
- 117 -
- Chæång V -
Tên hiãu âiãn khiãn phan häi
(tæ 1 thanh 0 sau 8 N TxC)
FCS
x0 x1 x2
x3
TxC
PISO
lsb
msb
Nap song song tæng byte trong N byte
trong khung tin
TxD
TxC
Thanh ghi PISO
Thanh ghi FCS
msb X0 X1 X2 X3
lsb
0
0
1
2
3
4
5
6
7
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
1
0
1
1
0
1
0
0
0
1
0
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
8
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
1
0
10
11
Hçnh 5.12 Så âä mach tao CRC bãn phat
x3 qua âæång phan häi trå lai cac âáu vao chon loc cua FCS. Sau khi 8 bit âáu (byte âáu tiãn
- 118 -
- Chæång V -
trong khung tin) âi qua hãt thanh ghi PISO, thu tuc nay âæåc làp lai. Sau khi xuát ra byte tin
cuäi cung trong khung tin, thanh ghi PISO âæåc nap toan la sä 0, tên hiãu âiãu khiãn phan häi
tæ 1 trå thanh 0, do âo näi dung cua thanh ghi FCS - la cac bit kiãm tra - âi theo sau khung
tin phat ra âæång truyãn. Trong hçnh 5.12, ta âa gia sæ khung tin chè co 1 byte (N = 1)
FCS
x0 x1 x2
x3
RxD
RxC
SIPO
lsb
msb
Âoc song song byte (xN)
Thanh ghi SIPO
Thanh ghi FCS
RxC RxD
lsb
0
msb X0 X1 X2 X3
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
0
1
1
0
1
1
0
0
1
2
1
1
1
1
0
0
1
1
3
1
1
1
1
0
0
1
4
0
1
1
1
0
0
5
0
1
1
1
0
6
1
1
1
1
7
1
1
1
8
0
1
9
Âoc byte
10
11
12
Dæ = 0
Hçnh 5.13 Så âä mach kiãm tra CRC bãn thu
- 119 -
- Chæång V -
Hçnh 5.13 trçnh bay så âä kiãm tra CRC bãn thu. Sä liãu thu RxD lán læåt âæåc dëch vao
thanh ghi vao näi tiãp - ra song song SIPO ( Serial Input - Parallel Output) å giæa mäi ä bit.
Cac bit RxD lán læåt âæåc XOR våi x3 va phan häi trå lai thanh ghi SIPO, mäi khi nhán âæåc
byte 8 bit, thiãt bë âiãu khiãn se âiãu khiãn âoc byte.
d) Giai ma ma CRC bàng phæång phap báy läi
Xet træång håp ma CRC âæåc thanh láp våi sä bit tin k va sä bit täng cäng n thoa man bát
2n
âàng thæc: 2k ≤
. Vê du k = 4, n = 7
n +1
Phán têch xn +1 ra cac thæa sä nguyãn tä räi chon thæa sä bác r lam âa thæc sinh. Vê du:
x7 +1= (x +1)(x3 + x2 +1)(x3 + x +1).
Chon âa thæc sinh la G(x) = x3 + x2 +1hoàc la G(x) = x3 + x +1
Ma CRC trong træång håp nay co kha nàng sæa âæåc läi, cu thã la 1 läi.
Begin
ÂÃM = 0
Dëch vong T'(x) sang trai
Chia T'(x) cho G(x) - dæ la R'(x)
Tàng ÂÃM
lãn 1
Tênh trong læång dæ W
N
W ≤ 1 ?
Y
T'(x) = T'(x) + R'(x)
Dëch vong T'(x) sang phai ÂÃM lán
End
Hçnh 5.14 Thuát toan sæa läi ma CRC bàng phæång phap báy läi
- 120 -
- Chæång V -
Hçnh 5.14 trçnh bay thuát toan sæa läi cho ma CRC bàng phæång phap báy läi. Goi T'(x) la
âa thæc biãu diãn cho tæ ma thu. Qua trçnh sæa läi bàt âáu bàng viãc dëch vong T'(x) sang
trai, sau âo chia cho G(x) âã tçm sä dæ R'(x). Viãc dëch vong se diãn ra nhiãu lán cho âãn khi
trong læång dæ nho hån hoàc bàng 1. Trong læu âä trãn, ta dung biãn ÂÃM âã âãm sä lán
dëch vong trai. Sau âo cäng T'(x) våi R'(x), läi âæåc báy va sæa sau phep cäng nay. Tuy
nhiãn, ta cán phai sæa lai vë trê cac bit trong T'(x) do nhæng lán dëch vong trai. Do âo, phai
dëch vong T'(x) ngæåc lai sang phai våi sä lán bàng sä lán træåc âo âa dëch vong sang trai (sä
lán dëch vong phai å âáy chênh la ÂÃM).
Vê du tin la 4 bit 1100, âa thæc sinh chon la x3 + x2 +1. Thæc hiãn ma hoa ta âæåc tæ ma
phat la 1100 101. Gia sæ bãn thu thu âæåc tæ ma 1110 101. Kiãm tra läi bàng cach chia T'(x)
cho G(x), ta tháy phep chia con dæ nãn kãt luán co läi. Váy tiãn hanh sæa läi nhæ sau:
Dëch vong trai lán thæ nhát âæåc 1101011, chia cho G(x) dæ la 011.
Dëch vong trai lán thæ hai âæåc 1010111, chia cho G(x) dæ la 110.
Dëch vong trai lán thæ ba âæåc 0101111, chia cho G(x) dæ la 001.
Thæc hiãn phep cäng modulo-2: 0101111 ⊕ 001 ta âæåc 0101110, räi dëch vong sang phai 3
lán ta âæåc lai tæ ma 1100101 giäng nhæ bãn phat.
5.3.3 Ma Hamming
Ma Hamming la mät træång håp riãng âån gian nhát cua ma vong. Ma Hamming co d = 3, co
kha nàng sæa âæåc 1 läi.
Mät tæ ma Hamming âæåc biãu diãn dæåi dang täng quat c c ic iiic i.... . Å âáy i la cac
1
2
4
8
bit tin va c la cac bit kiãm tra.
Cac bit c chênh la kãt qua cua phep XOR gia trë chè vë trê cua cac bit 1 våi nhau. Qua trçnh
kiãm tra läi bãn thu diãn ra tæång tæ nhæ bãn phat. Nãu kãt qua cua phep XOR la mät gia trë
khac 0 thç âo chênh la vë trê cua bit läi.
Vê du xet kha nàng sæa läi âån cua ma Hamming (7, 11) trong træång håp tæ ma mang tin la
1011101.
Tæ ma Hamming co dang: c c 1c 011c 101.
1
2
4
8
Cac bit 1 å cac vë trê: 3, 6, 9 va 11. Âäi cac sä nay sang nhë phán:
3 ↔ 0011,6 ↔ 0110,7 ↔ 0111,9 ↔1001,11↔1011
Tênh XOR:
0011⊕ 0110 ⊕ 0111⊕1001⊕1011=1001.
Váy tæ ma Hamming phat âi la: 10100110101
Gia sæ å bãn thu, thu âæåc tæ ma: 10000110101. Âäi gia trë chè vë trê cua cac bit 1 sang nhë
phán räi tênh XOR tæång tæ nhæ bãn phat:
- 121 -
- Chæång V -
1↔ 0001,6 ↔ 0110,7 ↔ 0111,9 ↔1001,11↔1011
0001⊕ 0110 ⊕ 0111⊕1001⊕1011= 0011↔ 3
Tæ âáy xac âënh âæåc bit läi la bit å vë trê thæ 3. Váy tæ ma thu âæåc sæa lai la: 10100110101
giäng nhæ tæ ma phat.
5.4Ma cháp
5.4.1 Ma hoa ma cháp
Nhæ trçnh bay å muc 5.1.2, ma cháp âæåc âàc træng båi ba sä nguyãn la n, k va K. Ma cháp
(n, k, K) âæåc xáy dæng tæ cac thanh ghi dëch kK bit. Å âáy ta xet loai ma cháp phä biãn
nhát la ma cháp co k = 1. Bä ma hoa la thanh ghi dëch K bit. Âáu ra cua cac vë trê trong thanh
ghi âæåc læa chon âã cäng modulo-2 våi nhau. Sä læång bä cäng modulo-2 chênh la n. Mät
bä chuyãn mach se lán læåt láy máu mäi âáu ra cua bä cäng modulo-2 theo nhëp cua âäng hä
thanh ghi dëch.
Hçnh 5.15 minh hoa mät bä ma hoa ma cháp våi k = 1, K = 3, n = 2.
1
T0 T0 T0
2
Vao 1
1
0
1
Ra 11 10 11 01
Hçnh 5.15 Vê du bä ma hoa ma cháp ty lã 1/2
a) Biãu diãn ma cháp bàng âa thæc sinh
Co thã biãu diãn bä ma hoa ma cháp bàng cac âa thæc sinh. Mäi âa thæc sinh biãu diãn cho
mät bä cäng modulo-2. Âa thæc sinh co bác ≤ K −1 miãu ta sæ kãt näi giæa âáu ra cua mät
vë trê trong thanh ghi dëch våi bä cäng modulo-2. Theo vê du trãn, hai âa thæc sinh
laG (x) =1+ x2 va G (x) =1+ x
1
2
Gia sæ day tin vao bä ma hoa la 1100, day ma hoa se la 11101101 . . ., nghéa la æng våi mät
bit tin vao co hai bit ma hoa ra. Do âo, ty lã ma la 1/2.
Âënh nghéa âap æng xung cua ma hoa la âap æng cua bä ma hoa khi bit vao la 1. Trong vê du
trãn, âap æng xung se la: 110110. Våi day vao la 1101, ta tháy day ra co thã âæåc tênh la cháp
day vao våi âap æng xung. Do âo ma nay co tãn la ma cháp.
b) Biãu diãn ma cháp bàng så âä cáy
Hçnh 5.16 trçnh bay så âä cáy biãu diãn ma cháp cho vê du trãn. Gia sæ ban âáu toan bä
thanh ghi âæåc xoa vã 0. Âoc så âä cáy theo phæång ngang tæ trai qua phai, mäi nhanh cáy
- 122 -
Tải về để xem bản đầy đủ
24 trang
19480
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Kĩ thuật thông tin số - Chương 5: Mã hóa kênh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_ki_thuat_thong_tin_so_chuong_5_ma_hoa_kenh.pdf
