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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''''Код Шеннона''''' — алгоритм префиксного кодирования алфавита, предложенный Клодом Шен...»)
 
Строка 1: Строка 1:
'''''Код Шеннона''''' — алгоритм префиксного кодирования алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.
+
'''''Код Шеннона''''' — алгоритм [[Кодирование информации#Префиксный код | префиксного кодирования]] алфавита, предложенный Клодом Шенноном, в котором используется избыточность сообщения, заключённая в неоднородном распределении частот символов первичного алфавита, то есть заменяет коды более частых символов короткими последовательностями, а коды более редких символов — более длинными последовательностями.
  
'''Вход:''' <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов.
+
'''Вход:''' <tex>A=\{a_{1},a_{2},\dots,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов с вероятностями <tex>P=\{p_{1},p_{2},\dots,p_{n}\}</tex>.
  
'''Выход:''' <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex> — набор кодовых слов, соответствующий входным данным.
+
'''Выход:''' <tex>C=\{c_{1},c_{2},\dots,c_{n}\}</tex> — набор кодовых слов, соответствующий входным данным.
  
 
== Определение ==
 
== Определение ==
Строка 9: Строка 9:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|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>, такой, что:
+
Пусть <tex>A=\{a_{1},a_{2},\dots,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов с вероятностями <tex>P=\{p_{1},p_{2},\dots,p_{n}\}</tex>, <tex>b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}</tex>.  Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},\dots,c_{n}\}</tex>, такой, что:
  
 
1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</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>
+
2. <tex>c_{i}</tex> представляет собой <tex>\lceil -\log p_{i}\rceil</tex> коэффициентов двоичного разложения числа <tex>{b_{i}}</tex>
  
 
называется '''кодом Шеннона'''.
 
называется '''кодом Шеннона'''.
 
}}
 
}}
 
 
== Алгоритм построения бинарного кода Шеннона ==
 
== Алгоритм построения бинарного кода Шеннона ==
  
# Сортируем элементы алфавита по не возрастанию весов.
+
Пусть нам даны наборы <tex>A</tex> и <tex>P</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>b_{x}=\sum\limits_{i \in [1, x - 1]}p_{i}</tex>, при этом <tex>b_{1}=0</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>{b_{x}}</tex> в виде двоичной дроби.
 +
# В качестве кодового слова для <tex>a_{x}</tex> использовать первые <tex>L_{x}=\lceil -\log p_{x}\rceil</tex> коэффициентов представления <tex>{b_{x}}</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>:
+
Для примера возьмём алфавит <tex>A=\{a,b,c,d,e,f\}</tex> и набор <tex>P</tex>:
  
 
{| class="wikitable"
 
{| class="wikitable"
! Символ || a || b || c || d || e
+
! Символ || a || b || c || d || e || f
 
|-
 
|-
| Вес || 5 || 2 || 6 || 1 || 2
+
| <tex>p_{x}</tex> || 0,10 || 0,20 || 0,10 || 0,10 || 0,35 || 0,15
 
|}
 
|}
  
По алгоритму сортируем элементы алфавита по не возрастанию весов:
+
По алгоритму сортируем элементы алфавита по не возрастанию <tex>p_{x}</tex>:
  
 
{| class="wikitable"
 
{| class="wikitable"
! Символ || c || a || b || e || d
+
! Символ || e || b || f || a || c || d
 
|-
 
|-
| Вес || 6 || 5 || 2 || 2 || 1
+
| <tex>p_{x}</tex> || 0,35 || 0,20 || 0,15 || 0,10 || 0,10 || 0,10
 
|}
 
|}
  
Строка 46: Строка 46:
  
 
{| class="wikitable"
 
{| class="wikitable"
! Символ || c || a || b || e || d
+
! Символ || e || b || f || a || c || d
 
|-
 
|-
| Вес || 6 || 5 || 2 || 2 || 1
+
| <tex>b_{x}</tex> || 0,00 || 0,35 || 0,55 || 0,70 || 0,80 || 0,90
|-
 
| <tex>b_{x}</tex> || 0 || 6 || 11 || 13 || 15
 
 
|}
 
|}
  
Посчитаем <tex dpi = "160">\frac{b_{x}}{s}</tex> и переведём в двоичную систему счисления:
+
Переведём <tex>b_{x}</tex> в двоичную систему счисления:
  
 
{| class="wikitable"
 
{| class="wikitable"
! Символ || c || a || b || e || d
+
! Символ || e || b || f || a || c || 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>
+
| <tex>b_{x}</tex> || 0,00000 || 0,01010 || 0,10001 || 0,10110 || 0,11001 || 0,11100
|}
 
 
 
{| 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
 
 
|}
 
|}
  
Строка 70: Строка 62:
  
 
{| class="wikitable"
 
{| class="wikitable"
! Символ || c || a || b || e || d
+
! Символ || e || b || f || a || c || d
 
|-
 
|-
| <tex>L_{x}</tex> || 2 || 2 || 3 || 3 || 4
+
| <tex>L_{x}</tex> || 2 || 3 || 3 || 4 || 4 || 4
 
|-
 
|-
| Код || 00 || 01 || 101 || 110 || 1111
+
| Код || 00 || 010 || 100 || 1011 || 1100 || 1110
 
|}
 
|}
  
== Декодирование ==
+
{{Утверждение
 +
|statement=
 +
Код Шеннона является префиксным
 +
|proof=
 +
Для доказательства выбираем два произвольных кодовых слова с номерами <tex>i</tex> и <tex>j</tex>, <tex>i</tex><tex><</tex><tex>j</tex>. Кодовое слово <tex>c_{i}</tex> заведомо короче, чем <tex>c_{j}</tex>, поэтому достаточно доказать, что эти слова отличаются в одном из первых <tex>L_{i}</tex> символов. Рассмотрим разность:
 +
<tex>b_{j} - b_{i}</tex> = <tex>\sum\limits_{k \in [1, j - 1]}p_{k} - \sum\limits_{k \in [1, i - 1]}p_{k} = \sum\limits_{k \in [i, j - 1]}p_{k} \geqslant p_{i}</tex>.
  
Для декодирования необходимо последовательно вычислять первые <tex>L_{x}</tex> цифр двоичной дроби <tex dpi = "160">\frac{b_{x}}{s}</tex> и сравнивать их с первыми <tex>L_{x}</tex> символами последовательности кодовых слов. Их совпадение определяет символ <tex>x</tex>.
+
Длина слова и его вероятность связаны соотношением
 +
<tex>L_{i} = \lceil -\log p_{i}\rceil \geqslant -\log p_{i}</tex>.
 +
Поэтому <tex>p_{i} \geqslant 2^{-L_{i}}</tex>. С учётом этого неравенства получаем, что <tex>b_{j} - b_{i} \geqslant 2^{-L_{i}}</tex>.
 +
В двоичной записи числа в правой части мы имеем после запятой <tex>L_{i} - 1</tex> нулей и единицу в позиции с номером <tex>L_{i}</tex>. Поэтому по меньшей мере в одном из <tex>L_{i}</tex> разрядов слова <tex>c_{i}</tex> и <tex>c_{j}</tex> отличаются и, следовательно, <tex>c_{i}</tex> не является префиксов для <tex>c_{j}</tex>. Это верно для любой пары слов, так как <tex>i</tex> и <tex>j</tex> были выбраны произвольно. Значит, код является префиксным.
 +
}}
 +
== См.также ==
 +
* [[Алгоритм Хаффмана]]
 +
* [[Арифметическое кодирование]]
  
== Литература ==
+
== Источники информации ==
 
* Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.
 
* Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.
 +
* Б. Д. Кудряшов Теория информации. С.—Пб.: Питер, 2009 — с. 36.
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Алгоритмы сжатия ]]

Версия 15:16, 8 января 2015

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

Вход: [math]A=\{a_{1},a_{2},\dots,a_{n}\}[/math] — алфавит из [math]n[/math] различных символов с вероятностями [math]P=\{p_{1},p_{2},\dots,p_{n}\}[/math].

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

Определение

Определение:
Пусть [math]A=\{a_{1},a_{2},\dots,a_{n}\}[/math] — алфавит из [math]n[/math] различных символов с вероятностями [math]P=\{p_{1},p_{2},\dots,p_{n}\}[/math], [math]b_{x}=\sum\limits_{i \in [1, x - 1]}w_{i}[/math]. Тогда набор бинарных кодов [math]C=\{c_{1},c_{2},\dots,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 p_{i}\rceil[/math] коэффициентов двоичного разложения числа [math]{b_{i}}[/math]

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

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

Пусть нам даны наборы [math]A[/math] и [math]P[/math], тогда для нахождения кодовых слов необходимо:

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

Пример

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

Символ a b c d e f
[math]p_{x}[/math] 0,10 0,20 0,10 0,10 0,35 0,15

По алгоритму сортируем элементы алфавита по не возрастанию [math]p_{x}[/math]:

Символ e b f a c d
[math]p_{x}[/math] 0,35 0,20 0,15 0,10 0,10 0,10

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

Символ e b f a c d
[math]b_{x}[/math] 0,00 0,35 0,55 0,70 0,80 0,90

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

Символ e b f a c d
[math]b_{x}[/math] 0,00000 0,01010 0,10001 0,10110 0,11001 0,11100

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

Символ e b f a c d
[math]L_{x}[/math] 2 3 3 4 4 4
Код 00 010 100 1011 1100 1110
Утверждение:
Код Шеннона является префиксным
[math]\triangleright[/math]

Для доказательства выбираем два произвольных кодовых слова с номерами [math]i[/math] и [math]j[/math], [math]i[/math][math]\lt [/math][math]j[/math]. Кодовое слово [math]c_{i}[/math] заведомо короче, чем [math]c_{j}[/math], поэтому достаточно доказать, что эти слова отличаются в одном из первых [math]L_{i}[/math] символов. Рассмотрим разность: [math]b_{j} - b_{i}[/math] = [math]\sum\limits_{k \in [1, j - 1]}p_{k} - \sum\limits_{k \in [1, i - 1]}p_{k} = \sum\limits_{k \in [i, j - 1]}p_{k} \geqslant p_{i}[/math].

Длина слова и его вероятность связаны соотношением [math]L_{i} = \lceil -\log p_{i}\rceil \geqslant -\log p_{i}[/math]. Поэтому [math]p_{i} \geqslant 2^{-L_{i}}[/math]. С учётом этого неравенства получаем, что [math]b_{j} - b_{i} \geqslant 2^{-L_{i}}[/math].

В двоичной записи числа в правой части мы имеем после запятой [math]L_{i} - 1[/math] нулей и единицу в позиции с номером [math]L_{i}[/math]. Поэтому по меньшей мере в одном из [math]L_{i}[/math] разрядов слова [math]c_{i}[/math] и [math]c_{j}[/math] отличаются и, следовательно, [math]c_{i}[/math] не является префиксов для [math]c_{j}[/math]. Это верно для любой пары слов, так как [math]i[/math] и [math]j[/math] были выбраны произвольно. Значит, код является префиксным.
[math]\triangleleft[/math]

См.также

Источники информации

  • Ю. М. Штарьков, “Обобщенные коды Шеннона”, Пробл. передачи информ., 20:3 (1984), 3—16 — с. 4.
  • Б. Д. Кудряшов Теория информации. С.—Пб.: Питер, 2009 — с. 36.