Elias deltakodning

Elias δ-kod eller Elias deltakod är en universell kod som kodar de positiva heltal som utvecklats av Peter Elias .

Kodning

För att koda ett nummer X ≥ 1:

Låt N = ⌊log ₂ X ⌋; vara den högsta potensen av 2 i X , så 2 ^N ≤ X < 2 ^{N +1} .
Låt L = ⌊log ₂ N +1⌋ vara den högsta potensen av 2 i N +1, så 2 ^L ≤ N +1 < 2 ^{L +1} .
Skriv L nollor, följt av
L + 1-bitars binära representation av N +1, följt av
alla utom den inledande biten (dvs. de sista N bitarna) av X .

Ett likvärdigt sätt att uttrycka samma process:

Separera X i den högsta potensen av 2 det innehåller (2 ^N ) och de återstående N binära siffrorna.
Koda N +1 med Elias gammakodning .
Lägg till de återstående N binära siffrorna till denna representation av N +1.

För att representera ett tal $x$ använder Elias delta (δ) $\ lgolv \log _{2}(x)\rgolv +2\lgolv \log _{2}(\lgolv \log _{2}(x)\rgolv +1)\rgolv +1$ bitar.

Koden börjar med $\gamma '$ istället för $\gamma$ :

siffra	N	N+1	δ-kodning	Underförstådd sannolikhet
1 = 2⁰	0	1	`1`	1/2

2 = ²¹⁺0	1	2	`0 1 00`	1/16
3 = 2 ¹ + 1	1	2	`0 1 0 1`	1/16

4 = 2 ² + 0	2	3	`0 1 1 00`	1/32
5 = 2 ² + 1	2	3	`0 1 1 01`	1/32
6 = 2 ² + 2	2	3	`0 1 1 10`	1/32
7 = 2 ² + 3	2	3	`0 1 1 11`	1/32

8 = 2 ³ + 0	3	4	`00 1 00 000`	1/256
9 = 2 ³ + 1	3	4	`00 1 00 001`	1/256
10 = 2 ³ + 2	3	4	`00 1 00 010`	1/256
11 = 2 ³ + 3	3	4	`00 1 00 011`	1/256
12 = 2 ³ + 4	3	4	`00 1 00 100`	1/256
13 = 2 ³ + 5	3	4	`00 1 00 101`	1/256
14 = 2 ³ + 6	3	4	`00 1 00 110`	1/256
15 = 2 ³ + 7	3	4	`00 1 00 111`	1/256

16 = ²⁴⁺0	4	5	`00 1 01 0000`	1/512
17 = 2 ⁴ + 1	4	5	`00 1 01 0001`	1/512

För att avkoda ett Elias deltakodat heltal:

Läs och räkna nollor från strömmen tills du når den första. Kalla detta nolltal för L .
Med tanke på att den som uppnåddes vara den första siffran i ett heltal, med värdet 2 ^L , läs de återstående L -siffrorna i heltalet. Kalla detta heltal N +1 och subtrahera ett för att få N .
Sätt en etta på första platsen i vår slutliga utdata, vilket representerar värdet 2 ^N .
Läs och lägg till följande N siffror.

Exempel:

 001010011 1. 2 inledande nollor i 001 2. läs ytterligare 2 bitar dvs 00101 3. avkoda N+1 = 00101 = 5 4. få N = 5 − 1 = 4 återstående bitar för hela koden dvs '0011' 5. kodat nummer = 2 ⁴ + 3 = 19

Denna kod kan generaliseras till noll eller negativa heltal på samma sätt som beskrivs i Elias gammakodning .

Exempelkod

Kodning

    

     
     
     
    
           
           0
           0

              
           
      
               0 
            0
               0 
                
               0 
                
    
    
    
 void  eliasDeltaEncode  (  char  *  source  ,  char  *  dest  )  {  IntReader  intreader  (  source  );  BitWriter  bitwriter  (  dest  );  while  (  intreader  .  hasLeft  ())  {  int  num  =  intreader  .  getInt  ();  int  len  =  ;  int  lengthOfLen  =  ;  len  =  1  +  våning  (  log2  (  antal  ));  // beräkna 1+golv(log2(tal))  lengthOfLen  =  floor  (  log2  (  len  ));  // beräkna floor(log2(len))  för  (  int  i  =  lengthOfLen  ;  i  >  ;  --  i  )  bitwriter  .  outputBit  (  );  för  (  int  i  =  lengthOfLen  ;  i  >=  ;  --  i  )  bitwriter  .  outputBit  ((  len  >>  i  )  &  1  );  för  (  int  i  =  len  -2  ;  i  >=  ;  i  --  )  bitskrivare  .  outputBit  ((  num  >>  i  )  &  1  );  }  bitskrivare  .  stäng  ();  inträdare  .  stäng  ();  }

Avkodning

    

     
     
     
    
           
           
           0
              
            
            0    
        
              
             
                  
        
            0    
        
              
             
                  
        
                    
    
    
    
 void  eliasDeltaDecode  (  char  *  source  ,  char  *  dest  )  {  BitReader  bitreader  (  source  );  IntWriter  intwriter  (  dest  );  while  (  bitläsare  .  hasLeft  ())  {  int  num  =  1  ;  int  len  =  1  ;  int  lengthOfLen  =  ;  while  (  !  bitreader  .  inputBit  ())  // potentiellt farligt med felaktiga filer.  lengthOfLen  ++  ;  for  (  int  i  =  ;  i  <  lengthOfLen  ;  i  ++  )  {  len  <<=  1  ;  if  (  bitläsare  .  inputBit  ())  len  |=  1  ;  }  for  (  int  i  =  ;  i  <  len  -1  ;  i  ++  )  {  num  <<=  1  ;  if  (  bitläsare  .  inputBit  ())  num  |=  1  ;  }  inskrivare  .  putInt  (  antal  );  // skriv ut värdet  }  bitläsare  .  stäng  ();  inskrivare  .  stäng  ();  }

Generaliseringar

Elias deltakodning kodar inte noll eller negativa heltal. Ett sätt att koda alla icke-negativa heltal är att lägga till 1 före kodning och sedan subtrahera 1 efter avkodning. Ett sätt att koda alla heltal är att sätta upp en bijektion , avbilda heltal alla heltal (0, 1, −1, 2, −2, 3, −3, ...) till strikt positiva heltal (1, 2, 3, 4, 5, 6, 7, ...) före kodning. Denna bijektion kan utföras med hjälp av "ZigZag"-kodningen från Protocol Buffers (inte att förväxla med Zigzag-kod eller JPEG Zig-zag-entropikodning) .

Se även

Vidare läsning

Hamada, Hozumi (juni 1983). "URR: Universell representation av reella tal" . Ny generation datoranvändning . 1 (2): 205–209. doi : 10.1007/BF03037427 . ISSN 0288-3635 . Hämtad 2018-07-09 . (OBS. Elias δ-koden sammanfaller med Hamadas URR-representation.)