Елајасов код

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

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

Датотека:Fja raspodele elajas-koda.jpg

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

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

$F(i)=\sum _{k\le i}p(k)$

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

$Fs(i)=\overline{F}(i)=\sum _{k<i}p(k)+\frac{1}{2}p(i)$

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

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

$L={\lfloor \overline{F}(i)\rfloor }_{l(i)}$

Сад имамо:

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

Ако је:

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

Тада имамо:

$\frac{1}{2^{l(i)}}=2^{-l(i)}=2^{-\lceil -\log p(i)\rceil -1}\le 2^{\log p\left(i\right)-1}=\frac{p(i)}{2}=\overline{𝐅}\left(i\right)-𝐅(i-1)\Rightarrow {\lfloor \overline{F}\left(i\right)\rfloor }_{l(i)}>F(i-1)$

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

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

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

$[0.b_1{b}_2\dots b_l,0.b_1{b}_2\dots b_l+\frac{1}{2^l}]$

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

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

$\overline{l}=\sum _{i}p\left(i\right)\cdot l\left(i\right)=\sum _{i}p\left(i\right)\cdot (\lceil -\log p\left(i\right)\rceil +1)\le \sum _{i}p\left(i\right)\cdot (-\log p\left(i\right)+2)=-\sum _{i}p\left(i\right)\cdot \log p\left(i\right)+2\cdot \sum _{i}p\left(i\right)$

Дакле

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

$l_{\gamma }\left(x\right)=2\lfloor 𝐥𝐨{𝐠}_{2}x\rfloor +1$

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

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

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

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

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

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

$E\left[l_{\gamma }\left(X\right)\right]=\frac{1}{N}\underset{x=1}{\sum ^N}(2{\log }_{2}x-1)=\frac{2}{N}\log \log (\underset{x=1}{\prod ^N}x)-1=\frac{2}{N}{\log }_2(N!)-1$

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

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

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

$\underset{N\to \mathrm{\infty }}{\lim }\frac{E\left[l_{\gamma }\left(X\right)\right]}{\log N}\ge 2$

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

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

$\begin{array}{cc}& E[l_{\delta }\left(X\right)]\le \frac{1}{N}\underset{x=1}{\sum ^N}(2{\log }_2({\log }_{2}x+1)+1+{\log }_{2}x)=\\ & =\frac{1}{N}\log \left(\underset{x=1}{\prod ^N}x\right)+\frac{2}{N}\underset{x=1}{\sum ^N}{\log }_2({\log }_{2}x+1)+1\le \frac{1}{N}\log (N!)+2{\log }_2({\log }_{2}N+1)+1,\\ \end{array}$

како

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

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

${\log }_2({\log }_{2}x+1)\le {\log }_2({\log }_{2}N+1)$

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

$\underset{N\to \mathrm{\infty }}{\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

}-Шаблон:Литература крај