Elias Omega-kod

Elias Omega Code  är en universell kod för att koda positiva heltal, utvecklad av Peter Elias.

Precis som Elias gamma- och deltakoder tilldelar den början av ett heltal storleksordningen i den universella koden. Men till skillnad från de andra två nämnda koderna kodar omega-koden rekursivt prefixet, vilket är anledningen till att den också är känd som den rekursiva Elias-koden .

För att koda ett nummer:

  1. Skriv om en grupp med nollor i slutet av vyn.
  2. Om numret som ska kodas är ett, sluta; Om inte, lägg till den binära representationen av talet som en grupp i början av representationen.
  3. Upprepa föregående steg, med antalet siffror (bitar) som just skrivits, minus en, som med det nya numret som ska kodas.

De första koderna visas nedan. En så kallad uppskattad fördelning ges också, som beskriver fördelningen av värden för vilka denna kodning resulterar i en kod av minsta storlek (se: universell kod ).

Börja koda:

siffra Kodning Uppskattad
sannolikhet
ett 0 1/2
2 100 1/8
3 11 0 1/8
fyra 10 100 0 1/64
5 10 101 0 1/64
6 10 110 0 1/64
7 10 111 0 1/64
åtta 11 1000 0 1/128
9 11 1001 0 1/128
tio 11 1010 0 1/128
elva 11 1011 0 1/128
12 11 1100 0 1/128
13 11 1101 0 1/128
fjorton 11 1110 0 1/128
femton 11 1111 0 1/128
16 10 100 10 000 0 1/2048
17 10 100 10001 0 1/2048
…

Algoritm för att avkoda numret som representeras i Elias omega-koden:

  1. Börja med variabel N inställd på 1.
  2. Läs den första "gruppen" efter de återstående N siffrorna, som kommer att bestå av antingen "0" eller "1". Om det består av "0", betyder det att värdet på heltal är 1; om det börjar med "1", så får N värdet på gruppen, vilket tolkas som ett binärt tal.
  3. Läs varje nästa grupp; den kommer att bestå av antingen en "0" eller en "1" efter de återstående N siffrorna. Om gruppen är "0", betyder det att värdet på heltal är N; om det börjar med "1", så tar N värdet av en grupp, tolkat som ett binärt tal.

Omega-kodning används i applikationer där det största värdet som ska kodas inte är känt i förväg, eller för datakomprimering där små värden är mycket vanligare än stora.

Se även

Litteratur