В теории информации , Шеннон-Фано-Элиас кодирование является предшественником арифметического кодирования , в котором вероятности используются для определения кодовых слов. [1]
Учитывая дискретной случайной величины Х из упорядоченных значений, подлежащих кодированию, пустьесть вероятность для любого х в X . Определить функцию
Алгоритм:
- Для каждого x в X ,
- Пусть Z - двоичное разложение .
- Выберите длину кодировки x , , чтобы быть целым числом
- Выберите кодировку x , , будь первым Наиболее значимые биты после десятичной точки Z .
Пример
Пусть X = {A, B, C, D} с вероятностями p = {1/3, 1/4, 1/6, 1/4}.
- Для
- В двоичном формате Z (A) = 0,001 0101010 ...
- L (А) = = 3
- код (A) - 001
- Для B
- В двоичном формате Z (B) = 0,011 10101010101 ...
- L (B) = = 3
- код (B) - 011
- Для C
- В двоичной системе Z (C) = 0. 1010 10101010 ...
- L (C) = = 4
- код (C) - 1010
- Для D
- В двоичной, Z (D) = 0. 111
- L (D) = = 3
- код (D) 111
Код префикса
Кодирование Шеннона – Фано – Элиаса дает двоичный префиксный код , позволяющий осуществлять прямое декодирование.
Пусть bcode (x) будет рациональным числом, образованным добавлением десятичной точки перед двоичным кодом. Например, если code (C) = 1010, то bcode (C) = 0.1010. Для всех x, если не существует y такого, что
тогда все коды образуют префиксный код.
Сравнивая F с CDF X, это свойство может быть продемонстрировано графически для кодирования Шеннона – Фано – Элиаса.
По определению L следует, что
И поскольку биты после L (y) усекаются от F (y) для формирования кода (y), отсюда следует, что
таким образом, bcode (y) должен быть не меньше CDF (x).
Таким образом, приведенный выше график демонстрирует, что , поэтому свойство префикса сохраняется.
Длина кода
Средняя длина кода .
Таким образом, для H (X) энтропия случайной величины X,
Шеннон Фано Элиас кодирует от 1 до 2 дополнительных бит на символ из X, чем энтропия, поэтому на практике этот код не используется.