Тема 3. Кодирование источника (774420), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Представим, например, дискретный источник с алфавитом (а,), ~'=0,5, как новый источник с алфавитом (а,.',о,~, 0 ~' = 0,5, т.е. в качестве одного укрупненного сообщения на выходе источника теперь рассматривается два последовательных сообщения. Если источник не 261 Фактически мы доказали теорему кодирования для каналов без помех и источника без памяти. Более того, было доказано, что предельное значение средней длины пп/и может быть получено при кодировании при помощи неравномерного префиксного кода с длинами последовательностей, выбранными в соответствии с (7.4). Остается показать, как может быть построен такой префиксный код. Существует несколько алгоритмов построения неравномерных кодов с префиксным свойством. Среди них оптимальным, т.е.

позволяющим сколь угодно приближаться к пределу (7.5), является алгоритм Хаффмена 181. Однако рассмотрим здесь более простой алгоритм Шеннона-Фано, который в большинстве случаев приводит к тем же результатам. Алгоритм Шеннона-Фано заключается в следующем. Символы алфавита источника (первичного или укрупненного) записываются в порядке не возрастающих вероятностей. Затем они разделяются на две части так, чтобы суммы вероятностей символов, входящих в каждую из таких частей, были примерно одинаковыми. Всем символам первой части приписывается в качестве первого символа комбинации неравномерного кода ноль, а символам второй части— единица.

Затем каждая из этих частей (если она содержит более одного сообщения) делится в свою очередь на две, по возможности равновероятные части и к ним применяется то же самое правило кодирования. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению. имеет памяти, то Р(а„е.~=Р(а>)Р(а,).Если же исходный источник имеет память, то, например, Р(а,,а,) ~ Р(а,,а,), что будет учтено при последующем оптимальном префиксном кодировании для нового источника с укрупненным алфавитом.

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

Например, необходимо сконструировать двоичный префиксный код для передачи текста на различных языках, имеющих общий алфавит. Казалось бы, эта задача является неразрешимой, но в действительности удается сконструировать некоторый универсальный сжимающий код. Рассмотрим кратко метод сжатия подобного типа, известный как алгоритм Зива-Лемпела и широко применяемый в ЭВМ для архивирования файлов. Общая идея данного метода состоит в том, что последовательность символов источника разбивается на кратчайшие различимые цепочки, которые не встречались раньше, а затем эти цепочки кодируются равномерным кодом.

Например, если последовательность имела вид 1011010!00010, то она будет разбита на цепочки-следующим образом: 1, О, 11, 01, 010, 00, 10. При таком способе разбиения все префиксы данной цепочки могут находиться лишь слева от нее. В частности, цепочка, которая отличается от данной лишь в последнем символе (бите), всегда будет располагаться слева. Если с(в) означает число различных цепочек разбиения для данной последовательности длины л, то необходимо !ойз с(л) бит, чтобы закодировать номер префикса к данной цепочке и еше один бит для описания последнего элемента этой цепочки.

Так, для рассмотренной выше последовательности и ее разбиений мы получим следующий равномерный код: (000, 1) (000, О) (001, 1) (010, 1) (011, О) (010, О) (001, О), где первые три бита определяют номер префикса к очередной цепочке, а последний бит дает значение последнего символа этой цепочки. Очевидно, что декодирование такого кода производится однозначным образом. Рассмотренный пример дает фактически не сжатие, а "растяжение" сообщений, поскольку вместо 13 исходных бит мы получаем 28 бит. Однако для длинных последовательностей сообщений эффективность алгоритма увеличивается, и в асимптотике, т.е. при л -+ се, сжатие сообщений приближается к предельно возможному, определяемому теоремой кодирования в канале без помех, а именно доказывается, что для любого стационарного эргодического источника сообщений с(и)(1овс(и) + 1) я-+ о л Заметим, что фактически для сжатия файлов используется модифицированный алгоритм, называемый алгоритмом сжатия Зива-Лемпела-Велча, на основе этого алгоритма построены наиболее эффективные программы архивирования файлов, такие как РКАКС, РК2'.1Р, 1СЕ и др.

7.3. ПОМЕХОУСТОЙЧИВОЕ (КАНАЛЬНОЕ) КОДИРОВАНИЕ Если экономное кодирование сокращает избыточность источника сообщений, то помехоустойчивое кодирование, напротив, состоит в целенаправленном введении избыточности для того, чтобы появилась возможность обнаруживать и(или) исправлять ошибки, возникающие при передаче по каналу связи. В дальнейшем будем рассматривать только чисто канальное (помехоустойчивое) кодирование, хотя общий подход также возможен и, более того, дает весьма значительный эффект, особенно при передаче преобразованных к дискретному виду непрерывных сигналов (см. гл.

8). Переходим к изложению общей теории блоковых кодов. Будем называть канальным (помехоустойчивым) блоковым геодом Р'любое множество из М различных последовательностей (комбинаций, слов) х1, х2, хз, ..., хьг длины п, 2б2 кращает входную полосу частот до выбранной полосы частот канала и повторно выбирает сигнал до самой низкой частоты, что позволяет избежать наложения разделенных полос частот данных. В приемнике производится обратный процесс. Разделенные на полосы данные для увеличения их частоты до желаемой частоты дискретизации проходят через интерполируюшие фильтры и смешиваются обратно до их соответствующего спектрального положения. Чтобы создать исходный смешанный сигнал, они объединяются.

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

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

Замена обычно является временной и производится, для того чтобы достичь экономии при запоминании или передаче символов дискретного источника. Двоичный код, присвоенный каждому символу источника, должен удовлетворять определенным ограничениям, чтобы позволить обращение замены. К тому же код может быть далее ограничен спецификацией системы, например ограничениями памяти и простотой реализации. Мы настолько привыкли к использованию двоичных кодов для представления символов источника, что можем забыть о том, что это всего лишь один из вариантов присвоения.

Наиболее общим примером этой процедуры является двоичное присвоение количественным числительным (даже не будем рассматривать отрицательные числа). Можно прямо переводить в двоичную систему счисления, двоичные коды восьмеричных чисел, двоичные коды десятичных чисел, двоичные коды шестнадцатеричных чисел, десятичные коды "два из пяти", десятичные коды с избытком три и т.д. В этом примере при выборе соответствия учитывается простота вычисления, определения ошибки, простота представления или удобство кодирования.

Для определенной задачи сжатия данных основной целью является сокращение каличесглва бит. Конечные дискретные источники характеризуются множеством различных символов, Х(л), где и = 1, 2, ..., Ф вЂ” алфавигл источника, а и — индекс данных. Полное описание требует вероятности каждого символа и совместных вероятностей символов, выбранных по два, три и т.д. Символы могут представлять двухуровневый (двоичный) источник, такой как черно-белые уровни факсимильного изображения, или многосимвольный источник, такой как 40 общих знаков санскрита Еше одним общим многосимвольным алфавитом является клавиатура компьютерного терминала. Эти недвоичные символы отображаются посредспюм словаря, называемого знаковым кодом, в описание с помощью двоичного алфавита.

Характеристики

Список файлов лекций