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.