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


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

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

Содержание

Описание алгоритма

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

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

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

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

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

Число Значение Кодирование Предполагаемая
вероятность
1 20 + 0 1 1/2
2 21 + 0 01 0 1/8
3 21 + 1 01 1 1/8
4 2² + 0 001 00 1/32
5 2² + 1 001 01 1/32
6 2² + 2 001 10 1/32
7 2² + 3 001 11 1/32
8 2³ + 0 0001 000 1/128
9 2³ + 1 0001 001 1/128
10 2³ + 2 0001 010 1/128
11 2³ + 3 0001 011 1/128
12 2³ + 4 0001 100 1/128
13 2³ + 5 0001 101 1/128
14 2³ + 6 0001 110 1/128
15 2³ + 7 0001 111 1/128
16 24 + 0 00001 0000 1/512
17 24 + 1 00001 0001 1/512

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

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

  1. Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей.
  2. Принимая во внимание единицу, которая станет первым (самая значащим) битом целого числа, со значением 2N, считать оставшиеся 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=0; a < l; 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);
        }
     }
}

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Гамма-код Элиаса" в других словарях:

  • Дельта-код Элиаса —   это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Содержание 1 Кодирование 2 Декодирование 3 Эффективность …   Википедия

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

  • Экспоненциальный код Голомба — порядка k  это универсальный код, параметризованный целым числом k. Для кодирования неотрицательного числа в экспоненциальный код Голомба порядка k, можно использовать следующий метод: Взять число N в двоичном коде, без последних k цифр.… …   Википедия

  • Универсальный код — для целых чисел в сжатии данных  префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение  монотонно… …   Википедия

  • Универсальный код (сжатие данных) — Универсальный код для целых чисел в сжатии данных  префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распространение … …   Википедия

  • Энтропийное кодирование — Для термина «Кодирование» см. другие значения. Энтропийное кодирование  кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения… …   Википедия

  • Кодирование энтропии — кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых… …   Википедия

  • Кодирование с минимальной избыточностью — Кодирование энтропии кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных… …   Википедия

  • Энтропийное сжатие — Кодирование энтропии кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных… …   Википедия

  • Цветовая субдискретизация — (англ. Chroma subsampling) технология кодирования изображений со снижением цветового разрешения, при которой частота выборки цветоразностных сигналов может быть меньше частоты выборки яркостного сигнала. Основана на особенности человеческого …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.