Teorija 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.

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

Postoje četiri vrste kodiranja:^[1]

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 .^[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 , i .

Kodiranje izvora

Glavni članak: Kompresija podataka

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

Definicija

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

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

Kod je funkcija

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

${\displaystyle C(x)}$ je kodna reč asocirana sa ${\displaystyle x}$.

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

${\displaystyle l(C(x))}$.

Očekivana dužina koda je

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

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

Kodna reč praznog niza je sam prazni niz:

${\displaystyle C(\epsilon )=\epsilon }$

Svojstva

1. ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ je nesingularno ako je injektivno.
2. ${\displaystyle C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}}$ je jedinstveno dekodivo ako je injektivno.
3. ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ je trenutno ako ${\displaystyle C(x_{1})}$ nije prefix od ${\displaystyle 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.