Приложение Г. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 21

1. Предварительные соображения

Для удобства представим матрицу входящую в проверочную матрицу блокового -кода в виде

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

Лемма Если минимальное расстояние блокового и любые различные символы из ряда то

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

Лемма Имеет место равенство

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

При равенство дает

Здесь знак указывает на сложение по а знак — на обычное сложение действительных чисел. Равенство легко проверяется подстановкой всех четырех возможных комбинаций значений

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

Применяя равенство к двум членам справа в равенстве получим

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

Равенство приводится к виду

что и доказывает лемму индукцией по

2. Доказательство теоремы 21

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

Случай 1:

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

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

а это совпадает с достаточным условием полной ортогонализации.

Случай 2:

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

тельно будет неравенство

или неравенство

Из соображений симметрии неравенство является также достаточным условием существования проверок, ортогональных относительно а отсюда — достаточным условием полной ортогонализации. Применяя леммы Г. 1 и Г. 2 к первым двум столбцам матрицы получим, что неравенство является также необходимым условием для быть минимальным кодовым расстоянием.

Случай 3:

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

или

Снова, в силу соображений симметрии, неравенство является также достаточным условием существования проверок, ортогональных относительно а отсюда — достаточным условием полной ортогонализации. Применяя леммы Г. 1 и Г. 2 к первым трем столбцам матрицы Я, находим, что неравенство является также необходимым условием для быть минимальным кодовым расстоянием.

СПИСОК ОБОЗНАЧЕНИЙ

(см. скан)