Задание линейного кода

Линейный n-значный код, содержащий k информационных символов, удобно задавать с помощью порождающей матрицы G, содержащей kстрок и n столбцов. В качестве строк порождающей матрицы выбираются любые не нулевые линейно независимые n-значные векторы, отстоящие друг от друга не менее чем на заданное кодовое расстояние. Векторы V₁, V₂ , …, V_k называются линейно зависимыми, если существуют скаляры C₁, C₂, …, C_k не все равные нулю, такие, что:

C₁ V₁ + C₂ V₂ + ... + C_k V_k = 0

Для двоичных кодов C_i = {0, 1}, а сложение выполняется по модулю два. Если же равенство выполняется лишь в единственном случае, когда C₁ = C₂ = =..= C_k = 0, то векторы V₁, V₂ … V_k называются линейно независимыми.

Пример:

Вектора а = (2, 1, 0); b = (-5, 0, 3); d = (3, 4, 3) Составим векторное равенство C₁^.a+ C₂^.b + C₃^.d = 0 равносильное в координатной записи системе

2 ^. C₁ - 5 ^. C₂ + 3 ^. C₃ = 0 C₁ = -4 ^. C₃

C₁ + 4 ^. C₃ = 0 тогда C₂ = -C₃

3 ^. C₂ + 3 ^. C₃ = 0

Таким образом, векторное равенство справедливо при C₁= -4 ^. C₃; C₂= -C₃; C₃ не равно нулю, то есть имеет место равенство:

-4 ^. C₃^.a - C₃^.b + C₃^.d = 0 или d = 4^.a + b

Следовательно, вектор d является линейной комбинацией векторов а и b, то есть векторы a, b, d – линейно зависимы.

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

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

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

Свойство линейной независимости остается справедливо при: перестановке строк и столбцов, замены i-той строки суммой i-той и j-той строки, i неравно j. Используя эти операции, можно привести матрицу G к некоторой стандартной форме, получившей название приведенно-ступенчатой формы.

Порождающая матрица линейного кода в приведенно-ступенчатой форме имеет следующий вид:

G = [ I G" ], где I - единичная матрица размерности k × k,

a G" - матрица размерности k × (n - k)

Порождающая матрица кода (7, 4) имеет следующий вид:

1 0 0 0 1 0 1

G = 0 1 0 0 1 1 1

0 0 1 0 1 1 0

0 0 0 1 0 1 1

Операция кодирования сводится к умножению передаваемого сообщения S длиной к на порождающую матрицу:

X = S^. G = (S₁, S₂, …, S_k, C₁, C₂, …, C_n-k),

где C_j = Σ S₁^. G_ij, j = l, 2, ..., n-k i = l, 2, ..., k;

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

Пример:

Пусть входные сообщения поступают в виде следующих двоичных
векторов: S₁ = 0001, S₂ = 0110, S₃ = 1111

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

X₁ = 0001 011, X₂ = 0110 001, X₃ = 1111 111

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

Наряду с порождающей матрицей используется проверочная матрица: H=[G"^T; I],

где G"T – транспонированная матрица G" размерности (n - k) × k, I – единичная матрица порядка (n - k).

Если в m × n — матрице А строки и столбцы поменять местами, то получим n × m – матрицу А^T которая называется транспонированной для А.

Проверочная Н и порождающая Gматрицы удовлетворяют легко проверяемому соотношению:

G^. H^T = 0, где H^T – транспонированная проверочная матрица. На этом свойстве основано декодирование линейных групповых кодов. Если в принятом слове X отсутствуют ошибки, то матричное произведение равно нулю:

X^. H^T = S ^. G ^. H^T = S ^. 0 = 0;

Если же при передаче информации возникли ошибки, то:

(Х + Е) ^. H^T = X^. H^T + E^. H^T = 0 + E^. H^T = E^. H^T – синдром, где Е – вектор ошибки.

Длина синдрома равна (n-k). Ненулевая величина синдрома свидетельствует о наличии ошибки. Если различным ошибкам соответствуют различные синдромы, то по виду синдрома можно определить вид ошибки и, следовательно, исправить ее.

Для рассмотренного ранее кода (7, 4) проверочная матрица запишется следующим образом:

1 1 1 0 1 0 0

H = 0 1 1 1 0 1 0

1 1 0 1 0 0 1

Пусть было передано сообщение S = 0110, которое в соответствии с порождающей матрицей было закодировано вектором Х = 0110 001. Если при передаче ошибок не произошло, то синдром: X^. H^T = {000}

Допустим теперь, что первый символ был принят неверно, т.е. был принят вектор Х= 1110 001. В этом случае синдром – {101}.