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

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

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

Деля полный объем пространства (2я) на объем этих сфер, находим верхнюю
границу числа К возможных кодированных сигналов в пространстве:
суП
>2*
1 +п + п(п - 1)/2 •
(4.3.16)
Аналогичные неравенства могут быть записаны и для сфер большего радиуса,
если мы исследуем возможность исправления более двух ошибок.
Выясним, каким образом можно осуществить такой код (рис. 4.8). Рассмотрим
следующий пример.
Пусть мы имеем источник с репертуаром из восьми слов, каждое длиной три
бита, записанных в алфавите из двух символов- нуля и единицы (23 = 8).
Как "раздуть" пространство состояний так, чтобы стало возможным
исправление одиночной или многократной ошибки в принятом сигнале?
Основная идея состоит в том, чтобы сделать наши восемь символьных слов
как можно более "ортогональными". Ортогональность в данном случае
означает, что парная кросс-корреляция между двумя кодовыми словами
Рис. 4.8. Представление множества трехзначных двухсимвольных слов.
Р (т) = т ? X,.
'/ + Т>
(4.3.17)
! = 1 / = 1
Элементы теории информации и кодирования
179
где X/ - строки из нулей и единиц длиной стремится к дельта-функции при
voo. Рассмотрим первый этап кодирования, а именно процесс преобразования
множества слов длиной в 3 бит в множество слов такой длины, при которой
становится возможным исправление одиночной ошибки.
Для этого мы воспользуемся устройством, известным под названием
"сдвиговый регистр" (рис. 4.9). Такой регистр состоит из
последовательности (каскада) двоичных ячеек, каждая из которых может
находиться лишь в одном из двух состояний, причем при прохождении
импульса содержимое каждой ячейки сдвигается на одну ячейку "влево".
Создавая (как на рис. 4.9)
Рис. 4.9. Сдвиговый регистр с петлей обратной связи (см. текст).
петлю обратной связи, используя сложение по модулю 2 выходов некоторых
ячеек для определения следующего двоичного символа на входе регистра, мы
получаем возможность генерировать последовательность максимальной длины.
Последовательность имеет максимальную длину, если при Л стадиях (в нашем
случае Л = 3) выходная последовательность, прежде чем повториться,
принимает все возможные комбинации и расположения А двоичных символов
(кроме комбинации, состоящей из одних лишь нулей). Таким образом,
максимальная последовательность имеет длину \ = 2Л-1, где | - длина
максимальной последовательности в битах, Л - число ячеек в регистре
генератора. Последовательности максимальной длины называются также
псевдослучайными последовательностями, так как статистика их появления
напоминает статистику чисто случайных двоичных событий (бросаний монеты).
Таким образом, в последовательности максимальной длины единиц всегда на
одну больше, чем нулей. Кроме того, периодическая автокорреляция
оптимальна: она принимает значение 1 при т = 0 и -1Д при всех остальных т
и, разумеется, периодична по
В нашем примере описанная выше схема действует следующим образом. Каждое
слово длиной в 3 бит из репертуара в 8 слов мы вводим в регистр и
предоставляем логической петле обратной связи действовать до тех пор,
пока слово, записанное
180
Глава 4
Таблица 4.4. Преобразование слов длиной в 3 бит в слова, позволяющие
исправить одиночную ошибку
Начальное множество (Л) Конечное множество (?)
111 1110010
110 1100101
100 1001011
001 0010111
010 0101110
101 1011100
011 0111001
000 0000000
нами в регистр, не появится снова. В результате мы получаем отображение,
представленное в табл. 4.4. Парные корреляции могут быть заданы
отношением (Л - В)/7, где А - число совпадающих символов в двух словах, а
В - число символов, которыми два слова отличаются. В нашем случае А = 3,
В = 4, поэтому функция парных корреляций равна -1/7.
В общем случае после многих "метакодирующнх" операций функция парных
кросс-корреляций принимает вид
и р ->- 0 при Л-"-оо, т. е. достигается ортогональность.
Ясно, что новые 8 слов длиной 7 бит допускают исправление одиночной
ошибки. Всего существует 128 (-27) слов длиной 7 бит, но из них только
восемь "законных".
4.4. Источники информации с памятью.
Цепи Маркова
В предыдущем разделе мы видели, что максимальная скорость передачи
информации достигается путем устранения всей избыточности из подлежащих
передаче строк слов, т. е. после того, как все передаваемые символы
становятся равновероятными и статистически независимыми. Но, как мы
видели, для придания нашим сигналам иммунитета к шуму в канале сигналы
необходимо отобразить в пространство состояний, или закодировать, чтобы
мы могли обнаруживать и исправлять ошибки. Иначе говоря, для обеспечения
надежности связи нам приходится снова вводить избыточность ¦- на этот раз
"с черного хода".
Ясно, что требования скорости и надежности передачи информации
противоречивы. Каким образом можно примирить их,
Элементы теории информации и кодирования
181
чтобы создать язык связи, который обладал бы, с одной стороны,
достаточной надежностью, а с другой стороны, достаточной вариабельностью,
Предыдущая << 1 .. 61 62 63 64 65 66 < 67 > 68 69 70 71 72 73 .. 187 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed