§ 7.2. Коды Рида — Маллера первого порядка

В качестве первого примера, иллюстрирующего применение метода обобщенной ортогонализации, приведем следующую теорему.

Теорема 22. Для любого существует двоичный блоковый -код с кодовым расстоянием допускающий ортогонализацию в 2 шага.

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

такой код имеет минимальное расстояние и может быть ортогонализован в два шага.

Определим, сколько можно построить проверок, ортогональных относительно Для каждой строки матрицы начинающейся символами 10, найдется единственная строка, начинающаяся символами 0 1 и совпадающая с первой во всех остальных позициях. Сумма двух этих строк дает проверку относительно и никакие другие информационные шумовые символы этой проверкой не контролируются. Точно так же для каждой строки матрицы начинающейся символами веса не менее 5, найдется единственная строка, начинающаяся символами и совпадающая с первой во всех остальных позициях. Сумма этих строк снова дает проверку относительно и никакие другие информационные шумовые символы этой проверкой не контролируются. Наконец, во всех строках веса 3 матрицы начинающихся символами 1 1, третьи единицы находятся в несовпадающих позициях. Каждая из них представляет собой проверку, контролирующую сумму и еще один информационный шумовой символ, различный для различных строк. Пользуясь этим методом, можно построить столько проверок, ортогональных относительно сколько существует строк матрицы с единицей на первой позиции, т. е.

Из симметрии матрицы имеющей своими строками все векторы нечетного веса, не меньшего трех, следует, что можно построить проверок, ортогональных относительно суммы любых двух информационных шумовых символов. Теперь считая, что все суммы известны и могут быть использованы для исключения переменных из первоначальных проверочных уравнений, можно построить модифицированную проверочную матрицу Заметим, что из известных по предположению сумм можно построить любую сумму четного числа переменных [например, Но так как все строки матрицы имеют нечетный вес, то все проверки

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

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

Остается показать, что Минимальное расстояние не может быть менее этой величины. С другой стороны, может не более чем на единицу превышать число единиц в любом столбце матрицы (ср. с леммой Г.1), а в каждом столбце имеется единиц. Отсюда должно быть в точности равным что и завершает доказательство теоремы.

Коды, описанные в доказательстве теоремы 18, эквивалентны кодам Рида — Маллера первого порядка [12, стр. 91], т. е. они отличаются от последних только перестановкой позиций. Однако в той форме, в которой эти коды использованы, они являются систематическими, что означает, что первые кодовых символов совпадают с информационными. Это упрощает кодирование и обычно представляется желательным также и по другим причинам (например, некоторые принимающие станции могут и не иметь декодирующих устройств, но все же там желательно извлечь некоторые данные из принятой информации). Коды Рида — Маллера обычно не даются в систематической форме, так как алгоритм декодирования Рида [14] не может применяться непосредственно, т. е. без предварительного линейного преобразования.

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

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

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