Елајасов код

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

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

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

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

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

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

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

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

Сад имамо:

Ако је:

Тада имамо:

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

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

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

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

Дакле

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

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

Кодовање природног броја 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.

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

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

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

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

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

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

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

како

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

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

Овим смо показали да за јако велико 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