Елајасов код

Елајасов код (Шенон-Фано-Елајасов код) је код са структуром стабла променљиве дужине који неограничено дуге низове изворних симбола кодује у неограничено дуге низове кодованих симбола. Операција кодовања има клизајућу структуру, код које, како неколико симбола уђе у кодер тако га неколико кодованих бита и напушта. Број кодованих бита на излазу из декодера након уласка једног изворног симбола је променљив и зависи од структуре низа изворних симбола.

Математичка интерпретација Елајасовог кода

Функција расподеле F(i)

Претпоставимо да имамо извор без меморије Xi који узима вредности из алфабета {1,2,...,L}. Претпоставимо да су вероватноће свих ових симбола строго позитивне p(i)>0, ∀i. Функција расподеле F(i) је дата са:

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

Модификована функција расподеле која представља суму вероватноћа свих симбола од i, и половину вероватноће симбола i може се записати као:

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

C обзиром да су све вероватноће позитивне, F(i)≠F(j) за i≠j можемо одредити i ако знамо модификовану функцију расподеле (директно са графика). Вредности модификоване функције расподеле се могу користити као код за i. У општем случају је Fs(i) је реалан број који може да се прикаже само са бесконачним бројем бита у његовом бинарном облику, тако да не можемо да користимо ту вредност као кодну реч.

Претпоставимо да заокружимо бинарну представу Fs(i) на ${\displaystyle l(i)}$ бита што се може записати као:

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

Сад имамо:

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

Ако је:

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

Тада имамо:

${\displaystyle {\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)}$

Из овога следи да се број L налази у интервалу који одговара вредности i, и да довољан број бита да се опише i износи

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

Овако конструисани код је префиксан (ниједна кодна реч није префикс друге кодне речи) што ћемо и доказати. Претпоставимо да је кодна реч b1b2…bl. Ови битови представљају интервал

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

Да би код био префиксан потребно је да интервали који одговарају кодним речима буду дисјунктни. Интервал који одговара кодној речи симбола i има дужину 2^-l(i) што је мање од половине корака који одговара симболу i. Почетна тачка интервала се налази у доњој половини корака. Ово значи да се крајња тачка интервала налази испод врха корака. Дакле сви интервали су дисјунктни и код је префиксан.

Просечна дужина кодне речи износи:

${\displaystyle {\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)}$

Дакле

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

Елајасов Гама код

Елајасов Гама код је најпростија реализација Елајасовог кода који се користи у ситуацијама када највећа кодована вредност није позната унапред, или да би се компримовали подаци у којима се чешће појављују мале вредности него велике вредности.

Кодовање природног броја x є N = {1,2,3,…}:

1. Број се написе у бинарном облику (да би се број написао у бинарном облику потребно је ⌊log₂(x)⌋+1 цифара)
2. Испред броја у бинарном облику се дописе ⌊log₂(x)⌋ нула

Декодовање броја кодованог Елајасовим Гама кодом:

1. Преброји се број, нпр n, нула на почетку речи до појаве прве јединице. Ако је n=0 онда је декодовани број 1; ако је n≠0, онда декодер чита наредних n+1 бита и декодује одговарајући бинарни број.

Елајасов Делта код

Елајасов Делта код– сложенији је и користи Елајасов Гама код као основу.

Кодовање природног броја x є N = {1,2,3,…}:

1. Број се напише у бинарном облику
2. Број ⌊log₂x⌋+1 се напише у бинарном облику (X)
3. Од бинарног броја добијеног у кораку 1 се одузме водећи бит и преостали бити се записују (Y)
4. На крај бинарног броја X се дода бинарни број Y
5. Пребројати број бита добијених под 2 и од тога броја одузети 1 и толико нула додати испред.

Декодовање броја кодованог Елајасовим Делта кодом

1. Преброји се број нула док се не наиђе на прву јединицу. Нека је овај број нула - L.
2. Прва јединица се сматра да је прва цифра броја са вредношћу 2^l. Прочитамо преосталих L цифара. Нека је овај број N.
3. Ставити 1 на првом месту коначног излаза. Прочитамо и додамо преосталих N-1 бита

Поређење Елајасовог Гама и Елајасовог Делта кода

Нека се ова два кода користе за кодовање бројева из скупа {1,2,…,N}, N>>1.

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

${\displaystyle {{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 }$

Нека је X произвољна случајна променљива са униформном расподелом над {1,2,…,N}, и тада има ентропију

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

Очекивана дужина Елајасовог Гама кода износи

${\displaystyle 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)}$

Знамо да је ⌊${\displaystyle a}$⌋>${\displaystyle a}$-1,∀${\displaystyle a}$, па следи:

${\displaystyle 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}$

Користећи чињеницу:

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

можемо закључити

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

За јако велико N очекивана дужина Елајасовог Гама кода се приближава двострукој ентропији што није оптимално.

Очекивана дужина Елајасовог Делта кода износи

${\displaystyle {\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}}}$

како

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

Знамо да за свако N важи

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

па можемо закључити:

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

Овим смо показали да за јако велико N очекивана дужина Елајасовог Делта кода се приближава ентропији, и закључујемо да је делта код асимптотски оптималан.

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