SHPORA.net :: PDA

[ Back ]

Kodeerimine



* Ruumi kokkuhoiuks (pakkimine, näit. Shannon-Fano, Huffmani ja Ziv-Lempeli koodid)

* Edastusvigade automaatseks parandamiseks (näit. Hammingi koodid)

* Krüptoloogia (salajase ja avaliku võtme krüptograafia, digiallkiri, sõnumilühendid jne.)



Kodeerimisskeem on kujutus, mis seab lähtetekstile vastavusse kodeeritud teksti.



Tähestikupõhine kodeerimisskeem vaatleb lähteteksti sümbolite kaupa ning seab igale sümbolile vastavusse tema koodi.



Kui lähtetekst on koodi põhjal täpselt taastatav, siis nimetatakse seda üheseks kodeerimisskeemiks.



Üheses kodeerimisskeemis kadusid ei esine:



* erinevate sümbolite koodid on erinevad

* kodeeritud tekstis saab koode eristada üheselt (ei leidu kahte erinevat lähteteksti, mis annaksid ühesuguse kodeeritud teksti)



Viimast omadust saab tagada näiteks nn. prefikskoodide abil: ühegi sümboli kood ei ole mingi teise sümboli koodi prefiksis.



Vaatleme edasises juhtu, kus koodi väljendatakse kahendsüsteemis (0-1).

Siis saab kodeerimisskeemi kujutada kahendpuuna, mille lehtedeks on kodeeritavad sümbolid. Iga liikumine vasakusse alampuusse on kodeeritud nulliga, liikumine paremasse alampuusse ühega. Sümboli koodiks on bitijada, mis saadakse liikumisel selle kahendpuu juurest sümbolile vastava leheni.



Eelpool kirjeldatud puud nimetatakse antud sümbolite hulga koodipuuks. Tegemist on prefikskoodiga, sest:



* tee kahendpuu juurest leheni on üheselt määratud,

* mistahes koodi prefiksile vastab koodipuus vahetipp, mitte kunagi leht.



"Tavaline" kodeering on täielik 8-tasemeline kahendpuu (igale sümbolile vastab bitijada pikkusega 8).

Pakkimine



Kokkuhoidu mälumahus saab saavutada näiteks kasutades muutuva pikkusega koode - sagedamini esinevatel sümbolitel on lühike kood, harvaesinevatel pikem. Vajame infot sümbolite esinemissageduse kohta.

Prefikskoodi kasutamisel oleks vaja koodipuu koostada nii, et sagedamini esinevad sümbolid oleksid juurele lähemal, harvemesinevad kaugemal.