Δ-код Элиаса или дельта-код Элиаса - это универсальный код, кодирующий положительные целые числа, разработанный Питером Элиасом . [1] : 200
Кодирование
Чтобы закодировать число X ≥ 1:
- Пусть N = ⌊log 2 X ⌋; - наибольшая степень двойки в X , поэтому 2 N ≤ X <2 N +1 .
- Пусть L = ⌊log 2 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] : 200
Код начинается с использования вместо :
Число | N | N + 1 | δ кодирование | Предполагаемая вероятность |
---|---|---|---|---|
1 = 2 0 | 0 | 1 | 1 | 1/2 |
2 = 2 1 + 0 | 1 | 2 | 0 1 0 0 | 1/16 |
3 = 2 1 + 1 | 1 | 2 | 0 1 0 1 | 1/16 |
4 = 2 2 + 0 | 2 | 3 | 0 1 1 00 | 1/32 |
5 = 2 2 + 1 | 2 | 3 | 0 1 1 01 | 1/32 |
6 = 2 2 + 2 | 2 | 3 | 0 1 1 10 | 1/32 |
7 = 2 2 + 3 | 2 | 3 | 0 1 1 11 | 1/32 |
8 = 2 3 + 0 | 3 | 4 | 00 1 00 000 | 1/256 |
9 = 2 3 + 1 | 3 | 4 | 00 1 00 001 | 1/256 |
10 = 2 3 + 2 | 3 | 4 | 00 1 00 010 | 1/256 |
11 = 2 3 + 3 | 3 | 4 | 00 1 00 011 | 1/256 |
12 = 2 3 + 4 | 3 | 4 | 00 1 00 100 | 1/256 |
13 = 2 3 + 5 | 3 | 4 | 00 1 00 101 | 1/256 |
14 = 2 3 + 6 | 3 | 4 | 00 1 00 110 | 1/256 |
15 = 2 3 + 7 | 3 | 4 | 00 1 00 111 | 1/256 |
16 = 2 4 + 0 | 4 | 5 | 00 1 01 0000 | 1/512 |
17 = 2 4 + 1 | 4 | 5 | 00 1 01 0001 | 1/512 |
Чтобы декодировать целое число с дельта-кодом Элиаса:
- Считайте и считайте нули из потока, пока не дойдете до первого. Назовите этот счетчик нулей L .
- Считая, что достигнутая цифра является первой цифрой целого числа со значением 2 L , прочтите оставшиеся L цифр целого числа. Назовем это целое число N + 1, и вычесть один , чтобы получить N .
- Поместите один в первую очередь нашего окончательного вывода, представляющее значение 2 N .
- Прочтите и добавьте следующие N цифр.
Пример:
0010100111. 2 ведущих нуля в 0012. Прочтите еще 2 бита, т.е. 001013. декодировать N + 1 = 00101 = 54. получить N = 5 - 1 = 4 оставшихся бита для полного кода, т.е. '0011'5. закодированное число = 2 4 + 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 - ) битовая запись . outputBit (( число >> я ) & 1 ); } bitwriter . закрыть (); читатель . закрыть (); }
Расшифровка
void eliasDeltaDecode ( char * source , char * dest ) { BitReader bitreader ( источник ); IntWriter intwriter ( dest ); в то время как ( средство чтения . hasLeft ()) { int num = 1 ; int len = 1 ; int lengthOfLen = 0 ; while ( ! bitreader . inputBit ()) // потенциально опасно с искаженными файлами. lengthOfLen ++ ; для ( int я = 0 ; я < lengthOfLen ; я ++ ) { len << = 1 ; если ( средство чтения . inputBit ()) len | = 1 ; } для ( 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-представлением Хамады.)