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)
2. Kontrola greške (ili odiranje kanala)
3. Kriptografsko kodiranje
4. 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. 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.

Golajov binarni kod razvijen je 1949. godine. 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. 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

Glavni članak: Kompresija podataka

Cilj kodiranja izvora je da se izvorni podaci učiniti manjim.

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

1. $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ je nesingularno ako je injektivno.
2. $C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}$ je jedinstveno dekodivo ako je injektivno.
3. $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. Smatra se da neuroni mogu kodirati digitalne i analogne informacije, i da neuroni slede principe teorije informacija i komprimuju informacije. Oni detektuju i koriguju greške u signalima koji se šalju kroz mozak i širi nervni sistem.

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, , Inc., Pless, Vera (1982). Introduction to the Theory of Error-correcting Codes. New York: John Wiley & Sons. 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. 

Spoljašnje veze

• Explanation of lossless signal compression method used by most codecs
• Interactive blind listening tests of audio codecs over the internet