Sustavi kodiranja: Uvod

Uvod u sustave kodiranja

• Kodiranje se koristi za efikasan prijenos, pohranu i sigurnost podataka.
• Razlikuju se kodiranje, šifriranje i kompresija.
• Kodiranje ima dugu povijest i razne primjene u digitalnim sustavima.

Zašto je kodiranje važno

• Efikasnim se kodiranjem koristi minimalan broj bitova za prikaz informacija.
• Jednoznačno dekodiranje omogućuje rekonstrukciju podataka bez greške.
• Važna je redundantnost za otpornost na pogreške.
• Kodiranje se primjenjuje u pohrani i sigurnosti podataka.

Simboli, abeceda i kodne riječi

• Simboli su osnovni elementi informacija.
• Abeceda je skup mogućih simbola u sustavu kodiranja.
• Kodne riječi su sekvence simbola koje predstavljaju podatke.
• ASCII, Unicode i binarni kod su primjeri abeceda i kodnih riječi.
• ASCII decimalni kod za slovo A je 65, a binarni prikaz 1000001.
• ASCII decimalni kod za slovo B je 66, a binarni prikaz 1000010.
• ASCII decimalni kod za slovo C je 67, a binarni prikaz 1000011.

Kodovi s fiksnom i varijabilnom duljinom

• Kodovi s fiksnom duljinom koriste isti broj bitova za sve simbole.
• Kodovi s varijabilnom duljinom koriste kraće kodne riječi za češće simbole.
• ASCII, Morseov kod i Huffmanovo kodiranje su primjeri kodiranja.
• ASCI kod slova E je 1000101 i ima duljinu 7, dok Morseov kod (.) ima duljinu 1.
• ASCI kod slova T je 1010100 i ima duljinu 7, dok Morseov kod (-) ima duljinu 1.
• ASCI kod slova Q je 1010001 i ima duljinu 7, dok Morseov kod (--.-) ima duljinu 4.
• ASCI kod slova Z je 1011010 i ima duljinu 7, dok Morseov kod (--) ima duljinu 4.

Redundantnost u kodiranju

• Redundantnost se odnosi na višak podataka u kodiranju.
• Uloga redundantnosti se ogleda u omogućavanju detekcije i ispravljanja pogrešaka.
• Prirodni jezici i digitalni kodovi su primjeri redundantnosti.
• Potrebno je balansirati između redundantnosti i učinkovitosti kodiranja.

Primjeri kodiranja - ASCII, Unicode, Base64

• ASCII je osnovni standard kodiranja znakova sa 7-bitnom tablicom.
• Broj znaka u ASCII kodu je 128, duljina kodiranja je 7 bita, a primjenjuje se u engleskom tekstu i osnovama računarstva.
• Unicode je prošireni skup znakova koji podržava više jezika i simbola.
• Broj znaka u Unicode kodu je 1.1 x 10^6, duljina kodiranja je 8, 16, 32 bita, a primjenjuje se u globalnim jezicima, emojijima i matematičkim simbolima.
• Base64 kodiranje služi za prijenos binarnih podataka kroz tekstualne formate.
• Broj znaka u Base64 kodu je 64, duljina kodiranja je 6 bita po simbolu, a primjenjuje se za tekstualni prikaz binarnih podataka.
• ASCII kodiranje znaka A je 65, a binarni prikaz (7-bit) je 1000001.
• Unicode kod za A (U+0041) ima binarni prikaz 01000001 (UTF-8).
• Unicode kod za Č (U+010C) ima binarni prikaz 11000100 10001100 (UTF-8).
• Originalni tekst "ABC" u ASCII kodiranju: 1000001 1000010 1000011, a u Base64 ekvivalentu je QUJD.

Entropija i optimalno kodiranje

• Entropija je mjera nesigurnosti informacije.
• Optimalno kodiranje smanjuje prosječnu duljinu kodne riječi.
• Shannonov teorem definira teorijsku granicu efikasnosti kodiranja.
• Lmin > H, gdje je L prosječna duljina kodiranja, a H entropija izvora
• Huffmanovo kodiranje je primjer binarnog kodiranja.
• Za simbol A (vjerojatnost 50%) fiksni binarni kod (3 bita) je 000, a Huffmanov kod (varijabilna duljina) je 0.
• Za simbol B (vjerojatnost 25%) fiksni binarni kod (3 bita) je 001, a Huffmanov kod (varijabilna duljina) je 10.
• Za simbol C (vjerojatnost 12.5%) fiksni binarni kod (3 bita) je 010, a Huffmanov kod (varijabilna duljina) je 110.
• Za simbol D (vjerojatnost 12.5%) fiksni binarni kod (3 bita) je 011, a Huffmanov kod (varijabilna duljina) je 111.

Shannonov teorem za kodiranje izvora

• Osnovna ideja teorema je granica minimalne duljine kodiranja.
• Izračunata matematička formulacija opisuje prosječnu duljinu kodne riječi.
• H(X) ≤ L ≤ H(X) + 1
• Za A, B, C, D, H(X) = 2.25 bita po simbolu.
• Primjer Huffmanovog koda (varijabilna duljina) je 0, 10, 110, 111.

Ograničenja prijenosa preko bučnih kanala

• Bučni komunikacijski kanal uzrokuje pojavu pogrešaka tijekom prijenosa.
• Šum utječe na kodirane podatke.
• Redundantnost se koristi kao rješenje za smanjenje pogrešaka.
• Shannonov kapacitet kanala definira maksimalnu stopu prijenosa bez pogrešaka.
• Formula za Shannonov kapacitet kanala: C = B log2(1 + S/N).

Klasifikacija kodova

• Jednoznačno dekodirajući kodovi imaju jedinstvenu interpretaciju za svaki niz.
• ASCII decimalni kod za slovo A je 65, a binarni prikaz 1000001.
• ASCII decimalni kod za slovo B je 66, a binarni prikaz 1000010.
• ASCII decimalni kod za slovo C je 67, a binarni prikaz 1000011.

Prefiksni, ekvipotencijalni i kodovi s detekcijom pogrešaka

• Prefiksni kodovi osiguravaju jednoznačno dekodiranje.
• Ekvipotencijalni kodovi minimiziraju redundantnost kodiranja.
• Kodovi s detekcijom pogrešaka omogućuju prepoznavanje prijenosnih grešaka.
• Kodovi se koriste u digitalnim sustavima.
• Primjer Huffmanovog koda za simbol A je 0, za simbol B je 10, za simbol C je 110, a za simbol D je 111.

Huffmanovo kodiranje

• To je specifična tehnika kompresije podataka.
• Koristi se jer su kraći kodovi za češće simbole.
• Implementira se u digitalnim sustavima.

Izgradnja Huffmanovog stabla

• Izračunavanje i dodjeljivanje frekvencija.
• Stvaranje početnih čvorova.
• Kombiniranje najmanjih čvorova.
• Ponavljanje postupka dok ne ostane samo jedan korijenski čvor.
• Dodjeljivanje kodova.
• Dekodiranje Huffmanovih kodova.
• Simbol F ima frekvenciju 45 i Huffmanov kod 0.
• Simbol C ima frekvenciju 12 i Huffmanov kod 100.
• Simbol D ima frekvenciju 13 i Huffmanov kod 101.
• Simbol A ima frekvenciju 5 i Huffmanov kod 1100.
• Simbol B ima frekvenciju 9 i Huffmanov kod 1101.
• Simbol E ima frekvenciju 16 i Huffmanov kod 111.

Efikasnost i ograničenja Huffmanovog kodiranja

• Huffmanovo kodiranje je optimalno kad simboli imaju diskretne i poznate vjerojatnosti pojavljivanja.
• Vjerojatnosti simbola su potencije broja 2.
• Nije optimalan za sve distribucije vjerojatnosti.
• Fiksna tablica kodiranja je problem kod Huffmanovog kodiranja.
• Mali abeceda i fiksnih tablica kodiranja je problem kod Huffmanovog kodiranja.

Razlika između Huffmanovog i aritmetičkog kodiranja

• Huffmanovo kodiranje je diskretno kodiranje sa cijelim brojem bitova po simbolu.
• Aritmetičko kodiranje je kontinuirano kodiranje koje generira jedan decimalni broj.
• Huffmanovo kodiranje koristi cijele bitove, aritmetičko koristi frakcionalne bitove.

Aritmetičko kodiranje

• Omogućuje kompaktniju reprezentaciju podataka od fiksnih kodova, cijela poruka postaje jedan broj između 0 i 1.
• Postupak sužava raspona decimalnih vrijednosti.
• Postiže se manji bitovni prostor za istu količinu informacija.
• Primjeri kodiranja jednostavne poruke (string znakova A-50%, B-30%, C-20%).
• Nova vrijednost znaka za string "A" je=[0.0,0.5].
• Nova vrijednost znaka za string "AB" je=[0.25,0.4].
• Nova vrijednost znaka za string "ABA" je =[0.25,0.325].

Dekodiranje aritmetičkog kodiranja

• Dekodiranje koristi početni broj, bilo koju vrijednost između 0.25 i 0.325.
• Dekodiranje koristi početni raspon i vjerojatnosti za rekonstrukciju niza.
• Dekodiranje postupno pronalazi svakog simbola.
• Dekodiranje uključuje iterativni proces sužavanja raspona.

Prednosti, nedostaci i primjene aritmetičkog kodiranja

• Prednosti su izražene u odnosu na Huffmanovo kodiranje.
• Glavni nedostaci su složenost i preciznost računanja.
• Primjenjuje se u modernim kodecima (H.265, JPEG2000).

Balansiranje redundantnosti i efikasnosti kodiranja

• Redundantnost podrazumijeva višak podataka dodan radi sigurnosti i pouzdanosti prijenosa.
• Više redundantnosti znači veću otpornost na greške, ali i veću veličinu podataka.
• Optimalna razina redundantnosti ovisi o primjeni.
• Kodovi s kontrolom grešaka kompromis su između sigurnosti i efikasnosti.

Redundantno kodiranje za ispravljanje grešaka

• Postoje kodovi s kontrolom grešaka za otkrivanje i ispravljanje pogrešaka.
• Paritetni bitovi su jednostavan način detekcije grešaka.
• Hammingov kod je napredna metoda koja omogućuje ispravljanje pogrešaka.
• Postoje kanalni kodovi i njihova primjena u digitalnim sustavima.

Reed-Solomon kodovi

• Reed-Solomon kodovi se temelji na polinomskim kodovima.
• P(x) = a0 + a1x + a1x^2 + ... + ak-1x^(k-1)
• k objašnjava broj podataka (informacijskih simbola).
• n je ukupni broj simbola (informacijski simboli + kontrolni simboli)
• t = (n-k)/2 je broj pogrešaka koje možemo ispraviti u jednom bloku.
• Ispravljanje višestrukih grešaka u blokovima podataka.
• Koristi se u CD/DVD diskovima, satelitskoj komunikaciji i mrežnim protokolima.
• Nedostatak je povećana redundantnost i složenost dekodiranja.

Low-Density Parity-Check (LDPC) kodovi

• LPDC kodovi koristi rijetke matrice za efikasno kodiranje sa matricnim prikazom.
• HcT = 0
• H – rijetka binarna matrica (s puno nula)
• c – kodni vektor (kodirani podaci)
• 0 – vektor nula koji pokazuje da su podaci ispravno kodirani
• c = uG
• u – ulazni podaci (informacijski vektor)
• G – generacijska matrica koja se dobiva iz H
• LPDC kodovi su efikasni kod za korekciju pogrešaka u bežičnim mrežama i 5G
• Prednosti su visoka otpornost na šum uz minimalnu redundantnost
• Primjenjuju se u Wi-Fi, 5G, satelitskim sustavima i optičkim mrežama

Optimizacija prijenosa podataka

• Kodovi smanjuju veličinu podataka i povećavaju brzinu prijenosa.
• Koriste se za detekciju i ispravljanje pogrešaka.
• Optimiziranje signala za pouzdanu transmisiju.
• Prilagođavanje različitih vrsta kodiranja specifičnim sustavima prijenosa.

Run-Length Encoding (RLE)

• RLE se koristi za kompresiju podataka.
• Smanjuje veličinu kodiranjem uzastopnih ponavljanja znakova.
• Pogodan je slikovnim i tekstualnim formatima (BMP, TIFF, fax, ASCII art).
• Original poruka: AAAAABBBCCDDDDDD -> RLE: 5A3B2C6D.
• RLE nije optimalan za podatke bez ponavljanja znakova.

Manchester kod

• Manchester kod osigurava sinkronizaciju signala.
• U Manchester kodu se svaki bit se prenosi s prijelazom (0 → 1 ili 1 → 0).
• Logička 0 → Prijelaz iz visoke razine (1) u nisku razinu (0) (1 → 0).
• Logička 1 → Prijelaz iz niske razine (0) u visoku razinu (1) (0 → 1).
• IEEE 802.3 (Ethernet) koristi ovu konvenciju.
• Primjer ulaznog binarnog niza (110010)-> kodirani signal (01 01 10 10 01 10).
• Koristi se u Ethernet mrežama i RFID sustavima.
• Olakšava dekodiranje signala u prijenosnim sustavima.

Kodiranje u video i audio kodecima

• Kodiranje u multimediji omogućuje smanjenje veličine datoteka bez gubitka kvalitete.
• MP3 i AAC koriste perceptualno kodiranje zvuka (eliminacija neslušljivih frekvencija).
• H.264 i AV1 pružaju napredne metode kompresije videozapisa.
• Kodiranje osigurava balans između veličine datoteke i kvalitete reprodukcije.

Usporedba video i audio kodeka

• MP3 je audio format koji se koristi u glazbi i na prijenosnim uređajima.
• AAC je audio format koji se koristi u streamingu i mobilnim aplikacijama.
• H.264 je video format koji se koristi u streamingu, digitalnoj TV.
• AV1 je video format budućnosti video stremanja
• MP3, AAC, H.264 i AV1 formati omogucuju prilagodbu kvalitete.

Primjena kodiranja u bazama podataka

• Primjenjuje se u pohrani podataka.
• Komprimirani formati baze (SQLite, MySQL, NoSQL).
• Primjena u distribucijskim sustavima (RAID, erasure coding).
• Hash funkcije osiguravaju integritet podataka.
• Algoritmi optimizaciju pristup podacima.

Kodiranje u obradi prirodnog jezika (NLP)

• Kodiranje teksta u numeričke reprezentacije
• Word embeddings (npr. Word2Vec, GloVe, BERT) važni su modeli kodiranja teksta.
• Kodiranje ima bitnu ulogu u strojnim prevoditeljima i chatbotovima
• Omogućuje se komprimiranje i optimizacija podataka u NLP modelima

Budućnost kodiranja

• Fokus je na kvantnom kodiranju, koje omogućuje ultra-sigurnu enkripciju.
• DNK pohrana nudi ekstremno visoku gustoću podataka.
• Cilj je primjena kvantne komunikacije u sigurnosnim sustavima s mogućnosti pohrane podataka u biološkim sustavima.

Kvantno kodiranje

• U kvantnom kodiranju kvantna stanja (qubit) zamjenjuju klasične bitove.
• Kvantna superpozicija i zapetljanost se primjenjuju za prijenos podataka.
• Quantum Key Distribution (QKD) je neprobojna metoda enkripcije.
• Sustav automatski detektira upad ako napadač pokuša prisluškivati.

DNK pohrana

• Podatci se pohranjuju unutar molekula DNK što omogućava izuzetno veliku gustoća pohrane
• Pretvaranje binarnih podataka (0 i 1) u sekvence DNK baza (A, T, C, G).
• DNK nudi dugoročnu stabilnost podataka - tisuće godina bez degradacije
• DNK se primjenjivani znanstvenim istraživanjima, arhiviranju podataka, bioinformatici

Sažetak

• Kodiranje omogućuje efikasan prijenos, pohranu i sigurnost podataka.
• Moderna kodeci omogućuju kompresiju bez gubitka kvalitete.
• Budućnost kodiranja je u kvantnoj sigurnosti i DNK pohrani podataka.
• Optimizacija duljine kodova i balans između efikasnosti i otpornosti na pogreške.