Построение линейного кода по заданной порождающей матрице

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

(7.1)

Чтобы найти решение, нужно произвольно задать компонент вектора , а остальные вычислить по формуле (2.6). Таким образом, первые компонент вектора полностью его определяют

(7.2)

Матрица называется порождающей. Ее столбцы образуют базис пространства решений системы . Учитывая особенности поля , порождающая матрица имеет вид .

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

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

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

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

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

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

Рассмотрим некоторые примеры линейных кодов.

Код с разрядом для проверки на четность является линейным кодом с проверочной матрицей . Действительно, уравнение в этом случае имеет вид

или

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

Код с повторением является линейным кодом с проверочной матрицей

Линейное уравнение, определяющее код, в данном случае имеет вид

а его решения описываются соотношениями . Эти равенства означают, что три проверочных разряда повторяют один информационный разряд. Любые 3 столбца проверочной матрицы являются линейно независимыми (сумма любых трех столбцов не равна нулевому столбцу), поэтому кодовое расстояние, равное 4, обеспечивает исправление одной ошибки и обнаружение трех. Код содержит всего 2 кодовых слова: и . Считается, что слово передано с ошибкой, если не все разряды в нем одинаковы. Исправление одной ошибки производится по принципу голосования. Если в полученном слове больше единичных разрядов, то, очевидно, оно ближе к кодовому слову , чем к кодовому слову , поэтому декодирование производится в слово . По аналогичной причине, когда в принятом слове больше нулевых разрядов, декодирование производится в слово .