Научная литература
booksshare.net -> Добавить материал -> Физика -> Николис Дж. -> "Динамика иерархических систем: эволюционное представление" -> 64

Динамика иерархических систем: эволюционное представление - Николис Дж.

Николис Дж. Динамика иерархических систем: эволюционное представление — М.: Мир, 1989. — 490 c.
Скачать (прямая ссылка): dinamikaiearhicheskihsistem1989.pdf
Предыдущая << 1 .. 58 59 60 61 62 63 < 64 > 65 66 67 68 69 70 .. 187 >> Следующая

пространства состояний, в котором отдельные "слова" (в дискретизированной
по теореме Шеннона о выборке формы) фигурируют в качестве гипервекторов.
На принимающем конце канала связи "сокращение" размерности,
осуществляемое декодером канала, сводится к образованию серии сверток
поступающего (зашумленного) сигнала и каждого элемента/слова репертуара
передатчика. Так как в отсутствие шума отдельные "слова" взаимно
ортогональны, их попарные кросс-корреляции равны нулю. Таким образом,
описанные выше операции позволяют приемнику детектировать и исправлять
многие ошибки (хотя число их должно быть конечным), обусловленные шумом в
канале. В следующем разделе мы узнаем, как именно осуществляется такой
процесс кодирования- декодирования в рамках схемы Шеннона.
4.3. Некоторые эффективные алгоритмы кодирования
для установления соответствия между скоростью передачи информации от
источника и пропускной способностью канала. Обнаружение и исправление
одной ошибки
Кодирование преследует двоякую цель: во-первых, установление соответствия
между скоростью передачи информации от
п Можно доказать, что при такой схеме декодирования (если канал связи не
имеет памяти) число шагов декодирования с увеличением длины п кодового
слова возрастает не экспоненциально (2"), как в случае декодирования с
заменой принятого сигнала ближайшим сигналом, а лишь как ~п2. Кроме того,
можно показать, что, используя иерархические принципы кодирования-
декодирования (см., например, [4.3]), можно еще более понизить
вычислительную сложность--до
В иерархической схеме кодирования - декодирования одни коды "вставляются"
в другие. В частности, и кодирование, и декодирование осуществляются шаг
за шагом по восходящим ступеням иерархии. Сначала на низшем уровне
простые символы ("алфавит") группируются в блоки ("слова"), Затем на
втором уровне каждый из блоков ("слов") рассматривается как новый символ
и многие из них снова группируются в блоки ("предложения") и т. д. При
декодировании происходит обратная процедура. Такой принцип "вложенных"
кодов представляет собой не что иное, как попытку имитировать
иерархическую структуру естественного языка.
172
Глава 4
источника и пропускной способностью канала связи и, во-вторых,
преобразование передаваемого сигнала в такую последовательность нулей и
единиц, при которой неоднозначность выбора правильной строки нулей и
единиц или волнового сигнала в декодере канала сводилась бы к минимуму.
4.3.1. Кодирование для установления соответствия между скоростью
передачи информации от источника и пропускной способностью канала
Начнем с источников, обладающих нулевой памятью, т. е. с источников со
статистически независимыми символами. В "блоке кодирования" каждое
состояние источника, т. е. каждый сигнал, преобразуется всегда в одну и
ту же последовательность кодовых "букв", или символов, которая называется
"кодовым словом". Нас интересует, как достичь максимальной скорости
передачи информации. Ясно, что для этого код должен нести максимум
информации на одну букву (или на один символ). (Имея "алфавит" из г букв,
мы можем составить п = гЛ кодовых слов средней длины Л.) Если
рассматривать кодовые символы (а не кодовые слова) как состояния,
принимаемые самим кодом, то для кода с алфавитом из г символов указанный
выше максимум может быть достигнут при условии, если все г букв
независимы и равновероятны, что дает SMaKclog2r бит/букву. Пусть кодовое
слово xi состоит из последовательности, содержащей Я, букв. Тогда средняя
длина кодового слова равна величине
П
A='^JXiP(xi) символов/слов, (4.3.1)
i=i
и кодовое слово несет среднее количество информации
-Дй log2 г бит/'символ, (4.3.2)
где
П
S(X)= - ? P(Xi)log2P(Xi), (4.3.3)
i=i
где P(xi) - априорная вероятность сигнала/слова х,-.
Определим эффективность кода как
<4-3-4>
Из этой формулы следует, что 100 %-ная эффективность соответствует коду с
независимыми н равновероятными символами. Реально эффективность кода
должна быть меньше 100 % по двум причинам. Во-первых, в любом
естественном языке бук-
Элементы теории информации и кодирования
173
вы встречаются не равновероятно (вариация составляет величину 5(X) С log2
гА). Во-вторых, буквы взаимозависимы (надежность). Информация,
переносимая одной буквой, понижается за счет того, что данная буква может
быть предсказана исходя из предшествующей последовательности букв.
Предсказуемость повышает априорную вероятность и, следовательно, понижает
количество информации, переносимое буквой.
Пусть L - продолжительность каждого состояния/слова кода. Источник выдает
сигналы, или кодовые слова, со скоростью ~F = Х/L сигналов/с, или /= 1/1
букв/с, если f - FA и I - продолжительность передачи одной буквы. Пусть
для канала без шума максимальная частота букв в секунду, которые могут
быть переданы без ошибки составляет /макс букв/с.
Мы хотели бы знать, какова максимальная скорость передачи сигналов Xi
источника по такому каналу без ошибок и каков оптимальный способ
Предыдущая << 1 .. 58 59 60 61 62 63 < 64 > 65 66 67 68 69 70 .. 187 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed