Помехоустойчивое кодирование (ч. 1) (Материалы к семинарам по помехоустойчивому кодированию)

Помехоустойчивое кодирование применяется в дискретном канале связи для борьбы с ошибками, возникающими при передаче из-за влияния помех.

Исторически помехоустойчивое кодирование развивалось по двум направлениям: для приема «в целом» и для поэлементного приема.

При приёме «в целом» каждому сообщению ставится в соответствие свой отдельный сигнал. В приемнике принятый сигнал сравнивается с образцами сигналов, соответствующих всем возможным сообщениям. После сравнения выносится решение о том, какой образец наиболее похож на принятый сигнал. Соответствующее этому образцу сообщение считается принятым.

Примером приема «в целом» может служить иероглифический текст. В нём слово читается как цельная картинка, а не как набор отдельных символов.

Чтобы минимизировать вероятность ошибок необходимо использовать набор сигналов максимально непохожих друг на друга. Показателем «похожести» двух сигналов является их коэффициент взаимной корреляции . Поэтому при приеме «в целом» m возможных сообщений требуется система из m сигналов, коэффициент взаим­ной корреляции  между любой парой которых был бы минимален.

В. А. Котельников показал, что этот минимальный коэффициент взаим­ной корреляции равен

(*)

где l = 1,2,…

Очевидно, что наименьший _min=  1. Это возможно только в системе из двух сигналов, которые называются противоположными. При увеличении количества сигналов _min неизбежно увеличивается. Кроме этого не во всех системах коэффициент взаим­ной корреляции между разными парами сигналов остается одинаковым.

Для наглядности можно представить сигналы как геометрические точки в многомерном пространстве (гиперпространстве), тогда степень «непохожести» двух сигналов будет отображена расстоянием между соответствующими точками, а сама система сигналов будет являться некой геометрической фигурой. Среди геометрических фигур гиперпространства извест­на такая, в которой расстояния между любой парой вершин являются одинаковыми. Такая фигура называется симплексом. В двумерном пространстве такой фигурой является равносторонний треугольник, а в трехмерном пространстве  тетра­эдр, изображенный на рис. 1. Если геометри­ческой моделью сигналов являются вершины симплекса, то соответствующие сигналы называются симплексными.

Такие системы существуют при , где и т. д. Все пары симплексных сигналов в системе имеют . Симплексные сигналы легко генерируются на регистрах сдвига с со­ответствующим образом подобранными линейными обратными связями. На рис. 2 приведен такой генератор при k = 3, что позволяет полу­чить двоичных симплексных сигналов. Для получения одного из них надо в сдвигающий ре­гистр (СР) записать ненулевое k= 3 – разрядное двоичное число, а затем, сдвигая содержимое регистра слева направо, через n = 7 тактов на выходе регистра закончится один период симплексного сиг­нала. Элемент  на этом рисунке осуществляет операцию суммирова­ния по модулю два, которая определяется в соответствии с таблицей, приведенной на этом рисунке.

С
имплексные сигналы, формируемые та­ким способом, часто называют линейными рекуррентными последова­тельностями максимальной длины, или, сокращенно, М-последовательностями. Таким образом, М-последовательности позволяют получить сигналы, строго оптимальные при их оптимальном приеме в целом в присутствии аддитивного белого гауссова шума.

Из соотношения (*) следует, что . Сигналы, у которых  = 0 называются ортогональными. При большом числе сигналов ортогональные сигналы близки к оптимальным, точнее, орто­гональные сигналы являются асимптотически оптимальными. Двоичные ортогональные сигналы можно рассматривать как строки матрицы Адамара соответствующего размера. Матрица Адамара Н – это квадратная таблица размера , состоящая из символов и обладающая тем свойством, что

где Н^Т – транспонированная матрица Н, т.е. такая, которая полу­чается из Н путем замены ее строк на столбцы; I – единичная матри­ца, т.е. такая, элементы которой на главной диагонали равны едини­це, а остальные элементы равны нулю.

Из этого определения матрицы Адамара следует, что любые две ее строки ортогональны. Перестановка ее строк или столбцов, равно как и умножение ее строк или столбцов на –1, сохраняет это свойст­во ортогональности. Предполагается, что матрицы Адамара существу­ют для всех (l = 1, 2, 3, …) и для всех таких в на­стоящее время матрицы Адамара построены. Если (k= 1, 2, 3,...), то матрицы Адамара можно построить, используя так называемое кронекеровское произведение матриц Адамара меньшего размера. В соот­ветствии с этим правилом

где H_i – матрица Адамара размера ; – матрица Адамара раз­мера , в которой все 1 заменены на – 1 и наоборот. При этом исходная матрица .

Строки получаемых таким обра­зом матриц Адамара принято называть функциями Уолша, по имени пер­вого их исследователя (Walsh T.L., 1923 г.)

Если ко всем комбинациям ортогонального двоичного кода доба­вить их инверсии, т. е. комбинации исходного кода, в которых все «1» заменены на «–1», и обратно, то полученное множество из 2п комбинаций будет составлять биортогональный код. Легко ви­деть, что в полученной системе коэффициент взаимной корреляции между разными парами сигналов будет разным (такие сигналы называются неэквидистантные), причем некоторые пары сигналов (являющихся инверсиями друг друга) будут иметь  = 1.

Системы сигналов, у которых между всеми парами одинаковые коэффициенты , называются эквидистантными. К ним относятся симплексные и ортогональные сигналы.

В среднем коэффициент взаимной корреля­ции любой пары сигналов . Таким образом, в соответст­вии с (*) это будут оптимальные в среднем сигналы при их оптимальном приеме «в целом».

Иногда сигналы, у которых средний коэффициент взаимной корре­ляции меньше нуля, называют трансортогональными. Таким образом, симплексные и биортогональные сигналы относятся к трансортогональ­ным.

Из изложенного выше следует, что трансортогональные и ортого­нальные сигналы либо оптимальны, либо близки к оптимальным при приеме в целом в присутствии аддитивного белого гауссова шума, и весьма просто могут быть генерированы. Что же мешает практичес­кому использованию этих сигналов при оптимальном приеме в целом? Препятствием является сложность реализации оптимального приемника. Для каждого из m возможных сигналов в приемнике необходим свой коррелятор (согласованный фильтр). При значительном числе m такой приемник оказывается практически нереализуемым.

Другим методом, позволяющим упростить реализацию прием­ника, является переход от приема в целом к поэлементному (посим­вольному) приему. При этом процедура приема разбивается на 2 эта­па и осуществляется двумя решающи­ми схемами. Первая решающая схе­ма выносит решения о принимаемом символе (элементе) сиг­нала, а вторая решающая схема, наблюдая п решений первой, выносит решение о номере принятого сигнала. Таким образом, вторая решающая схема, являющаяся собственно декодером, работает со стандартными сигналами – решениями первой решающей схемы, – которые уже свободны от шумов, т. е. это цифровые сигналы.

Продолжая аналогию с текстом, можно сравнить поэлементный прием с буквенной системой записи слов. Таким образом, построение приемника похоже на изучение азбуки. Для того, чтобы читать тексты на европейских языках, надо выучить несколько десятков букв и знаков препинания, а чтобы читать китайские или японские тексты, необходимо выучить несколько тысяч иероглифов.

Если принятый сигнал жестко квантуется на два подпространства, обозначаемых как «0» и «1», то такой способ поэлементного приема называет­ся поэлементным приемом с жесткими решениями. Существует поэлементный прием с мягкими реше­ниями, когда все пространство сигналов квантуется в первой решаю­щей схеме на число подпространств большее, чем основание исполь­зуемого кода. Например, для двоичных кодов (q = 2) возможно кван­тование на 2² = 4 или 2³ = 8 зон, и при попадании результата обра­ботки сигнала и шума в некоторую зону во вторую решающую схему передается номер этой зоны, представленный для приведенных выше примеров соответственно двухразрядным или трехразрядным двоичным кодом. Мягкие решения позволяют улучшить помехоустойчивость прием­ника, однако существенно усложняют работу декодера.

Сравнение помехоустойчивости оптимального приема в целом и поэлементного приема с жесткими решениями показывает, что при одинаковых условиях всегда имеет место неравенство

где Р_Ц и P_П – вероятности ошибки в определении номера принятого сигнала при приеме в целом и при поэлементном приеме с жесткими решениями соответственно, причем равенство выполняется только тогда, когда используемые сигналы не содержат избыточности. Это соотношение известно как одна из формулировок теоре­мы Финка (Л. М. Финк, 1963). Таким образом, упростив реализацию приемника путем перехода от приема в целом к поэлементному приему с жесткими решениями, в случае сигналов, содержащих избыточность, т. е. при , мы проигрываем в помехоустойчивости приема. Физи­чески это объясняется тем, что при использовании жестких решений в первой решающей схеме часть информации о принимаемых символах утрачивается. Именно – утрачиваются конкретные значения апостери­орной вероятности принятых символов.

Для повышения помехоустойчивости поэлементного приема при возможно большей простоте реализации второй решающей схемы (т. е. декодера) разработано большое число помехоустойчивых кодов и разнообразных алгоритмов их декодирования.

Общая идея помехоустойчивого кодирования заключается в введении в передаваемые данные искусственной избыточности, позволяющей на приемной стороне обнаруживать и исправлять возникшие ошибки.

Так при плохой слышимости в телефонном разговоре «именуются» буквы важного слова. Например, слово «КНИГА » передается как «Константин, Николай, Иван, Григорий, Александр». Вместо одного слова передано пять, но зато вероятность ошибки при приеме значительно снижена.