Teorya ng kodigo
Teorya ng kodigo (Ingles: coding theory) ang pag-aaral sa mga katangian ng kodigo at ang silbi nito sa ilang partikular na mga gawain. Ginagamit ang mga kodigo sa pagpapaliit ng datos, kriptograpiya, pagtukoy at pagtama sa error, pagpapadala ng datos, at pagtatabi ng datos. Pinag-aaralan sa maraming magkakaugnay na larangan ang mga kodigo, tulad halimbawa sa teorya ng impormasyon, inhinyerang elektrikal, matematika, lingwistika, at agham pangkompyuter, upang makadisenyo ng mga mas magaganda, mabibilis, at maaasahang paraan sa pagpapadala ng datos. Kadalasan, nagagawa ito sa pamamagitan ng pagtatanggal sa mga paulit-ulit o hindi kailangan na mga datos at pagtatama at pagtutukoy sa mga error sa naipadalang datos.[1]
Nahahati sa apat ang pagkokodigo: pagpapaliit ng datos (o pagkokodigo sa pinagmulan), pagkontrol sa error (o pagkokodigo sa daanan), kriptograpiya, at pagkokodigo sa linya. Layunin ng pagpapaliit ng datos na matanggal ang mga hindi kailangan o paulit-ulit na mga datos mula sa pinagmulan upang mabilis itong maipadala sa patutunguhan nito. Halimbawa, pinapaliit ng algoritmong ZIP ang mga file upang maipadala ito sa internet nang mabilis.[2] Samantala, layunin naman ng pagtatama sa error na magamit ang mga paulit-ulit na datos upang masiguro ang mas matibay at di magagambalang pagdaan ng datos sa isang daanan.[3] Halimbawa, ginagamit sa mga compact disc ang kodigong Reed-Solomon upang maitama ang mga nawalang o nagulong datos mula sa pagkiskis o dumi.[4]
Kasaysayan[baguhin | baguhin ang wikitext]
Si Claude Shannon ang itinuturing na nagpasimula sa teorya ng kodigo nang inilathala niya noong 1948 ang "A Mathematical Theory of Information"[a] sa dalawang magkahiwalay na bahagi sa isyu ng Hulyo at Oktubre ng Bell System Technical Journal. Dito niya inilatag ang mga ideya niya patungkol sa pinakamagandang paraan para maisakodigo ang impormasyon na gustong ipadala. Dinebelop ni Shannon ang entropiya ng impormasyon bilang panukat sa pagiging hindi tiyak ng isang mensahe, na nagbigay-daan naman sa pagkabuo sa larangan ng teorya ng impormasyon.[6][7]
Noong 1949, nadebelop ni Marcel Golay ang dalawahang kodigong Golay, isang kodigong pangtama ng error na kayang itama ang hanggang tatlong error sa bawat 24-bit na word, gayundin ang pagtukoy sa pang-apat.[8][9]
Nanalo naman si Richard Hamming ng Gawad Turing noong 1968 para sa mga ginawa niya sa Bell Labs tulad ng mga paraang numerikal, mga awtomatikong sistemang pangkodigo, at mga kodigo sa pagtukoy at pagtama sa mga error.[10]
Noong 1972, iminungkahi ni Nasir Ahmed ang konsepto ng discrete cosine transform (DCT), na kalauna'y ginawa niya rin noong 1973 kasama ang kanyang mga doktoral na estudyante at ang kaibigang niyang K.R. Rao sa Pamantasan ng Texas sa Arlington.[11] Ito ang pinakaginagamit na algoritmo para sa pagpapaliit na lossy, at ang basehan para sa mga format tulad ng JPEG.[12]
Disiplina[baguhin | baguhin ang wikitext]
Pagpapaliit ng datos[baguhin | baguhin ang wikitext]
Isa sa apat na disiplinang pinag-aaralan sa ilalim ng teorya ng kodigo ang pagpapaliit ng datos (Ingles: data compression) o pagkokodigo sa pinagmulan (Ingles: source coding). Layunin nito na paliitin ang inookupang datos ng isang bagay; halimbawa ay ang pagpapaliit sa mga masyadong malilinaw na larawan sa mga kompyuter upang makatipid ng espasyo.[2] Nagiging posible ito dahil sa mga algoritmong naghahanap ng mga pwedeng tanggalin na mga nauulit na datos. May dalawang paraan ang pwedeng gawin para dito: lossless (lit. na 'walang nawawala') at lossy (lit. na 'may nawawala').[13]
Pagtukoy at pagtama sa error[baguhin | baguhin ang wikitext]
Layunin ng pagtukoy at pagtama sa error (Ingles: error detection and correction, EDAC), o pagkokodigo sa daanan (Ingles: channel coding), na masiguro na maipapadala ang impormasyon mula sa nagpadala nito papunta sa pinadalhan nito nang kumpleto at maayos. Ginagamit ito sa pagpapadala ng datos, tulad halimbawa ng sa internet. Hindi maasahan salahat ng pagkakataon ang mga daanan ng impormasyon, kaya naman ginawa ang ilang mga algoritmo para rito, tulad halimbawa ng kodigong Hamming at Reed-Solomon. Inuulit ng mga algoritmo angnilang bahagi ng impormasyon upang masiguro na makakarating ito sa papadalhan kahit na magkaproblema ito sa daan. Halimbawa, ginagamit sa mga CD ang kodigong Reed-Solomon upang ayusin ang mga datos na nawala o nasira dahil sa mga pagkiskis.
Kriptograpiya[baguhin | baguhin ang wikitext]
Kriptograpiya ang pag-aaral sa mga paraan upang maitago ang isang impormasyon at masiguro ang seguridad ng komunikasyon sa pagitan ng nagpapadala at pinapadalhan nito.[14] Bagamat matagal na ang pag-aaral na ito, ginagamit na ngayon sa modernong kriptograpiya ang mga kompyuter upang gawin ang mga paraang hindi makokompyut nang mano-mano ng sinumang tao. Nakasalalay ang mga paraang ito sa ideya ng pagpapalagay sa kahirapang makompyut. Gayunpaman, hindi nito ginagarantiya na hindi ito mabubuksan. Dahil sa pagbilis ng pag-abante ng teknolohiya tulad ng mga superkompyuter, kinakailangan pa ring ma-update ang mga paraang ito upang manatiling hindi ito makokompyut nang maayos at mabilis.[15]
Kodigong linya[baguhin | baguhin ang wikitext]
Kodigong linya (Ingles: line code) ang tawag sa boltahe, daloy, o mga photon na ginagamit para kumatawan sa ipinapadalang digital na datos sa isang daanan ng komunikasyon o di kaya'y isinusulat sa isang taguan ng datos. Ginagawa nitong digital na signal ang mga datos na nasa anyong dalawahan (Ingles: binary) upang makadaan ito sa mga linya ng pagpapadala, tulad halimbawa ng mga broadband.[16]
Tingnan din[baguhin | baguhin ang wikitext]
Talababa[baguhin | baguhin ang wikitext]
- ↑ Sa wikang Filipino, "Isang Teoryang Matematikal ng Impormasyon". Pinalitan niya ang pamagat nito sa mga sumunod na paglalathala bilang "The Mathematical Theory of Information" ("Ang Teoryang Matematikal ng Impormasyon") matapos niyang mapagtanto ang kahalagahan ng kanyang gawa.[5]
Sanggunian[baguhin | baguhin ang wikitext]
- ↑ "Coding Theory" [Teorya ng Kodigo]. Wolfram Math World (sa Ingles). Nakuha noong 25 Mayo 2023.
- ↑ 2.0 2.1 Hemmendinger, David. "data compression" [pagpapaliit ng datos]. Britannica (sa Ingles). Nakuha noong 25 Mayo 2023.
- ↑ "Error detecting and correcting codes" [Mga kodigong pantukoy at pantama ng error]. University of Michigan (sa Ingles). Nakuha noong 25 Mayo 2023.
- ↑ Immink, Kees Schouhamer (Oktubre 1999). "Reed-Solomon codes and the compact disc" [Mga kodigong Reed-Solomon at ang compact disc]. In Wicker, Stephen B. (pat.). Reed-Solomon Codes and Their Applications [Mga Kodigong Reed-Solomon at ang kanilang Gamit] (sa Ingles). Wiley IEEE.
- ↑ Shannon, Claude; Weaver, Warren (1949). The Mathematical Theory of Communication [Ang Matematikal na Teorya ng Komunikasyon] (PDF) (sa Ingles). University of Illinois Press. ISBN 0-252-72548-4. Inarkibo mula sa ang orihinal (PDF) noong 15 Hulyo 1998.
- ↑ Markowsky, George. "Claude Shannon". Britannica (sa Ingles). Nakuha noong 31 Mayo 2023.
- ↑ Tse, David (22 Disyembre 2020). "How Claude Shannon Invented the Future" [Paano Inimbento ni Claude Shannon ang Hinaharap]. Quanta Magazine (sa Ingles). Nakuha noong 31 Mayo 2023.
- ↑ Golay, Marcel J. E. (1949). "Notes on Digital Coding" [Mga Notes sa Digital na Pagkokodigo] (PDF). Proc. IRE (sa Ingles). 37: 657. Inarkibo mula sa ang orihinal (PDF) noong 2023-05-14. Nakuha noong 2023-06-11.
- ↑ Pegg Jr., Ed; Terr, David; Weisstein, Eric W. "Golay code" [Kodigong Golay]. Wolfram Mathworld (sa Ingles). Nakuha noong 31 Mayo 2023.
- ↑ Robertson, Edmund F. "Richard W. Hamming". ACM Turing Award (sa Ingles). Nakuha noong 9 Hunyo 2023.
- ↑ Ahmed, Nasir (Enero 1991). "How I Came Up With the Discrete Cosine Transform" [Paano Pumasok sa Isip Ko ang Discrete Cosine Transform]. Digital Signal Processing (sa Ingles). 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
- ↑ Cabeen, Ken; Gent, Peter. "Image Compression and the Discrete Cosine Transform" [Pagpapaliit sa Larawan at ang Discrete Cosine Transform] (PDF). Chinese University of Hong Kong. Nakuha noong 9 Hunyo 2023.
- ↑ "Lossy vs Lossless Compression Differences and When to Use" [Mga Pagkakaiba ng Pagpapaliit na Lossy vs. Lossless at Kailan Dapat Itong Gamitin]. Adobe (sa Ingles). Nakuha noong 9 Hunyo 2023.
- ↑ Rivest, Ronald L. (1990). "Cryptography". In J. Van Leeuwen (pat.). Handbook of Theoretical Computer Science [Handbook ng Teoretikal na Agham Pangkompyuter] (sa Ingles). Bol. 1. Elsevier.
- ↑ Goldwasser, Shafi; Kalai, Yael Tauman (19 Disyembre 2015). "Cryptographic Assumptions: A Position Paper". Lecture Notes in Computer Science (conference paper) (sa Ingles). Nakuha noong 10 Hunyo 2023.
- ↑ "Difference between Unipolar, Polar and Bipolar Line Coding Schemes" [Pagkakaiba ng Unipolar, Polar, at Bipolar na Iskema ng Kodigong Linya]. Geeks for Geeks (sa Ingles). Nakuha noong 11 Hunyo 2023.