Bài giảng Kỹ thuật thông tin số: Chương 4 - Mã hóa nguồn

"Bài giảng Kỹ thuật thông tin số: Chương 4 - Mã hóa nguồn" được biên soạn giúp các bạn hiểu rõ hơn về cơ sở lý thuyết của mã hóa nguồn, các mục đích và định dạng của mã hóa. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật thông tin số: Chương 4 - Mã hóa nguồn - 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 - - 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 = − log p(i) p(i) - 82 - - Chæång IV - Âån vë âo cuía læåüng tin tuyì thuäüc vaìo cå säú cuía loga. Âån vë cuía læåüng tin laì bit, laì nat hay laì hartley khi cå säú cuía loga láön læåüt laì 2, laì e hay laì 10. Trong âoï ...