2. Основная лемма

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

Затем следует установить, какое максимальное возможное значение имеет смысл задавать для числа d при данных и b, и уже после этого окончательно сформулировать правила для отыскания оптимальных линейных форм.

При фиксированной системе линейных форм комбинация кода (VI.1.5) однозначно определяется значениями своих информационных символов, так как проверочные символы однозначно связаны с информационными, см. (VI.1.2). Поэтому символы комбинации можно рассматривать как свободные члены избыточной системы линейных уравнений, содержащей независимых переменных (информационных символов):

(VI.2.1)

Система уравнений (VI.2.1) является совместной и определенной. Выделим из нее произвольную подсистему уравнений

(VI.2.2)

Если (VI.2.2) имеется хотя бы одна подсистема линейно независимых уравнений, то она разрешается относительно т независимых переменных, и ее решение совпадает с информационными символами: .

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

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

Таким образом, доказана основная лемма.

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

Следствие 1 (Леммы VI.1). Если символов комбинации совпадают с символами хотя бы одной другой комбинации, то среди представляющих их линейных форм невозможно указать ни одной подсистемы линейно независимых форм.

Это следствие легко доказывается от противного и оказывается весьма полезным для определения числа всевозможных подсистем в (VI.2.1), разрешимых относительно независимых переменных.

Лемму - VI.1 и ее следствие хорошо иллюстрируют коды табл. VI.1 и VI.4. В первом из них две любые формы линейно независимы, поэтому кодовые комбинации различимы по двум любым символам. В коде (VI.1.7) формы и линейно независимы, и поэтому все кодовые комбинации различимы по соответствующим им символам. Символы комбинации , стоящие на и позициях, совпадают с символами комбинаций , и формы и линейно зависимы. То же самое можно сказать про символы комбинации и , стоящие на и позициях, и линейные формы и .