Elias Omega kode

Elias Omega Code  er en universel kode til indkodning af positive heltal, udviklet af Peter Elias.

Ligesom Elias gamma- og deltakoderne tildeler den begyndelsen af ​​et heltal størrelsesordenen i den universelle kode. Men i modsætning til de to andre nævnte koder koder omega-koden rekursivt præfikset, hvorfor den også er kendt som den rekursive Elias-kode .

Sådan kodes et nummer:

  1. Omskriv en gruppe af nuller i slutningen af ​​visningen.
  2. Hvis nummeret, der skal kodes, er ét, stop; hvis ikke, skal du tilføje den binære repræsentation af tallet som en gruppe til begyndelsen af ​​repræsentationen.
  3. Gentag det forrige trin med antallet af cifre (bits) lige skrevet, minus én, som med det nye tal, der skal kodes.

De første par koder er vist nedenfor. Der gives også en såkaldt estimeret fordeling, som beskriver fordelingen af ​​værdier, for hvilke denne kodning resulterer i en kode af minimumsstørrelse (se: universel kode ).

Start kodning:

Nummer Kodning Estimeret
Sandsynlighed
en 0 1/2
2 100 1/8
3 11 0 1/8
fire 10 100 0 1/64
5 10 101 0 1/64
6 10 110 0 1/64
7 10 111 0 1/64
otte 11 1000 0 1/128
9 11 1001 0 1/128
ti 11 1010 0 1/128
elleve 11 1011 0 1/128
12 11 1100 0 1/128
13 11 1101 0 1/128
fjorten 11 1110 0 1/128
femten 11 1111 0 1/128
16 10 100 10000 0 1/2048
17 10 100 10001 0 1/2048
…

Algoritme til afkodning af tallet repræsenteret i Elias omega-koden:

  1. Start med variabel N sat til 1.
  2. Læs den første "gruppe" efter de resterende N cifre, som vil bestå af enten "0" eller "1". Hvis det består af "0", betyder det, at værdien af ​​hele tallet er 1; hvis det starter med "1", så får N værdien af ​​gruppen, som tolkes som et binært tal.
  3. Læs hver næste gruppe; den vil bestå af enten et "0" eller et "1" efter de resterende N cifre. Hvis gruppen er "0", betyder det, at værdien af ​​hele tallet er N; hvis det starter med "1", så tager N værdien af ​​en gruppe, fortolket som et binært tal.

Omega-kodning bruges i applikationer, hvor den største værdi, der skal kodes, ikke er kendt på forhånd, eller til datakomprimering, hvor små værdier er meget mere almindelige end store.

Se også

Litteratur