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

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

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

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

2017-10-11 525
Кодирование сообщений при передаче по каналу без помех 0.00 из 5.00 0 оценок
Заказать работу

 

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

 

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

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

Это равенство можно представить в виде

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

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

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

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

 

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

 

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

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

 

 

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

 

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

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

 

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

Теорема. Если целые числа удовлетворяют неравенству

(4.7)

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

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

Доказательство. Пусть числа удовлетворяют неравенству (4.7).

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

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

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

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

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

 


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

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.013 с.