Динамика иерархических систем: эволюционное представление - Николис Дж.
Скачать (прямая ссылка):
кодирования источника, позволяющий достигать этого максимума или
приближаться к нему сколь угодно близко. Так как среднее количество
информации на сигнал, выдаваемое источником, равно S(X), скорость
передачи информации от источника равна
R = FS (X) бит/с, (4.3.5)
поэтому
^ = 1-5(Х) бит/с. (4.3.6)
Максимальный поток информации, который может быть передан по каналу связи
без ошибки, составляет величину
С =/"акс =/макс log2Г бит/с, (4.3.7)
\ /макс
так как 5(Х) не превосходит Alog2r. Таким образом, мы приходим к выводу о
том, что сигналы не могут быть переданы без ошибок, со скоростью,
превышающей пропускную способность канала, т. е. при F > C/S(X)
сигналов/с. Заметим, что неравенство 5(А)/Л log2 г сохраняется, если от
двоичных логарифмов перейти к логарифмам с основанием г, т. е. Sr(X) /A
1, или
П П
- Z р (Xi) log, Р (xt) < z КР (Xi). (4.3.8)
1=1 i=1
Мы видим, что пропускная способность канала достигается при
Л, = -log,/>(*,), (4-3.9)
т. е. при
Р(Х.) = Г~Ч (4.3.10)
174
Глава 4
(для источника, у которого априорные вероятности сигналов закодированы по
закону (4.3.10), образование слов становится все менее вероятным по мере
увеличения длины слова). Но, даже если распределение вероятности
состояний источника не следует экспоненциальному закону (4.3.10), мы все
же можем добиться почти 100%-ной эффективности кода следующим образом.
Запишем неравенство (4.3.9) в виде
- log, Р (*,-)< Яг < - log, Р (xt) + 1, (4.3.11)
где второе неравенство следует из первого потому, что мы выбрали как
ближайшее к -logrP(Xi) целое число.
Умножая соотношение (4.3.11) на P(xt) и суммируя по всем г, получаем
1. (4.3.12)
log2r ^ ^ log2r
Рассмотрим теперь все последовательности символов, генерируемых
источником, т. е. последовательности отношений сигналы/состояние, взятых
по т экземпляров за один раз; таких последовательностей всего пт. Будем
рассматривать каждую такую последовательность как новый сигнал/состояние,
принадлежащий более высокому иерархическому уровню и источник с п'п
состояниями. (Это называется т-м расширением Х<-т'> исходного источника
X.) Так как по предположению х,- независимы, справедливо соотношение
S(Xm) = mS(X), (4.3.13)
и средняя длина кодовых слов, кодирующих каждую последовательность,
составляет тА букв. Подставляя ее в неравенство
(4.3.12), получаем
mS(X) ^ . mS(X) . ,
log2 Г ^ log2 Г
или
1 <'П + -^д-- (4.3.14)
Так как при кодировании достаточно длинных последовательностей число т
может быть сколь угодно велико, эффективность т) нового кода может сколь
угодно мало отличаться от единицы, - разумеется, ценой увеличения
сложности кодирования.
Прежде чем продвигаться дальше, рассмотрим кратко, каким образом мы можем
на практике реализовать оптимальное распределение (4.3.10), с тем чтобы
максимизировать скорость передачи информации, т. е. сделать так, чтобы
скорость передачи информации асимптотически приближалась к пропускной
Элементы теории информации и кодирования 175
способности канала. Предположим, что источник обладает репертуаром,
состоящим, например, из восьми независимых сигналов А, В, С, D, Е, F, G и
Я, которые встречаются с априорными вероятностями, приведенными в табл.
4.2.
Таблица 4.2. Априорные вероятности восьми независимых сигналов от
источника (подробности см. в тексте)
Х1 А в С D Е F а я
1 o' О, 0,18 0,4 0,05 0,06 0,1 0,007 0,004
Предположим, кроме ТОГО, что сигналы поступают в канал
со скоростью один сигнал в секунду. Энтропия источника, вычисляемая по
формуле -r?uPi^og2Pi, составляет --2,55 бит/с. Если этот набор сигналов
передается по каналу, в котором сигнал может находиться на любом из
восьми уровней по напряжению, то такой источник можно закодировать,
считая, что каждый из таких уровней представляет собой сигнал.
Максимальное количество информации, переносимое восьмиуровневым сигналом,
равно log28 = 3 бит, и канал, в котором независимые уровни возникают
каждую секунду, обладает пропускной способностью С = 3 бит/с.
Следовательно, эффективность кодирования по такой схеме составляет (2,55-
100)/3 ж 85 %. Этот показатель можно улучшить, если воспользоваться
приведенным выше теоретическим анализом и упорядочить восемь сигналов
заново так, чтобы более длинные сигналы были менее вероятными.
Итак, все сигналы упорядочены в порядке убывания их вероятности. Разделим
всю серию сигналов на две группы так, чтобы суммы вероятностей сигналов в
каждой группе отличались как можно меньше. В свою очередь каждую из этих
групп разделим по тому же принципу на две подгруппы и будем повторять
этот процесс до тех пор, пока не дойдем до подгрупп, состоящих только из
одного сигнала. При каждом делении сигналам первой группы условимся
сопоставлять символ 0, а сигналам второй группы - символ 1. Тогда
кодированная двоичная форма каждого сигнала будет задаваться
соответствующей последовательностью двоичных символов. Вся процедура
представлена в табл. 4.3.
Пропускную способность двоичного канала, необходимую для передачи наших
