3.2. Описание линейных кодов при помощи матриц

Любой набор базисных векторов линейного кода V можно рассматривать как строки матрицы называемой порождающей матрицей кода Пространство строк матрицы является линейным кодом V, и вектор является кодовым вектором тогда и только тогда, когда он является линейной комбинацией строк матрицы Если

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

Преимущество матричного описания кодов ясно: во всех случаях, кроме того, когда малы, матричное описание кода более компактно, чем перечисление всех кодовых векторов. Двоичный групповой -код описывается матрицей размерности , но имеет более чем 109 кодовых векторов.

Пример. Код из предыдущего примера является пространством строк любой из следующих матриц:

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

Если и элемент, входящий в строку и столбец матрицы И, обозначен то соотношение 3.1 означает, что для каждого (т. е. для каждой строки матрицы

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

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

Пример. Нулевое пространство для векторного пространства V из предыдущего примера содержит четыре вектора; и Эти четыре вектора образуют векторное пространство. Первые два ненулевых вектора линейно независимы и образуют базис. Таким образом, является пространством строк матрицы

Код является нулевым пространством этой матрицы. Каждый вектор из задает уравнение, которому должны удовлетворять компоненты любого кодового вектора. Например, вектору соответствует уравнение

которое должно удовлетворяться для любой точки кода Для двоичных кодов это эквивалентно наличию четного числа единиц среди последних четырех компонент кодового вектора или проверке на четность последних четырех компонент. Заметим, что в отличие от векторов над полем действительных чисел ненулевой вектор над конечным полем может быть ортогонален сам себе. Например, вектор принадлежит одновременно V, и

Векторное пространство V и его нулевое пространство V оба являются подпространствами пространства последовательностей длины и потому оба являются линейными кодами. Они называются двойственными кодами. Если V — это -код, то - это -код. Если код является пространством строк некоторой матрицы, то двойственный к нему код — это нулевое пространство этой матрицы и наоборот.

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

Доказательство. Вектор является кодовым глэвом тогда и только тогда, когда или, если обозначить вектор-столбец матрицы тогда и только тогда, когда

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

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

Следствие 3.2. Код, являющийся нулевым пространством матрицы И, имеет минимальный вес (и следовательно, минимальное расстояние), равный самое меньшее тогда и только тогда, когда любая совокупность или меньшего числа столбцов Я является линейно независимой.

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

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

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

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

Пусть теперь произвольная последовательность длины к. Рассмотрим вектор и, являющийся линейной комбинацией строк матрицы с элементом в качестве коэффициента:

где

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

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

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

Теорема 3.4. Если V — пространство строк матрицы где единичная матрица размерности а матрица размерности — то V является нулевым пространством матрицы где — единичная матрица размерности

Доказательство. Легко проверить, что и поскольку сумма рангов матриц равна то пространство строк матрицы является нулевым пространством для И. Ч. т. д.

Если кодовый вектор, то

что в точности совпадает с соотношениями 3.5. Связь между в рассматриваемом случае особенно ясно видна из этого соотношения, если заметить, что в обоих случаях элемент из

строки и столбца матрицы является как раз коэффициентом пр информационном символе в сумме, которая задает проверочный символ

Пример. Порождающая матрица

для кода, использованного в предыдущих примерах, задана в приведенно-ступенчатой форме. Если положить

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

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

и это уравнение может быть решено относительно