Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 64
Текст из файла (страница 64)
КОДИРОВАНИЕ ИСТОЧНИКОВ И КАНАЛОВ СВЯЗИ В предыдущей главе были установлены потенциальные возможности кодирования источников и каналов, которые определялись теоремами кодирования Шеннона. Однако ни формулировки, ни доказательства этих теорем не указывали прямо на способы кодирования и декодирования, которые обеспечивают эти потенциальные возможности. (Исключением было лишь кодирование в непрерывном канале с неограниченной полосой частот, когда постоянная скорость передачи при сколь угодно малой вероятности ошибок могла быть обеспечена при выборе ортогональных сигналов). Хотя исторически некоторые способы кодирования источников и каналов появились даже раньше теории Шеннона, она явилась мощным стимулом для поиска многих других, более эффективных методов, приближающихся к потенциально возможным.
Это обстоятельство вызвало большой поток работ, посвященных тематике конструктивных методов кодирования. В данной главе будут описаны основные подходы к кодированию источников и каналов связи, причем в отличие от математической теории кодирования мы остановимся здесь не столько на деталях доказательств различных свойств кодов, сколько на демонстрации энергетических, скоростных или спектральных выигрышей, которые обеспечивают данные методы по сравнению с "некодированной" передачей сообщений. Под кодированием в широком смысле понимают отображение сообщения в сигнал для передачи его по каналу.
Под кодированием в узком смысле понимают преобразование сообщений дискретного источника для передачи их по дискретному каналу. Если иное не указано, под словом кодирование далее будет подразумеваться кодирование в узком смысле. Реализация кодирования на передающей стороне всегда предполагает применение обратной процедуры — декодирования — для восстановления принятого сообщения. Устройства, осуществляющие кодирование и декодирование, называются соответственно кодер и декодер.
Вместе их называют кодеком. 7.1. КЛАССИФИКАЦИЯ МЕТОДОВ КОДИРОВАНИЯ Классификация рассматриваемых в данной главе методов кодирования приведена на рис. 7.1. Эта классификация не является исчерпывающей. В нее включены лищь некоторые методы, которые широко используются в современных системах связи. По своему назначению кодирование подразделяется на примитивное, экономное и помехоустойчивое.
Примитивное, или безызбыточное, кодирование применяется для согласования алфавита источника и алфавита канала. Пример, приведенный в табл. 7.1, показывает, как сообщения дискретного источника с объемом алфавита К = 4 могут быть преобразованы для передачи по, дискретному двоичному каналу. Отличительное свойство примитивного кодирования состоит в том, что избыточность дискретного источника, образованного выходом примитивного кодера, равна избыточности источника на входе кодера. 257 Примитивное кодирование используется также в целях шифрования передаваемой информации и повышения устойчивости работы системы синхронизации.
В последнем случае правило кодирования выбирается так, чтобы вероятность появления на выходе кодера длинной последовательности, состоящей только из нулей или только из единиц, была минимальной. Подобный кодер называется также скремблераи (от английского слова "зсгашЫе" — перемешивать).
Особенности систем шифрования и синхронизации изучаются в специальных курсах и здесь не рассматриваются. Экономное кодирование, или сжатие данных, применяется для уменьшения времени передачи информации или требуемого объема памяти при ее хранении. Отличительное свойство экономного кодирования состоит в том, что избыточность источника, образованного выходом кодера, меньше, чем избыточность источника на входе кодера. Экономное кодирование применяется в ЭВМ.
Так, последние версии операционных систем обязательно содержат в своем составе программы сжатия данных (динамические компрессоры и архиваторы), а новый стандарт 'Ч.42Ьи на модемы для связи между ЭВМ по телефонным сетям общего пользования включает сжатие в число процедур обработки данных. Помехоустойчивое, или избыточное, кодирование применяется для обнаружения и(или) исправления ошибок, возникающих при передаче по дискретному каналу. Отличительное свойство помехоустойчивого кодирования состоит в том, что избыточность источника, образованного выходом кодера, больше, чем избыточность источника на входе кодера.
Помехоустойчивое кодирование используется в различных системах связи, при хранении и передаче данных 258 в сетях ЭВМ, в бытовой и профессиональной аудио- и видеотехнике, основан- ной на цифровой записи. 7.2. КОНСТРУКТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ ИСТОЧНИКОВ СООБЩЕНИЙ Су1цествует множество 'способов кодирования источников сообщений. Многие способы реализованы на практике, особенно для сжатия сообщений с большой избыточностью, например факсимильных и телевизионных, где они позволяют увеличить скорость передачи сообщений в десятки раз (см.гл.11). В данном параграфе мы рассмотрим сначала кодирование источников с известной статистикой сообщений.
Общая идея построения такого кода подсказывается теоремой кодирования 1 для каналов без помех. Поскольку минимизируется средняя длина кодовой последовательности, то код должен быть неравномерным. Очевидно, что средняя длина неравномерного кода будет минимизироваться тогда, когда с более вероятными сообщениями источника будут сопоставляться более короткие комбинации канальных символов. Проблема, однако, состоит в том, что у неравномерного кода на приемной стороне оказываются неизвестными границы этих комбинаций.
Если же мы попытаемся их выделить, используя известный способ кодирования, то декодирование может оказаться неоднозначным. (Действительно, если, например, с буквой А сопоставлена комбинация О, с буквой Б — 1, а с буквой С вЂ” 10, то невозможно определить по принятой комбинации 10, передавались ли буква С или пара букв А и Б). Для того чтобы используемый код обладал свойством однозначной декодируемости, он, очевидно, должен удовлетворять некоторым условиям. Однозначное декодирование. будет обеспечено, если ни одно кодовое слово не является началом другого кодового слова.
Такие коды называются префиксными. Необходимые и достаточные условия существования префнксното кода определяются неравенством Крафта, которое мы сформулируем в виде теоремы. Теорема 7.1. Пусть т — обЪем алфавита дискретного канала без помех, а пь ! = 1, 2, ..., М," есть конечное множесп!во положительных целых чисел. лр!л существования семейства М последовательностей с длинами пь пв ..., пм, обладающего свойством префиксного кода, необходимо и доспиппочно выполнение следующего неравенства: м ~Ут ' <1. (7.1) ! ! Докажем достаточность.
Пусть множество п!, пь..., пм удовлетворяет неравенству (7.1). Перепишем это неравенство в виде ~!о,!и ' <1, / 1 где ит — число последовательностей длины !' и и = шахи!. I Далее преобразуем это неравенство, раскрыв сумму н „< т" — ьу,т" ' —...— ьу„!и. (7.2) Поскольку все ит неотрицатгльны, то из (7.2) последовательно получим систему нера- венств и-1 и-2 гу < т -уу и —...— 3у т л-1 1 и-2 -г ,-3 н и-2 и 3'гт "' и-Зи (7.4) 260 (7.3) 3 2 Нг <т — уг,т г ЪУ'1 < и Эта система неравенств и определяет способ построения кода с данным набором кодовых длин. Сначала выберем гу! слов длиной 1, используя для этого различные буквы из алфавита обьема и. Остается и — гу! неиспользованных символов, и поэтому мы можем построить (и — в!)и слов длиной 2, добавляя к ним па символу нз алфавита объема т.
Из этих слов длины 2 выберем вч произвольных слов, что составляет т' — н!1т — гуг "свободных" префиксов длины 2. Добавляя к этим префиксам разные символы алфавита, получаем (и' — н11т — н,)т слов длиной 3, из которых выберем гуЗ пРоизвольных слов и т.Д. Продолжая таким образом, мы построим префиксный код, длина комбинаций которого удовлетворяет неравенству Краф- та (7.1).. Рассмотрим теперь некоторый источник дискретных сообщений без памя- ти, который согласно 9 6.1 однозначно определяется своим алфавитом А объе- ма К и вероятностями появления символов Р(а;), ~=0, 1, ..., К вЂ” 1.
Тогда. если последовательности символов, выдаваемые этим источником, разбить на блоки длины и, то каждый из таких блоков можно рассматривать как символ нового источника с укрупненным алфавитом Ау объема К„= К" и вероятностями по- явления символов Р(а„г), !' = О, 1, ..., Ку — 1, определяемыми как произведение вероятностей первичных символов, входящих в данные блоки.
Определим дли- ны блоков и, неравномерного кода, описанного в теореме 7.1, следующим об- разом: $~РЯ 1оии(~„) п! < + 1о ! Оо 1о о Ку 1 1ояи ' 1оит Тогда из (7.4) получаем, что К -1 Ху "1 ~~~, и "' <~~~ Р(а„„) =1, и поэтому по теореме 7.1 можно символами источника с укрупненным алфави- том сопоставить последовательности символов и-ичного канала без помех, имеющие длины и;. Тогда для средней длины такой последовательности л-1 и = ~~~ Р(а„,)и, выполняются неравенства ' Н(А ) Н(А„) 1ояи 1ор,т Учитывая тот факт, что для источника без памяти Н(А ) = иН(А) и, кроме того, относя эту величину к одному символу источника, получаем Иш — =— п Н(А) (7.5) п 1оят Фактически мы доказали теорему кодирования для каналов без помех и источника без памяти.
Более того, было доказано, что предельное значение средней длины п7п может быть получено при кодировании при помощи неравномерного префиксного кода с длинами последовательностей, выбранными в соответствии с (7.4). Остается показать, как может быть построен такой префиксный код. Существует несколько алгоритмов построения неравномерных кодов с префиксным свойством. Среди них оптимальным, т.е. позволяющим сколь угодно приближаться к пределу (7.5), является алгоритм Хаффмена 181. Однако рассмотрим здесь более простой алгоритм Шеннона-Фано, который в большинстве случаев приводит к тем же результатам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
