Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
19
1.2. МОДЕЛИ ИСТОЧНИКОВ И КОДИРОВАНИЕ ДЛЯ ИСТОЧНИКОВ
Здесь мы дадим краткое описание математических моделей источников, которые будут рассматриваться в дальнейшем. Естественно, что более подробно эти модели будут рассмотрены в последующих главах. Все источники в теории информации моделируются с помощью случайных процессов или случайных последовательностей. Простейший класс моделей источников составляют дискретные источники без памяти. В этих источниках выходом является последовательность (во времени)
Способ / Способ 2 af-^OO ctf^O аг-^ОГ аЮ аг-*-Ю о-ъ -*¦ НО
букв, каждая из которых выбрана из некоторого фиксированного алфавита, скажем, содержащего буквы аи а2, •••, «/<• Последовательность на выходе источника состоит из этих букв, выбираемых из алфавита статистически независимо и случайно, и при этом выбор производится в соответствии с некоторым заданным распределением вероятностей Q (ах), ..., Q (а/с).
Несомненно, что на первый взгляд кажется довольно странным моделирование реальных источников, которые по предположению производят осмысленную информацию, с помощью случайных процессов. Следующий пример поможет пояснить причину этого. Предположим, что нужно провести некоторое измерение несколько раз подряд и что результатом каждого измерения может быть одно из четырех событий аъ а2, а3 или а4. Пусть эта последовательность измерений должна быть накоплена в двоичной форме записи, и предположим, что предлагаются два способа перехода к двоичным символам, изображенные на рис. 1.2.1.
В первом из представленных выше способов требуются два двоичных символа для представления каждой буквы источника, в то время как во втором способе требуется переменное число символов. Если известно, что в подавляющем большинстве измерений результатом будет аъ тогда способ 2 позволит накопить длинную последовательность измерений с помощью значительно меньшего числа двоичных символов, чем способ I. Методы кодирования выхода дискретного источника в двоичные данные будут подробно обсуждаться в гл. 3. Важным моментом здесь является то, что относительная эффективность методов, изображенных на рис. 1.2.1, критически зависит от частоты появления различных событий и что в математической модели источника последние определяются с помощью распределения вероятности на множестве букв источника. Хорошо известные, но более сложные примеры такого типа дает стенография, в которой короткие символы ^используются для наиболее употребительных слов, и код Морзе, в котором короткие последовательности точек и тире сопоставлены часто встречающимся буквам, а длинные последовательности — редким буквам.
20
Рис. 1.2.1. Два способа преобразования алфавита из четырех букв в двоичные символы.
С кодированием выхода источника в двоичные данные тесно связана мера информации (или неопределенности) букв алфавита источника, которая будет описана в гл. 2. Если k-я буква алфавита источника имеет вероятность Q (ah), то собственная информация этой буквы (измеренная в битах) определяется как / (ak)^ — log2 Q (ak). С интуитивной точки зрения (подробнее это будет рассматриваться в гл. 2) это, связанное с техникой связи определение, имеет много качественных черт, свойственных общеупотребительному понятию информации. В частности, если Q (ak) = 1, то / (ah) = 0 в соответствии с тем, что появление ah не несет никакой информации, так как оно неизбежно должно произойти. Точно также, чем меньше вероятность ah, тем больше ее собственная информация. Вместе с тем, нетрудно заметить, что это специальное определение информации имеет некоторые качественные недостатки в сравнении с общеупотребительным понятием информации. Например, не имеет значения то, насколько редким является событие; мы не считаем это информативным (в общеупотребительном смысле), если само по себе наступление события не оказывается интересным для нас. Это не означает, что имеется какой-то недостаток в определении собственной информации; польза от того или иного определения в теории определяется тем, насколько оно дает возможность проникнуть в существо проблемы, и тем, как оно'упрощает теоремы. Определение, которое дается здесь, оказывается полезным в теории, главным образом, именно потому, что оно позволяет отделить понятие неожиданности в информации от того, что представляет в информации интерес или смысл.
Среднее по буквам алфавита значение собственной инЛопмаиии является особенно важной величиной, которая называется энтропией букштхсточникщтнтропия задается выражением
2 — QK)log2Q(afe).
? = 1
Значение энтропии буквы источника определяется, главным образом, теоремой кодирования для источника, которая рассматривается в гл. 3. Она утверждает, что если Н — энтропия буквы источника в дискретном источнике без памяти, то последовательность на выходе источника не может быть представлена двоичной последовательностью, использующей в среднем меньше чем Н двоичных символов на букву источника, но она может быть представлена двоичной последовательностью, использующей в среднем сколь угодно близкое к Н число двоичных символов на букву источника. Некоторое ощущение справедливости этого результата может быть получено, если заметить, что в случае, когда для некоторого целого L источник имеет алфавит из 2L равновероятных букв, то энтропия буквы источника равна L бит. Вместе с тем, если заметить, что всего имеется 2L различных последовательностей из L двоичных символов, то можно понять, что каждая из этих последовательностей может быть сопоставлена различным буквам алфавита источника, представляя, таким образом, выход источника с помощью L двоичных символов на букву источника. Этот пример дает
