Показать меню
Показать категории

Чем кодирование Голомба отличается от кодирования Фибоначчи?

+1 голос
421 просмотров
спросил(а) enginr (111 баллов) в категории Образование и наука

1 Ответ

+1 голос
 
Лучший ответ

Кодирование данных - основа всех методов сжатия информации, в основе которых лежит достаточно простая идея:

если часто используемые элементы представлять короткими кодами, в то время, как используемые редко — длинными,

то на каждый блок данных потребуется меньший объем памяти для его хранения,

в отличие от метода хранения данных,

при котором каждому элементу присваиваются коды одинаковой длины.

 

Существуют семейства универсальных и энтропийных кодов.

Так кодирование Фибоначчи — двоичный префиксный код переменной длины, относится к семейству универсальных кодов. Строится данный метод кодирования, как это и следует из названия, на основе последовательности Фибоначчи.

А именно на той ее особенности, что любое число можно представить в виде суммы некоторых её членов так, что никакие суммируемые элементы не будут в последовательности соседними.

В итоге, код состоит из последовательности бит-значений, чей вес соответствует элементам последовательности, завершаемой маркером конца кода.

Маркер состоит из двух последовательных единиц, из которых:

  • первая — старший установленный разряд,

  • вторая — незначащая.

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

 

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

Говоря об энтропийном кодировании, то предполагается, что:

-до кодирования; отдельные элементы последовательности имеют различную вероятность появления.

-после кодирования; вероятность появления отдельных символов практически одинакова (т. е. энтропия на символ максимальна).

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

Процедура кодирования, предложенная Голомбом, описывается нижеследующим примером. Допустим требуется закодировать число n=13,
при этом поток характеризуется следующими значениями:

p = 0.85

Удовлетворяющее неравенству pm=1/2, значение m:

m=4


 

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

q=n/m=13/4 =3, унарный код : q нулей с завершающей единицей, т. е. 0001

и кодированного остатка r=1, записанного в log2(m)-битах: 01

Откуда следует, что результирующее кодовое слово:

0001|01

ответил(а) Александра-lab (404 баллов)

Похожие вопросы

...