11.2. ПОРОЖДАЮЩАЯ И ПРОВЕРОЧНАЯ МАТРИЦЫ

Пусть -код над GF(q) с проверочной матрицей и порождающей матрицей

Теорема 1 Код представляет собой код МДР тогда и только тогда, когда любые столбцов матрицы линейно независимы

Доказательство Код содержит кодовое слово веса тогда и только тогда, когда столбцов матрицы линейно зависимы

(теорема 10 гл. 1). Следовательно, в коде расстояние тогда и только тогда, когда никакие или меньше столбцов матрицы не являются линейно зависимыми.

Теорема 2. Если код МДР, то дуальный ему код также является кодом МДР.

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

Пример. Матрица

является порождающей для -кода МДР над полем Дуальный ему код имеет порождающую матрицу

и также представляет собой -код МДР.

Следствие 3. Пусть -код над GF(q). Следующие утверждения эквивалентны:

(i). - код МДР.

(ii). Любые столбцов порождающей матрицы линейно независимы (т. е. любые символов в кодовых словах могут быть выбраны в качестве информационных символов).

(iii). Любые столбцов проверочной матрицы линейно независимы.

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

Открытая проблема может быть теперь сформулирована следующим образом.

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

Или, что эквивалентно, в терминологии векторных пространств:

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

Упражнения. (2). Показать, что единственными двоичными кодами МДР являются тривиальные коды.

(3). Граница Синглтона для нелинейных кодов. Показать, что если -код над то всегда