Динамика иерархических систем: эволюционное представление - Николис Дж.
Скачать (прямая ссылка):
сигналов со скоростью один сигнал в секунду, мы получаем, вычисляя
среднюю скорость появления двоичных цифр. Например, при достаточно
большом Т двузначные двоич-
176
Глава 4
Таблица 4.3. Кодирование восьми независимых сигналов источника,
представленных в табл. 4.2
Сигнал С В A F G Е D Н
Вероятность 0,4 0,18 0,1 0,1 0 07 0,06 0,05 0,04
0 10 10 10 1
0 1
0 1
О 1
Код 00 01 100 101 1100 1101 1110 1111
ные сигналы встречаются (0,4 + 0,18)7', а общее число двоичных знаков
равно
Т [2 (0,4 + 0,18) + 3 (0,1 + 0,1) + 4 (0,07 + 0,06 + 0,05 + 0,04)] = -
2,64Т двоичных знаков.
Пропускная способность канала связи, передающего 2,64 двоичных символа в
секунду, равна С - 2,64 бит/с, что приводит к эффективности кодирования
(2,55-100) /2,64 = 96,6 %• Вводя в изложенный выше алгоритм небольшие
модификации, мы можем асимптотически достичь 100 %-ной эффективности
(см., например, работу Хаффмана [4.4]).
4.3.2. Кодирование для обнаружения и исправления ошибки
Теперь нас будет интересовать кодирование с целью обнаружения и
исправления одной ошибки или нескольких некоррелированных ошибок,
обусловленных шумом в канале. Будем рассматривать строку из п нулей и
единиц как точку в /г-мерном пространстве. Каждый двоичный символ задает
значение соответствующей координаты в /г-мерном пространстве (мы
предполагаем, что все закодированные сигналы имеют длину п символов).
Таким образом, мы получаем куб в /г-мерном пространстве; каждая вершина
представляет собой строку из п нулей и единиц. Пространство состоит
только из 2" вершин; иногда его называют векторным пространством. Каждая
вершина соответствует одному из возможных принятых сигналов, но только
некоторые из вершин кодируют исходные сигналы. Одна ошибка в сигнале
перемещает точку в пространстве сигналов вдоль одного из ребер гиперкуба
в соседнюю вершину. Если потребо-
Элементы теории информации и кодирования
177
вать, чтобы каждый из возможных исходных сигналов находился на
расстоянии, равном по крайней мере удвоенной длине ребра, от точки,
соответствующей другому сигналу, то одиночная ошибка сдвинет изображающую
точку лишь на длину одного ребра, и тем самым принятый сигнал перейдет в
разряд недопустимых ("незаконных"). Если минимальное расстояние между
точками, соответствующими сигналам, равно утроенной длине ребра куба, то
в результате одиночной ошибки принятый сигнал окажется к исходному
сигналу ближе, чем к любому другому сигналу. Тем самым мы обретаем
возможность исправления одиночной ошибки.
По существу нам необходимо ввести функцию расстояния, равную минимальному
числу ребер куба, которое необходимо пройти, чтобы перейти из одной
вершины куба в другую. В результате мы получаем число битов, на которое
одно из двух слов отличается от другого. Такое расстояние можно
рассматривать как логическую (в булевом смысле) разность или сумму двух
точек. Такая метрика называется расстоянием Хэмминга [4.1].
Минимальное расстояние между вершинами куба в пространстве сигналов мы
можем выразить через ошибки, которые можно исправить. Для единственности
кода минимальное расстояние должно быть равно по крайней мере единице.
Минимальное расстояние, равное двум, обеспечивает возможность обнаружения
одиночной ошибки, минимальное расстояние, равное трем, - возможность
исправления одиночной ошибки; любая одиночная ошибка приводит к тому, что
изображающая принятый сигнал точка оказывается ближе к исходному сигналу,
чем к любому другому. Минимальное расстояние, равное четырем, позволяет
достичь двух целей - исправления одной ошибки плюс обнаружения двойной
ошибки. Минимальное расстояние, равное пяти, позволило бы достичь
исправления двойной ошибки.
Наоборот, если требуется достичь определенного уровня обнаружения или
исправления ошибок, то необходимо выдерживать соответствующее минимальное
расстояние. Например, в случае исправления одиночной ошибки с минимальным
расстоянием, равным трем, мы можем окружить каждую точку в пространстве
сигналов единичной сферой так, что эти сферы не будут пересекаться. Объем
"сферы" единичного радиуса равен центру плюс п точек, отличающихся от
центра только одной координатой, т. е. я + 1. Полный объем я-мериого
пространства равен 2п - максимально возможному числу точек. Так как
"сферы" не перекрываются, максимальное число К точек, соответствующих
сигналам, должно удовлетворять неравенству
Полный объем ^ А, ,
-7- т ^Максимальное число сфер,
Объем "сферы" т Г
178
Глава 4
или
2я п + 1
:2*.
(4.3.15)
Мы можем исследовать соответствующие ограничения на исправление большего
числа ошибок. Например, для исправления двойной ошибки минимальное
расстояние должно быть равно пяти. Тогда мы можем описать
неперекрывающиеся сферы радиуса 2 вокруг каждой точки в пространстве
сигналов. Объем сферы радиуса 2 равен центру плюс п точек, отстоящих от
центра на единичное расстояние, плюс точки, отличающиеся от центра двумя
координатами, - их число равно п (п- 1) /2.
