Код Шеннона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''''Код Шеннона''''' — алгоритм префиксного кодирования алфавита, предложенный Клодом Шен...»)
(нет различий)

Версия 19:32, 7 января 2015

Код Шеннона — алгоритм префиксного кодирования алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.

Вход: [math]A=\{a_{1},a_{2},...,a_{n}\}[/math] — алфавит из n различных символов, [math]W=\{w_{1},w_{2},...,w_{n}\}[/math] — соответствующий ему набор положительных целых весов.

Выход: [math]C=\{c_{1},c_{2},...,c_{n}\}[/math] — набор кодовых слов, соответствующий входным данным.

Определение

Определение:
Пусть [math]A=\{a_{1},a_{2},...,a_{n}\}[/math] — алфавит из [math]n[/math] различных символов, [math]W=\{w_{1},w_{2},...,w_{n}\}[/math] — соответствующий ему набор положительных целых весов, [math]s=\sum\limits_{i \in [1, n]}w_{i}[/math], [math]b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}[/math]. Тогда набор бинарных кодов [math]C=\{c_{1},c_{2},...,c_{n}\}[/math], такой, что:

1. [math]c_{i}[/math] не является префиксом для [math]c_{j}[/math], при [math]i \ne j[/math]

2. [math]c_{i}[/math] представляет собой [math]\lceil -\log b_{i}\rceil[/math] коэффициентов двоичного разложения дроби [math]{\frac{b_{i}}{s}}[/math]

называется кодом Шеннона.


Алгоритм построения бинарного кода Шеннона

  1. Сортируем элементы алфавита по не возрастанию весов.
  2. Элементу [math]a_{x}[/math] ставим в соответствие число [math]b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}[/math], при этом [math]b_{1}=0[/math].
  3. Представляем каждое число [math]{\frac{b_{x}}{s}}[/math], где [math]s=\sum\limits_{i \in [1, n]}w_{i}[/math], в виде двоичной дроби.
  4. В качестве кодового слова для [math]a_{x}[/math] используем первые [math]L_{x}=\lceil -\log b_{x}\rceil[/math] коэффициентов представления дроби [math]{\frac{b_{x}}{s}}[/math]. ([math]\lceil z \rceil[/math] — наименьшее целое число, не меньшее [math] z [/math])

Пример

Для примера возьмём алфавит [math]A=\{a,b,c,d,e\}[/math], а набор весов [math]W=\{5,2,6,1,2\}[/math]:

Символ a b c d e
Вес 5 2 6 1 2

По алгоритму сортируем элементы алфавита по не возрастанию весов:

Символ c a b e d
Вес 6 5 2 2 1

Каждому символу [math]a_{x}[/math] сопоставляем [math]b_{x}[/math]:

Символ c a b e d
Вес 6 5 2 2 1
[math]b_{x}[/math] 0 6 11 13 15

Посчитаем [math]\frac{b_{x}}{s}[/math] и переведём в двоичную систему счисления:

Символ c a b e d
[math]\frac{b_{x}}{s}[/math] [math]\frac{0}{16}[/math] [math]\frac{6}{16}[/math] [math]\frac{11}{16}[/math] [math]\frac{13}{16}[/math] [math]\frac{15}{16}[/math]
Символ c a b e d
[math]\frac{b_{x}}{s}[/math] 0.0000 0.0110 0.1011 0.1101 0.1111

Посчитаем [math]L_{x}[/math] и запишем коды:

Символ c a b e d
[math]L_{x}[/math] 2 2 3 3 4
Код 00 01 101 110 1111

Декодирование

Для декодирования необходимо последовательно вычислять первые [math]L_{x}[/math] цифр двоичной дроби [math]\frac{b_{x}}{s}[/math] и сравнивать их с первыми [math]L_{x}[/math] символами последовательности кодовых слов. Их совпадение определяет символ [math]x[/math].

Литература

  • Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.