4.2. Граница Варшамова-Гилберта

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

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

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

то существует код из символов, самое большее с проверочными символами (и, следовательно, самое меньшее с информационными символами) с минимальным расстоянием Этот код является нулевым пространством матрицы размерности которая получается при описанном способе выбора столбцов.

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

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

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

или если

Но поскольку то

Эта граница изображена на рис. 4.1 в предположении, что настолько велики, что