Код Шеннона

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

Вход: [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.