Bài giảng thông tin số Chương 5

Chia sẻ: Mr Nguyen | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

428
lượt xem 200
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chương 5 trình bày về mã hóa kênh. Theo quan điểm của ngành thông tin, tài nguyên thông tin chủ yếu là công suất, thời gian và băng thông của tín hiệu. Đối với một môi trường thông tin cho trước, ba tài nguyên này có thể mâu thuẫn lẫn nhau.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng thông tin số Chương 5

- 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: C = B log 2 (1 + S / N) (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î hoïa âiãöu khiãøn läùi Maî khäúi Maî cháûp Maî khäng Maî tuyãún tênh tuyãún tênh (Maî nhoïm) Maî khäng voìng Maî voìng Maî Golay RS BCH nhë phán Hamming (e=1) e>1 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. k n bit bit Bäü maî hoïa khäúi tin maî hoïa 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) - 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î C vaì i C j báút kyì, ta luän coï C i + C j = C k , C k 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) a = 00 00000 b = 01 Maî hoïa 00111 c = 10 11100 d = 11 11011 c ⊕ b = d, c ⊕ d = b, b ⊕ d = 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ï m thãø sæía âæåüc t läùi trong tæì maî daìi n bit, våïi n = 2 − 1, n − k ≤ mt, d ≥ 2 t + 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 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ï n−k thãø sæía sai t läùi, våïi t = . ÅÍ âáy n vaì k laì säú kyï tæû maî hoïa vaì säú kyï tæû mang tin chæï 2 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 2k nàng sæía sai 1 läùi. Quan hãû giæîa n vaì k thoía maîn báút âàóng thæïc: 2 ≤ n +1 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 -
- Chæång V - a) Mäúi quan hãû giæîa khoaíng caïch Hamming vaì khaí nàng phaït hiãûn vaì sæía läùi Lyï thuyãút maî âaî chæïng minh ràòng: khoaíng caïch Hamming giæîa caïc tæì maî trong mäüt bäü maî coï liãn quan âãún khaí nàng phaït hiãûn sai vaì sæía sai cuía bäü maî âoï, cuû thãø laì: d ≥ r + s +1 trong âoï d laì khoaíng caïch Hamming, r laì säú läùi phaït hiãûn âæåüc, s laì säú läùi sæía âæåüc, s ≤ r . Ta kiãøm tra âiãöu naìy qua mäüt vê duû minh hoüa 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ï khoaíng caïch Hamming âãöu laì 2. Nãúu choün tæì maî B (001) laìm tæì maî xuáút phaït thç bäü maî M1 bao gäöm 4 tæì maî sau: Kyï tæû B C E H Tæì maî 001 010 100 111 Goüi 4 tæì maî trãn laì tæì maî duìng vaì 4 tæì maî coìn laûi laì tæì maî cáúm. Trong træåìng håüp sai 1 läùi, roî raìng caïc tæì maî duìng âæåüc truyãön âi seî chuyãøn thaình caïc tæì maî cáúm bãn thu. Cuû thãø laì B (001) chuyãøn thaình F (101), D (011), A (000); C chuyãøn thaình G(110), A (000), D (011); E chuyãøn thaình A (000), G (110), F (101); H chuyãøn thaình D (011), F (101), G (110). Luïc naìy coï thãø dãù daìng phaït 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î naìo (B, C hay E) âaî truyãön âi. Noïi caïch khaïc, khi säú træåìng håüp sai nhiãöu hån säú tæì maî cáúm thç khäng thãø phaït hiãûn âæåüc läùi. Trong træåìng håüp sai 2 läùi, ta tháúy tæì maî duìng naìy seî chuyãøn thaình tæì maî duìng khaïc nãn khäng thãø phaït hiãûn âæåüc läùi. Tæì M, ta láûp bäü maî M2 coï khoaíng caïch Hamming âãöu laì 3. Nãúu choün tæì maî B (001) laìm tæì maî xuáút phaït 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î raìng caïc tæì maî duìng âæåüc truyãön âi seî chuyãøn thaình caïc tæì maî cáúm bãn thu. Cuû thãø laì B (001) chuyãøn thaình F (101), D (011), A (000); G chuyãøn thaình C(010), E (100), H (111). Luïc naìy coï thãø dãù daìng phaït hiãûn âæåüc läùi vaì do säú træåìng håüp sai - 110 -
- Chæång V - khäng truìng 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î duìng chuyãøn thaình tæì maî cáúm nhæng truìng våïi tæì maî cáúm trong træåìng håüp sai 1 läùi chè phaït hiãûn âæåüc läùi chæï khäng sæía âæåüc läùi. Toïm laûi, tæì vê duû trãn ta coï thãø kãút luáûn: nãúu khoaíng caïch Hamming laì 2 thç coï khaí nàng phaït hiãûn âæåüc 1 läùi, nãúu khoaíng caïch Hamming laì 3 thç coï khaí nàng phaït hiãûn vaì sæía âæåüc 1 läùi vaì phaït hiãûn âæåüc 2 läùi. Âiãöu naìy hoaìn toaìn âuïng chæïng minh trãn vãö mäúi quan hãû giæîa khoaíng caïch Hamming vaì khaí nàng phaït hiãûn vaì sæía läùi cuía maî. Cuîng 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 daìi 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 vaìo nhàòm muûc âêch kiãøm tra läùi. Pháön sau ta seî xeït täøng quaït vãö mäúi quan hãû giæîa âäü daìi täøng cäüng cuía tæì maî vaì säú bit tin. b) Mäúi quan hãû giæîa âäü daìi täøng cäüng cuía tæì maî vaì säú bit tin Âãø tçm ra mäúi quan hãû giæîa âäü daìi täøng cäüng cuía tæì maî vaì säú bit tin, træåïc hãút ta âæa ra khaïi niãûm vector läùi e. Vector läùi laì vector biãøu diãùn vë trê caïc 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î phaït laì 1110010 vaì tæì maî thu laì 1100110. Luïc naìy vector läùi laì e = 0010100 Goüi âäü daìi täøng cäüng cuía tæì maî laì: n; suy ra säú tæì maî täøng cäüng laì: 2n Goüi säú bit tin trong tæì maî laì : k; suy ra säú tæì maî duìng laì: 2k Váûy säú tæì maî cáúm laì: 2n - 2k Goüi E laì säú læåüng vector läùi, ta coï: E = E1 + E 2 + E 3 + ... + E n Åí âáy Ei laì vector läùi biãøu diãùn træåìng håüp sai i läùi. i n! Ei = Cn = i!(n − i)! Våïi mäùi tæì maî duìng truyãön âi thç täúi âa coï thãø xaíy ra E træåìng håüp läùi. Váûy våïi säú tæì maî duìng laì 2k thç täúi âa coï thãø xaíy ra Ex2k træåìng håüp läùi. Âãø coï thãø phaït hiãûn vaì sæía hãút táút caí caïc läùi naìy thç yãu cáöu mäùi træåìng håüp sai phaíi chuyãøn tæì maî duìng sang mäüt tæì maî cáúm khaïc nhau, noïi caïch khaïc, säú træåìng håüp sai khäng âæåüc væåüt quaï säú læåüng tæì maî cáúm, nghéa laì: k n k Ex 2 ≤ 2 − 2 . Trong træåìng håüp sai 1 läùi, ta coï: E = E1 = n Váûy quan hãû giæîa n vaì k phaíi thoía maîn báút âàóng thæïc sau: - 111 -
- Chæång V - n k 2 2 ≤ n +1 5.2 Maî khäúi 5.2.1 Maî kiãøm tra chàôn leí (parity) Âáy laì loaûi maî khäúi âån giaín nháút. Maî naìy âæåüc duìng phäø biãún trong truyãön säú liãûu daûng ASCII. Våïi phæång phaïp naìy, mäùi kyï tæû træåïc khi truyãön âi âæåüc thãm vaìo mäüt bit chàôn leí, goüi laì bit parity (P). Bit P âæåüc tênh toaïn dæûa vaìo kyï tæû phaït sao cho täøng säú bit 1 trong kyï tæû (kãø caí bit P) laì säú chàôn nãúu parity laì loaûi chàôn ( even parity) vaì laì säú leí nãúu parity laì loaûi leí (odd parity). Duìng maî parity leí seî traïnh âæåüc træåìng håüp truyãön tæì maî gäöm toaìn säú 0, tuy nhiãn, maî parity chàôn laûi âæåüc duìng phäø biãún hån. Hçnh 5.4 laì mäüt vê duû minh hoüa 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 Maûch tênh toaïn bit parity - 112 -
- Chæång V - Khi nháûn kyï tæû, bãn thu seî thæûc hiãûn tênh toaïn bit parity tæång tæû nhæ bãn phaït vaì so saïnh. Nãúu chuïng bàòng nhau thç kãút luáûn khäng coï läùi, nãúu khaïc nhau thç kãút luáûn coï läùi. Maûch tênh toaïn bit parity cho caí bãn phaït vaì bãn thu âån giaín laì táûp caïc cäøng XOR nhæ trãn hçnh 5.5. Báy giåì ta xeït âãún khaí nàng phaït hiãûn läùi cuía maî parity. Giaí sæí duìng P chàôn, caïc tæì maî mang tin laì 7 bit tæì 0000000 âãún 1111111, caïc tæì maî liãn tiãúp trong bäü maî naìy seî laì: 0000000 0 0000001 1 0000010 1 .................. Ta tháúy khoaíng caïch Hamming cuía bäü maî naìy laì 2. Váûy theo lyï thuyãút maî, maî naìy chè phaït hiãûn âæåüc 1 läùi. Tuy nhiãn, thæûc tãú maî naìy phaït hiãûn âæåüc táút caí caïc läùi âån hay caïc läùi xuáút hiãûn våïi säú läùi leí, khäng phaït hiãûn âæåüc caïc 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. Xaïc suáút khäúi kyï tæû bë läùi goüi laì xaïc suáút läùi khäúi (block error rate). Khi truyãön âi khäúi kyï tæû, ta coï thãø caíi thiãûn khaí nàng khaí nàng phaït hiãûn läùi cuía maî parity bàòng caïch khäng chè thãm bit P cho riãng tæìng kyï tæû âån leí maì coìn thãm táûp caïc bit P tênh trãn caí mäüt khäúi hoaìn chènh. Våïi phæång phaïp naìy, mäùi kyï tæû trong khäúi âæåüc thãm vaìo mäüt bit P, goüi laì bit parity haìng (row parity), mäùi vë trê cuía bit trong khäúi âæåüc thãm mäüt bit P goüi laì bit parity cäüt (column parity). Táûp caïc bit parity cäüt taûo thaình kyï tæû kiãøm tra täøng khäúi BCC. Hçnh 5.6 trçnh baìy mäüt vê duû duìng parity chàôn cho haìng vaì parity leí cho cäüt. B0 B1 B2 B3 B4 B5 B6 P Näüi Caïc 1 0 0 1 1 1 0 0 dung 0 1 1 0 0 0 1 1 bit khung 1 1 0 0 0 0 0 0 Parity 1 1 1 1 0 0 1 1 haìng BCC = 0 0 1 1 0 0 1 1 Caïc bit parity cäüt Bit P cho BCC 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 phaït hiãûn nhåì bit parity haìng nhæng seî âæåüc phaït hiãûn nhåì bit parity cäüt. Maî naìy khäng phaït hiãûn âæåüc hai bit läùi trong cuìng kyï tæû xaíy ra åí cuìng cäüt vaìo cuìng thåìi âiãøm (vê duû nhæ caïc bit läùi xuáút hiãûn åí caïc vë trê nhæ âaïnh dáúu trong hçnh). Tuy nhiãn, khaí nàng naìy ráút êt xaíy ra nãn maî kiãøm tra täøng âaî caíi thiãûn âæåüc khaí nàng phaït hiãûn läùi cuía maî parity âån. Nãúu xaíy ra läùi âån thç càn cæï vaìo bit P haìng vaì P cäüt thu sai khaïc so våïi P haìng vaì P cäüt tênh, ta coï thãø xaïc âënh âæåüc vë trê bit läùi, do âoï coï thãø sæía läùi. Phæång phaïp kiãøm tra täøng thæåìng âæåüc duìng trong træåìng håüp säú liãûu truyãön âi laì mäüt maíng kyï tæû ASCII. Phæång phaïp naìy coï mäüt biãún thãø laì sæí duûng täøng buì 1 âãø tênh BCC thay cho täøng modulo-2. Trong phæång phaïp måïi naìy, xem caïc kyï tæû trong khäúi cáön truyãön nhæ laì caïc säú nhë phán khäng dáúu. Træåïc hãút, cäüng caïc säú naìy laûi duìng thuáût toaïn buì 1, sau âoï âaío ngæåüc kãút quaí laûi taûo thaình BCC. Bãn thu tiãún haình tênh täøng buì 1 cuía táút caí caïc kyï tæû trong khäúi (kãø caí BCC), nãúu khäng coï läùi xuáút hiãûn thç kãút quaí phaíi bàòng 0. Læu yï ràòng, våïi thuáût toaïn buì 1, bit nhåï cuäúi cuìng âæåüc quay voìng räöi cäüng vaìo täøng âang coï cho nãn säú 0 seî âæåüc biãøu diãùn hoàûc laì toaìn säú 0 hoàûc laì toaìn säú 1. Phæång phaïp måïi naìy âæåüc trçnh baìy qua vê duû trãn hçnh 5.7. Tæì vê duû ta tháúy phæång phaïp måïi naìy phaït hiãûn läùi täút hån phæång phaïp täøng modulo-2. Bãn phaït Bãn thu 0111001 0111001 1000110 1000110 0000011 0000011 1001111 1001111 1 1 0 1 0 0 0 1 = täøng buì 1 0101101 0 1 1111110 1010010 1 Âaío bit 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 toaïn bàòng pháön mãöm, duìng âãø kiãøm tra läùi cho caïc baín 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 hoüa mäüt maûch taûo 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æí duìng parity chàôn, mäúi quan hãû giæîa caïc bit tin vaì bit kiãøm tra laì: P1 = I1 ⊕ I 3 ⊕ I 4 P2 = I1 ⊕ I 2 ⊕ I 4 P3 = I1 ⊕ I 2 ⊕ I 3 Nãúu caïc bit tin laì I1 = 1, I2 = 0, I3 = 1, I4 = 1, caïc 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 Maûch taûo maî khäúi (4, 7) Ta coï thãø viãút laûi quan hãû giæîa caïc bit tin vaì bit kiãøm tra trong vê duû trãn nhæ sau: P1 = 1xI1 ⊕ 0 xI 2 ⊕ 1xI 3 ⊕ 1xI 4 P1 = 1xI1 ⊕ 1xI 2 ⊕ 0 xI 3 ⊕ 1xI 4 P1 = 1xI1 ⊕ 1xI 2 ⊕ 1xI 3 ⊕ 0 xI 4 Tæì caïc phæång trçnh quan hãû naìy, ta ruït ra ma tráûn kiãøm tra H nhæ sau: ⎡1 0 11 : 1 0 0⎤ H = ⎢11 0 1 : 0 1 0⎥ ⎢ ⎥ ⎢111 0 : 0 0 1⎥ ⎣ ⎦ Pháön bãn traïi cuía âæåìng cháúm cháúm laì caïc hãû säú cuía caïc bit tin I1 âãún I4, pháön bãn phaíi âæåìng cháúm cháúm laì ma tráûn 3x3 coï âæåìng cheïo 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 taûo ra bàòng caïch kãút håüp mäüt ma tráûn âån vë 4 x 4 våïi ma tráûn hoaïn vë cuía ma tráûn bãn traïi âæåìng cháúm cháúm cuía H. Trong vê duû trãn, ma tráûn sinh laì: ⎡1 0 0 0 : 111 ⎤ ⎢0 1 0 0 : 0 11⎥ G=⎢ ⎥ ⎢0 0 1 0 : 1 0 1⎥ ⎢ ⎥ ⎣0 0 0 1 : 1 1 0⎦ Nhåì ma tráûn sinh G, ta coï thãø tênh toaïn âæåüc tæì maî bàòng caïch nhán vector haìng m biãøu diãùn - 113 -
- Chæång V - cho tæì maî mang tin våïi G. Trong vê duû trãn, daîy mang tin laì 1011, tæì maî khäúi tuyãún tênh (4,7) âæåüc taûo ra laì: ⎡1000111 ⎤ ⎢0100011⎥ [1011]⎢ ⎥ = [1011100] ⎢0010101⎥ ⎢ ⎥ ⎣0001110⎦ 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 traïi laì 4 bit tin I1 âãún I4, 3 bit bãn phaíi chênh laì 3 bit kiãøm tra P1 âãún P3. Theo caïch láûp maî naìy, ta nháûn tháúy khoaíng caïch Hamming täúi thiãøu laì 3, do âoï maî naìy sæía sai âæåüc 1 läùi. c) Baíng syndrome âãø giaíi maî sæía läùi Syndrome laì mäüt tæì maî âäüc láûp våïi tæì maî phaït vaì chè phuû thuäüc vaìo daîy thu bë läùi, kyï hiãûu vector syndrome laì s. Baíng syndrome laì táûp håüp táút caí caïc syndrome coï thãø coï. Goüi c laì vector biãøu diãùn cho tæì maî khäúi (n, k) . Ta coï quan hãû: mxG=c Goüi e laì vector läùi vaì r laì tæì maî thu, ta coï: r=c⊕e Syndrome âæåüc tênh nhæ sau: T T T T T T s = r x H = ( c ⊕ e) x H = c x H ⊕ e x H = 0 ⊕ e x H = e x H Baíng syndrome âæåüc tênh sàôn våïi giaí thiãút laì truyãön âi tæì maî gäöm toaìn bit 0. Vê duû baíng 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 Baíng syndrome hoaìn chènh cho táút caí caïc läùi âån Nhçn vaìo baíng hçnh 5.9 ta tháúy: khi khäng coï läùi syndrome laì 0, khi coï läùi syndrome khaïc 0 - 114 -
- Chæång V - vaì caïc syndrome khäng giäúng nhau nãn coï thãø càn cæï vaìo 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î âuïng 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 chuìm, ngæåìi ta sæí duûng kyî thuáût taûo loaûn (interleaving): xaïo träün thæï tæû caïc bit tin trong baín tin maî hoïa træåïc khi phaït vaì sàõp xãúp laûi sau khi thu, âãø taïch chuìm läùi thaình caïc läùi âån räöi måïi âæa âãún bäü giaíi maî. 5.3 Maî voìng 5.3.1 Âàûc âiãøm cuía maî voìng Nhæ âaî giåïi thiãûu åí trãn (5.1.2), maî voìng laì mäüt låïp con cuía maî khäúi tuyãún tênh. Maî voìng coï caïc âàûc âiãøm sau: - Cáúu truïc toaïn hoüc cuía maî voìng cho pheïp khaí nàng sæía läùi cao. - Coï thãø thæûc hiãûn maî voìng dãù daìng bàòng pháön cæïng, bàòng caïc thanh ghi dëch vaì caïc cäøng XOR - Dëch voìng mäüt tæì maî cuîng âæåüc mäüt tæì maî thuäüc cuìng bäü maî. - Coï thãø biãøu diãùn maî voìng bàòng âa thæïc - Coï thãø taûo ra tæì maî voìng bàòng caïch nhán modulo-2 vector mang tin våïi âa thæïc sinh. Luïc naìy maî voìng âæåüc goüi laì maî voìng khäng hãû thäúng 5.3.2 Maî kiãøm tra âäü dæ voìng CRC (Cyclic Redundancy Check) Maî CRC laì mäüt loaûi maî voìng âæåüc sæí duûng räüng raîi trãn caïc kãnh truyãön näúi tiãúp bit âãø phaït hiãûn läùi (khäng sæía läùi). Trong CRC, mäüt táûp bit kiãøm tra âæåüc tênh toaïn cho mäùi khung tin dæûa vaìo näüi dung khung, sau âoï âæåüc gàõn thãm vaìo âuäi khung âãø truyãön âi. Bãn thu thæûc hiãûn tênh toaïn tæång tæû nhæ bãn phaït âãø phaït hiãûn läùi. Caïc bit kiãøm tra goüi laì daîy kiãøm tra khung FCS (Frame Check Sequence). Thuáût toaïn cuû thãø nhæ sau: a) Tênh toaïn taûo maî CRC bãn phaït vaì kiãøm tra läùi bãn thu Goüi 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 - r Thæûc hiãûn pheïp chia M ( x ) x cho G(x), seî âæåüc: r M( x ) x R (x) = Q( x ) + , våïi Q(x) laì thæång säú vaì R(x) laì säú dæ G(x) G(x) Tæì âáy suy ra: r M( x ) x + R ( x ) = Q( x ) G(x) r Âàût T ( x ) = M ( x ) x + R ( x ) laì âa thæïc biãøu diãùn cho tæì maî CRC phaït. Roî raìng 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æí duûng maî CRC âãø phaït hiãûn läùi, âa thæïc sinh sæí duûng laì 11001. Tæì maî CRC âæåüc taûo ra nhæ hçnh 5.10 sau: 11100110 0000 11001 ⊕1 1 0 0 1 10110110 0010111 ⊕1 1 0 0 1 11100 ⊕1 1 0 0 1 00101 00 ⊕1 1 0 01 011 010 ⊕1 1 001 00 0110 Dæ (FCS) Hçnh 5.10 Vê duû taûo maî CRC Sau khi thæûc hiãûn tênh toaïn 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æí taûi bãn thu, ta thu âæåüc tæì maî: 111001101111. Hçnh 5.11 trçnh baìy viãûc thæûc hiãûn pheïp chia âa thæïc thu cho âa thæïc sinh nhæ trãn. - 116 -
- Chæång V - 11100110 1111 11001 ⊕1 1 0 0 1 10110110 0010111 ⊕1 1 0 0 1 11100 ⊕1 1 0 0 1 00101 11 ⊕1 1 0 01 011 101 ⊕1 1 001 00 1001 Dæ ≠ 0 nãn phaït hiãûn âæåüc läùi Hçnh 5.11 Vê duû giaíi maî CRC vaì phaït hiãûn läùi Viãûc læûa choün âa thæïc sinh ráút quan troüng vç noï xaïc âënh caïc kiãøu läùi coï thãø phaït hiãûn. Mäüt âa thæïc sinh báûc r coï êt nháút 3 säú 1 seî phaït hiãûn âæåüc táút caí caïc läùi âån, táút caí caïc läùi âäi, táút caí caïc läùi xaíy ra våïi säú leí, táút caí caïc läùi chuìm ngàõn hån r vaì háöu hãút caïc läùi chuìm daìi hån hoàûc bàòng r. Sau âáy laì mäüt vaìi âa thæïc sinh thæåìng duìng 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 duìng räüng raîi trong WAN, CRC - 32 âæåüc duìng trong háöu hãút caïc LAN. Khaí nàng tæû sæía läùi cuía CRC tháúp nhæng khaí nàng phaït hiãûn läùi ráút cao nãn thæåìng âæåüc duìng kãút håüp våïi ARQ âãø sæía läùi. c) Maûch thæûc hiãûn maî CRC Hçnh 5.12 trçnh baìy så âäö thæûc hiãûn CRC bãn phaït. Ta xeït cuû thãø vê duû trãn. Säú bit trong FCS laì 4 nãn cáön mäüt thanh ghi dëch 4 bit (goüi laì thanh ghi FCS) âãø biãøu diãùn x3, x2, x1 vaì x0 trong âa thæïc sinh (goüi laì caïc bit têch cæûc - active bit). Våïi âa thæïc sinh naìy thç caïc säú x3 vaì x0 laì 1 coìn x2 vaì x1 laì 0. Traûng thaïi måïi cuía x1 vaì x2 âæåüc thay bàòng traûng thaïi træåïc âoï cuía x0 vaì x1. Traûng thaïi måïi cuía x0 vaì x3 âæåüc xaïc âënh båíi traûng thaïi cuía âæåìng phaín häöi âaî XOR våïi säú træåïc âoï. Maûch hoaût âäüng nhæ sau: træåïc tiãn xoïa thanh ghi dëch FCS vaì naûp song song 8 bit âáöu tiãn trong khung tin vaìo thanh ghi vaìo song song - ra näúi tiãúp PISO (Parallel Input - Serial Output). Tên hiãûu âiãöu khiãøn phaín häöi laì 1. Theo täúc âäü cuía âäöng häö phaït TxC, caïc bit naìy âæåüc dëch ra âæåìng truyãön láön læåüt tæì msb âãún lsb. Cuìng luïc naìy, doìng bit naìy âæåüc XOR våïi - 117 -
- Chæång V - Tên hiãûu âiãön khiãøn phaín häöi (tæì 1 thaình 0 sau 8 N TxC) FCS x0 x1 x2 x3 TxC PISO lsb msb Naûp song song tæìng byte trong N byte trong khung tin TxD TxC Thanh ghi PISO Thanh ghi FCS lsb msb X0 X1 X2 X3 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 2 0 0 0 1 1 0 0 1 0 1 0 0 3 0 0 0 0 1 1 0 0 1 0 1 1 4 0 0 0 0 0 1 1 0 1 1 0 0 5 0 0 0 0 0 0 1 1 0 1 1 0 6 0 0 0 0 0 0 0 1 1 0 1 0 7 0 0 0 0 0 0 0 0 1 1 0 0 8 0 0 0 0 0 0 0 0 0 1 1 0 9 0 0 0 0 0 0 0 0 0 0 1 1 10 0 0 0 0 0 0 0 0 0 0 0 1 11 0 0 0 0 0 0 0 0 0 0 0 0 Hçnh 5.12 Så âäö maûch taûo CRC bãn phaït x3 qua âæåìng phaín häöi tråí laûi caïc âáöu vaìo choün loüc cuía 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í tuûc naìy âæåüc làûp laûi. Sau khi xuáút ra byte tin cuäúi cuìng trong khung tin, thanh ghi PISO âæåüc naûp toaìn laì säú 0, tên hiãûu âiãöu khiãøn phaín häöi tæì 1 tråí thaình 0, do âoï näüi dung cuía thanh ghi FCS - laì caïc bit kiãøm tra - âi theo sau khung tin phaït 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 Âoüc song song byte (xN) RxC RxD Thanh ghi SIPO Thanh ghi FCS lsb msb X0 X1 X2 X3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 2 1 1 1 1 1 0 0 3 0 1 1 1 1 1 1 0 4 0 0 1 1 1 0 1 1 1 5 1 0 0 1 1 1 1 0 1 0 6 1 1 0 0 1 1 1 1 1 0 1 7 0 1 1 0 0 1 1 1 0 1 1 1 8 0 0 1 1 0 0 1 1 1 1 0 1 0 9 1 Âoüc byte 0 1 0 1 10 1 0 0 1 1 11 0 0 0 0 0 12 0 0 0 0 Dæ = 0 Hçnh 5.13 Så âäö maûch kiãøm tra CRC bãn thu - 119 -
- Chæång V - Hçnh 5.13 trçnh baìy så âäö kiãøm tra CRC bãn thu. Säú liãûu thu RxD láön læåüt âæåüc dëch vaìo thanh ghi vaìo näúi tiãúp - ra song song SIPO ( Serial Input - Parallel Output) åí giæîa mäùi ä bit. Caïc bit RxD láön læåüt âæåüc XOR våïi x3 vaì phaín häöi tråí laûi thanh ghi SIPO, mäùi khi nháûn âæåüc byte 8 bit, thiãút bë âiãöu khiãøn seî âiãöu khiãøn âoüc byte. d) Giaíi maî maî CRC bàòng phæång phaïp báùy läùi Xeït træåìng håüp maî CRC âæåüc thaình láûp våïi säú bit tin k vaì säú bit täøng cäüng n thoaí maîn báút n 2 k âàóng thæïc: 2 ≤ . Vê duû k = 4, n = 7 n +1 n Phán têch x + 1 ra caïc thæìa säú nguyãn täú räöi choün thæìa säú báûc r laìm âa thæïc sinh. Vê duû: 7 3 2 3 x + 1 = ( x + 1)( x + x + 1)( x + x + 1) . 3 2 3 Choün âa thæïc sinh laì G ( x ) = x + x + 1 hoàûc laì G ( x ) = x + x + 1 Maî CRC trong træåìng håüp naìy coï khaí nàng sæía âæåüc läùi, cuû thãø laì 1 läùi. Begin ÂÃÚM = 0 Dëch voìng T'(x) sang traïi Chia T'(x) choÜ G(x) - dæ laì R'(x) Tàng ÂÃÚM lãn 1 Tênh troüng læåüng dæ W N W≤1? Y T'(x) = T'(x) + R'(x) Dëch voìng T'(x) sang phaíi ÂÃÚM láön End Hçnh 5.14 Thuáût toaïn sæía läùi maî CRC bàòng phæång phaïp báùy läùi - 120 -
- Chæång V - Hçnh 5.14 trçnh baìy thuáût toaïn sæía läùi cho maî CRC bàòng phæång phaïp báùy läùi. Goüi 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 voìng T'(x) sang traïi, sau âoï chia cho G(x) âãø tçm säú dæ R'(x). Viãûc dëch voìng seî diãùn ra nhiãöu láön cho âãún khi troüng læåüng dæ nhoí hån hoàûc bàòng 1. Trong læu âäö trãn, ta duìng biãún ÂÃÚM âãø âãúm säú láön dëch voìng traïi. Sau âoï cäüng T'(x) våïi R'(x), läùi âæåüc báùy vaì sæía sau pheïp cäüng naìy. Tuy nhiãn, ta cáön phaíi sæía laûi vë trê caïc bit trong T'(x) do nhæîng láön dëch voìng traïi. Do âoï, phaíi dëch voìng T'(x) ngæåüc laûi sang phaíi våïi säú láön bàòng säú láön træåïc âoï âaî dëch voìng sang traïi (säú láön dëch voìng phaíi åí âáy chênh laì ÂÃÚM). 3 2 Vê duû tin laì 4 bit 1100, âa thæïc sinh choün laì x + x + 1 . Thæûc hiãûn maî hoïa ta âæåüc tæì maî phaït laì 1100 101. Giaí sæí bãn thu thu âæåüc tæì maî 1110 101. Kiãøm tra läùi bàòng caïch chia T'(x) cho G(x), ta tháúy pheïp chia coìn dæ nãn kãút luáûn coï läùi. Váûy tiãún haình sæía läùi nhæ sau: Dëch voìng traïi láön thæï nháút âæåüc 1101011, chia cho G(x) dæ laì 011. Dëch voìng traïi láön thæï hai âæåüc 1010111, chia cho G(x) dæ laì 110. Dëch voìng traïi láön thæï ba âæåüc 0101111, chia cho G(x) dæ laì 001. Thæûc hiãûn pheïp cäüng modulo-2: 0101111 ⊕ 001 ta âæåüc 0101110, räöi dëch voìng sang phaíi 3 láön ta âæåüc laûi tæì maî 1100101 giäúng nhæ bãn phaït. 5.3.3 Maî Hamming Maî Hamming laì mäüt træåìng håüp riãng âån giaín nháút cuía maî voìng. 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 daûng täøng quaït c c i c i i ic i.... . ÅÍ âáy i laì caïc 1 2 4 8 bit tin vaì c laì caïc bit kiãøm tra. Caïc bit c chênh laì kãút quaí cuía pheïp XOR giaï trë chè vë trê cuía caïc 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 phaït. Nãúu kãút quaí cuía pheïp XOR laì mäüt giaï trë khaïc 0 thç âoï chênh laì vë trê cuía bit läùi. Vê duû xeït khaí nàng sæía läùi âån cuía maî Hamming (7, 11) trong træåìng håüp tæì maî mang tin laì 1011101. Tæì maî Hamming coï daûng: c c 1c 011c 101 . 1 2 4 8 Caïc bit 1 åí caïc vë trê: 3, 6, 9 vaì 11. Âäøi caïc säú naìy 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 phaït âi laì: 10100110101 Giaí sæí åí bãn thu, thu âæåüc tæì maî: 10000110101. Âäøi giaï trë chè vë trê cuía caïc bit 1 sang nhë phán räöi tênh XOR tæång tæû nhæ bãn phaït: - 121 -
- Chæång V - 1 ↔ 0001,6 ↔ 0110,7 ↔ 0111,9 ↔ 1001,11 ↔ 1011 0001 ⊕ 0110 ⊕ 0111 ⊕ 1001 ⊕ 1011 = 0011 ↔ 3 Tæì âáy xaïc âënh âæåüc bit läùi laì bit åí vë trê thæï 3. Váûy tæì maî thu âæåüc sæía laûi laì: 10100110101 giäúng nhæ tæì maî phaït. 5.4 Maî cháûp 5.4.1 Maî hoïa maî cháûp Nhæ trçnh baìy åí muûc 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æì caïc thanh ghi dëch kK bit. ÅÍ âáy ta xeït loaûi maî cháûp phäø biãún nháút laì maî cháûp coï k = 1. Bäü maî hoïa laì thanh ghi dëch K bit. Âáöu ra cuía caïc vë trê trong thanh ghi âæåüc læûa choün âãø cäüng modulo-2 våïi nhau. Säú læåüng bäü cäüng modulo-2 chênh laì n. Mäüt bäü chuyãøn maûch seî láön læåüt láúy máùu mäùi âáöu ra cuía bäü cäüng modulo-2 theo nhëp cuía âäöng häö thanh ghi dëch. Hçnh 5.15 minh hoüa mäüt bäü maî hoïa maî cháûp våïi k = 1, K = 3, n = 2. 1 T0 T0 T0 2 Vaìo 1 1 0 1 Ra 11 10 11 01 Hçnh 5.15 Vê duû bäü maî hoïa 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î hoïa maî cháûp bàòng caïc â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 cuía 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 2 laì G ( x ) = 1 + x vaì G ( x ) = 1 + x 1 2 Giaí sæí daîy tin vaìo bäü maî hoïa laì 1100, daîy maî hoïa seî laì 11101101 . . ., nghéa laì æïng våïi mäüt bit tin vaìo coï hai bit maî hoïa ra. Do âoï, tyí lãû maî laì 1/2. Âënh nghéa âaïp æïng xung cuía maî hoïa laì âaïp æïng cuía bäü maî hoïa khi bit vaìo laì 1. Trong vê duû trãn, âaïp æïng xung seî laì: 110110. Våïi daîy vaìo laì 1101, ta tháúy daîy ra coï thãø âæåüc tênh laì cháûp daîy vaìo våïi âaïp æïng xung. Do âoï maî naìy 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 baìy så âäö cáy biãøu diãùn maî cháûp cho vê duû trãn. Giaí sæí ban âáöu toaìn bäü thanh ghi âæåüc xoaï vãö 0. Âoüc så âäö cáy theo phæång ngang tæì traïi qua phaíi, mäùi nhaïnh cáy - 122 -