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