Коды Голомба


Коды Голомба

Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства.

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа i с вероятностями P(i) = (1-p)p^{i}, где p — произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число m таково, что

p^m = \frac 1 2 ,

то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной С. Голомбом процедурой, согласно которой для любого кодируемого числа n при известном m кодовое слово образуют унарная запись числа q = \left[ \frac{n}{m}\right] и кодированный в соответствии с описанной ниже процедурой остаток r от деления \frac{n}{m}:

  1. Если m является степенью числа 2, то код остатка представляет собой двоичную запись числа r, размещённую в \log_2(m) битах.
  2. Если m не является степенью 2, вычисляется число b = \lceil\log_2(m)\rceil. Далее:
Если r < 2^b-m , код остатка представляет собой двоичную запись числа r, размещённую в b-1 битах,
иначе остаток r кодируется двоичной записью числа r+2^b-m, размещённой в b битах.

Позже Р. Галлагером и Д. Ван Вурхисом было показано, что предложенный Голомбом код оптимален не только для дискретного набора значений p, удовлетворяющих приведённому выше критерию, но и для любых p, для которых справедливо двойное неравенство

p^{m} + p^{m+1} \le 1 < p^{m} + p^{m-1},

где m — целое положительное число. Поскольку для любого p всегда найдётся не более одного значения m, удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения p.

Чрезвычайно простая в реализации, но не всегда оптимальная разновидность кода Голомба в случае, когда m является степенью 2, называется кодом Райса.

Пример

Пусть p = 0.85, требуется закодировать число n = 13.

Удовлетворяющее двойному неравенству Галлагера — Ван Вурхиса значение m = 4.

В соответствии с описанной выше процедурой кодирования кодовое слово, соответствующее кодируемому числу 13, строится как унарная запись частного от деления n/m:

 q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3 ,

(унарный код  0001 , то есть q нулей с завершающей единицей),

и кодированного остатка

r = 1,

(код  01 , то есть собственно остаток, записанный в \lceil\log_2(m)\rceil битах).

Результирующее кодовое слово

 0001|01

См. также

Ссылки


Wikimedia Foundation. 2010.

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

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

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

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

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

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

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

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

  • Алгоритм Шеннона — Фано — Алгоритм Шеннона  Фано  один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано (англ. Fano). Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет …   Википедия

  • Кодирование Шеннона-Фано — Алгоритм Шеннона Фано  один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм… …   Википедия

  • Код Шеннона-Фано — Алгоритм Шеннона Фано  один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм… …   Википедия


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

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

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