1.10. НЕКОТОРЫЕ ОБЩИЕ СВОЙСТВА ЛИНЕЙНОГО КОДА

В заключение этой главы приведем несколько важных свойств линейных кодов. Первые четыре из них справедливы для линейных кодов над любым полем.

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

Эта теорема не требует доказательства.

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

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

Теорема 10 дает другое доказательство того, что расстояние кодов Хэмминга равно 3. В самом деле, все столбцы матрицы различны и, следовательно, любые два линейно независимы, в то время как имеются три линейно зависимых столбца.

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

Теорема 11. (Граница Синглтона.) Если — -код. то

Первое доказательство. Число это ранг матрицы который равен максимальному числу линейно независимых столбцов.

Второе доказательство. Вес кодового слова, в котором только один информационный символ не равен нулю, не превосходит Следовательно,

Коды с называются разделимыми кодами с максимальным расстоянием (сокращенно кодами МДР), и они изучаются в гл. 11.

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

Теорема 12. (Граница Варшамова — Гилберта.) Если выполняется неравенство

то существует двоичный линейный код длины с минимальным расстоянием по крайней мере имеющий не более чем проверочных символов.

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

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

Для больших см. теорему 30 и рис. 17.7.

Упражнение. (45). Продолжение границы Варшамова — Гилберта. Доказать, что если

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