Кодирование сообщений при передаче по каналу без помех

Возможность оптимального (эффективного) кодирования

Под кодированием будем понимать отображение состояний некоторой системы (источника сообщений) с помощью состояний сложного сигнала, который представляет собой последовательность из n элементарных сигналов. Множество Y состояний элементарного сигнала образует алфавит кода размера mу. При my=2 элементарный сигнал имеет два состояния, которые обозначим через 1 и 0. Состояние сложного сигнала описывается последовательностью из нулей и единиц, которая называется кодовым словом. Если кодовые слова имеют разную длину, то код называется неравномерным, а если одинаковую, то код называется равномерным.

Пусть источник сообщений вырабатывает последовательность из k букв, причем xi буква в этой последовательности появляется n раз. Каждой букве xi (i= кодирование сообщений при передаче по каналу без помех - student2.ru ) поставим в соответствие кодовое слово с длиной, равной li (посимвольное кодирование). Тогда длина соответствующей последовательности из кодовых слов будет равна кодирование сообщений при передаче по каналу без помех - student2.ru

Это равенство можно представить в виде кодирование сообщений при передаче по каналу без помех - student2.ru

При неограниченном увеличении числа букв К в последовательности относительная частота появления х{ буквы с вероятностью, равной единице, совпадает со значением вероятности pi появления этой буквы. Поэтому с вероятностью, равной единице, выполняется равенство кодирование сообщений при передаче по каналу без помех - student2.ru

кодирование сообщений при передаче по каналу без помех - student2.ru - по определению средняя длина кодового слова. Длина последовательности кодовых слов L является случайной величиной, но значительные отклонения ее от среднего значения кодирование сообщений при передаче по каналу без помех - student2.ruкодирование сообщений при передаче по каналу без помех - student2.ru маловероятны при неограниченном возрастании K.

Таким образом, источник сообщений с вероятностью, равной единице, вырабатывает типичные последовательности, длина которых мало отличается от их среднего значения К кодирование сообщений при передаче по каналу без помех - student2.ru .

Поскольку время передачи сообщений определяется длиной L, то имеется возможность его сокращения за счет уменьшения средней длины кодового слова кодирование сообщений при передаче по каналу без помех - student2.ru ( кодирование сообщений при передаче по каналу без помех - student2.ru ). Задача оптимального кодирования заключается в определении однозначно декодируемых кодовых слов с такими длинами, при которых их средняя длина минимальна.

Префиксные коды

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

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

кодирование сообщений при передаче по каналу без помех - student2.ru

Рис. 4.2. Полное троичное (mx=3) кодовое дерево третьего порядка (l=3): 1, 2, 3 узлы первого, второго, третьего порядков

Дерево представляет собой множество точек (узлов), соединенных отрезками, которые называются ребрами дерева. Из каждого узла выходят mу ребер, каждое из которых изображает соответствующий символ алфавита кода. Слова, состоящие всего из одной буквы, изображаются узлами первого порядка. Их число равно mу. Слова, состоящие из двух букв, изображаются узлами второго порядка и т. д. Причем узлов (слов) K-го порядка в mу раз больше, чем узлов (К-1)-го порядка, поскольку каждый узел предыдущего порядка порождает mу узлов следующего порядка. Конкретный вид кодового слова определяется по изображающему его узлу как последовательность ребер (букв), которые соединяют основание дерева с указанным узлом. В случае префиксных кодов на пути, соединяющем основание дерева с изображающим узлом, не может быть промежуточных изображающих узлов.

Поскольку с помощью дерева (рис. 4.2) можно изобразить все кодовые слова с длиной, меньшей или равной l, то оно называется полным деревом порядка l с алфавитом объема mу.

Неравенство Крафта

Теорема. Если целые числа кодирование сообщений при передаче по каналу без помех - student2.ru удовлетворяют неравенству

кодирование сообщений при передаче по каналу без помех - student2.ru (4.7)

то существует код, обладающий свойством префикса с алфавитом объема mу, длины кодовых слов в котором равны, этим числам. Обратно, длины кодовых слов любого кода, обладаю­щего свойством, префикса, удовлетворяют указанному неравенству.

Теорема не утверждает, что любой код с длинами кодовых слов, удовлетворяющими (4.7), является префиксным. Так, например, множество двоичных кодовых слов 0,00,11 удовлетворяет (4.7), но не обладает свойством префикса. Теорема утверждает только существование префиксного кода, но не указывает его конкретный вид. Кодовые слова 0,10,11 удовлетворяют неравенству (4.7) и обладают свойством префикса.

Доказательство. Пусть числа кодирование сообщений при передаче по каналу без помех - student2.ru удовлетворяют неравенству (4.7).

Покажем, как можно построить префиксный код с этими длинами кодовых слов, и тем самым докажем существование префиксного кода. Не нарушая общности доказательства, все числа можно перенумеровать в порядке возрастания их значений. Тогда будем иметь кодирование сообщений при передаче по каналу без помех - student2.ru . Построение будем вести на полном дереве порядка lN.

Построение сводится к последовательному выбору узлов порядков кодирование сообщений при передаче по каналу без помех - student2.ru , но так, чтобы очередной выбираемый узел не был порожден каким-либо ранее выбранным узлом. Первый узел (кодовое слово) выбирается произвольно из числа узлов порядка l1. Этот узел порождает кодирование сообщений при передаче по каналу без помех - student2.ru кодирование сообщений при передаче по каналу без помех - student2.ru -ю часть узлов более высокого порядка, которые уже не могут быть использованы. После выбора следующего узла порядка l2 уже кодирование сообщений при передаче по каналу без помех - student2.ru кодирование сообщений при передаче по каналу без помех - student2.ru часть узлов не может быть использована и т.д. После выбора (М-1)-го узла может быть использована кодирование сообщений при передаче по каналу без помех - student2.ru часть узлов порядка lN.

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

Отметим еще одно свойство кодовых слов. Если код однозначно декодируется, то его кодовые слова удовлетворяют неравенству Крафта. Доказательство можно найти, например, в работе [4].

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

Наши рекомендации