7
правок
Изменения
Новая страница: «'''''Код Шеннона''''' — алгоритм префиксного кодирования алфавита, предложенный Клодом Шен...»
'''''Код Шеннона''''' — алгоритм префиксного кодирования алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.
'''Вход:''' <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов.
'''Выход:''' <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex> — набор кодовых слов, соответствующий входным данным.
== Определение ==
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов, <tex>s=\sum\limits_{i \in [1, n]}w_{i}</tex>, <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}</tex>. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:
1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>
2. <tex>c_{i}</tex> представляет собой <tex>\lceil -\log b_{i}\rceil</tex> коэффициентов двоичного разложения дроби <tex dpi = "160">{\frac{b_{i}}{s}}</tex>
называется '''кодом Шеннона'''.
}}
== Алгоритм построения бинарного кода Шеннона ==
# Сортируем элементы алфавита по не возрастанию весов.
# Элементу <tex>a_{x}</tex> ставим в соответствие число <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}</tex>, при этом <tex>b_{1}=0</tex>.
# Представляем каждое число <tex dpi = "160">{\frac{b_{x}}{s}}</tex>, где <tex>s=\sum\limits_{i \in [1, n]}w_{i}</tex>, в виде двоичной дроби.
# В качестве кодового слова для <tex>a_{x}</tex> используем первые <tex>L_{x}=\lceil -\log b_{x}\rceil</tex> коэффициентов представления дроби <tex dpi = "160">{\frac{b_{x}}{s}}</tex>. (<tex>\lceil z \rceil</tex> — наименьшее целое число, не меньшее <tex> z </tex>)
=== Пример ===
Для примера возьмём алфавит <tex>A=\{a,b,c,d,e\}</tex>, а набор весов <tex>W=\{5,2,6,1,2\}</tex>:
{| class="wikitable"
! Символ || a || b || c || d || e
|-
| Вес || 5 || 2 || 6 || 1 || 2
|}
По алгоритму сортируем элементы алфавита по не возрастанию весов:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| Вес || 6 || 5 || 2 || 2 || 1
|}
Каждому символу <tex>a_{x}</tex> сопоставляем <tex>b_{x}</tex>:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| Вес || 6 || 5 || 2 || 2 || 1
|-
| <tex>b_{x}</tex> || 0 || 6 || 11 || 13 || 15
|}
Посчитаем <tex dpi = "160">\frac{b_{x}}{s}</tex> и переведём в двоичную систему счисления:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| <tex dpi = "150">\frac{b_{x}}{s}</tex> || <tex>\frac{0}{16}</tex> || <tex>\frac{6}{16}</tex> || <tex>\frac{11}{16}</tex> || <tex>\frac{13}{16}</tex> || <tex>\frac{15}{16}</tex>
|}
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| <tex dpi = "150">\frac{b_{x}}{s}</tex> || 0.0000 || 0.0110 || 0.1011 || 0.1101 || 0.1111
|}
Посчитаем <tex>L_{x}</tex> и запишем коды:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| <tex>L_{x}</tex> || 2 || 2 || 3 || 3 || 4
|-
| Код || 00 || 01 || 101 || 110 || 1111
|}
== Декодирование ==
Для декодирования необходимо последовательно вычислять первые <tex>L_{x}</tex> цифр двоичной дроби <tex dpi = "160">\frac{b_{x}}{s}</tex> и сравнивать их с первыми <tex>L_{x}</tex> символами последовательности кодовых слов. Их совпадение определяет символ <tex>x</tex>.
== Литература ==
* Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.
'''Вход:''' <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов.
'''Выход:''' <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex> — набор кодовых слов, соответствующий входным данным.
== Определение ==
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов, <tex>s=\sum\limits_{i \in [1, n]}w_{i}</tex>, <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}</tex>. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:
1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>
2. <tex>c_{i}</tex> представляет собой <tex>\lceil -\log b_{i}\rceil</tex> коэффициентов двоичного разложения дроби <tex dpi = "160">{\frac{b_{i}}{s}}</tex>
называется '''кодом Шеннона'''.
}}
== Алгоритм построения бинарного кода Шеннона ==
# Сортируем элементы алфавита по не возрастанию весов.
# Элементу <tex>a_{x}</tex> ставим в соответствие число <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}</tex>, при этом <tex>b_{1}=0</tex>.
# Представляем каждое число <tex dpi = "160">{\frac{b_{x}}{s}}</tex>, где <tex>s=\sum\limits_{i \in [1, n]}w_{i}</tex>, в виде двоичной дроби.
# В качестве кодового слова для <tex>a_{x}</tex> используем первые <tex>L_{x}=\lceil -\log b_{x}\rceil</tex> коэффициентов представления дроби <tex dpi = "160">{\frac{b_{x}}{s}}</tex>. (<tex>\lceil z \rceil</tex> — наименьшее целое число, не меньшее <tex> z </tex>)
=== Пример ===
Для примера возьмём алфавит <tex>A=\{a,b,c,d,e\}</tex>, а набор весов <tex>W=\{5,2,6,1,2\}</tex>:
{| class="wikitable"
! Символ || a || b || c || d || e
|-
| Вес || 5 || 2 || 6 || 1 || 2
|}
По алгоритму сортируем элементы алфавита по не возрастанию весов:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| Вес || 6 || 5 || 2 || 2 || 1
|}
Каждому символу <tex>a_{x}</tex> сопоставляем <tex>b_{x}</tex>:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| Вес || 6 || 5 || 2 || 2 || 1
|-
| <tex>b_{x}</tex> || 0 || 6 || 11 || 13 || 15
|}
Посчитаем <tex dpi = "160">\frac{b_{x}}{s}</tex> и переведём в двоичную систему счисления:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| <tex dpi = "150">\frac{b_{x}}{s}</tex> || <tex>\frac{0}{16}</tex> || <tex>\frac{6}{16}</tex> || <tex>\frac{11}{16}</tex> || <tex>\frac{13}{16}</tex> || <tex>\frac{15}{16}</tex>
|}
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| <tex dpi = "150">\frac{b_{x}}{s}</tex> || 0.0000 || 0.0110 || 0.1011 || 0.1101 || 0.1111
|}
Посчитаем <tex>L_{x}</tex> и запишем коды:
{| class="wikitable"
! Символ || c || a || b || e || d
|-
| <tex>L_{x}</tex> || 2 || 2 || 3 || 3 || 4
|-
| Код || 00 || 01 || 101 || 110 || 1111
|}
== Декодирование ==
Для декодирования необходимо последовательно вычислять первые <tex>L_{x}</tex> цифр двоичной дроби <tex dpi = "160">\frac{b_{x}}{s}</tex> и сравнивать их с первыми <tex>L_{x}</tex> символами последовательности кодовых слов. Их совпадение определяет символ <tex>x</tex>.
== Литература ==
* Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.
