Tag Archives: even-rodeh

IT

Even-Rodeh kodas

Data EncodingS. Even ir M. Rodeh sugalvotas kodas remiasi panašiu principu kaip ir Elijaus omega kodas. Pagrindinis skirtumas yra tas, kad Even-Rodeh kodavime simbolio ilgis yra pridedami iš kairės iki tol, kol simbolio ilgio užrašymui pakanka trijų bitų. Pavyzdžiui skaičiaus 2761 Even-Rodeh kodas būtų 100|1100|101011001001|0.

Šio kodo ilgis \(\) tenkina sąlygą \(\). Kur \(\) yra n dvejetainio atitikmens (beta kodo) ilgis. Sužinoti tikslų kodo ilgi duotajam \(\) galima pasinaudojus formule \(\), kol \(\) reikšmę galima užrašyti trimis bitais dvejetainėje sistemoje.

Turint simbolių eilutę \(\), prieš kiekvieną \(\) simbolį reikia pridėti Even-Rodeh kodą R su ilgiu \(\). Tuomet visus simbolius galima sujungti į eilutę \(\). Tokioje sukonstruotoje eilutėje kiekvienas simbolis gali būti nesunkiai atskiriamas, nes kodai veikia kaip tarpai, t.y. pakeičia kablelius, o 000 žymi eilutės pabaigą.

Even-Rodeh kodų ilgis asimptotiškai mažėja į nulį. Pavyzdžiui, eilutėms, kurių ilgis \(\) bitų, kodo priešdėlis tesudaro 2 proc. ilgio.

Reikšmė Even-Rodeh ilgis
1 3
2-3 3
4-7 4
8-15 8
16-31 9
32-63 10
64-127 11
128-255 17
256-512 18

Pavyzdys:

Turime užkoduotą eilutę \(\)

Nuskaitome pirmus tris bitus eilutėje - 100, jų reikšmė dešimtainėje sistemoje yra 4. Nuskaitę sekančius 4 bitus gauname 1100, o tai yra 12. Skaitome toliau, dabar jau 12 bitų. 101011001001 dešimtainėje sistemoje yra 2761. Toliau dekodavimui turėsime nuskaityti 2761 bitus, tačiau nuskaitę pirmąjį gauname 0. Jeigu pirmas nuskaitytas bitas yra 0, jį suprantame kaip kablelį, o prieš tai buvusi reikšmė - užkoduotas skaičiukas. Šiuo atveju tai yra 2761. Toliau tęsiame vėl skaitydami tris bitus. 111 reiškia, kad turėsime skaityti 7 sekančius bitus, bet pirmasis iš jų yra 0, tad užkoduotas skaičius - 7. Sekantys trys bitai yra 000, o tai reiškią eilutės pabaigą.

Literatūra:

Fenwick P. Variable-Length Integer Codes Based on the Goldbach Conjecture, and Other Additive Codes. IEEE Trans. Inform. Theory, 48(8), 2002.
David Salomon, Giovanni Motta. Handbook of Data Compression. Springer, 2010.
Khalid Sayood. Lossless Compression Handbook. Academic Press, 2002.