коды Голомба

Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства. Рассмотрим источник, независимым образом порождающий целые неотрицательные числа с вероятностями , где — произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число таково, что , то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной Соломоном Голомбом процедурой, согласно которой для любого кодируемого числа при известном кодовое слово образуют унарная запись числа и кодированный в соответствии с описанной ниже процедурой остаток от деления : 1. * Если является степенью числа 2, то код остатка представляет собой двоичную запись числа , размещённую в битах. 2. * Если не является степенью 2, вычисляется число . Далее:Если , код остатка представляет собой двоичную запись числа , размещённую в битах,иначе остаток кодируется двоичной записью числа , размещённой в битах. Позже Р. Галлагером и Д. Ван Вурхисом было показано, что предложенный Голомбом код оптимален не только для дискретного набора значений , удовлетворяющих приведённому выше критерию, но и для любых , для которых справедливо двойное неравенство , где — целое положительное число. Поскольку для любого всегда найдётся не более одного значения , удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения . Чрезвычайно простая в реализации, но не всегда оптимальная разновидность кода Голомба в случае, когда является степенью 2, называется кодом Райса.