Сжатие передаваемой информации

При передаче сообщения возникают две взаимосвязанные про­блемы: устранение избыточности в передаваемой информации и ее сжатие. Кратко рассмотрим их. Под избыточностью будем пони­мать бесполезную, лишнюю при приеме часть информации, кото­рой все равно невозможно воспользоваться. Одной из причин здесь является невосприимчивость человеческих органов к некоторой части принятой информации. Так, например, телевизионное изо­бражение может содержать до 16 тысяч цветовых оттенков, тогда как зрение человека, чувствительное к яркости, невосприимчиво к такой громадной гамме цветов. В лучшем случае человек может различить до нескольких сотен цветовых оттенков. Поэтому часть цветовых оттенков при передаче можно исключить без ощутимой со стороны человека потери качества цветного изображения на экране телевизора. То же самое можно сказать относительно передачи по каналу связи устной речи, верхнюю частоту спектра которой можно ограничить частотой 3400 Гц без потери смысла принятого сооб­щения.

Устранение избыточности в передаваемой информации позво­ляет передавать или хранить меньшее число байт А . Вместе с тем Согласно (1.5) уменьшение объема А передаваемого сообщения позволяет при неизменном интервале времени Т = const снизить скорость передачи V, что согласно (1.11) допускает, в свою оче­редь, сужение полосы пропускания канала связи и, следовательно, повышение его помехозащищенности. С другой стороны, сохранив неизменной скорость V- const, можно существенно уменьшить вре­мяпередачи Т. Уменьшение числа байт А позволяет также разместитьв электронной памяти большее число полезных сведений. Во всехуказанных случаях в результате устранения избыточности, т.е. уменьшения числа байт А, можно получить значительный экономическийэффект.

Предположим теперь, что избыточность в передаваемой ин­формации устранена. Но при этом все равно по разным причинам сохраняется потребность в уменьшении объема передаваемой ин­формации, т.е. количества байт А . Одной из причин здесь является ограниченная пропускная способность канала связи С (1.17), не позволяющая повысить скорость передачи V ≤ С. В этой связи воз­никает проблема по сжатию передаваемой информации с полным ее восстановлением на приемном конце линии связи. Решить данную за­дачу можно путем оптимального кодирования, связанного с затратой минимального количества бит на передачу сообщения с требуемой достоверностью при известных параметрах канала связи.

Сущность сжатия информации рассмотрим сначала на примере передачи текстового сообщения. При равномерном коде согласно табл. 1.1 любая буква алфавита передается 6 битами. Частота по­явления букв в тексте при этом не учитывается. Вместе с тем ста­тистический анализ показывает, что в стандартном тексте на рус­ском языке, состоящем из 1000 символов, буква О встречается в среднем 95 раз, буква Е - 74 раза, буква Ф - всего 2 раза, пробел между словами - 145 раз и т.д. Частота появления букв в тексте на русском языке приведена в табл. 1.3.

С помощью табл. 1.3, в которой буквы расположены в порядке убывания их частот, составим неравномерный код согласно методу Шеннона-Фано. С этой целью разделим весь список на две группы с неравным количеством букв, но с примерно равной суммарной ве­роятностью. В первую группу поместим буквы из верхней части спи­ска от «пробела» до буквы Т с суммарной вероятностью 0,498, во вторую - все остальные буквы с суммарной вероятностью 0,502. Каждой букве из первой группы в качестве первой цифры кода при­своим 0, а из второй группы - 1.

Таблица1.3

Каждая из полученных групп букв аналогичным образом вновь делится на две части с добавлением еще одной цифры кода. Так, первая группа будет разделена на две подгруппы: от «пробела» до буквы О и от Е до Т. Для всех букв первой подгруппы на втором месте кода поставим 0, второй - 1. Аналогичным образом разделим вторую группу букв. Процесс такого деления с присвоением новой цифры кода будем продолжать до тех пор, пока в каждом из разря­дов не останется одна буква, которая будет закодирована двоич­ным числом наибольшей длительности. Полученный в результате описанного алгоритма неравномерный код представлен в табл. 1.3. В нем часто встречающиеся буквы в тексте закодированы всего тремя битами, а редко - девятью. В результате общее число бит в передаваемом тексте будет уменьшено, чго сократит объем пе­редаваемой информации.

Проверим последнее утверждение на примере передачи слова «Дополнительное". Закодированное согласно табл. 1.3 это слово примет вид: 110010 001 110011 001 10110 1000 0110 0111 0100 10110 111001 1000 001 0100.

Общее число бит составит 61 вместо 84 при передаче того же слова равномерным шестизначным кодом согласно табл. 1.1. Та­ким образом, в рассмотренном примере применение неравномер­ного кода взамен равномерного позволяет сжать объем переда­ваемой информации на 38% .

Другой метод сжатия информации, называемый RLE, основан на учете часто повторяющихся и следующих друг за другом одинако­вых символов (RLE есть аббревиатура слов Run-Lengh Encoding, что в переводе на русский язык означает кодирование длины по­следовательности). Например, при методе RLE последователь­ность символов в виде ААААААВВВСССС будет передана как 6АЗВ4С, что при 8-разрядном коде сократит число передаваемых бит со 104 до 48. Этот метод дает, в частности, ощутимый выигрыш при передаче изображений с одинаковыми цветовыми участками.

Более эффективные методы, позволяющие многократно сжи­мать дискретную информацию, подразделяются на три основные группы: статистические, словарные и контекстные [32, 33].

При первом методе производится статистическая обработка пе­редаваемой информации с целью определения вероятности появ­ления в текущем контексте того или иного символа или определен­ной последовательности символов, что определяет длину кода.

Рассмотрим статистический метод на примере сжатия речевого сигнала с помощью устройства, называемого кодером, работа ко­торого основывается на учете статистических характеристик рече­вого сигнала согласно методу линейного предсказания [21].

Сущность последнего заключается в том, что по каналу связи передаются не сами параметры речевого сигнала, а параметры специального фильтра линейного предсказания, являющегося мо­делью голосового тракта человека, и параметры сигнала возбужде­ния этого фильтра. Относительно самого речевого сигнала следует иметь в виду, что он состоит из гласных звуков со средней дли­тельностью 210 мс и согласных - 95 мс с мгновенным уровнем из­менения амплитуды 35...40 дБ. Постоянная времени слуха челове­ка составляет 20...30 мс при нарастании звука и 100...200 мс при его спаде.

В целом один из типов кодера работает следующим образом. Сначала речь человека - аналоговый сигнал, занимающий полосу частот 300...3400 Гц, с помощью аналого-цифрового преобразова­теля (АЦП) преобразуется в цифровой сигнал с частотой дискрети­зации 8000 Гц и скоростью следования бит V - 64 кбит/с (см. при­мер в конце § 1.3). Далее оцифрованный сигнал разбивается на сегменты длительностью 20 мс с учетом постоянной времени слуха человека. При данном интервале времени речевой сигнал можно рассматривать как квазистационарный гауссовский процесс. Для каждого сегмента согласно методу линейного предсказания произ­водится определение параметров специального фильтра и сигнала возбуждения. Сущность такого предсказания заключается в том, что каждая очередная выборка речевого сигнала определяется как линейная комбинация нескольких предшествующих выборок, по­скольку каждый звук статистически зависит от предшествующих звуков:

где а_i - коэффициент линейного предсказания.

Исходя из полученного значения выборки определяются пара­метры специального фильтра - своеобразной модели голосового тракта человека на интервале времени в 20 мс. Параметры этого фильтра и сигнала возбуждения поступают в канал связи. На при­емном конце согласно полученным данным осуществляется синтез фильтра, моделирующего голосовой тракт на время одной 20-миллисекундной выборки речи. Далее цифровой сигнал с помощью цифро-аналогового преобразователя (ЦАП) переводится в анало­говую форму. Устройство восстановления сигнала называется де­кодером. Структурная схема описанного метода передачи речи при­ведена на рис. 1.6.

В результате описанной процедуры удается передать речевой сигнал при 8 кратном уменьшении числа бит со скоростью 8 кбит/с вместо 64 кбит/с и, следовательно, осуществить сжатие переда­ваемой информации в 8 раз.

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

В словарь-таблицу записываются часто повторяющиеся после­довательности бит. При новом появлении аналогичных кодовых комбинаций производится обращение к соответствующей ячейке таб­лицы и передача не ее содержимого, а только номера, что значи­тельно сокращает объем передаваемой информации. Структурная схема одного из алгоритмов такой группы, называемого LZW, при­ведена на рис. 1.7.

Алгоритм LZW, названный по первым буквам фамилий его авто­ров - Lempel, Ziv, Welch, позволяет автоматически адаптироваться к качественному составу входного битового потока, использовать плавающую длину байта от 9 до Л/ бит, экономно использовать ди­намическую память.

В результате кодовый поток бит на выходе, передаваемый по каналу связи, оказывается в несколько раз меньшим по объему, чем входной поток бит.

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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: