9. КОДИРОВАНИЕСООБЩЕНИЙИСТОЧНИКА
Из теории информации известно, что максимальное количество информации содержится в сообщениях, составленных из равновероятных и независимых символов. Реальные источники создают сообщения, которые не обладают указанными свойствами. Из-за этого длина сообщений оказывается больше необходимой при сохранении того же количества информации. Говорят, что источник или его сообщения обладают избыточностью. Так, избыточность русского языка составляет около 75%, что соответствует удлинению машинописного текста примерно в 4 раза.
Эта избыточность, с одной стороны, полезна, так как позволяет человеку находить опечатки в тексте и исправлять их. С другой стороны, вредна, если требуется запомнить сообщение или передать по каналу связи. Естественную избыточность технически сложно использовать для борьбы с искажениями в канале. Кроме того, величина ее может быть слишком велика для канала высокого качества, что снизит эффективность его применения. Поэтому согласование реального источника с каналом связи происходит в два этапа. Сначала естественную избыточность устраняют с помощью экономного или статистического кодирования, так называемого сжатияданных. Затем вводится новая избыточность в форме, позволяющей на приемной стороне создать устройства обнаружения и исправления ошибок (см. гл. 7).
Множество алгоритмов экономного кодирования делится на две группы. К первой относятся правила, позволяющие восстановить исходное сообщение без погрешности (алгоритмы Шеннона-Фано, Хаффмена, словарные методы сжатия). Вторая группа объединяет методы, допускающие восстановление с заданной погрешностью (алгоритмы сжатия аналоговых сигналов, в частности, речи).
9.1. Методыкодированияисточника безпотерьинформации
Современные системы мобильной связи наряду с передачей речи обеспечивают передачу факсимильных и текстовых сообщений.
Для сжатия факсимильных сообщений рекомендуется использовать кодыХаффмена[50]. В результате строчной развертки оригинала формируется последовательность нулей и единиц, соответствующих белым и черным элементам изображения. Избыточность проявляется в том, что число подряд следующих нулей или единиц (длина серий) имеет разную вероятность появлений^ Поэтому кодированию по Хаффмену подвергаются серии нулей и единиц, при этом наиболее вероятным сериям сопоставляются самые короткие кодовые слова.
Для сжатия текстовых сообщений разработаны словарные методыили алгоритмы сжатия семейства LZ, названные так по первым буквам фамилий авторов Лемпеля и Зива [51]. В отличие от статистических алгоритмов Хаффмена, Шеннона-Фано, для их реализации не требуется знать распределение вероятностей сообщений источника.
В основе этих алгоритмов лежит создание и использование на передающей и приемной сторонах особой информационной структуры - словаря, содержащего последовательности символов (строки), которые ранее реально создавались источником.
Кодирование вновь поступающей от источника последовательности заключается в поиске в словаре самой длинной строки, совпадающей с этой последовательностью, и передаче по каналу
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
