2.8. Линейные коды

До сих пор мы уделяли значительное внимание всем частям системы связи, кроме кодера. В грубом приближении кодирование

можно рассматривать как операцию просматривания таблицы. Каждый из сигнальных векторов запоминается в своем регистре памяти длины N и всякий раз, когда сообщение подлежит передаче, соответствующий сигнальный вектор считывается в модулятор. Другой метод заключается в том, что каждое из сообщений мы перенумеровываем векторами длины К над -ичным алфавитом, как это показано на рис. 2.1. Тогда кодирование превращается во взаимно однозначное отображение множества векторов сообщений в множестве сигнальных векторов Ограничимся двоичными алфавитами, предположив, что при всех а затем обобщим результаты на случай Особенно удобным для реализации является отображение, называемое линейным кодом. В случае двоичных информационных символов линейный код состоит из линейных по модулю 2 комбинаций информационных символов и может быть реализован схемой, показанной на рис. 2.18.

Рис. 2.18. Линейный блочный кодер

Регистр длины К в точности соответствует регистру блока информационных символов, представленному на диаграмме общей системы (см. рис. 2.1). Кодер состоит из сумматоров по модулю 2, каждый из которых суммирует некоторое подмножество информационных символов порождая кодовый символ при так, как это показано на рис. 2.18. Мы будем говорить о векторе как о кодовом векторе. Сложение по модулю 2 двоичных символов обозначается символом и определяется следующим образом:

Простая проверка показывает, что эта операция ассоциативна и коммутативна, т. е. если а, b и с — двоичные символы (0 или 1), то

и

Таким образом, первую ступень кодирования двоичных данных можно представить в виде

где при всех

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

называется порождающей матрицей линейного кода, ее вектор-строками. Следовательно, (2.9.3) можно переписать в векторной форме как

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

Чтобы завершить процедуру линейного кодирования, необходимо преобразовать -мерный кодовый вектор с компонентами из в N-мерный сигнальный вектор с компонентами из множества действительных чисел. В простейшем случае бифазной или квадрифазной модуляции необходимо всего лишь одномерное отображение

и выполняется равенство В более сложных схемах модуляции приходится выбирать Например, в схеме амплитудной четырехуровневой модуляции, показанной на рис. 2.14, нужно

положить Здесь четыре возможные комбинации пар четно) дают четыре значения символа сигнала Аналогичным образом в схеме шестнадцатифазовой модуляции (см. рис. 2.146) приходится полагать и использовать четыре последовательных у-символа для выбора одного шестнадцатифазового х-символа.

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

также представляет собой кодовый вектор. Это легко показать, применив ассоциативный закон к векторам Получим

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

что также представляет собой кодовый вектор. Как правило, кодовые векторы перенумеровываются последовательно, причем Из (2.9.4) следует, что и Вектор 0 называют нулевым, поскольку для любого другого кодового вектора

В силу соотношения (2.9.1) справедливо равенство

которое означает, что при сложении по модулю 2 каждый вектор совпадает со своим противоположным (по сложению). Если некоторое множество удовлетворяет условию замкнутости (2.9.6), включает нулевой (2.9.7) и противоположные элементы (2.9.8) при некоторой ассоциативной и коммутативной операции (2.9.2), его называют Абелевой группой. Поэтому линейные коды называют еще и групповыми. Их называют также кодами с проверкой на четность, поскольку кодовый символ если сумма, информационных символов, формирующих нечетна, и если четна.

Интересное следствие, вытекающее из свойства замкнутости, заключается в том, что набор расстояний Хэмминга от некоторого

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

то

что очевидно равно числу несовпадающих позиций и, следовательно, расстоянию Хэмминга между векторами. Ясно, что набор расстояний от до других кодовых векторов совпадает с Кроме того, набор расстояний от любого вектора До других кодовых векторов есть все Но по свойству замкнутости представляет собой некоторый кодовый вектор, отличный от Более того, для любых двух различных векторов где имеем

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

и, следовательно,

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

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

Класс симметричных каналов с двоичным входом, в который входят АБГШ каналы при бифазной и квадрифазной модуляции вместе с каналами, в которые они переходят при симметричном квантовании, можно задать следующим образом. Пусть при всех

Такой канал с двоичным входом называют симметричным, если

Легко проверить, что АБГШ канал, ДСК и любой другой симметрично квантованный АБГШ канал удовлетворяют условию (2.9.13). Чтобы доказать, что для двоичных линейных кодов в этом классе каналов выполняется свойство равномерности ошибки (2.9.11) при декодировании по максимуму правдоподобия, отметим, что из (2.3.1), (2.3.3) и (2.9.1) вытекает соотношение

где

Имеем

Но если положить

что представляет собой всего лишь замену переменной суммирования (или интегрирования), то равенства (2.9.15) и (2.9.14) перейдут соответственно в равенство

и

Сравнивая (2.9.146) и (2.9.156) с (2.9.14а) и (2.9.15а) соответственно при при всех найдем, что благодаря симметрии линейного кода (2.9.9) и случайному выбору правила декодирования в случае равенства (см. § 2.2) справедливо соотношение

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

В качестве примера рассмотрим линейно закодированный и бифазно-модулированный сигнал, передаваемый в АБГШ канале. Точный подсчет вероятности ошибки в общем случае исключительно сложен (если не считать специальных случаев, таких, как ортогональные или симплексные коды; см. задачи 2.4 и 2.5). Однако верхнюю аддитивную границу (см. § 2.3) легко вычислить, если известны веса всех кодовых векторов. Из соотношений (2.3.4) и (2.3.10) получаем, что в АБГШ канале при бифазной модуляции

где Евклидово расстояние между сигнальными векторами. Пусть вес Хэмминга совпадающий с расстоянием Хэмминга до , равен Это означает, что кодовых символов равны единице, и, следовательно, кодовых символов равны (оставшиеся равны Очевидно также, что все кодовые символы равны поскольку Таким образом,

и, следовательно, при бифазной (или квадрифазной) модуляции в АБГШ канале использования аддитивной границы дает оценку

Легко обобщить оценку (2.9.17) на любой симметричный канал с двоичным входом, воспользовавшись границей Бхаттачария (2.3.15) и аддитивной границей (2.3.4). В случае каналов без памяти граница (2.3.15) переходит в границу

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

а из этого неравенства и из соотношения (2.3.4) найдем, что

где представляет собой определенное ранее расстояние Бхаттачария, равное в АБГШ канале [см. (2.3.17) и (2.9.17)]. Заметим также, что для ДСК

где вероятность перехода. Более точные результаты для ДСК мы получим в следующем параграфе.

В принципе можно было бы воспользоваться более точной границей Галлагера (2.4.8), но она требует, вообще говоря, большей информации о структуре кода, чем знания только набора расстояний между кодовыми векторами. На самом деле даже вычисление набора кодовых весов в общем случае сделать

непросто. Часто единственным известным кодовым параметром оказывается минимальное расстояние между кодовыми векторами. В таких случаях из соотношений (2.9.17) и (2.9.19) можно получить весьма слабые оценки

для АБГШ канала и

для общего канала с двоичным входом.

Слабость такого подхода к оценке качества линейных кодов (кажущаяся непреодолимой) связана с тем, что большинство длинных кодов, для которых известны методы построения, обеспечивающие заданные расстояния или для которых имеются хорошие описания, имеют, как правило, плохие метрические свойства. Ряд коротких кодов оказывается оптимальным для некоторых скоростей и при сравнительно коротких длинах. Примером служит код Голея, рассматриваемый в § 2.11. Эти коды весьма полезны для иллюстрации преимуществ кодирования, однако те несколько примеров, причем обособленных, которые можно привести, едва ли убедительны при изучении свойств линейных или нелинейных кодов. В следующей главе мы выявим большинство этих свойств путем рассмотрения всего ансамбля кодов заданной длины и скорости в противовес безнадежным попыткам поиска оптимальных членов такого ансамбля.