такой код имеет минимальное расстояние
и может быть ортогонализован в два шага.
Определим, сколько можно построить проверок, ортогональных относительно
Для каждой строки матрицы
начинающейся символами 10, найдется единственная строка, начинающаяся символами 0 1 и совпадающая с первой во всех остальных позициях. Сумма двух этих строк дает проверку относительно
и никакие другие информационные шумовые символы этой проверкой не контролируются. Точно так же для каждой строки матрицы
начинающейся символами
веса не менее 5, найдется единственная строка, начинающаяся символами
и совпадающая с первой во всех остальных позициях. Сумма этих строк снова дает проверку относительно
и никакие другие информационные шумовые символы этой проверкой не контролируются. Наконец, во всех строках веса 3 матрицы
начинающихся символами 1 1, третьи единицы находятся в несовпадающих позициях. Каждая из них представляет собой проверку, контролирующую сумму
и еще один информационный шумовой символ, различный для различных строк. Пользуясь этим методом, можно построить столько проверок, ортогональных относительно
сколько существует строк матрицы
с единицей на первой позиции, т. е.
Из симметрии матрицы
имеющей своими строками все векторы нечетного веса, не меньшего трех, следует, что можно построить
проверок, ортогональных относительно суммы любых двух информационных шумовых символов. Теперь считая, что все суммы
известны и могут быть использованы для исключения переменных из первоначальных проверочных уравнений, можно построить модифицированную проверочную матрицу
Заметим, что из известных по предположению сумм можно построить любую сумму четного числа переменных
[например,
Но так как все строки матрицы
имеют нечетный вес, то все проверки
относительно
контролируют четное число переменных
, а эти последние можно исключить с помощью сумм, считающихся известными.
Таким образом, посредством строк матрицы
начинающихся единицей, можно построить матрицу
имеющую
строк вида
и, следовательно, из модифицированной проверочной матрицы можно построить
проверок, ортогональных относительно
Из симметрии матрицы
следует, что аналогичный процесс может быть применен к
Остается показать, что
Минимальное расстояние не может быть менее этой величины. С другой стороны,
может не более чем на единицу превышать число единиц в любом столбце матрицы
(ср. с леммой Г.1), а в каждом столбце имеется
единиц. Отсюда
должно быть в точности равным
что и завершает доказательство теоремы.
Коды, описанные в доказательстве теоремы 18, эквивалентны кодам Рида — Маллера первого порядка [12, стр. 91], т. е. они отличаются от последних только перестановкой позиций. Однако в той форме, в которой эти коды использованы, они являются систематическими, что означает, что первые
кодовых символов совпадают с информационными. Это упрощает кодирование и обычно представляется желательным также и по другим причинам (например, некоторые принимающие станции могут и не иметь декодирующих устройств, но все же там желательно извлечь некоторые данные из принятой информации). Коды Рида — Маллера обычно не даются в систематической форме, так как алгоритм декодирования Рида [14] не может применяться непосредственно, т. е. без предварительного линейного преобразования.
Наконец, следует отметить, что метод порогового декодирования можно усовершенствовать следующим образом. После того как определены все
сумм
и из модифицированной проверочной матрицы определено значение