Линейные коды

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

Код называется линейным, если он является подпространством этого пространства.

Рассмотрим способы задания линейного кода. Первый способ состоит в задании базиса из векторов подпространства размерности . Тогда

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

Если эти уравнения независимы, то размерность пространства решений равна . Бинарная матрица системы имеет размер . Тогда

. (1)

Матрица называется проверочной матрицей кода .

Пример. Описанный выше 7-разрядный код Хемминга представляет собой линейный код с проверочной матрицей

.

Так как

,

то из условия , получаем соотношения, которым удовлетворяют разряды кодовых слов в коде Хэмминга

Эти соотношения представляют собой проверки на четность. Например, первое из них выполняется, когда количество единиц в разрядах 4, 5, 6 и 7.

Будем далее считать, что линейный код задается проверочной матрицей , то есть определяется по формуле (1). Рассмотрим теперь корректирующие возможности линейного кода, то есть его способность исправлять ошибки. Как было установлено выше, это зависит от параметра . Для линейного кода он вычисляется проще, чем в общем случае. Весом двоичного слова называется число разрядов слова, равных единице:

.

Теорема 2. Если – линейный код, то

,

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

Это утверждение очевидным образом следует из следующих двух фактов

Теорема 3. Линейный код исправляет ошибок, если в его проверочной матрице любые столбцов линейно независимы.

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

. (2)

Количество коэффициентов, равных единице, в выражении (2) равно , нулевые коэффициенты можно отбросить. Тогда равенство (2) представляет собой соотношение линейной зависимости между столбцами проверочной матрицы. При выполнении условия теоремы получаем, что , следовательно, код исправляет ошибок.