Tag Archives: duomenu kodavimas

IT

Goldbach kodai (G0, G1, G2)

Goldbach kodas

Matematikai jau senai žinojo, kad dviejų pirminių skaičių suma yra lyginis skaičius. Tačiau tik 1742 metais, vokiečių matetikui Christian Goldbach kilo klausimas - Jeigu dviejų pirminių skaičių suma yra lyginis skaičius, ar tiesa, kad kiekvienas lyginis skaičius yra dviejų pirminių skaičių suma? Kitaip tariant, Goldbach spėjimas (problema) sako:

Kiekvienas lyginis skaičius, didesnis už 2, yra dviejų pirminių skaičių suma.

Šiuo metu spėjimas yra patvirtintas skaičiams iki maždaug \(\), tačiau kolkas nėra įrodymų, kad tai galioja visiems skaičiams.

Idėja panaudoti Goldbach spėjimą koduoti informacijai kilo Peter Fenwick. Jis panaudojo pirminius skaičius kaip skaičiavimo sistema. O kiekvienas lyginis skaičius užkoduotas dviejų pirminių skaičių suma, dvejetainėje formoje turės tik du vienetus. Kad būtų galima atskirti kiekvieną užkoduotą skaičių iš eilutės, dvejetainė jo forma užrašoma iš kito galo. Tai galima vadinti vienetaine sistema.

G0

Pirmasis Goldbach kodas vadinamas G0. Tai aukščiau aprašytos vienetainės sistemos plėtinys. G0 užkoduoją teigiamą sveikąjį skaičių n, paskaičiavus lyginį skaičių \(\) ir užrašant jį kaip dviejų pirminių skaičių sumą iš kairės į dešinę.

n 2(n+3) Pirminiai sk. G0 kodas
1 8 3+5 11
2 10 3+7 101
3 12 5+7 011
4 14 3+11 1001
5 16 5+11 0101
6 18 7+11 0011
7 18 7+13 00101
8 22 5+17 010001
9 24 11+13 00011
10 26 7+19 0010001
11 28 11+17 000101
12 30 13+17 000011
13 32 13+19 000101
14 34 11+23 00010001

Kodo ilgis auga, tačiau ne monotoniškai. Funkcijos surasti kodo ilgiui duotam n skaičiui nėra. G0 yra efektyvus tik nedidelėms n reikšmėms, dėl trijų priežasčių: 1. Naudojantis priminių skaičių lentele, lengva surasti reikiamus pirminius skaičius. 2. G0 kodą lengva dekoduoti. 3. G0 kodo ilgis yra panašaus ilgio kaip Fibinacci kodo arba standartinės dvejetainės išraiškos.

Didėjant n reikšmei, G0 kodai tampa per ilgi. Taip pat, galimų pirminių skaičių pasirinkimas smarkiai išauga, o kiekvienas toks rinkinys nulemia skirtingo ilgio G0 kodą. Tad geriausių pirminių skaičių radimas užima per daug laiko.

G1

Dėl prastų rezultatų koduojant didelius skaičius su G0 kodu, buvo sugalvotas būdas, pavadintas G1, kaip sutrumpinti užkoduotus skaičius. Koduojant skaičių n, G1 kodu, surandami du pirminiai skaičiai \(\) ir \(\) \(\), kurių suma lygi skaičiui n. Rastųjų pirminių skaičių indeksų pora \(\) yra užkoduojama gamma kodais. Indeksas i gali būti lygus j, todėl kodavimui negalima poros apskaičiuoti pagal formulę \(\).

n Suma Indeksai Pora G1 kodas Ilgis
2 1+1 1,1 1,1 1:1 2
4 1+3 1,2 1,2 1:010 4
6 3+3 2,2 2,1 010:010 6
10 3+7 2,4 2,3 010:011 6
20 7+13 4,6 4,3 00100:011 8
40 17+23 7,9 7,3 00111:011 8
40 3+37 2,12 2,11 010:0001011 10
50 13+37 6,12 6,7 00110:00111 10
50 19+31 8,11 8,4 0001000:00100 12
70 29+41 10,13 10,4 0001010:00100 12
80 37+43 12,14 12,3 0001100:011 10
100 47+53 15,16 15,2 0001111:010 10

Kodo ilgio priklausomybę nuo pasirinktų pirminių skaičių pademonstruoja lentelės pavyzdys su skaičiais 40 ir 50. Dažniausiai, trumpiausias kodas gaunamas pasirenkant du panašius pirminius skaičius, tačiau pasitaiko atvejų, kada tokia taisykle vadovautis negalima.

Norint pritaikyti G1 praktikoje, reikalinga galimybė užkoduoti bet kokį teigiamą skaičių. Tą pasiekti galima dviem būdais:

1. Prieš pradedant G1 kodavimą, duotąjį skaičių n paversti į \(\) ir pradėti kodavimą su skaičiumi N. Tačiau naudojant šį būdą, indeksai padidėja apie 60 procentų, o tai sąlygoja ilgesnius G1 kodus.

2. Kiekvieną koduojamą skaičių įvertinti individualiai ir pagal tai pritaikyti apdorojimą. Šį būdą naudoja G2 kodavimas.

Nors nėra tikslios formulės, norint sužinoti G1 kodo ilgį duotajam skaičiui n, tačiau apytikslį kodo ilgį galime apskačiuoti. Vieno iš G1 sudarančių gamma kodų ilgis yra apytiksliai apskaičiuojami pagal formulę

\(\)

Kitas indeksas poroje \(\) yra apytiksliai \(\) ilgio. Iš to seka, kad G1 kodo ilgis duotajam n apytiksliai yra \(\), kur L yra gaunamas pagal aukščiau pateiktą formulę.

G1 kodas yra trumpesnis už gamma kodus, kai n neviršyja 100. Tačiau esant didesniam n, G1 kodas yra ilgesnis už gamma kodą.

G2

G2 kodavimas pratęsia G1 ir leidžia užkoduoti bet kokius teigiamus skaičius. G2 kodavime išskiriami keturi atvejai:

1. Skaičiai 1 ir 2 yra užkoduojami atitinkamai 110 ir 111. Jokie kiti kodai neprasidės dviem vienetais priekyje.

2. Lyginiai sveikieji skaičiai koduojami panašiai kaip ir G1. Apskaičiavus pirminių skaičių porą, jų indeksų pora gaunama pagal formulę \(\). Jeigu \(\), jis užkoduojamas kaip 010 - gamma kodas skaičiaus 2. Tai garantuoja, kad G2 kodai su lyginių skaičiumi neprasidės 1 ir visada bus formos \(\).

3. Jei n yra pirminis \(\), jis yra užkoduojamas \(\) gamma kodu ir iš dešinės pusės pridedamas 1, tokie skaičiai visada bus formos \(\).

4. Jei n yra nelyginis, tačiau ne pirminis, jo G2 kodas prasideda 1, o toliau seka G2 kodas skaičiaus \(\). Užkoduoti skaičiai turi forma \(\).

n G2 kodas Ilgis
1 110 3
2 111 3
3 0101 4
4 010010 6
5 0111 4
10 01100100 8
11 001011 6
16 0010100100 10
20 00111011 8
30 0001010010 10
40 0001100011 10
60 000010001010 12
80 000010110010 12
100 000011001011 12

Apytikslis G2 kodo ilgis apskaičiuojamas pagal formulę \(\)

Pvz.: \(\), pagal formulę, užkoduoto skaičiaus ilgis gaunasi 16.625, tai yra 1.66 karto daugiau, nei standartinė dvejetainė išraiška. Tačiau, šiuo atveju, gamma kodas yra ilgesnis 2 kartus.

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.

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.