Teorija kodiranja

Dvodimenzionalna vizualizacija Hamingovog rastojanja, kritične mere u teoriji kodiranja.

Teorija kodiranja je studija koja proučava svojstva kodova i njihovu prikladnost za specifične primene. Kodovi se koriste za kompresiju podataka, kriptografiju, otkrivanje i ispravljanje grešaka, prenos podataka i skladištenje podataka. Kodovi se proučavaju u različitim naučnim disciplinama - poput teorije informacija, elektrotehnike, matematike, lingvistike i računarske nauke - u svrhu dizajniranja efikasnih i pouzdanih metoda prenosa podataka. To obično uključuje uklanjanje suvišnih vrednosti i ispravljanje ili otkrivanje grešaka u prenešenim podacima.

Postoje četiri vrste kodiranja:^[1]

Kompresija podataka (ili, kodiranje izvora)
Kontrola greške (ili odiranje kanala)
Kriptografsko kodiranje
Linijsko kodiranje

Kompresija podataka pokušava da ukloni suvišnost podataka iz nekog izvora kako bi se što efikasnije prenosili. Na primer, Zip komprimovanje podataka čini datoteke podataka manjim u svrhe poput smanjenja internetskog prometa. Kompresija podataka i ispravljanje grešaka mogu se proučavati u kombinaciji.

Ispravljanje grešaka dodaje ekstra bitove kako bi prenos podataka bio robusniji na smetnje koje nastaju na kanalu prenosa. Obični korisnik možda nije svestan mnogih vidova primene u kojima se koristi korekcija grešaka. Tipični muzički CD koristi Rid-Solomonov kod za korigovanja impakta ogrebotina i prašine. U ovoj aplikaciji kanal prenosa je sam CD. Mobilni telefoni takođe koriste tehnike kodiranja za korekciju slabljenja i buke prenosa visokih frekvencija. Modemi podataka, telefonski prenosi i Mreža dubokog svemira agencije NASA, svi koriste tehnike kodiranja kanala kako bi prenosili bitove, na primer turbo kod i LDPC kodove.

Istorija teorije kodiranja

Godine 1948. Klod Šanon je objavio „Matematičku teoriju komunikacija”, članak u dva dela u julskom i oktobarskom broju tehničkog časopisa Bell Sistem.^[2]^[3]^[4]^[5] Ovaj rad se fokusira na problem najboljeg kodiranja informacije koje pošiljalac želi da prenese. U ovom fundamentalnom radu on je koristio alate teorije verovatnoće, koje je razvio Norbert Viner, a koji su u to vreme bili u počenim stupnjevima primene u teoriji komunikacije. Šanon je razvio informacionu entropiju kao meru neizvesnosti u poruci, čime je esencijalno začeo polje teorije informacija.^[6]

Golajov binarni kod razvijen je 1949. godine.^[7]^[8] To je kod za ispravljanje grešaka kojim se mogu ispraviti do tri greške u svakoj 24-bitnoj reči i detektovati četvrta. Ričard Heming je osvojio Tjuringovu nagradu 1968. godine za svoj rad u Belovim laboratorijma na numeričkim metodama, sistemima automatskog kodiranja i kodovima za detektovanje i korigovanje grešaka. On je izumeo koncepte poznate kao Hemingovi kodovi, Hemingovi prozori, Hemingovi brojevi i Hemingovo rastojanje.

Nasir Ahmed je 1972. godine predložio diskretnu kosinusnu transformaciju (DCT), koju je razvio sa T. Natarajanom i K. R. Raom 1973. godine.^[9] DCT je najčešće korišten algoritam kompresije s gubitkom, i osnova za multimedijske formate kao što su JPEG, MPEG i MP3.

Kodiranje izvora

Cilj kodiranja izvora je da se izvorni podaci učiniti manjim.^[10]^[11]

Definicija

Podaci se mogu videti kao randomne promenljive $X:\Omega \rightarrow {\mathcal {X}}$ , gde se $x\in {\mathcal {X}}$ javlja sa verovatnoćom $\mathbb {P} [X=x]$ .

Podaci se kodiraju nizovima (rečima) preko abecede $\Sigma$ .

Kod je funkcija

$C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ (ili $\Sigma ^{+}$ ako prazan niz nije deo alfabeta).

$C(x)$ je kodna reč asocirana sa $x$ .

Dužina kodne reči se piše kao

$l(C(x))$ .

Očekivana dužina koda je

$l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]$

Spajanjem kodnih reči se dobija $C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})$ .

Kodna reč praznog niza je sam prazni niz:

$C(\epsilon )=\epsilon$

Svojstva

$C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ je nesingularno ako je injektivno.
$C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}$ je jedinstveno dekodivo ako je injektivno.
$C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ je trenutno ako $C(x_{1})$ nije prefix od $C(x_{2})$ (i suprotno).

Princip

Entropija izvora je mera informacija. U osnovi, izvorni kod pokušava da smanji suvišnost koja postoji u izvoru, i da predstavi izvor s manjim brojem bitova koji sadrže više informacija.

Kompresija podataka koja izričito pokušava da minimizuje prosečnu dužinu poruka prema određenom pretpostavljenom modelu verovatnoće naziva se entropijsko kodiranje.

Različite tehnike koje koriste sheme kodiranja izvora pokušavaju da ostvare granicu entropije izvora. C(x) ≥ H(x), gde je H(x) entropija izvora (bit-stopa), a C(x) je bit-stopa nakon kompresije. Konkretno, nijedna šema kodiranja izvora ne može nadmašiti entropiju izvora.

Primer

Faks transmisija koristi jednostavno kodiranje dužine izvođenja. Kodiranje izvora uklanja sve suvišne podatke prema potrebama predajnika, smanjujući opseg neophodan za prenos.

Neuralno kodiranje

Neuralno kodiranje je polje povezano sa neuronaukom koje se bavi načinom na koji su senzorne i druge informacije u mozgu predstavljene mrežama neurona. Glavni cilj proučavanja neuronskog kodiranja je karakterizacija odnosa između stimulusa i pojedinca ili odgovora neurona i odnosa između električne aktivnosti neurona u celini.^[12] Smatra se da neuroni mogu kodirati digitalne i analogne informacije,^[13] i da neuroni slede principe teorije informacija i komprimuju informacije.^[14] Oni detektuju i koriguju greške^[15] u signalima koji se šalju kroz mozak i širi nervni sistem.

Reference

^ James Irvine; David Harle (2002). „2.4.4 Types of Coding”. Data Communications and Networks. John Wiley & Sons. стр. 18. ISBN 9780471808725. „There are four types of coding”
^ Shannon, Claude Elwood (jul 1948). „A Mathematical Theory of Communication” (PDF). Bell System Technical Journal. 27 (3): 379—423. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2. Архивирано из оригинала (PDF) 15. 7. 1998. г. „The choice of a logarithmic base corresponds to the choice of a unit for measuring information. If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey.”
^ Shannon, Claude Elwood (oktobar 1948). „A Mathematical Theory of Communication”. Bell System Technical Journal. 27 (4): 623—666. doi:10.1002/j.1538-7305.1948.tb00917.x. hdl:11858/00-001M-0000-002C-4314-2.
^ Robert B. Ash. Information Theory. New York: Interscience, 1965. ISBN 0-470-03445-9. New York: Dover 1990. ISBN 0-486-66521-6. стр. v.
^ Yeung, R. W. (2008). „The Science of Information”. Information Theory and Network Coding. стр. 1—01. ISBN 978-0-387-79233-0. doi:10.1007/978-0-387-79234-7_1.
^ Shannon, Claude Elwood; Weaver, Warren (1949). A Mathematical Theory of Communication (PDF). University of Illinois Press. ISBN 0-252-72548-4. Архивирано из оригинала (PDF) 15. 7. 1998. г.
^ Golay, Marcel J. E. (1949). „Notes on Digital Coding”. Proc. IRE. 37: 657.
^ Berlekamp, E.R. (1974), Key Papers in the Development of Coding Theory, I.E.E.E. Press, стр. 4
^ Nasir Ahmed. „How I Came Up With the Discrete Cosine Transform”. Digital Signal Processing, Vol. 1, Iss. 1, 1991. стр. 4—5.
^ Mahdi, O.A.; Mohammed, M.A.; Mohamed, A.J. (novembar 2012). „Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique” (PDF). International Journal of Computer Science Issues. 9 (6, No. 3): 53—59. Архивирано из оригинала (PDF) 28. 12. 2018. г. Приступљено 6. 3. 2013.
^ Wade, Graham (1994). Signal coding and processing (2 изд.). Cambridge University Press. стр. 34. ISBN 978-0-521-42336-6. Приступљено 22. 12. 2011. „The broad objective of source coding is to exploit or remove 'inefficient' redundancy in the PCM source and thereby achieve a reduction in the overall source rate R.”
^ Brown EN, Kass RE, Mitra PP (maj 2004). „Multiple neural spike train data analysis: state-of-the-art and future challenges”. Nat. Neurosci. 7 (5): 456—61. PMID 15114358. S2CID 562815. doi:10.1038/nn1228.
^ Thorpe, S.J. (1990). „Spike arrival times: A highly efficient coding scheme for neural networks” (PDF). Ур.: Eckmiller, R.; Hartmann, G.; Hauske, G. Parallel processing in neural systems and computers (PDF). North-Holland. стр. 91—94. ISBN 978-0-444-88390-2. Приступљено 30. 6. 2013.
^ Gedeon, T.; Parker, A.E.; Dimitrov, A.G. (proleće 2002). „Information Distortion and Neural Coding”. Canadian Applied Mathematics Quarterly. 10 (1): 10. CiteSeerX 10.1.1.5.6365 . Архивирано из оригинала 17. 11. 2016. г. Приступљено 02. 09. 2019.
^ Stiber, M. (jul 2005). „Spike timing precision and neural error correction: local behavior”. Neural Computation. 17 (7): 1577—1601. PMID 15901408. S2CID 2064645. arXiv:q-bio/0501021 . doi:10.1162/0899766053723069.

Literatura

Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), Berlekamp, Elwyn R. (2015). Algebraic Coding Theory. World Scientific. ISBN 978-9-81463-589-9. .
MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. MacKay, David J. C. (25. 9. 2003). Information Theory, Inference and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. CS1 одржавање: Формат датума (веза)
Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., Pless, Vera (1982). Introduction to the Theory of Error-correcting Codes. Wiley. ISBN 0-471-08684-3. .
Randy Yates, A Coding Theory Tutorial.
Schroeder, Manfred R. (2014). „Bell Laboratories”. Acoustics, Information, and Communication: Memorial Volume in Honor of Manfred R. Schroeder. Springer. стр. 388. ISBN 9783319056609.
Gray, Robert M. (2010). „A History of Realtime Digital Speech on Packet Networks: Part II of Linear Predictive Coding and the Internet Protocol” (PDF). Found. Trends Signal Process. 3 (4): 203—303. ISSN 1932-8346. doi:10.1561/2000000036.
Ghanbari, Mohammed (2003). Standard Codecs: Image Compression to Advanced Video Coding. Institution of Engineering and Technology. стр. 1—2. ISBN 9780852967102.
Wade, Graham (1994). Signal coding and processing (2 изд.). Cambridge University Press. стр. 34. ISBN 978-0-521-42336-6. Приступљено 22. 12. 2011. „The broad objective of source coding is to exploit or remove 'inefficient' redundancy in the PCM source and thereby achieve a reduction in the overall source rate R.”
Salomon, David (2008). A Concise Introduction to Data Compression. Berlin: Springer. ISBN 9781848000728.
S. Mittal; J. Vetter (2015), „A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems”, IEEE Transactions on Parallel and Distributed Systems, IEEE, 27 (5): 1524—1536, S2CID 11706516, doi:10.1109/TPDS.2015.2435788
Tank, M.K. (2011). „Implementation of Lempel-ZIV algorithm for lossless compression using VHDL”. Thinkquest~2010. Thinkquest 2010: Proceedings of the First International Conference on Contours of Computing Technology. Berlin: Springer. стр. 275—283. ISBN 978-81-8489-988-7. doi:10.1007/978-81-8489-989-4_51.