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

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

( 7.1)

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

( 7.2)

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

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

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

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

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

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

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

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

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

или

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

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

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

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