Elajasov kod

Elajasov kod (Šenon-Fano-Elajasov kod) je kod sa strukturom stabla promenljive dužine koji neograničeno duge nizove izvornih simbola koduje u neograničeno duge nizove kodovanih simbola. Operacija kodovanja ima klizajuću strukturu, kod koje, kako nekoliko simbola uđe u koder tako ga nekoliko kodovanih bita i napušta. Broj kodovanih bita na izlazu iz dekodera nakon ulaska jednog izvornog simbola je promenljiv i zavisi od strukture niza izvornih simbola.

Matematička interpretacija Elajasovog koda

Funkcija raspodele F(i)

Pretpostavimo da imamo izvor bez memorije Xi koji uzima vrednosti iz alfabeta {1,2,...,L}. Pretpostavimo da su verovatnoće svih ovih simbola strogo pozitivne p(i)>0, ∀i. Funkcija raspodele F(i) je data sa:

$F(i)={\underset {k\leq i}{\mathop {\sum } }}\,p(k)$

Modifikovana funkcija raspodele koja predstavlja sumu verovatnoća svih simbola od i, i polovinu verovatnoće simbola i može se zapisati kao:

$Fs(i)={\overset {\bar {\ }}{\mathop {F} }}\,(i)={\underset {k<i}{\mathop {\sum } }}\,p(k)+{\frac {1}{2}}p(i)$

C obzirom da su sve verovatnoće pozitivne, F(i)≠F(j) za i≠j možemo odrediti i ako znamo modifikovanu funkciju raspodele (direktno sa grafika). Vrednosti modifikovane funkcije raspodele se mogu koristiti kao kod za i. U opštem slučaju je Fs(i) je realan broj koji može da se prikaže samo sa beskonačnim brojem bita u njegovom binarnom obliku, tako da ne možemo da koristimo tu vrednost kao kodnu reč.

Pretpostavimo da zaokružimo binarnu predstavu Fs(i) na $l(i)$ bita što se može zapisati kao:

$L={{\left\lfloor {\overset {\bar {\ }}{\mathop {F} }}\,(i)\right\rfloor }_{l(i)}}$

Sad imamo:

${\overset {\bar {\ }}{\mathop {F} }}\,\left(i\right)-{{\left\lfloor {\overset {\bar {\ }}{\mathop {F} }}\,(i)\right\rfloor }_{l(i)}}<{\frac {1}{{2}^{l(i)}}}$

Ako je:

$l(i)=\left\lceil -\log p(i)\right\rceil +1$

Tada imamo:

${\frac {1}{{2}^{l(i)}}}={{2}^{-l(i)}}={{2}^{-\left\lceil -\log p(i)\right\rceil -1}}\leq {{2}^{\log p\left(i\right)-1}}={\frac {p(i)}{2}}={\overset {\bar {\ }}{\mathop {\mathbf {F} } }}\,\left(i\right)-\mathbf {F} \left(i-1\right)\Rightarrow {{\left\lfloor {\overset {\bar {\ }}{\mathop {F} }}\,\left(i\right)\right\rfloor }_{l(i)}}>F\left(i-1\right)$

Iz ovoga sledi da se broj L nalazi u intervalu koji odgovara vrednosti i, i da dovoljan broj bita da se opiše i iznosi

$l(i)=\left\lceil -\log p(i)\right\rceil +1$

Ovako konstruisani kod je prefiksan (nijedna kodna reč nije prefiks druge kodne reči) što ćemo i dokazati. Pretpostavimo da je kodna reč b1b2…bl. Ovi bitovi predstavljaju interval

$[0.{{b}_{1}}{{b}_{2}}\ldots {{b}_{l}},0.{{b}_{1}}{{b}_{2}}\ldots {{b}_{l}}+{\frac {1}{{2}^{l}}}]$

Da bi kod bio prefiksan potrebno je da intervali koji odgovaraju kodnim rečima budu disjunktni. Interval koji odgovara kodnoj reči simbola i ima dužinu 2^-l(i) što je manje od polovine koraka koji odgovara simbolu i. Početna tačka intervala se nalazi u donjoj polovini koraka. Ovo znači da se krajnja tačka intervala nalazi ispod vrha koraka. Dakle svi intervali su disjunktni i kod je prefiksan.

Prosečna dužina kodne reči iznosi:

${\overset {\bar {\ }}{\mathop {l} }}\,={\underset {i}{\mathop {\sum } }}\,p\left(i\right)\cdot l\left(i\right)={\underset {i}{\mathop {\sum } }}\,p\left(i\right)\cdot \left(\left\lceil -\log p\left(i\right)\right\rceil +1\right)\leq {\underset {i}{\mathop {\sum } }}\,p\left(i\right)\cdot \left(-\log p\left(i\right)+2\right)=-{\underset {i}{\mathop {\sum } }}\,p\left(i\right)\cdot \log p\left(i\right)+2\cdot {\underset {i}{\mathop {\sum } }}\,p\left(i\right)$

Dakle

${\overset {\bar {\ }}{\mathop {l} }}\,=H\left({{X}_{i}}\right)+2$

Elajasov Gama kod

Elajasov Gama kod je najprostija realizacija Elajasovog koda koji se koristi u situacijama kada najveća kodovana vrednost nije poznata unapred, ili da bi se komprimovali podaci u kojima se češće pojavljuju male vrednosti nego velike vrednosti.

Kodovanje prirodnog broja x є N = {1,2,3,…}:

1. Broj se napise u binarnom obliku (da bi se broj napisao u binarnom obliku potrebno je ⌊log₂(x)⌋+1 cifara)
2. Ispred broja u binarnom obliku se dopise ⌊log₂(x)⌋ nula

Dekodovanje broja kodovanog Elajasovim Gama kodom:

1. Prebroji se broj, npr n, nula na početku reči do pojave prve jedinice. Ako je n=0 onda je dekodovani broj 1; ako je n≠0, onda dekoder čita narednih n+1 bita i dekoduje odgovarajući binarni broj.

Elajasov Delta kod

Elajasov Delta kod– složeniji je i koristi Elajasov Gama kod kao osnovu.

Kodovanje prirodnog broja x є N = {1,2,3,…}:

1. Broj se napiše u binarnom obliku
2. Broj ⌊log₂x⌋+1 se napiše u binarnom obliku (X)
3. Od binarnog broja dobijenog u koraku 1 se oduzme vodeći bit i preostali biti se zapisuju (Y)
4. Na kraj binarnog broja X se doda binarni broj Y
5. Prebrojati broj bita dobijenih pod 2 i od toga broja oduzeti 1 i toliko nula dodati ispred.

Dekodovanje broja kodovanog Elajasovim Delta kodom

1. Prebroji se broj nula dok se ne naiđe na prvu jedinicu. Neka je ovaj broj nula - L.
2. Prva jedinica se smatra da je prva cifra broja sa vrednošću 2^l. Pročitamo preostalih L cifara. Neka je ovaj broj N.
3. Staviti 1 na prvom mestu konačnog izlaza. Pročitamo i dodamo preostalih N-1 bita

Poređenje Elajasovog Gama i Elajasovog Delta koda

Neka se ova dva koda koriste za kodovanje brojeva iz skupa {1,2,…,N}, N>>1.

${{l}_{\gamma }}\left(x\right)=2\left\lfloor \mathbf {lo} {{\mathbf {g} }_{2}}x\right\rfloor +1$

${{l}_{\delta }}\left(x\right)={{l}_{\gamma }}\left(\left\lfloor {{\log }_{2}}x\right\rfloor +1\right)+\left\lfloor {{\log }_{2}}x\right\rfloor =2\left\lfloor {{\log }_{2}}(\left\lfloor {{\log }_{2}}x\right\rfloor +1)\right\rfloor +1+\left\lfloor {{\log }_{2}}x\right\rfloor$

Neka je X proizvoljna slučajna promenljiva sa uniformnom raspodelom nad {1,2,…,N}, i tada ima entropiju

$H\left(X\right)={{\log }_{2}}N{\frac {bits}{symbol}}$

Očekivana dužina Elajasovog Gama koda iznosi

$E\left[{{l}_{\gamma }}\left(X\right)\right]={\frac {1}{N}}{\underset {x=1}{\overset {N}{\mathop {\sum } }}}\,\left(2\left\lfloor {{\log }_{2}}x\right\rfloor +1\right)$

Znamo da je ⌊$a$⌋>$a$-1,∀$a$, pa sledi:

$E\left[{{l}_{\gamma }}\left(X\right)\right]={\frac {1}{N}}{\underset {x=1}{\overset {N}{\mathop {\sum } }}}\,\left(2{{\log }_{2}}x-1\right)={\frac {2}{N}}\log \log({\underset {x=1}{\overset {N}{\mathop {\prod } }}}\,x)-1={\frac {2}{N}}{{\log }_{2}}(N!)-1$

Koristeći činjenicu:

${\underset {n\to \infty }{\mathop {\lim } }}\,{\frac {\log(t!)}{t\log(t)}}=1$

možemo zaključiti

${\underset {N\to \infty }{\mathop {\lim } }}\,{\frac {E\left[{{l}_{\gamma }}\left(X\right)\right]}{\log N}}\geq 2$

Za jako veliko N očekivana dužina Elajasovog Gama koda se približava dvostrukoj entropiji što nije optimalno.

Očekivana dužina Elajasovog Delta koda iznosi

${\begin{aligned}&E[{{l}_{\delta }}\left(X\right)]\leq {\frac {1}{N}}{\underset {x=1}{\overset {N}{\mathop {\sum } }}}\,\left(2{{\log }_{2}}\left({{\log }_{2}}x+1\right)+1+{{\log }_{2}}x\right)=\\&={\frac {1}{N}}\log \left({\underset {x=1}{\overset {N}{\mathop {\prod } }}}\,x\right)+{\frac {2}{N}}{\underset {x=1}{\overset {N}{\mathop {\sum } }}}\,{{\log }_{2}}\left({{\log }_{2}}x+1\right)+1\leq {\frac {1}{N}}\log(N!)+2{{\log }_{2}}\left({{\log }_{2}}N+1\right)+1,\\\end{aligned}}$

kako

${\underset {t\to \infty }{\mathop {\lim } }}\,{\frac {\log(\log t+1)}{\log(t)}}=0$

Znamo da za svako N važi

${{\log }_{2}}({{\log }_{2}}x+1)\leq {{\log }_{2}}\left({{\log }_{2}}N+1\right)$

pa možemo zaključiti:

${\underset {N\to \infty }{\mathop {\lim } }}\,{\frac {E\left[{{l}_{\delta }}\left(X\right)\right]}{\log N}}=1$

Ovim smo pokazali da za jako veliko N očekivana dužina Elajasovog Delta koda se približava entropiji, i zaključujemo da je delta kod asimptotski optimalan.

Literatura

• David J.C. MacKay, 2008.Information Theory,Inference,and Learning Algorithms. Cambridge University Press 2003
• Thomas M. Cover, Joy A. Thomas, 2006. Elements of Information Theory. JOHN WILEY & SONS, INC.
• P. Elias, Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, vol. 21, pp. 194-203 March 1975.
• Te Sun Han, Kingo Kobayashi, 2001. Mathematics of information and coding.AMS Bookstore, 2001