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

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

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

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

, ;

откуда получаем

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

Известно, что H(x)<H_max(x), если априорные вероятности различных элементов сообщения различны (H(x)= H_max(x) при равной вероятности этих элементов). Но при неравной вероятности сообщений можно применить оптимальное (статистическое) кодирование, при котором уменьшается средняя длительность сообщений.

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

Рассмотрим принципы оптимального кодирования на приводимом ниже примере.

Пусть источник сообщений выдаёт 8 различных сообщений x₁ ... x₈ с вероятностями 0,495; 0,4; 0,026; 0,02; 0,018; 0,016; 0,015; 0,01 (сумма вероятностей равна 1).

Располагаем эти сообщения столбцом в порядке убывания вероятностей (рис. 6). Объединяем два сообщения с самыми минимальными вероятностями двумя прямыми и в месте их соединения записываем суммарную вероятность: p(x₇)+p(x₈)=0,015+0,01=0,025. В дальнейшем полученное число 0,025 учитываем в последующих расчётах наравне с другими оставшимися числами, кроме чисел 0,015 и 0,01. Эти уже использованные числа из дальнейшего расчёта исключаются.

Далее таким же образом объединяются числа 0,018 и 0,016, получается число 0,034, затем вновь объединяются два минимальных числа (0,02 и 0,025) и т.д.

Построенное таким образом кодовое дерево используется для определённых кодовых комбинаций. Напомним, что для нахождения любой кодовой комбинации надо исходить их корня дерева (точка с вероятностью 1) и двигаться по ветвям дерева к соответствующим сообщениям x₁... x₈. При движении по верхней ветви элемент двоичного кода равен нулю, а при движении по нижней – равен единице. Например, сообщению x₅ будет соответствовать комбинация 11010. Справа от кодового дерева записаны кодовые комбинации полученного неравномерного кода. В соответствии с поставленной задачей, наиболее часто встречающееся сообщение x₁ (вероятность 0,495) имеет длительность в 1 элемент, а наиболее редко встречающиеся комбинации имеют длительность в 5 элементов. В двух последних столбцах рисунка приведено число элементов N_э_i в кодовой комбинации и величина произведения p(x_i)×N_э_i , а представляет собой число элементов, приходящееся на одну комбинацию, т.е. в данном случае .

Если бы для кодирования был применён равномерный двоичный код, который чаще всего применяется на практике, число элементов в каждой кодовой комбинации для кодирования восьми различных сообщений равнялось бы трём (2³=8), т.е. .

В рассматриваемом примере средняя длительность комбинаций благодаря применённому статистическому кодированию уменьшилась в 3/1,774=1,72 раза. Во столько же раз увеличилась и производительность источника (24).

Вопросы к разделу 9

1. Какая цель достигается при оптимальном кодировании дискретных сообщений?

2. Почему оптимальное кодирование называется оптимальным и почему статистическим?

3. В чём заключается идея оптимального кодирования?

4. Как осуществляется процесс кодирования дискретных сообщений оптимальным кодом по методу Шеннона - Фано - Хаффмена?

5. Почему код Шеннона - Фано должен быть неравномерным и неприводимым?

10. Статистическое кодирование кодовых слов

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

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

p(а₁а₁)=0,8×0,8=0,64;

p(а₁а₂)= p(а₂а₁)=0,8×0,2=0,16;

p(а₂а₂)=0,2×0,2=0,04.

Применяя к полученным словам кодирование по методу Шеннона‑Фано, получаем кодовое дерево (рис. 7), из которого видно, что новые комбинации неравномерного кода имеют длительность t_э, 2t_э и 3t_э.

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

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

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

Энтропия источника

При отсутствии статистического кодирования ,

бит/с.

При кодировании слов по две буквы ,

бит/с.

При кодировании по две буквы

бит/с.

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

Статистическое кодирование слов целесообразно применять также в случае использования эргодического дискретного источника (источника с корреляционными связями букв), так как объединение букв в слова приводит к разрушению корреляционных связей (величина n должна быть не менее порядка эргодического источника, а n×t_э, соответственно, больше интервала корреляции букв первичного сообщения). Корреляционные связи между буквами трансформируются в различные вероятности появления возможных слов (n - буквенных сочетаний).

При этом необходимо помнить, что вероятность n‑буквенных сочетаний определяется не произведением вероятностей отдельных букв, а, в соответствии с теоремой умножения, вероятностей надо учитывать также условные вероятности. Так, например, для источника с независимым выбором букв p(a₁a₁)=p(a₁)×p(a₁), а для эргодического источника с корреляционными связями букв p(a₁a₁)=p(a₁)×p(a₁/a₁).

Вопросы к разделу 10

1. Какая цель достигается объединением букв в слова при оптимальном кодировании источников независимых сообщений?

2. Что является математической моделью источников сообщений с корреляционными связями?

3. Какая цель достигается объединением букв в слова при оптимальном кодировании источников зависимых сообщений, как выбирается длина кодовых слов?

4. Как осуществляется оптимальное кодирование сообщений с корреляционными связями?

5. В чём отличия алгоритмов оптимального кодирования кодовых слов для источников независимых и зависимых сообщений?

Дата добавления: 2018-02-15; просмотров: 1468; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!