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]

Pagpapakita sa distansyang Hamming, isang napakahalagang panukat sa teorya ng kodigo.

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

Si Claude Shannon ang itinuturing na nagpasimula sa teorya ng kodigo.

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

Pagpapaliit ng datos

Pangunahing artikulo: Pagpapaliit ng datos
Isang pagkukumpara sa mga larawang JPEG na nai-save ng Adobe Photoshop sa iba't-ibang antas ng kalidad.

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

Pangunahing artikulo: Pagtukoy at pagtama sa error
Isang halimbawa na gumagamit ng kodigong Reed-Solomon upang ayusin ang nasirang ipinadalang larawan ng Mona Lisa dahil sa noise.

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

Pangunahing artikulo: Kriptograpiya
Ang enkripsiyong pampublikong susi (Ingles: public key encryption), isa sa mga pinakamadalas gamiting enkripsiyon sa internet. Si Alice ang nagpapadala, samantalang si Bob ang pinapadalhan.

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

Pangunahing artikulo: Kodigong linya
Pagkokodigo sa isang linya ng impormasyon gamit ang kodigong Manchester.

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

Talababa

  1. ↑ 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

  1. ↑ "Coding Theory" [Teorya ng Kodigo]. Wolfram Math World (sa wikang Ingles). Nakuha noong 25 Mayo 2023.
  2. ↑ 2.0 2.1 Hemmendinger, David. "data compression" [pagpapaliit ng datos]. Britannica (sa wikang Ingles). Nakuha noong 25 Mayo 2023.
  3. ↑ "Error detecting and correcting codes" [Mga kodigong pantukoy at pantama ng error]. University of Michigan (sa wikang Ingles). Nakuha noong 25 Mayo 2023.
  4. ↑ Immink, Kees Schouhamer (Oktubre 1999). "Reed-Solomon codes and the compact disc" [Mga kodigong Reed-Solomon at ang compact disc]. Sa Wicker, Stephen B. (pat.). Reed-Solomon Codes and Their Applications [Mga Kodigong Reed-Solomon at ang kanilang Gamit] (sa wikang Ingles). Wiley IEEE.
  5. ↑ Shannon, Claude; Weaver, Warren (1949). The Mathematical Theory of Communication [Ang Matematikal na Teorya ng Komunikasyon] (PDF) (sa wikang Ingles). University of Illinois Press. ISBN 0-252-72548-4. Inarkibo mula sa orihinal (PDF) noong 15 Hulyo 1998.
  6. ↑ Markowsky, George. "Claude Shannon". Britannica (sa wikang Ingles). Nakuha noong 31 Mayo 2023.
  7. ↑ Tse, David (22 Disyembre 2020). "How Claude Shannon Invented the Future" [Paano Inimbento ni Claude Shannon ang Hinaharap]. Quanta Magazine (sa wikang Ingles). Nakuha noong 31 Mayo 2023.
  8. ↑ Golay, Marcel J. E. (1949). "Notes on Digital Coding" [Mga Notes sa Digital na Pagkokodigo] (PDF). Proc. IRE (sa wikang Ingles). 37: 657. Inarkibo mula sa orihinal (PDF) noong 2023-05-14. Nakuha noong 2023-06-11.
  9. ↑ Pegg Jr., Ed; Terr, David; Weisstein, Eric W. "Golay code" [Kodigong Golay]. Wolfram Mathworld (sa wikang Ingles). Nakuha noong 31 Mayo 2023.
  10. ↑ Robertson, Edmund F. "Richard W. Hamming". ACM Turing Award (sa wikang Ingles). Nakuha noong 9 Hunyo 2023.
  11. ↑ 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 wikang Ingles). 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
  12. ↑ 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.
  13. ↑ "Lossy vs Lossless Compression Differences and When to Use" [Mga Pagkakaiba ng Pagpapaliit na Lossy vs. Lossless at Kailan Dapat Itong Gamitin]. Adobe (sa wikang Ingles). Nakuha noong 9 Hunyo 2023.
  14. ↑ Rivest, Ronald L. (1990). "Cryptography". Sa J. Van Leeuwen (pat.). Handbook of Theoretical Computer Science [Handbook ng Teoretikal na Agham Pangkompyuter] (sa wikang Ingles). Bol. 1. Elsevier.
  15. ↑ Goldwasser, Shafi; Kalai, Yael Tauman (19 Disyembre 2015). "Cryptographic Assumptions: A Position Paper". Lecture Notes in Computer Science (conference paper) (sa wikang Ingles). Nakuha noong 10 Hunyo 2023.
  16. ↑ "Difference between Unipolar, Polar and Bipolar Line Coding Schemes" [Pagkakaiba ng Unipolar, Polar, at Bipolar na Iskema ng Kodigong Linya]. Geeks for Geeks (sa wikang Ingles). Nakuha noong 11 Hunyo 2023.