Статистическое кодирование дискретных сообщений

Статистическое кодирование дискретных сообщений. Энтропия непрерывного источника. Пропускная способность непрерывного канала связи.

Используя теорему К. Шеннона, сформулированную в предыдущем разде­ле, можно увеличить производительность источника дискретных сообщений, если априорные вероятности различных элементов сообщения неодинаковы, К.Шеннон предложил и метод такого кодирования, который получил название статистического или оптимального кодирования. В дальнейшем идея такого кодирования была развита в работах Фано и Хаффмена и в настоящее время широко используется на практике для "сжатия сообщений".

Основой статистического (оптимального) кодирования сообщений являет­ся теорема К. Шеннона для каналов связи без помех.

Кодирование по методу Шеннона-Фано-Хаффмена называется оптималь­ным, так как при этом повышается производительность дискретного источника, и статистическим, так как для реализации оптимального кодирования необхо­димо учитывать вероятности появления на выходе источника каждого элемента сообщения (учитывать статистику сообщений).

Используя определения производительности и избыточности дискретного источника, приведённые можно получить

Из этой формулы видно, что для увеличения производительности нужно уменьшать избыточность χ или среднюю длительность сообщений.

Идея статического кодирования заключается в том, что, применяя неравномерный неприводимый код, наиболее часто встречающиеся сообщения (буквы или слова) кодируются короткими кодовыми словами этого кода, а ред­ко встречающиеся сообщения кодируются более длительными кодовыми сло­вами.

Рассмотрим принципы оптимального кодирования на приводимом ниже примере. Пусть источник сообщений выдаёт 8 различных сообщений x1…x8 с вероятностями 0,495; 0,4; 0,026; 0,02; 0,018; 0,016; 0,015; 0,01 (сумма вероятно­стей равна 1).

Располагаем эти сообщения столбцом в порядке убывание вероятностей.

{x_i, p(x_i)} Кодовое дерево Код N_i p(x)N_i

------------- -----------------

x₁ 0,495 0 1 0,495

x₂ 0,4 10 2 0,8

x₃ 0,026 1100 4 0,104

x₄ 0,02 1110 4 0,08

x₅ 0,018 11010 5 0,09

x₆ 0,016 11011 5 0,08

x₇ 0,015 11110 5 0,075

x₈ 0,01 11111 5 0,05

------------- ---------------------

Рисунок 6 - Статистическое кодирование

Объединяем два сообщения с самыми минимальными вероятностями дву­мя прямыми и в месте их соединения записываем суммарную вероятность: p(x7)+p(x8)=0,015+0,01=0,025. В дальнейшем полученное число 0,025 учитыва­ем в последующих расчётах наравне с другими оставшимися числами, кроме чисел 0,015 и 0,01. Эти уже использованные числа из дальнейшего расчёта ис­ключаются. Далее таким же образом объединяются числа 0,018 и 0,016, получа­ется число 0,034, затем вновь объединяются два минимальных числа (0,02 и 0,026) и т.д.

Построенное таким образом кодовое дерево используется для определения кодовых слов нового кода. Напомним, что для нахождения любого кодового слова надо исходить из корня дерева (точка с вероятностью 1) и двигаться по ветвям дерева к соответствующим сообщениям x1…x8­. При движении по верх­ней ветви элемент двоичного кода равен нулю, а при движении по нижней - равен единице. Например, сообщению x5 будет соответствовать комбинация 11010. Справа от кодового дерева записаны кодовые слова полученного нерав­номерного кода. В соответствии с поставленной задачей, наиболее часто встре­чающееся сообщение x1 (вероятность 0,495) имеет длительность в 1 элемент, а наиболее редко встречающиеся имеют длительность в 5 элементов. В двух по­следних столбцах рисунка приведено число элементов Ni в кодовом слове и величина произведения p(xi)Ni=∑ p(xi)Ni= 1,774представляет собой число элементов, приходящееся на одно слово, т.е. в данном случае .

Если бы для кодирования был применён равномерный двоичный код, который чаще всего применяется на практике, число элементов в каждом кодовом слове для кодирования восьми различных сообщений равнялось бы трём (2³=8), т.е. .. В рассматриваемом примере средняя длительность кодового слова благодаря применённому статистическому кодированию уменьшилась в 3/1,774=1,72 раза. Во столько же раз увеличилась и производительность источника.

Дальнейшим развитием оптимального статистического кодирования явля­ется кодирование кодовых слов. В этом методе применяется также оптимальное кодирование по методу Шеннона-Фано-Хаффмена, однако не к отдельным бук­вам, а к кодовым словам( сочетаниямn букв первичного сообщения). Статисти­ческое кодирование слов позволяет ещё больше уменьшить среднюю длитель­ность сообщений, так как алфавит источника быстро увеличивается с увеличе­нием длины слова. Число возможных кодовых слов (алфавит источника после объединения букв) определяется выражением m=kⁿ, где k - алфавит букв первичного сообщения. Пусть, например, у нас имеется двоичный источник с ал­фавитомa₁ и a₂ (например, “1” и “0”). При передаче этих букв по каналу связи используются сигналы длительностью τ_э, а =τ_э.

Рассмотрим пример, когда p(a₁)=0,8 и p(a₂)=0,2 (если вероятности p(a₁) и p(a₂) равны между собой, никакое кодирование не может уменьшить среднюю длительность сообщения). Образуем из элементов a₁ и a₂ слова из двух букв (n=2), беря различные сочетания из этих букв. Если у нас источник с независимым выбором элементов сообщений, то

p(a₁a₁)=0,8*0,8=0,64;

p(a₁a₂)= p(a₂a₁)=0,8*0,2=0,16;

p(a₂a₂)=0,2*0,2=0,04.

Применяя к полученным словам кодирование по методу Шеннона-Фано-Хаффмена, получаем кодовое дерево (рисунок 2.6), из которого видно, что новые кодовые слова неравномерного кода имеют длительность τ_э, 2τ_э и 3τ_э.

Средняя длина кодового слова

τ_сл=0,64τ_э+0,16*2τ_э+0,16*3τ_э+ 0,04*3τ_э=1,56τ_э.

Но так как каждое слово содержит информацию о двух буквах первичного сообщения, то в расчёте на 1 букву получаем τэ, Отсюда видно, что средняя длина элемента сообщения сократилась по сравнению с первоначальной в 1/0,78=1,38 раза.

a₁a₁

a₁a₂

a₂a₁

a₂a₂

Рисунок 7 – Алфавит источника после объединения букв

Если усложнить кодирование и использовать n=3, то в этом случае полу­чим . Это уже почти предел, дальше уменьшать n уже нецелесооб­разно. Чтобы убедиться в этом, рассчитаем производительность источника со­общений для всех трёх случаев. Энтропия источника

бит.

Последняя величина близка к предельно возможной величине 1/ τ_э.

Статистическое кодирование слов целесообразно применять также в слу­чае использования эргодического дискретного источника (источника с корре­ляционными связями букв), так как объединение букв в слова приводит к раз­рушению корреляционных связей (величина nдолжна быть не менее порядка эргодического источника, а nτ_э, соответственно, больше интервала корреляции букв первичного сообщения). Корреляционные связи между буквами транс­формируются в различные вероятности появления возможных слов (n -буквен­ных сочетаний). При этом необходимо помнить, что вероятность n-буквенных сочетаний определяется не произведением вероятностей отдельных букв, а, в соответствии с теоремой умножения вероятностей надо учитывать также ус­ловные вероятности. Так, например, для источника с независимым выбором букв p(a₁a₁)=p(a₁)p(a₁), эргодического источника с корреляционными связями букв p(a₁a₁)=p(a₁)p(a₁/a₁).