Дельта-кодирование Элиаса

Δ-код Элиаса или дельта-код Элиаса - это универсальный код, кодирующий положительные целые числа, разработанный Питером Элиасом . ^[1]^{: 200}

Кодирование

Чтобы закодировать число X ≥ 1:

Пусть N = ⌊log ₂ X ⌋; - наибольшая степень двойки в X , поэтому 2 ^N ≤ X <2 ^{N +1} .
Пусть L = ⌊log ₂ N + 1⌋ - наибольшая степень двойки в N +1, поэтому 2 ^L ≤ N +1 <2 ^{L +1} .
Напишите L нулей, а затем
L + 1-битовое двоичное представление N + 1, а затем
все , но ведущий бит (т.е. последние N бит) X .

Эквивалентный способ выразить тот же процесс:

Разделите X в наивысшую степень двойки, он содержит (2 ^N ) и оставшиеся N двоичных цифр.
Кодируйте N +1 с гамма-кодированием Элиаса .
Добавьте оставшиеся N двоичных цифр к этому представлению N +1.

Для представления числа дельта Элиаса (δ) использует биты. ^[1]^:²⁰⁰ ${\ displaystyle x}$ ${\ Displaystyle \ lfloor \ log _ {2} (x) \ rfloor +2 \ lfloor \ log _ {2} (\ lfloor \ log _ {2} (x) \ rfloor +1) \ rfloor +1}$

Код начинается с использования вместо : ${\ displaystyle \ gamma '}$ $\gamma$

Число	N	N + 1	δ кодирование	Предполагаемая вероятность
1 = 2 ⁰	0	1	`1`	1/2

2 = 2 ¹ + 0	1	2	`0 1 0 0`	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 = 2 ⁴ + 0	4	5	`00 1 01 0000`	1/512
17 = 2 ⁴ + 1	4	5	`00 1 01 0001`	1/512

Чтобы декодировать целое число с дельта-кодом Элиаса:

Считайте и считайте нули из потока, пока не дойдете до первого. Назовите этот счетчик нулей L .
Считая, что достигнутая цифра является первой цифрой целого числа со значением 2 ^L , прочтите оставшиеся L цифр целого числа. Назовем это целое число N + 1, и вычесть один , чтобы получить N .
Поместите один в первую очередь нашего окончательного вывода, представляющее значение 2 ^N .
Прочтите и добавьте следующие N цифр.

Пример:

001010011
1. 2 ведущих нуля в 001
2. Прочтите еще 2 бита, т.е. 00101
3. декодировать N + 1 = 00101 = 5
4. получить N = 5 - 1 = 4 оставшихся бита для полного кода, т.е. '0011'
5. закодированное число = 2 ⁴ + 3 = 19

Этот код можно обобщить на ноль или отрицательные целые числа так же, как описано в гамма-кодировании Элиаса .

Пример кода

Кодирование

void  eliasDeltaEncode ( char *  source ,  char *  dest ) {  IntReader  intreader ( source );  BitWriter  bitwriter ( dest );  в то время как  ( intreader . hasLeft ())  {  int  num  =  intreader . getInt ();  int  len  =  0 ;  int  lengthOfLen  =  0 ; len  =  1  +  этаж ( log2 ( num ));  // вычисляем 1 + этаж (log2 (num))  lengthOfLen  =  floor ( log2 ( len ));  // вычисляем этаж (log2 (len)) для  ( int  i  =  lengthOfLen ;  i  >  0 ;  - i )  битовая запись . outputBit ( 0 );  для  ( int  i  =  lengthOfLen ;  i  > =  0 ;  - i )  битовая запись . outputBit (( len  >>  я )  &  1 );  для  ( int  i  =  len -2 ;  i  > = 0 ;  i - )  bitwriter . outputBit (( число  >>  я )  &  1 );  }  bitwriter . закрыть ();  читатель . закрыть (); }

Расшифровка

void  eliasDeltaDecode ( char *  source ,  char *  dest ) {  BitReader  bitreader ( источник );  IntWriter  intwriter ( dest );  в то время как  ( средство чтения . hasLeft ())  {  int  num  =  1 ;  int  len  =  1 ;  int  lengthOfLen  =  0 ;  в то время как  ( ! bitreader . inputBit ()) // потенциально опасно с искаженными файлами.  lengthOfLen ++ ;  для  ( int  я  =  0 ;  я  <  lengthOfLen ;  я ++ )  {  len  << =  1 ;  если  ( читатель . inputBit ())  len  | =  1 ;  }  for  ( int  i  =  0 ;  i  <  len -1 ;  i ++ )  {  num  << =  1;  если  ( считыватель битов . inputBit ())  число  | =  1 ;  }  интрайтера . putInt ( число );  // записываем значение  }  bitreader . закрыть ();  интрайтера . закрыть (); }

Обобщения

Дельта-кодирование Элиаса не кодирует нулевые или отрицательные целые числа. Один из способов кодирования всех неотрицательных целых чисел - добавить 1 перед кодированием и затем вычесть 1 после декодирования. Один из способов закодировать все целые числа - установить взаимно однозначное соответствие , отображая целые числа все целые числа (0, 1, −1, 2, −2, 3, −3, ...) в строго положительные целые числа (1, 2, 3, 4, 5, 6, 7, ...) перед кодированием. Это взаимное объединение может быть выполнено с использованием кодирования «зигзаг» из буферов протокола (не путать с кодом зигзага или энтропийным кодированием зигзаг JPEG ).

Смотрите также

использованная литература

^ ^а ^б Элиас, Питер (март 1975). «Универсальные наборы кодовых слов и представления целых чисел». IEEE Transactions по теории информации . 21 (2): 194–203. DOI : 10,1109 / tit.1975.1055349 .

дальнейшее чтение

Хамада, Ходзуми (июнь 1983 г.). «URR: Универсальное представление действительных чисел» . Вычислительная техника нового поколения . 1 (2): 205–209. DOI : 10.1007 / BF03037427 . ISSN 0288-3635 . Проверено 9 июля 2018 . (NB. Δ-код Элиаса совпадает с URR-представлением Хамады.)

[Elias-1] а ^б Элиас, Питер (март 1975). «Универсальные наборы кодовых слов и представления целых чисел». IEEE Transactions по теории информации . 21 (2): 194–203. DOI : 10,1109 / tit.1975.1055349 .

[1]