Гамма-код Элиаса

Гамма-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее.

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

1. Записать его в двоичной форме.
2. Перед двоичным представлением числа дописать нули. Количество нулей на единицу меньше количества битов двоичного представления числа.

Аналогичный способ описания этого процесса:

1. Выделить из целого числа старший значащий бит (самую большую степень 2, которую число включает — 2^N) и младшие N бит.
2. Записать N в унарном коде; то есть N нолей, за которыми следует единица.
3. Дописать N младших двоичных цифр числа следом за этим унарным кодом.

Начало кодирования:

Распределение предполагаемых вероятностей для кодов добавлено для ясности.

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

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

Гамма-кодирование используется в приложениях, где самое большое значение не может быть известно заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто чем большие.

Гамма-кодирование не подходит для кодирования нулевых значений или отрицательных чисел. Один из способов закодировать ноль — прибавить ко всем числам 1 до кодирования и отнять после декодирования. Другой способ — приписать в начале любого ненулевого кода 1 , а затем кодировать ноль как простой 0. Единственный способ закодировать все целые числа — перед началом кодирования установить биекцию (соответствие), отображая целые числа из (0, 1, −1, 2, −2, 3, −3, …) в (1, 2, 3, 4, 5, 6, 7, …).

// Кодирование void eliasGammaEncode(char* source, char* dest) {      IntReader intreader(source);      BitWriter bitwriter(dest);      while(intreader.hasLeft())      {       int num = intreader.getInt();       int l = log2(num);       for (int a=0; a < l; a++)       {                  bitwriter.putBit(false); //поместить нули, чтобы показать, сколько бит будут следовать       }       bitwriter.putBit(true); //пометить конец нолей       for (int a = l-1; a >= 0; a--) //записать биты как простые двоичные числа       {           if (num & (1 << a))              bitwriter.putBit(true);           else              bitwriter.putBit(false);       }      }      intreader.close();      bitwriter.close(); } // Декодирование void eliasGammaDecode(char* source, char* dest) {      BitReader bitreader(source);      BitWriter bitwriter(dest);      int numberBits = 0;      while(bitreader.hasLeft())      {         while(!bitreader.getBit() || bitreader.hasLeft())numberBits++; //продолжить чтение пока не встретится единица...         int current = 0;         for (int a=0; a < numberBits; a++) //прочитать numberBits битов         {             if (bitreader.getBit())                current += 1 << a;         }         //записать его как 32-битное число           current = current | ( 1 << numberBits ) ;//последний бит не декодируется!         for (int a=0; a < 32; a++) //прочитать numberBits битов         {             if (current & (1 << a))                bitwriter.putBit(true);             else                bitwriter.putBit(false);         }      } } 

• Омега-код Элиаса
• Дельта-код Элиаса

• Universal codeword sets and representations of the integers (англ.) // IEEE Transactions on Information Theory^[англ.] : journal. — 1975. — March (vol. 21, no. 2). — P. 194—203. — doi:10.1109/tit.1975.1055349.