Giáo trình Kỹ thuật thông tin số - Chương 4: Mã hóa nguồn

Nội dung text: Giáo trình Kỹ thuật thông tin số - Chương 4: Mã hóa nguồn

1. - Chæång IV - Chæång 4 Maî hoïa nguäön Hãû thäúng thäng tin âæåüc sæí duûng âãø truyãön tin tæïc tæì nguäön tin âãún nháûn tin. Nguäön tin sinh ra tin dæåïi nhiãöu daûng khaïc nhau, vê duû ám thanh trong hãû thäúng radio, tên hiãûu video trong hãû thäúng vä tuyãún truyãön hçnh Tin naìy coï thãø âæåüc âæa træûc tiãúp vaìo kãnh âãø truyãön âi, nhæng trong thæûc tãú, tin naìy thæåìng âæåüc biãún âäøi räöi âæa vaìo kãnh truyãön. Vê duû nhæ tin laì vàn baín tiãúng Anh, nguäön tin coï khoaíng 40 kyï tæû (symbol) khaïc nhau, gäöm caïc máùu tæû alphabet, con säú, dáúu cháúm cáu Vãö nguyãn tàõc ta coï thãø duìng 40 daûng soïng âiãûn aïp khaïc nhau âãø biãøu thë 40 kyï tæû naìy. Tuy nhiãn thæûc tãú thç phæång phaïp naìy khäng phuì håüp, quaï khoï thæûc hiãûn hay tháûm chê khäng thãø âæåüc, vç: - Kãnh truyãön khäng phuì håüp vãö màût váût lyï âãø coï thãø mang nhiãöu kyï tæû khaïc nhau nhæ váûy. - Daíi táön âoìi hoíi seî ráút räüng. - Viãûc læu træî hay xæí lyï tên hiãûu træåïc khi truyãön ráút khoï, trong khi nãúu chuyãøn sang nhë phán thç moüi viãûc seî dãù daìng hån nhiãöu. Váûy ta tháúy cáön phaíi thay âäøi daûng cuía tin khaïc âi so våïi daûng ban âáöu do nguäön cung cáúp. Cäng viãûc thay âäøi daûng naìy âæåüc goüi laì maî hoïa (encoding). Cå såí lyï thuyãút cuía maî hoïa laì lyï thuyãút tin (information theory). Lyï thuyãút tin liãn quan âãún viãûc biãøu diãùn tin bàòng caïc kyï tæû, âæa ra giåïi haûn lyï thuyãút cho viãûc thæcû hiãûn hãû thäúng thäng tin, cho pheïp âaïnh giaï hiãûu suáút cuía hãû thäúng thæûc tãú. Nãön taíng cuía lyï thuyãút tin do Hartley vaì Nyquist âæa ra tæì nhæîng nàm 1920 vaì âæåüc Shannon hoaìn chènh vaì täøng kãút vaìo nàm 1948. Âáy laì mäüt lyï thuyãút phæïc taûp, pháön âáöu cuía chæång naìy daình âãø trçnh baìy nhæîng váún âãö cå baín nháút cuía lyï thuyãút tin. Vãö caïc muûc âêch cuía maî hoïa, ta coï thãø toïm tàõt nhæ sau: - Âënh daûng, âãø chuyãøn tin tæì daûng gäúc tæû nhiãn sang daûng chuáøn vê duû sang daûng säú PCM. - Maî hoïa âæåìng, âãø âaím baío daûng soïng cuía kyï tæû truyãön âi phuì håüp våïi caïc âàcû âiãøm cuía kãnh truyãön. - Maî hoïa nguäön (source encoding), nhàòm giaím säú kyï tæû trung bçnh yãu cáöu âãø truyãön baín tin. - Máût maî hoïa (encryption), âãø maî hoïa baín tin bàòng mäüt khoïa máût maî nhàòm traïnh sæû thám nháûp traïi pheïp, âaím baío âäü an toaìn cho thäng tin. - Maî hoïa kãnh truyãön (channel encoding), cho pheïp bãn thu coï thãø phaït hiãûn, kãø caí sæía - 81 -
2. - Chæång IV - âæåüc caïc läùi trong baín tin thu âãø tàng âäü tin cáûy cuía thäng tin. Pháön âënh daûng vaì maî hoïa âæåìng âaî âæåüc xeït âãún trong chæång III. Do nhæîng âàûc âiãøm riãng, pháön máût maî hoïa khäng âæåüc âãö cáûp trong giaïo trçnh naìy. Pháön maî hoaï kãnh truyãön seî âæåüc trçnh baìy trong chæång sau. Chæång naìy trçnh baìy vãö maî hoïa nguäön, trong âoï táûp trung vaìo loaûi maî thäúng kã täúi æu. Loaûi maî naìy taûo ra tæì maî coï âäü daìi thay âäøi, trong âoï phäø biãún laì maî Huffman, bao gäöm maî Huffman cå såí (basic Huffman) vaì maî Huffman âäüng (dynamic Huffman). Pháön cuäúi chæång seî giåïi thiãûu så læåüc vã ö maî hoïa fax (facsimile) 4.1 Lyï thuyãút tin 4.1.1 Âo tin tæïc Âãø âaïnh giaï âënh læåüng cho tin tæïc, ngæåìi ta âæa ra khaïi niãûm læåüng tin (information content). Læåüng tin liãn quan âãún giaï trë cuía tin, hay noïi caïch khaïc laì khaí nàng dæû âoaïn âæåüc (predictability) cuía tin: mäüt tin coï khaí nàng âoaïn træåïc caìng nhiãöu thç caìng chæïa êt tin. Vê duû, baín tin vãö tyí säú tráûn boïng Manchester United - Bradford Academicals laì 7 - 0 chæïa ráút êt tin nhæng kãút quaí ngæåüc laûi thç gáy cháún âäüng, vaì do âoï chæïa ráút nhiãöu tin. Váûy xaïc suáút caìng cao thç baín tin caìng chæïa êt tin vaì ngæåüc laûi. Ta coï thãø viãút: p (baín tin) = 1 khäng mang tin p (baín tin) = 0 mang mäüt læåüng tin vä haûn. Tæì nháûn xeït trãn, ta tháúy tin caìng coï yï nghéa khi noï caìng hiãúm gàp,û nãn âäü låïn cuía noï phaíi tyí lãû nghëch våïi xaïc suáút xuáút hiãûn cuía tin. Xeït nguäön tin X råìi raûc sinh ra caïc tin i våïi xaïc suáút laì p(i), læåüng tin cuía tin i phaíi laì mäüt haìm coï caïc âàûc âiãøm sau: - Tyí lãû nghëch våïi xaïc suáút xuáút hiãûn p(i), hay âoï laì haìm f(1/p(i)). - Haìm naìy phaíi laì 0 khi p(i) = 1. - Nãúu hai tin âäüc láûp thäúng kã laì i vaì j âäöng thåìi xuáút hiãûn, ta coï tin laì (i,j), læåüng tin chung cuía chuïng phaíi bàòng täøng læåüng tin cuía tæìng tin, nghéa laì: f(1/p(i,j)) = f(1/p(i)) + f(1/p(j)) Theo luáût nhán xaïc suáút ta coï: p(i,j) = p(i).p(j) Do âoï: f(1/(p(i).p(j))) = f(1/p(i)) + f(1/p(j)) Ta tháúy haìm loga thoaí maîn táút caí caïc yãu cáöu naìy. Váûy haìm log(1/p(i)) âæåüc choün âãø âaïnh giaï âënh læåüng cho tin. Læåüng tin cuía mäüt tin i âæåüc kyï hiãûu laì I(i). Âënh nghéa læåüng tin cuía mäüt tin i laì: 1 I(i) = log = −logp(i) p(i) - 82 -
3. - 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ì: 1 I(i) = log = −log p(i) (bit) 2 p(i) 2 Váûy coï thãø âënh nghéa bit nhæ sau: bit laì læåüng tin mang trong mäüt kyï tæû coï xaïc suáút xuáút hiãûn laì p = 0,5. 4.1.2 Entropy cuía nguäön tin Entropy H âæåüc âënh nghéa laì giaï trë trung bçnh thäúng kã cuía læåüng tin. Âoï laì læåüng tin trung bçnh chæïa trong mäüt kyï tæû báút kyì cuía nguäön tin. Xeït mäüt nguäön tin sinh ra M kyï tæû âäüc láûp thäúng kã. Nguäön tin naìy âæåüc goüi laì nguäön råìi raûc khäng nhåï (discrete memoryless source). Entropy cuía nguäön naìy laìì: M 1 H = p(m)log (bit/kyï tæû) ∑ 2 m=1 p(m) trong âoï p (m) laì xaïc suáút choün kyï tæû thæï m. Lyï thuyãút tin âaî chæïng minh giaï trë låïn nháút cuía entropy laì H = log M , âaût âæåüc khi max 2 caïc kyï tæû âäüc láûp vaì âäöng xaïc suáút (equiprobable), nghéa laì: p(m) = 1/ M, ∀m = 1,M Âäúi våïi nguäön tin ASCII coï M = 128 thç entropy cæûc âaûi laì: Hmax = - log2(1/128) = 7 (bit/kyï tæû). Thæûc tãú thç âiãöu naìy khoï xaíy ra nãn entropy cuía nguäön ASCII laì: 128 1 H = p(m)log < 7 (bit/kyï tæû) ∑ 2 m=1 p(m) Âäú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ì: 2 1 1 1 H = p(m)log = plog + (1− p)log (bit/kyï tæû) ∑ 2 2 2 m=1 p(m) p 1− p 4.1.3 Entropy coï âiãöu kiãûn vaì âäü dæ Âäúi våïi caïc nguäön tin trong âoï viãûc sinh ra kyï tæû sau khäng âäüc láûp thäúng kã våïi caïc kyï tæû træåïc âoï ( goüi laì nguäön coï nhåï - memory source) thç cäng thæïc entropy trãn khäng âuí täøng quaït âãø tênh âæåüc entropy chênh xaïc. Trong træåìng håüp naìy phaíi xeït âãún xaïc suáút coï âiãöu kiãûn (conditional probability). Vê duû våïi nguäön coï nhåï mäüt kyï tæû, nghéa laì kyï tæû sau âæåüc choün phuû thuäüc vaìo mäüt kyï tæû træåïc âoï, entropy âæåüc tênh nhæ sau: - 83 -
4. - Chæång IV - 1 H = p(j,i)log (bit/kyï tæû) ∑ ∑ 2 i j p(ji) åí âáy p(j,i) laì xaïc suáút nguäön choün i vaì j, p(ji) laì xaïc suáút nguäön choün j nãúu træåïc âoï âaî choün i. Theo âënh lyï Bayes, ta coï: p(j,i) = p(i)p(ji) Váûy: 1 H = p(i) p(ji)log (bit/kyï tæû) ∑ ∑ 2 i j p(ji) 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: 1 r = H − H = log M − p(i) p(ji)log (bit/kyï tæû) max 2 ∑ ∑ 2 i j p(ji) Âäü dæ tæång âäúi cuía nguäön âæåüc âënh nghéa nhæ sau: H − H H r = max =1− H H max max 4.1.4 Sæû máút maït tin do nhiãùu Goüi kyï tæû nguäön thæï i âæåüc truyãön âi laì i , xaïc suáút xuáút hiãûn i laì p(i ) , læåüng tin cuía TX TX TX i laì I (i ): TX TX TX 1 I (i ) = log (bit) TX TX 2 p(i ) TX Âäúi våïi kãnh khäng nhiãùu (noiseless channel), giaí sæí âiãûn aïp v tæång æïng våïi kyï tæû phaït laì RX i , khi bãn nháûn tin taïch âæåüc v thç coï thãø biãút chàõc chàõn kyï tæû phaït åí nguäön laì i . TX RX TX Læåüng tin trong træåìng håüp naìy âæåüc baío toaìn khi truyãön qua kãnh: 1 I (v :i ) = I (i ) = log (bit) RX RX TX TX TX 2 p(i ) TX 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 v thç RX 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 p(i v ) , âáy laì xaïc suáút phaït kyï tæû thæï i vaì taïch âæåüc âiãûn aïp v åí bãn TX RX RX 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ì: - 84 -
5. - Chæång IV - p(i v ) I (v :i ) = log TX RX (bit) RX RX TX 2 p(i ) TX Giaí sæí bãn nháûn tin thæûc hiãûn quyãút âënh cæïng, âiãûn aïp v chuyãøn âäøi træûc tiãúp thaình kyï tæû RX nháûn laì i . Trong træåìng håüp naìy, læåüng tin nháûn âæåüc laì: RX p(i i ) I (i ) = log TX RX (bit) RX RX 2 p(i ) TX Sæû suy giaím læåüng tin trong mäùi kyï tæû do nhiãùu coï nghéa laì entropy nháûn nhoí hån entropy phaït. Entropy nháûn chênh laì entropy hiãûu quaí (effective entropy) cuía caïc kyï tæû nháûn. Kyï hiãûu entropy hiãûu quaí laì H vaì âæåüc tênh nhæ sau: eff H = p(i )I (i ) (bit/kyï tæû) eff ∑ RX RX RX i åí âáy p(i ) laì xaïc suáút thu kyï tæû thæï i. RX Sæû khaïc nhau giæîa H vaì entropy phaït goüi laì âäü nghi ngåì (equivocation) E: eff H = H - E (bit/kyï tæû) eff Âäü 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ì: 1 1 E = p(i , j )log = p(j ) p(i j )log ∑ ∑∑TX RX 2 RX ∑ TX RX 2 i jjp(i j ) i p(i j ) TX RX TX RX åí âáy p(j ) laì xaïc suáút nháûn kyï tæû thæï j, p(i j ) liãn quan âãún xaïc suáút läùi kyï tæû. RX TX RX 4.1.5 Täúc âäü láûp tin cuía nguäön tin Ngoaìi thäng säú cå baín cuía nguäön laì entropy tuyì thuäüc vaìo cáúu truïc thäúng kã cuía nguäön, coìn coï mäüt thäng säú khaïc tuyì thuäüc vaìo tênh cháút váût lyï cuía nguäön. Âoï laì täúc âäü thiãút láûp tin (information rate) cuía nguäön, kyï hiãûu laì R. Thäng säú naìy chè ra sæû hçnh thaình tin nhanh hay cháûm âãø âæa vaìo kãnh. Vê duû con ngæåìi, do kãút cáúu cuía cå quan phaït ám nãn mäùi giáy chè phaït ám âæåüc tæì 5 âãún 7 tiãúng, trong khi mäüt thiãút bë âáöu cuäúi säú liãûu coï thãø âaût âãún haìng ngaìn kyï hiãûu trong mäüt giáy. Täúc âäü thiãút láûp tin cuía nguänö coï âån vë laì læåüng tin trãn âån vë thåìi gian (træåìng håüp duìng loga cå säú 2 thç âån vë laì bit/s) vaì âæåüc tênh laì têch cuía entropy våïi säú kyï hiãûu láûp âæåüc trong mäüt âån vë thåìi gian: - 85 -
6. - Chæång IV - R = n H (bit/s) 0 trong âoï n0 laì säú kyï hiãûu láûp âæåüc trong mäüt âån vë thåìi gian, tuyì thuäüc vaìo tênh cháút váût lyï cuía nguäön. Ta tháúy âãø náng cao täúc âäü thiãút láûp tin cuía nguäön cáön thiãút phaíi náng cao entropy. Täúc âäü láûp tin cuía nguäön seî cæûc âaûi khi entropy cuía nguäön cæûc âaûi. 4.1.6 Thäng læåüng kãnh Âënh nghéa thäng læåüng cuía kãnh (channel capacity) laì læåüng tin täúi âa kãnh cho âi qua trong mäüt âån vë thåìi gian maì khäng gáy läùi. Kyï hiãûu thäng læåüng kãnh laì C vaì âån vë âo giäúng nhæ âån vë cuía täúc âäü láûp tin (bit/s). Thäng thæåìng täúc âäü láûp tin beï hån nhiãöu so våïi thäng læåüng kãnh: 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. Âãø so saïnh caïc loaûi hãû thäúng thäng tin khaïc nhau, ta coï thãø xeït kãnh truyãön cho thuáûn tiãûn. Xeït kãnh coï nhiãùu gausse tràõng, tyí säú tên hiãûu trãn nhiãùu trung bçnh laì S/N, bàng thäng cuía kãnh laì B. Theo âënh lyï Hartley - Shannon, thäng læåüng cuía kãnh naìy laì: C = Blog (1 + S/ N) (bit/s) 2 - 86 -
7. - Chæång IV - Coï thãø aïp duûng räüng raîi kãút quaí naìy cho nhiãöu hãû thäúng khaïc nhau båíi vç coï thãø mä hçnh hoïa nhiãöu kãnh thaình kãnh gausse tràõng (white gaussian channel). Kãút quaí naìy cuîng âæåüc cháúp nháûn cho caí kãnh liãn tuûc vaì råìi raûc. 4.2 Cå baín vãö maî hoïa 4.2.1 Âënh nghéa maî hoïa Cho nguäön tin råìi raûc X sinh ra N tin hay kyï tæû âäüc láûp ( x ,x , ,x , ,x ). Xeït mäüt táûp M 1 2 i N coï M pháön tæí hæîu haûn ( m ,m , ,m ). 1 2 q Maî hoïa (encoding) nguäön tin X bàòng táûp M coï nghéa laì biãún âäøi mäùi tin x cuía nguäön tin X i thaình mäüt táûp caïc pháön tæí thuäüc M nhàòm thoía maîn mäüt yãu cáöu naìo âoï cuía hãû thäúng thäng tin: x → m m m i i1 i2 il Pheïp biãún âäøi ngæåüc laûi: m m m → x i1 i2 il i âæåüc goüi laì giaíi maî (decoding). Thäng thæåìng, säú tin cuía nguäön tin ráút låïn nãn säú kyï hiãûu maî khäng thãø bàòng hoàûc nhiãöu hån säú tin. 4.2.2 Caïc tham säú cå baín cuía maî hoïa Táûp M âæåüc goüi laì maî hiãûu (code), caïc pháön tæí m goüi laì kyï hiãûu maî (symbol), säú kyï hiãûu maî k khaïc nhau trong maî goüi laì cå säú cuía maî. Maî nhë phán laì maî cå säú 2, trong âoï maî chè coï 2 kyï hiãûu maî laì 0 vaì 1. Daîy liãn tuûc caïc kyï hiãûu maî duìng âãø maî hoïa mäüt tin cuía nguäön âæåüc goüi laì tæì maî (codeword). ÅÍ âáy tæì maî tæång æïng våïi tin x laì m m m . i i1 i2 il Säú kyï hiãûu maî coï trong mäüt tæì maî âæåüc goüi laì âäü daìi cuía tæì maî (codeword length), kyï hiãûu laì l. Vê duû tæì maî 00100 coï âäü daìi laì 5. Tham säú tiãúp theo laì troüng læåüng tæì maî (codeword weigh), âoï laì täøng säú caïc kyï hiãûu khaïc 0 coï màût trong tæì maîî, kyï hiãûu laì w. Vê duû tæì maî 110001 coï troüng læåüng laì 3. Mäüt tham säú næîa laì khoaíng caïch maî (distance), kyï hiãûu laì d. Âoï laì säú kyï hiãûu cuìng vë trê khaïc nhau giæîa hai tæì maî daìi bàòng nhau. Vê duû khoaíng caïch giæîa hai tæì maî 110001 vaì 101000 laì 3. Goiü C1 vaì C2 laì hai tæì maî daìi bàòng nhau. Coï thãø dãù daìng nháûn tháúy khoaíng caïch maî giæîa hai tæì maî naìy laì: d(C ,C ) = w(C ⊕ C ) 1 2 1 2 - 87 -
8. - Chæång IV - 4.2.3 Phán loaûi maî Ta coï thãø phán loaûi maî theo nhiãöu caïch khaïc nhau. Dæåïi âáy laì mäüt säú caïch hay gàûp: - Dæûa vaìo âäü daìi cuía tæì maî, ta phán ra maî coï âäü daìi khäng âäøi goüi laì maî âãöu vaì maî coï âäü daìi thay âäøi goüi laì maî khäng âãöu. Âäúi våïi maî khäng âãöu, âäü daìi trung bçnh laì mäüt thäng säú cå baín cuía maî vaì âæåüc tênh theobiãøu thæïc: M l = p(m)l ∑ m m=1 trong âoï lm laì âäü daìi tæì maî tæång æïng våïi kyï tæû m. - Dæûa vaìo troüng læåüng cuía tæì maî, ta phán ra maî coï troüng læåüng khäng âäøi vaì maî coï 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í nàng phaït hiãûn vaì sæía läùi vaì ma î khäng coï khaí nàng 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æ: D = B ⊕ C,F = B ⊕ E,G = C ⊕ E,H = B ⊕ C ⊕ E . Váûy khäng cáön thiãút phaíi liãût kã hãút táút caí caïc tæì maî trong baíng maî maì chè cáön choün mäüt säú tæì maî laìm cå såí. Caïc tæì maî cå såí naìy seî láûp thaình baíng dæåïi daûng ma tráûn vaì goüi laì ma tráûn sinh (generated matrix). - 88 -
9. - Chæång IV - Vê duû ma tráûn sinh tæång æïng våïi baíng maî trãn laì: ⎡0 0 1⎤ ⎢ ⎥ 0 1 0 ⎢ ⎥ ⎣⎢1 0 0⎦⎥ Khi thaình láûp ma tráûn sinh, quy æåïc loaûi boí caïc tæì maî gäöm toaìn kyï hiãûu 0. c) Phæång phaïp cáy Cáy maî (code tree) gäöm coï nuït gäúc (root node), nuït laï (leaf node) vaì caïc nuït nhaïnh (branch node). Gäúc cuía cáy goüi laì nuït gäúc. Tæì nuït gäúc phán ra täúi âa q nhaïnh (q laì cå säú cuía maî). Mäùi nhaïnh mang mäüt kyï hiãûu maî, âoï laì giaï trë cuía nhaïnh. Nhaïnh âæåüc bàõt âáöu åí nuït mæïc i vaì kãút thuïc åí nuït mæïc i+1. Nuït maì tæì âoï coìn phán nhaïnh tiãúp goüi laì nuït nhaïnh. Tæì mäùi nuït nhaïnh phán ra täúi âa q nhaïnh. Nuït cuäúi cuìng cuía cáy goiü laì nuït laï. Mäùi nuït laï biãøu diãùn mäüt cho mäüt tæì maî. Tæì maî bao gäöm caïc kyï hiãûu maî laì giaï trë cuía caïc nhaïnh theo thæï tæû âi tæì nuït gäúc qua caïc nuït nhaïnh âãún nuït laï. Hçnh 4.1 laì vê duû vãö mäüt cáy maî cho bäü maî nhë phán gäöm caïc tæì maî laì 00, 01, 10, 1101, 11001. Mæïc 0 1 Mæïc 1 0 1 0 1 Mæïc 2 00 01 10 0 Mæïc 3 0 1 Mæïc 4 1 1101 Mæïc 5 11001 Hçnh 4.1 Vê duû vãö cáy maî Nhçn vaìo cáy maî ta coï thãø biãút âæåüc âáy laì maî âãöu hay khäng âãöu. Maî laì âãöu khi táút caí caïc nuït laï coï cuìng mæïc. Maî biãøu diãùn bàòng cáy maî åí hçnh 4.1 thuäüc loaûi maî khäng âãöu. d) Phæång phaïp âa thæïc Phæång phaïp naìy duìng laìm mä hçnh toaïn âãø biãøu diãùn maî voìng. Æu âiãøm cuía phæång phaïp naìy laì coï thãø thæûc hiãûn maî hoïa vaì giaíi maî maî voìng dãù daìng bàòng caïch sæí duûng caïc pheïp toaïn âäúi våïi âa thæïc nhæ pheïp cäüng, nhán vaì chia. Tæì maî k bit m m m m m ( theo thæï tæû tæì traïi qua phaíi laì msb âãún lsb) coï thãø âæåüc k−1 k−2 2 1 0 biãøu diãùn bàòng âa thæïc sau: - 89 -
10. - Chæång IV - k−1 k−2 2 f (x) = m x + m x + + m x + m x + m k−1 k−2 2 1 0 6 5 3 Vê duû tæì maî nhë phán 1101001 coï thãø biãøu diãùn bàòng âa thæïc: f (x) = x + x + x +1. 4.3 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 coï ráút nhiãöu daûng khaïc nhau, nhæng coï thãø phán thaình hai loaûi chênh laì nguäön liãn tuûc (continuous source) nhæ nguäön ám thanh, nguäön video vaì nguäön råìi raûc (discrete source) nhæ nguäön dæî liãûu tæì maïy tênh. Trong hãû thäúng thäng tin säú, âáöu ra cuía nguäön phaíi âæåüc chuyãøn thaình daûng thêch håüp âãø coï thãø truyãön âi bàòng kyî thuáût säú. Theo sæû phán loaûi nguäön, ta coï hai kyî thuáût maî hoïa nguäön chênh laì maî hoïa nguäön liãn tuûc vaì maî hoïa nguäön råìi raûc. Näüi dung maî hoïa nguäön liãn tuûc cuîng trungì våïi näüi dung säú hoaï tên hiãûu liãn tuûc âaî xeït trong chæång træåïc. Trong pháön naìy, ta xeït quaï trçnh maî hoïa nguäön råìi raûc (discrete source encoding). Nguäön råìi raûc laì nguäön sinh ra caïc kyï tæû våïi mäüt quy luáût phán bäú xaïc suáút naìo âoï. Âãø cho âån giaín, ta xeït træåìng håüp nguäön khäng nhåï, caïc kyï tæû âæåüc sinh ra âäüc láûp våïi nhau. Thäng thæåìng, quy luáût phán bäú xaïc suáút sinh ra caïc kyï tæû laì khäng âãöu nãn âäü dæ cuía nguäön låïn, entropy cuía nguäön beï, täúc âäü láûp tin cuía nguäön coìn xa måïi âaût âãún thäng læåüng kãnh. Luïc âoï nhiãûm vuû cuía maî hoïa nguäön råìi raûc laì laìm cho cáúu truïc thäúng kã cuía nguäön tråí nãn håüp lyï bàòng caïch tàng entropy cuía caïc kyï tæû duìng âãø maî hoïa nguäön. Nguyãn tàõc cuía maî hoïa nguäön råìi raûc laì maî hoïa caïc kyï tæû coï xaïc suáút sinh ra låïn bàòng caïc tæì maî ngàõn vaì maî hoïa caïc kyï tæû coï xaïc suáút sinh ra beï bàòng caïc tæì maî daìi. Loaûi maî naìy goüi laì maî hoïa thäúng kã (statistical encoding). Mäüt vê duû cuía maî hoïa thäúng kã laì maî Morse duìng âãø maî hoïa baín tin tiãúng Anh. Trong maî Morse, kyï tæû xuáút hiãûn nhiãöu nháút laì 'e' âæåüc maî hoaï bàòng tæì maî ngàõn nháút '.' (1 bit). Dæûa theo nguyãn tàõc naìy ta tháyú maî hoïa thäúng kã giuïp traïnh hiãûn tæåüng kãnh truyãön bë quaï taíi khi baín tin chæïa quaï nhiãöu kyï tæû coï xaïc suáút xuáút hiãûn låïn. Viãûc truyãön tin seî tråí nãn kinh tãú hån nãúu maî thäúng kã coï âäü daìi trung bçnh cuía tæì maî laì nhoí nháút. Loaûi maî nhæ váûy goüi laì maî thäúng kã täúi æu (optimum statistical code). Âáy chênh laì maî hoïa neïn (copression) Pháön sau âáy seî xeït cuû thãø caïc tiãu chuáøn cuía maî thäúng kã täúi æu cå säú 2. 4.3.1 Giåïi haûn cuía âäü daìi tæì maî trung bçnh Giaí sæí nguäön tin X sinh ra caïc kyï tæû xi âäüc láûp. Maî hoïa nguäön tin X bàòng bäü maî nhë phán M, caïc kyï hiãûu maî 0 vaì 1 coï xaïc suáút bàòng nhau p(0) = p(1) = 0.5. Læåüng tin riãng cuía mäüt kyï hiãûu 0 hay 1 bàòng våïi læåüng tin trung bçnh vaì âaût giaï trë cæûc âaûi: I(0) = I(1) = log 2 =1 (bit/kyï hiãûu) 2 Maî hoïa kyï tæû xi bàòng mäüt tæì maî nhë phán daìi li. Nhæ váûy læåüng tin chæïa trong tæì maî naìy seî laì li (bit). Læåüng tin trung bçnh chæïa trong mäüt tæì maî seî laì âäü daìi trung bçnh cuía tæì maî, laì L (bit) - 90 -
11. - 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: L ≥ H Âá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: l = −logp(x ) i i Vç li laì säú nguyãn nãn - logp(xi) 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 = Lmin. Ta coï bäü maî thäúng kã täúi æu. Thæåìng thç - logp(xi) khäng phaíi laì säú nguyãn nãn L ≥ H chè laì mäüt âiãöu kiãûn giåïi haûn. Ta coï thãø tháúy: âãø âäü daìi tæì maî trung bçnh nhoí nháút khi - logp(xi) khäng phaíi laì säú nguyãn thç L phaíi thoaí maîn báút âàóng thæïc sau: H ≤ L < H + 1 Váûy giåïi haûn trãn cuía âäü daìi tæì maî trung bçnh laì H+1. Mäüt bäü maî coï âäü daìi tæì maî trung bçnh thoaí âiãöu kiãûn naìy âæåüc goüi laì maî thäúng kã täúi æu. 4.3.2 Hiãûu suáút maî Âënh nghéa hiãûu suáút maî (code efficiency) laì tyí säú giæîa entropy cuía nguäön tin coï caïc kyï tæû âäüc láûp vaì entropy cæûc âaûi cuía nguäön âoï: M 1 p(m)log H ∑ 2 p(m) η = x100% = m=1 x100% H log M max 2 Nãúu caïc kyï tæû nguäön âæåüc maî hoïa thaình mäüt táûp caïc kyï tæû måïi nhæ hçnh 4.2 thç H vaì H max laì entropy vaì entropy cæûc âaûi cuía táûp kyï tæû måïi naìy. Baín tin Baín tin Maî hoïa (Táûp kyï tæû 1) (Táûp kyï tæû 2) 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 -
12. - Chæång IV - H H η = x100% = x100% (bit/säú nhë phán) L M p(m)l ∑ m m=1 åí âáy lm laì âäü daìi cuía mäùi tæì maî nhë phán vaì L laì âäü daìi tæì maî trung bçnh. So saïnh hai cäng thæïc tênh hiãûu suáút maî åí trãn, ta ruït ra âæåüc: Hmax (bit/kyï tæû) = L (bit/tæì maî) 4.3.3 Giaíi maî trong træåìng håüp tæì maî coï âäü daìi thay âäøi Noïi chung laì chuïng ta âi tçm mäüt caïch maî hoïa hæîu hiãûu coï thãø biãøu diãùn caïc tin giäúng nhau maì trung bçnh duìng êt säú nhë phán hån. Kãút quaí laì âäü daìi cuía caïc tæì maî biãøu diãùn caïc kyï tæû khaïc nhau seî khaïc nhau. Váún âãö âàût ra laì laìm thãú naìo âãø bãn giaíi maî nháûn ra âæåüc âiãøm bàõt âáöu vaì kãút thuïc cuía caïc tæì maî daìi khaïc nhau nhæ váûy. Sau âáy laì caïc âàûc âiãøm cáön phaíi coï âãø giaíi maî våïi caïc tæì maî daìi khaïc nhau: a) Giaíi maî duy nháút (unique decoding) Âiãöu naìy laì cáön thiãút âãø cho caïc baín tin thu chè coï mäüt nghéa duy nháút. Xeït mäüt nguäön tin gäöm 4 kyï tæû alphabet, caïc kyï tæû âæåüc maî hoïa bàòng caïc tæì maî nhë phán nhæ sau: A = 0, B = 01, C = 11, D = 00 Nãúu bãn thu nháûn âæåüc daîy tæì maî 0011thç khäng biãút laì bãn phaït truyãön âi DC hay laì AAC. Váûy vê duû trãn khäng thoía tênh giaíi maî duy nháút. b) Giaíi maî tæïc thåìi (instaneous decoding) Báy giåì xeït mäüt nguäön tin khaïc gäöm 4 kyï tæû alphabet, caïc kyï tæû âæåüc maî hoïa bàòng caïc tæì maî nhë phán nhæ sau: A = 0, B = 10, C = 110, D = 111 Maî naìy coï thãø giaíi maî tæïc thåìi duìng cáy maî nhæ trong hçnh 4.3 a, vç khäng coï tæì maî hoaìn thaình naìo laì pháön âáöu (prefix) cuía tæì maî khaïc daìi hån noï. Maî thoía âiãöu kiãûn naìy goüi laì maî coï tênh prefix. Vê duû naìy ngæåüc våïi vê duû træåïc coï A laì pháön âáöu cuía caí B vaì D. Âäi khi maî khäng coï tênh prefix nhæng váùn âaím baío giaíi maî duy nháút, tuy nhiãn luïc naìy khäng thãø giaíi maî tæïc thåìi âæåüc maì phaíi máút thãm thåìi gian âãø xem xeït caïc säú tiãúp theo træåïc khi kãút luáûn chênh xaïc âæåüc âiãøm kãút thuïc cuía tæì maî. Vê duû nhæ nguäön tin sau: A = 0, B = 01, C = 011, D = 111 Ta tháúy nãúu bãn thu nháûn âæåüc säú 0 thç phaíi chåì nháûn thãm säú tiãúp theo. Nãúu säú tiãúp theo laì 0 thç quyãút âënh säú 0 træåïc laì A, nãúu säú tiãúp theo la ì 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 -
13. - 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î. (a) 0 1 A 0 1 B 0 1 C D (b) Doìng bit thu: 0 1 0 0 1 1 1 1 1 0 0 - - - thåìi gian 1000001 1000010 1000001 1000100 Tæì maî: A B A D Begin (c) TÆÌ MAÎ = 0 Âoüc bit tiãúp theo tæì DOÌNG BIT & gàõn thãm vaìo caïc bit âang coï trong TÆÌ MAÎ N TÆÌ MAÎ âaî coï sàôn trong cáy maî ? Y Taíi kyï tæû ASCII vaìo BÄÜ ÂÃÛM THU Âaî xæí lyï táút caí bit trong DOÌNG BIT N Y 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 -
14. - Chæång IV - 4.4 Maî hoïa Huffman Nháûn tháúy xaïc suáút xuáút hiãûn cuía caïc kyï tæû trong nguäön tin laì khäng bàòng nhau, coï nhæîng kyï tæû xuáút hiãûn thæåìng xuyãn hån nhæîng kyï tæû khaïc, nàm 1952, Huffman âaî âæa ra mäüt thuáût toaïn maî hoïa dæûa trãn xaïc suáút xuáút hiãûn cuía caïc kyï tæû. Thuáût toaïn cuía Huffman täúi æu theo nghéa âäü daìi tæì maî trung bçnh laì nhoí nháút. Maî Huffman khäng coï âàûc tênh sæía läùi, nhæng coï tênh giaíi maî duy nháút vaì tæïc thåìi. Sau âáy ta seî xeït hai vê duû, mäüt vê duû vãö maî hoïa Huffman cå såí vaì mäüt vê duû vãö maî hoïa Huffman âäüng. 4.4.1 Maî hoïa Huffman cå såí (basic Huffman encoding) Giaí sæí co ï mäüt säú baín tin âæåüc truyãön giæîa hai maïy tênh qua maûng PSTN. Caïc baín tin chè chæïa caïc kyï tæû tæì A âãún H. Theo kãút quaí thäúng kã cho tháúy xaïc suáút xuáút hiãûn cuía caïc kyï tæû nhæ sau: Kyï tæû A B C D E F G H X.suáút 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04 Entropy cuía nguäön laì: 8 1 H = p(m)log = 2.55 (bit/kyï tæû) ∑ 2 m=1 p(m) Entropy cæûc âaûi cuía nguäön laì: H = log 8 = 3 (bit/kyï tæû) 2 Nhæ váûy hiãûu suáút cuía nguäön laì: 2.55 η = x100 % = 85 % 3 Nãúu mäùi kyï tæû trãn âæåüc maî hoïa thaình 3 bit thç hiãûu suáút maî hoïa seî giæî nguyãn khäng thay âäøi laì 85 %. Maî hoïa Huffman thæûc hiãûn maî hoïa sæí duûng êt bit hån cho caïc kyï tæû coï xaïc suáút xuáút hiãûn cao vç chuïng âæåüc truyãön âi thæåìng xuyãn hån vaì ngæåüc laûi, nhiãöu bit hån cho caïc kyï tæû coï xaïc suáút xuáút hiãûn tháúp nãn coï thãø tàng âæåüc hiãûu suáút. Thuáût toaïn maî hoïa Huffman gäöm caïc bæåïc sau: (1) Sàõp xãúp caïc kyï tæû theo thæï tæû xaïc suáút giaím dáön. (2) Gaïn cho hai kyï tæû coï xaïc suáút xuáút hiãûn tháúp nháút våïi hai nhaïnh (0) vaì (1) cuía cáy maî. Tæì hai kyï tæû co ï xaïc suáút tháúp nháút giaím coìn mäüt kyï tæû våïi xaïc suáút bàòng täøng cuía hai xaïc suáút. (3) Làûp laûi tæì bæåïc (1) cho âãún khi chè coìn laûi mäüt kyï tæû duy nháút våïi xaïc suáút laì 1. (4) Duyãût cáy maî âãø tçm ra tæì maî tæång æïng våïi tæìng kyï tæû cuía nguäön. - 94 -
15. - 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) 1 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) G 0.07 0.09 0.10(1) 0.10(0) E 0.06 0.07(1) 0.09(0) D 0.05(1) 0.06(0) H 0.04(0) 1.0 (b) 0 1 C 0.40 0.60 0 1 0.23 0.37 0 1 0 1 A 0.10 0.13 B 0.18 0.19 0 1 0 1 E 0.06 0.09 G 0.07 F 0.10 0 1 H 0.04 D 0.05 Thæï tæû troüng säú = 0.04 0.05 0.06 0.07 0.09 0.10 0.10 0.13 0.18 0.19 0.23 0.37 0.40 0.60 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 tàng 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 -
16. - Chæång IV - Kyï tæû C B A F G E D H Tæì maî 0 110 100 1111 1011 1010 11101 11100 Âäü daìi tæì maî trung bçnh báy giåì laì: L = 1(0.4) + 3(0.18 + 0.10) + 4(0.10 + 0.07 + 0.06) + 5(0.05 + 0.04) = 2.61(bit/kyï tæû) Váûy âäü låüi maî hoïa laì: H 2.55 η = x100 % = x100 % = 97.7 % L 2.61 Qua vê duû trãn ta tháúy hiãûu suáút 85 % khi khäng maî hoïa âaî tàng lãn âãún 97.7 % khi maî hoïa Huffman. Ta tháúy ràòng phæång phaïp maî hoïa Huffman khäng phaíi chè cho mäüt bäü maî duy nháút, vç ta coï thãø kyï hiãûu báút cæï nhaïnh naìo laì 0 hay 1 chæï khäng bàõt buäüc. Táút nhiãn khi âoï hiãûu suáút maî hoïa seî khäng thay âäøi, nhæng thæï tæû troüng säú cuía caïc nuït seî thay âäøi. Do tæì maî Huffman khaïc nhau âäúi våïi caïc táûp kyï tæû khaïc nhau nãn âãø bãn thu coï thãø giaíi maî âæåüc thç yãu cáöu bãn thu phaíi biãút caïc tæì maî liãn quan âãún dæî liãûu phaït. Coï thãø thæûc hiãûn âiãöu naìy bàòng hai caïch. Hoàûc laì bãn phaït gåíi baíng maî træåïc khi phaït dæî liãûu, hoàûc laì bãn thu phaíi coï sàôn baíng maî. Phæång phaïp âáöu coï æu âiãøm laì coï thãø maî hoïa neïn thêch nghi, vç tæì maî coï thãø thay âäøi cho phuì håüp våïi kiãøu dæî liãûu truyãön, nhæng coï khuyãút âiãøm laì phaíi máút thåìi gian truyãön baíng maî måïi mäùi khi gåíi kiãøu dæî liãûu måïi. 4.4.2 Maî hoïa Huffman âäüng (dynamic Huffman encoding) Khaïc våïi maî hoïa Huffman cå såí, phæång phaïp maî hoïa Huffman âäüng khäng yãu cáöu bãn phaït vaì bãn thu biãút baíng maî liãn quan âãún dæî liãûu phaït, cuîng khäng yãu cáöu kãút quaí thäúng kã xaïc suáút xuáút hiãûn kyï tæû cuía nguäön tin. Phæång phaïp maî hoïa Huffman âäüng cho pheïp caí bãn phaït (ma î hoïa) vaì bãn thu (giaíi maî) láûp cáy maî Huffman - vaì dáùn âãún baíng maî - mäüt caïch âäüng khi kyï tæû âæåüc phaït/ thu. Våïi phæång phaïp naìy, nãúu kyï tæû phaït âang coï màût trong cáy maî thç tæì maî tæång æïng seî âæåüc xaïc âënh giäúng maî Huffman cå såí vaì gåïi âi theo caïch thäng thæåìng. Nãúu kyï tæû chæa coï màût trong cáy maî - nghéa laì xuáút hiãûn láön âáöu, thç noï seî âæåüc gåíi âi theo daûng khäng neïn. Bäü maî hoïa bãn phaït cáûp nháût vaìo cáy maî Huffman bàòng caïch tàng säú láön xuáút hiãûn (tàng troüng säú) cuía kyï tæû phaït hoàûc laì âæa thãm kyï tæû måïi vaìo cáy. Ngoaìi ra, âãø cho bãn thu coï thãø xaïc âënh âæåüc kyï tæû maì noï nháûn, mäùi tæì maî phaït âæåüc maî hoïa theo cuìng caïch cuía bãn thu. Bãn thu tiãún haình caïc thay âäøi giäúng nhæ bãn phaït vaì coï mäüt baíng sao riãng cuía cáy. Nhåì âoï bãn thu seî xaïc âënh âuïng tæì maî tiãúp theo âæåüc nháûn tuyì vaìo cáúu truïc cáy måïi cáûp nháût. Caí bãn phaït vaì bãn thu âãöu bàõt âáöu våïi mäüt cáy maî chè coï mäüt nhaïnh traïi - nhaïnh 0 - vaì mäüt - 96 -
17. - Chæång IV - nuït laï räùng (empty leaf node) - nuït laï coï 0 láön xuáút hiãûn. Âãø mä taí chi tiãút phæång phaïp naìy, ta xeït vê duû baín tin truyãön âi bàõt âáöu bàòng daîy kyï tæû: A B C D C D C . . . Hçnh 4.5 minh hoüa caïc bæåïc láûp cáy maî Huffman. Træåïc tiãn, caí bãn phaït vaì bãn thu cuìng thaình láûp cáy ban âáöu ( mäüt nhaïnh 0 vaì mäüt nuït laï räùng e0). Tiãúp theo, bäü maî hoïa bàõt âáöu âoüc kyï tæû âáöu tiãn trong baín tin - A - vaì gaïn 'A'ï vaìo nhaïnh phaíi- nhaïnh 1 âáöu tiãn. Vç âáy laì láön xuáút hiãûn âáöu tiãn cuía 'A' nãn noï âæåüc truyãön âi khäng neïn (daûng ASCII). Vç cáy bãn giaíi maî âang räùng nãn noï nháûn ra daîy bit nháûn âæåüc laì mäüt kyï tæû khäng neïn vaì no ï sàõp xãúp kyï tæû naìy vaìo trong cáy theo caïch giäúng bãn maî hoïa (hçnh 4.5a). Våïi mäùi kyï tæû tiãúp theo, træåïc hãút bäü maî hoïa kiãøm tra xem kyï tæû âoï âaî coï màût trong cáy maî chæa. Nãúu coï räöi thç bäü maî hoïa seî gåíi tæì maî theo caïch thäng thæåìng giäúng nhæ maî Huffman cå såí, tæì maî âæåüc xaïc âënh båíi vë trê cuía kyï tæû trong cáy. Nãúu chæa coï thç bäü maî hoïa gåíi tæì maî hiãûn haình cho nuït laï räùng - âæåüc xaïc âënh båíi vë trê cuía nuït laï räùng trong cáy, theo sau laì tæì maî khäng neïn cuía kyï tæû. Vç bäü giaíi maî cuîng coï cáy maî y nhæ váûy nãn noï coï thãø suy ra tæì doìng bit nháûn âæåcü âáu laì tæì maî coï neïn, âáu laì nuït laï räùng våïi kyï tæû khäng neïn theo sau. Bäü maî hoïa vaì giaíi maî cáûp nháût vaìo cáy maî dæûa trãn kyï tæû cuäúi cuìng âæåüc phaït/ thu. Nãúu âáy laì kyï tæû måïi thç nuït laï räùng âang täön taûi trong cáy âæåüc thay bàòng mäüt nuït nhaïnh måïi, nuït laï räùng âæåüc gaïn bãn nhaïnh 0 vaì kyï tæû bãn nhaïnh 1 (hçnh 4.5 b). Nãúu kyï tæû âaî coï màût trong cáy thç säú láön xuáút hiãûn cuía nuït laï tæång æïng tàng lãn 1. Vê duû hçnh 4.5 e, bäü maî hoïa kiãøm tra vaì tháúy kyï tæû 'C' âaî coï màût trong cáy maî nãn noï truyãön âi tæì maî tæång æïng laì '01', troüng sä ú cuía nuït C tæì 1 tàng lãn thaình 2. Caïc vê duû tæång tæû khaïc åí trong hçnh 4.5 f vaì g. Luïc naìy, vë trê cuía nuït laï coï thãø khäng coìn laì vë trê täúi æu næîa. Vç váûy, mäùi láön cáûp nháût cáy - tæïc laì thãm kyï tæû måïi hoàûc tàng säú láön xuáút hiãûn cuía kyï tæû sàôn coï - caí bäü maî hoïa vaì giaíi maî âãöu phaíi kiãøm tra vaì nãúu cáön thç phaíi thay âäøi vë trê hiãûn taûi cuía táút caí caïc nuït trong cáy. Âãø âaím baío caí bäü maî hoïa vaì giaíi maî âãöu laìm viãûc naìy theo cuìng mäüt caïch, træåïc hãút caí bäü maî hoïa vaì giaíi maî phaíi liãût kã caïc troüng säú cuía caïc nuït theo chiãöu tæì traïi sang phaíi, tæì dæåïi lãn trãn bàõt âáöu tæì nuït laï räùng. Nãúu thæï tæû sàõp xãúp tàng dáön thç khäng thay âäøi cáy, nãúu khäng âuïng thç phaíi thay âäøi cáúu truïc cuía cáy bàòng caïch thay âäøi vë trê cuía caïc nuït trong cáy. Khi âæa nuït laï âãún vë trê måïi phaíi keìm theo toaìn bäü caïc nhaïnh vaì nuït con cuía chuïng (hçnh 4.5 c âãún 4.5 g). Qua vê duû trãn ta tháúy nãúu truyãön daîy kyï tæû A B C D C D C bàòng maî ASCII thç máút 49 bit, trong khi duìng maî Huffman âäüng thç máút 41 bit. Bàng thäng truyãön dáùn chè âæåüc tiãút kiãûm bàõt âáöu tæì khi coï kyï tæû làûp laûi. Thæûc tãú, caïc file vàn baín luän coï sæû làûp laûi kyï tæû, vaì maî Huffman âäüng âæåüc æïng duûng trong nhiãöu æïng duûng truyãön thäng, nhæ laì neïn dæî liãûu trong modem V.32. - 97 -
18. - Chæång IV - 0 Kyï tæû Phaït e 0 (a) A 'A' 0 1 e 0 A1 (b) B 0 'B' 0 1 1 A1 0 1 e 0 B1 (c) C 0 0 'C' 0 1 2 A1 0 1 1 B1 0 1 e 0 C1 0 1 A1 2 0 1 1 B1 0 1 e 0 C1 (d) D 1 0 0 'D' - 98 -
19. - Chæång IV - (d) D 1 0 0 'D' 0 1 A1 3 0 1 2 B1 0 1 1 C1 0 1 e 0 D1 0 1 2 2 0 1 0 1 1 C1 A1 B1 0 1 e 0 D1 (e) C 01 0 1 2 2 0 1 0 1 1 C2 A1 B1 0 1 e 0 D1 - 99 -
20. - Chæång IV - 0 1 2 3 0 1 0 1 1 B1 A1 C2 0 1 e 0 D1 0 1 (f) D 001 3 3 0 1 0 1 2 B1 A1 C2 0 1 e 0 D2 0 1 2 4 0 1 0 1 1 B1 D2 C2 0 1 e 0 A1 (g) C 11 0 1 2 5 0 1 0 1 1 B1 D2 C3 0 1 e 0 A1 - 100 -
21. - Chæång IV - 0 1 C3 4 0 1 D2 2 0 1 1 B1 0 1 e 0 A1 Hçnh 4.5 Vê duû maî hoïa Huffman âäüng 4.5 Maî hoïa facsimile (fax) Fax laì dëch vuû truyãön caïc taìi liãûu säú âen tràõng, gäöm caïc vàn baín âaïnh maïy, viãút tay, tranh aính, âäö thë, baíng biãøu Trong maïy fax coï maïy queït, queït mäüt trang theo chiãöu doüc våïi âäü phán giaíi laì 3.85 hoàûc 7.7 doìng/ mm vaì 1728 âiãøm aính (pixel) trãn mäùi doìng. Nãúu mäùi pixel âæåüc læåüng tæí hoïa nhë phán thaình bit 0 cho maìu tràõng vaì bit 1 cho maìu âen thç mäüt trang giáúy A4 taûo ra khoaíng 2 triãûu bit. Nãúu truyãön trang A4 khäng neïn qua modem 4.8 kbps thç máút gáön 7 phuït âãø truyãön. Thæûc tãú, trong háöu hãút caïc taìi liãûu, nhiãöu doìng queït chè gäöm toaìn maìu tràng,õ nhiãöu doìng khaïc chæïa caí daîy daìi maìu tràõng vaì daîy daìi maìu âen. Vç maïy fax thæåìng duìng våïi maûng cäng cäüng nãn ITU-T âaî âæa ra caïc chuáøn liãn quan. Âoï laì fax nhoïm 1, nhoïm 2, nhoïm 3 vaì nhoïm 4. Nhoïm 1 vaì nhoïm 2 ngaìy nay ráút êt duìng, nhoïm 3 duìng trong maûng PSTN, nhoïm 4 duìng trong maûng hoaìn toaìn säú ISDN. Caí nhoïm 3 vaì nhoïm 4 âãöu âaût tyí lãû neïn khoaíng 10:1. Do váûy âãø truyãön trang A4 våïi fax nhoïm 3 chè máút chæa âáöy 1 phuït, våïi fax nhoïm 4 do coï âæåìng truyãön täúc âäü cao hån (64kbps) nãn chè máút vaìi giáy. Quaï trçnh maî hoïa træåïc tiãn laì phán têch täøng quaït trang taìi liãûu âæåüc queït. Baíng maî fax âæåüc taûo ra dæûa trãn cå såí vãö táön suáút xuáút hiãûn cuía mäüt säú pixel tràõng vaì âen liãn tuûc (goüi laì run length) trong mäùi doìng queït. Tæì maî ngàõn hån thç âæåüc áún âënh cho caïc run length hay xuáút hiãûn hån vaì ngæåüc laûi. Noïi caïch khaïc, âáy chênh laì maî hoïa Huffman cå såí. Baíng maî fax cäú âënh gäöm hai baíng maî riãng biãût: baíng maî cuäúi (termination-codes table) va ì baíng maî make- up (make-up codes table). Baíng 4.2 laì baíng maî nhoïm 3 vaì nhoïm 4 theo chuáøn ITU-T. Baíng maî cuäúi duìng cho caïc run length tæì 0 âãún 63 pixel, bæåïc nhaíy laì 1 pixel. Baíng maî make-up duìng cho caïc run length tæì 64 âãún 2560 pixel, bæåïc nhaíy laì 64 pixel. Kyî thuáût queït - 101 -
22. - Chæång IV - ngáöm âënh laì táút caí caïc doìng âãöu bàõt âáöu våïi êt nháút laì 1 pixel maìu tràõng. Theo caïch naìy, bãn thu biãút âæåüc tæì maî âáöu tiãn luän luän liãn quan âãún pixel maìu tràõng. (a) Run length tràõng Tæì maî Run length âen Tæì maî 0 00110101 0 0000110111 1 000111 1 010 2 0111 2 11 3 1000 3 10 62 00110011 62 000001100110 63 00110100 63 000001100111 (b) Run length tràõng Tæì maî Run length âen Tæì maî 64 11011 64 0000001111 128 10010 128 000011001000 192 010111 192 000011001001 2560 000000011111 2560 000000011111 EOL 00000000001 EOL 00000000001 Baíng 4.2 Baíng maî Fax nhoïm 3 vaì nhoïm 4 (ITU-T) (a) Baíng maî cuäúi (b) Baíng maî make-up Vê duû mäüt run length gäöm 12 pixel tràõng thç âæåüc maî hoïa træûc tiãúp thaình 001000, mäüt run length gäöm 140 pixel âen thç âæåüc maî hoïa thaình 000011001000 + 0000111, vç 140 pixel = 128 pixel + 12 pixel. Nãúu run length gäöm nhiãöu hån 2560 pixel thç seî âæåüc maî hoïa bàòng caïch duìng nhiãöu maî make - up cäüng våïi mäüt maî cuäúi. Mäüt vê duû khaïc, mäüt doìng queït cuía daîy kyï tæû T I E âæåüc maî hoïa nhæ hçnh 4.6. Fax nhoïm 3 khäng coï thuí tuûc xæí lyï läùi. Nãúu trong quaï trçnh truyãön coï mäüt hoàûc vaìi bit läùi thç bãn thu seî máút âäöng bäü. Âãø cho pheïp bãn thu coï thãø âäöng bäü laûi, mäùi doìng queït luän âæåüc kãút - 102 -
23. - Chæång IV - thuïc bàòng kyï tæû EOL (end-of-line), mäùi trang kãút thuïc bàòng daîy 6 kyï tæû EOL liãn tiãúp. Theo caïch naìy, nãúu bãn thu khäng giaíi maî âæåüc sau mäüt säú bit täúi âa æïng våïi mäüt tæì maî thç noï phaíi tçm EOL. Nãúu sau vaìi doìng queït váùn chæa tçm âæåüc EOL thç bãn thu ngæng giaíi maî vaì thäng baïo cho bãn phaït. Fax nhoïm 4 coï thuí tuûc xæí lyï läùi. Âoï laì thuí tuûc MMR (modified-modifed read) [ 6] 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 cuía maî hoïa fax (Huffman) Hçnh 4.6 Vê duû maî hoïa fax TOÏM TÀÕT CHÆÅNG 1. Læåüng tin laì mäüt âaûi læåüng duìng âãø âaïnh giaï âënh læåüng cho tin tæïc. Læåüng tin liãn quan âãún khaí nàng dæû âoaïn âæåüc cuía tin. Læåüng tin âæåüc tênh laì logarit ám cuía xaïc suáút xuáút hiãûn cuía tin. Nãúu cå säú cuía liogarit laì 2 thç âån vë vuía læåüng tin laì bit. 2. Entropy H cuía nguäön tin laì læåüng tin trung bçnh chæïa trong mäüt kyï tæû báút kyì cuía nguäön tin. Giaï trë låïn nháút cuía entropy âaût âæåüc khi caïc kyï tæû âäüc láûp vaì âäöng xaïc suáút. Entropy cuía mäüt nguäön tin nhë phán âäüc láûp thäúng kã, xaïc suáút xuáút hiãûn cuía säú '1' vaì '0' bàngò nhau laì 1 bit/säú nhë phán. 3. Sæû phuû thuäüc thäúng kã cuía caïc kyï tæû vaì xaïc suáút xuáút hiãûn caïc kyï tæû khäng bàòng nhau laìm cho entropy cuía nguäön nhoí hån entropy cæûc âaûi. Sai khaïc giæîa entropy cæûc âaûi vaì entropy thæûc sæû cuía nguäön laì âäü dæ. 4. Nhiãùu trãn kãnh truyãön laìm cho quyãút âënh taûi bãn thu vãö kyï tæû thu khäng chàõc chàõn âuïng. Vç váûy nhiãùu laìm giaím læåüng tin trong doìng kyï tæû thu. Læåüng tin cuía caïc kyï tæû thu âæåüc goüi laì entropy hiãûu quaí, bàòng entropy phaït træì âi âäü nghi ngåì do nhiãùu. Coï thãø xem nhiãùu nhæ laì tin ám cäüng thãm vaìo doìng kyï tæû phaït. - 103 -
24. - Chæång IV - 5. Täúc âäü thiãút láûp tin cuía nguäön laì mäüt thäng säú phuû thuäüc vaìo tênh cháút váût lyï cuía nguäön. Thäng säú naìy chè ra sæû hçnh thaình tin nhanh hay cháûm âãø âæa vaìo kãnh, âæåüc tênh laì têch cuía entropy våïi säú kyï hiãûu nguäön láûp âæåüc trong mäüt âån vë thåìi gian, âån vë âo laì bit/s. Täúc âäü láûp tin cuía nguäön seî cæûc âaûi khi entropy cuía nguäön cæûc âaûi. 6. Thäng læåüng cuía kãnh laì læåüng tin täúi âa kãnh cho âi qua trong mäüt âån vë thåìi gian maì khäng gáy läùi. Âån vë âo giäúng nhæ âån vë cuía täúc âäü láûp tin (bit/s). Thäng thæåìng täúc âäü láûp tin beï hån nhiãöu so våïi thäng læåüng kãnh. Theo Shannon, 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. 7. Ma î hoïa nguäön tin X bàòng táûp M coï nghéa laì biãún âäøi mäùi tin cuía nguäön tin X thaình mäüt táûp caïc pháön tæí thuäüc M nhàòm thoía maîn mäüt yãu cáöu naìo âoï cuía hãû thäúng thäng tin. Pheïp biãún âäøi ngæåüc laûi âæåüc goüi laì giaíi maî. 8. Caïc tham säú cå baín cuía maî gäöm âäü daìi cuía tæì, maî troüng læåüng tæì maî, khoaíng caïch maî 9. Coï thãø phán loaûi maî theo nhiãöu caïch khaïc nhau, dæûa vaìo âäü daìi cuía tæì maî, troüng læåüng cuía tæì maî, khoaíng caïch maî giæîa hai tæì maî kãö nhau, cå säú cuaí maî, âäü tin cáûy, hiãûu suáút thäng tin 10. Coï nhiãöu phæång phaïp biãøu diãùn maî khaïc nhau: phæång phaïp liãût kã laì phæång phaïp âån giaín nháút, coï æu âiãøm laì roî raìng, cuû thãø nhæng cäöng kãönh, khäng thêch håüp våïi caïc bäü maî låïn; phæång phaïp ma tráûn ruït goün tæì phæång phaïp liãût kã, thêch håüp våïi caïc maî khäúi tuyãún tênh; phæång phaïp cáy giuïp cho viãûc giaíi maî dãù daìng, nhçn vaìo cáy coï thãø biãút âæåüc mäüt säú âàûc âiãøm cuía bäü maî; phæång phaïp âa thæïc thêch håüp våïi caïc maî voìng, giuïp cho viãûc maî hoïa vaì giaíi maî maî voìng dãù daìng bàòng caïch sæí duûng caïc pheïp toaïn âäúi våïi âa thæïc. 11. Maî hoïa nguäön nhàòm loaûi boí âäü dæ trong caïc kyï tæû duìng âãø maî hoïa, laìm cho viãûc truyãön vaì læu træî thäng tin tråí nãn hiãûu quaí hån. Noïi chung thç maî hoïa nguäön phaíi thoía tênh giaíi maî duy nháút. 12. Nguyãn tàõc cuía maî hoïa nguäön råìi raûc laì maî hoïa caïc kyï tæû coï xaïc suáút sinh ra låïn bàòng caïc tæì maî ngàõn vaì maî hoïa caïc kyï tæû coï xaïc suáút sinh ra beï bàòng caïc tæì maî daìi. Loaûi maî naìy goüi laì maî hoaï thäúng kã. 13. Viãûc truyãön tin seî tråí nãn kinh tãú hån nãúu maî thäúng kã coï âäü daìi trung bçnh cuía tæì maî laì nhoí nháút. Loaûi maî nhæ váûy goüi laì maî thäúng kã täúi æu. Âáy cuîng chênh laì maî hoïa neïn. 14. Maî Huffman laì mäüt loaûi maî thäúng kã täúi æu. Maî Huffman âaût âæåüc yãu cáöìu vãö âäü daìi tæì maî trung bçnh nhoí nháút vaì thoaí tênh giaíi maî duy nháút. Thãm vaìo âoï, maî Huffman coìn thoaí tênh giaíi maî tæïc thåìi, nghéa laì khäng coï tæì maî naìo truìng våïi pháön âáöu cuía tæì maî khaïc daìi hån noï. 15. Maî hoïa fax - loaûi maî hoïa duìng trong dëch vu û facsimile - laì mäüt æïng duûng cuía maî hoaï Huffman cå såí. Âáy laì loaûi maî thoaí tênh giaíi maî duy nháút, tæïc thåìi vaì khäng coï täøn hao. Phæång phaïp maî hoïa nguäön cho pheïp âaût nhæîng chè tiãu kinh tãú täút, tuy nhiãn cáön phaíi âaím baío chè tiãu truyãön tin chênh xaïc. Âãø giaíi quyãút váún âãö naìy coï mäüt giaíi phaïp laì maî hoïa kãnh. - 104 -