Елајасов код

Из Википедије, слободне енциклопедије

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

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

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

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

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

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

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) на l(i) бита што се може записати као:

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

Сад имамо:

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

Ако је:

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

Тада имамо:

\frac{1}{{{2}^{l(i)}}}={{2}^{-l(i)}}={{2}^{-\left\lceil -\log p(i) \right\rceil -1}}\le {{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 износи

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

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

[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. Почетна тачка интервала се налази у доњој половини корака. Ово значи да се крајња тачка интервала налази испод врха корака. Дакле сви интервали су дисјунктни и код је префиксан.

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

\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)\le \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)

Дакле

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

Елајасов Гама код[уреди]

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

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

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

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

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

Елајасов Делта код[уреди]

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

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

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

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

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

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

Нека се ова два кода користе за кодовање бројева из скупа {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

Нека је 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}{\overset{N}{\mathop \sum }}\,\left(2\left\lfloor {{\log }_{2}}x \right\rfloor +1 \right)

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

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

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

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

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

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

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

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

\begin{align}
  & E[{{l}_{\delta }}\left(X \right)]\le \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\le \frac{1}{N}\log (N!)+2{{\log }_{2}}\left({{\log }_{2}}N+1 \right)+1, \\ 
\end{align}

како

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

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

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

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

\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