что является одним из возможных выборов матрицы Н. Заметим, что точно так же, как существует много способов выбора матрицы G, существует много способов выбора матрицы Н.

Теорема 3.2.1. Порождающая матрица кеда является проверочной матрицей дуального кода W.

Доказательство непосредственно следует из предыдущих рассуждений. □

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

Теорема 3.2.2. Код содержит ненулевое кодовое слово веса Хэмминга не более w тогда и только тогда, когда Н содержит множество из w линейно зависимых столбцов.

Доказательство. Для любого кодового слова с выполняется равенство сН = 0. Пусть с имеет вес w. Исключим из рассмотрения нулевые компоненты вектора с. Полученное равенство будет соотношением линейной зависимости w столбцов из Н. Следовательно, Н содержит множество из w линейно зависимых столбцов.

Обратно, если Н содержит множество из w линейно зависимых столбцов, то найдется равная нулю линейная комбинация, составленная не более чем из w столбцов. Соответствующие w ненулевых коэффициентов определяют вектор веса не более w, для которого сН = 0. □

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

сН = 0,

Это равенство позволяет проверить, является ли данное слово кодовым. Матрица Н называется проверочной матрицей кода. Она является (п -k) X п матрицей; поскольку равенство сН = О выполняется при подстановке вместо с любой строки матрицы G, то *

ОН = 0.

Для порождающей матрицы G, рассмотренной в предыдущем примере, получаем

10 110 0 110 1

S.2. МАТРИЧНОЕ ОПИСАНИЕ 65

Следствие 3.2.3. Кед имеет минимальный вес не менее w тогда и только тогда, когда каждое множество из w ~ I столбцов матрицы Н линейно независимо.

Отсюда следует, что для того чтобы найти (п, )-код, исправляющий t ошибок, достаточно найти (п - k) X «-матрицу Н, в которой любые 2t столбцов линейно независимы.

Из данного (п, й)-кода с минимальным расстоянием d* можно получить новый код с теми же параметрами, если в каждом кодовом слове выбрать две позиции и поменять местами символы в этих позициях. Однако в этом случае мы получим код, который лишь тривиальным образом отличается от исходного. Говорят, что такой код эквивалентен исходному. Вообще два линейных кода, одинаковых с точностью до перестановки координат, называются эквивалентными.

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

1) перестановки столбцов и

2) элементарных операций над строками.

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

G = [l;P],

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

Предположим, что G= [1;Р]. Тогда естественным определением проверочной матрицы в систематическом виде, очевидно, является равенство Н = [- Р": I], поскольку

GHT= [I :Р] = p-f р = 0.

е гл. 3. Линейные блоковые Коды

Определение 3.2.4. Систематическим кодом называется код, которого каждое кодовое слово начинается с информационных символов. Оставшиеся символы называются проверочными символами.

Принято говорить о систематическом коде, хотя это всегда означает систематическое кодирование соответствующего кода.

Теорема 3.2.5. Каждый линейный код эквивалентен систематическому линейному коду.

Доказательство. Систематический линейный код кодируется умножением информационного вектора на порождающую матрицу G в систематИ(Н:еском виде, а каждая порождающая матрица G эквивалентна некоторой систематической матрице. □

В качестве примера выберем

10 0110

О 1 0 О 1 о о 1 1 1 1 ,

тогда i = [О 1 1 ] при систематическом кодировании отобразится в слово с = [О 1 1 1 0].

Рассматривая код в систематическом виде, можно получить простое неравенство, связывающее параметры кода. Эта граница является очень неточной, и большинство хороших кодов имеет минимальное расстояние, существенно меньшее, чем следует из границы, но бывают случаи, когда она оказывается полезной. Пусть задан некоторый систематический (п, й)-линейный код с минимальным расстоянием d*. Следующая теорема накладывает ограничение на возможные значения (п, k, d*).

Теорема 3.2.6 (граница Синглтона). Минимальное расстояние {минимальный вес) любого линейного (п, к)-кода удовлетворяет неравенству

d* I + п -k.

Доказательство. Ненулевое слово минимального веса в коде имеет вес d*. Существуют слова систематического кода с одним ненулевым информационным символом и п - k проверочными символами. Такое кодовое слово не может иметь вес, больший 1 +

") В гл. 5 будут рассматриваться циклические коды и будет удобно по соглашению считать, что кодовое слово с начинается с координаты с максимальным номером Сп 1 и кончается Со. В этом случае будем использовать эквивалентные матрицы вида О = [Р ! 1] и Н = [1 i - Р) для некоторой новой р. Эти матрицы получаются обращением всех столбцов и строк матриц, записанных в систематическом виде. Такие матрицы также называются систематическими.