1 Теория информации Теорема кодирования Лекция 7. Теорема кодирования

символов, принадлежащих заданному алфавиту.
Цель − конструирование последовательностей символов, минимизирующих среднее

число символов, приходящихся на одно сообщение по ансамблю статистически независимых сообщений.

Лекция 7. Теорема кодирования

ансамбль из сообщений , ,...,

,..., с соответствующими вероятностями .
− число символов в алфавите.
– число символов в кодовом слове, соответствующем сообщению .
Среднее число символов на одно сообщение:
 

Найдем нижнюю границу для .

Лекция 7. Теорема кодирования

при

− пропускная способность кодового алфавита

Лекция 7. Теорема кодирования

близкой к нижней границе по Шеннону
В каждой из позиций

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

Лекция 7. Теорема кодирования

только концевым узлам, иначе алфавит становится троичным (0, 1, остановка).

Кодовое слово - совокупность указаний для достижения узла, соответствующего сообщению. Ни одно из кодовых слов не совпало с началом (префиксом) какого-либо более длинного кодового слова. Иначе при непрерывной передаче сообщений невозможно однозначно разбить последовательность символов на последовательные сообщения.

Лекция 7. Теорема кодирования

слов, соответствующих концевым узлам дерева с длинами, равными

.
Доказательство. Покажем сначала, что это соотношение необходимо.
Из каждого узла дерева исходит не более ветвей. Отсюда следует, что может быть не более узлов порядка .

Лекция 7. Теорема кодирования

чем ) исключает возможных

узлов порядка


 


Необходимость условия теоремы доказана.

Лекция 7. Теорема кодирования

с концевыми узлами, т. е. множество кодовых слов с заданными

длинами, может быть фактически построено.
Пусть .
Предположим, что удалось построить дерево, содержащее все заданные концевые узлы порядка, меньшего , и что дерево должно содержать концевых узлов порядка . Согласно условию

Лекция 7. Теорема кодирования

Теорема кодирования

узлов порядка :
Отсюда следует, что число доступных узлов

порядка не меньше заданного числа концевых узлов того же порядка, а потому все они могут быть включены в дерево. Что и требовалось доказать.

Лекция 7. Теорема кодирования

иметь или не иметь еще добавочные концевые узлы. Заданное множество

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

Лекция 7. Теорема кодирования

является необходимым и достаточным условием того, чтобы заданное множество концевых узлов было полным.
Теорема. Равенство ,  
где – целое положительное число, является необходимым и достаточным условием существования дерева с полным множеством из
концевых узлов.

Лекция 7. Теорема кодирования

дерево построено вплоть до порядка
– число промежуточных узлов порядка

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




Необходимость условия доказана.

Лекция 7. Теорема кодирования

сообщений с энтропией и алфавитом, состоящим из символов,

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

Лекция 7. Теорема кодирования

средней длиной
 

 необходимо и достаточно, чтобы для каждого сообщения выполнялось условие
 
, где - целое число.  
Когда это условие выполнено,
 

Лекция 7. Теорема кодирования

угодно малом положительном числе можно найти натуральное число

и соответствующее множество кодовых слов, такое, что среднее число символов на сообщение удовлетворяет неравенству
 
.
 Обратно, невозможно найти натуральное число и соответствующее множество кодовых слов, такое, что
 
.

Лекция 7. Теорема кодирования

; ;

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

Лекция 7. Теорема кодирования

получению оптимального множества кодовых слов в том смысле, что никакое

другое множество не имеет меньшего среднего числа символов на сообщение.
1-й шаг. сообщений располагаются в порядке убывания вероятностей.
2-й шаг. Пусть – целое число, удовлетворяющее двум требованиям
, , где - целое положительное число.

Лекция 7. Теорема кодирования

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

первоначального ансамбля образуем вспомогательный ансамбль сообщений, рассматривая подмножество из сообщений, образованных на 2-м шаге, как отдельное сообщение с вероятностью, равной вероятности всего подмножества. Вновь располагаем сообщения этого вспомогательного ансамбля в порядке убывания вероятностей.

Лекция 7. Теорема кодирования

D сообщений вспомогательного ансамбля, имеющих наименьшие вероятности, и вычисляем их

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

Лекция 7. Теорема кодирования

путем повторения 4-го и 5-го шагов, пока в ансамбле не

останется единственное сообщение с вероятностью единица.
7-й шаг. Проводя линии, соединяющие сообщения, образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно построить, приписывая различные символы из заданного алфавита ветвям, исходящим из каждого промежуточного узла. Только один из промежуточных узлов может иметь меньше чем
ветвей, а именно узел, образованный на 2-м шаге.

Лекция 7. Теорема кодирования

быть сопоставлены слова большей длины.
Условие 2. Два наименее вероятных сообщения

должны соответствовать кодовым словам одной и той же длины (максимальная длина), т. е. узлам одного и того же порядка.
Условие 3. Число концевых узлов порядка , сопоставленных сообщениям, и число
– промежуточных узлов порядка
должны удовлетворять неравенству
 
.

Лекция 7. Теорема кодирования

порядка меньшего, чем , должно

исходить
ветвей.
Условие 5. Предположим, что некоторый промежуточный узел преобразован в концевой, т. е. исключены все порождаемые им ветви и узлы. Сопоставим этому узлу составное сообщение, имеющее вероятность, равную сумме вероятностей сообщений, сопоставленных исключенным концевым узлам. Тогда, если первоначальное дерево было оптимальным для исходного ансамбля сообщений, новое дерево должно быть оптимальным для нового ансамбля сообщений.

Лекция 7. Теорема кодирования

порядка, меньшего , должен порождать ветвей.
Лекция

7. Теорема кодирования

букв:

Лекция 7. Теорема кодирования

)

Лекция 7. Теорема кодирования