3.2. МАТРИЧНОЕ ОПИСАНИЕ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ

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

Строки матрицы линейно независимы, и число строк равно размерности подпространства. Размерность всего пространства равна Всего существует кодовых слов, и различных -последовательностей над могут быть отображены на множество кодовых слов.

Любое взаимно однозначное соответствие -последовательностей и кодовых слов может быть использовано для кодирования, но наиболее естественный способ кодирования использует отображение

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

В качестве простого примера двоичного блокового кода рассмотрим порождающую матрицу

В этом случае информационное слово

будет кодироваться в кодовое слово

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

Поскольку является подпространством, оно имеет ортогональное дополнение которое состоит из всех векторов, ортогональных к Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как код. Когда само рассматривается как код, оно называется кодом, дуальным к

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

Это равенство позволяет проверить, является ли данное слово кодовым. Матрица называется проверочной матрицей кода. Она является матрицей; поскольку равенство выполняется при подстановке вместо с любой строки матрицы то

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что Тогда естественным определением проверочной матрицы в систематическом виде, очевидно, яаляется равенство поскольку

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

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

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

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

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

тогда II при систематическом кодировании отобразится в слово с

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

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

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

Таким образом, минимальный вес кода не может быть больше

Определение 3.2.7. Любой код с минимальным расстоянием, удовлетворяющим равенству

называется кодом с максимальным расстоянием.

Граница Синглтона показывает, что для исправления ошибок код должен иметь не менее проверочных символов (2 проверочных символа на ошибку). Большинство кодов, даже оптимальных, имеют намного больше проверочных символов, чем требует граница Синглтона, но параметры некоторых кодов удовлетворяют границе с равенством. Коды с максимальным расстоянием имеют точно проверочных символов.