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

Блочным линейным кодом называется (n,k) код, проверочные символы которого являются линейными комбинациями информационных символов. Здесь:

n – длина кода, то есть длина кодовых слов

k – число информационных символов

Обозначим U – последовательность из k информационных символов.

U=(u₁, u₂,…….u_k)

Обозначим V – кодовое слово линейного кода длиной n символов.

V=(v₁, v₂,……….v_n)

Кодовое слово V формируется из последовательности U по следующему правилу:

Коэффициенты a_l,i представляют собой фиксированные двоичные символы, не зависящие от u. При выборе разных совокупностей a_l,i получаются различные линейные коды.

Отношение R=k/n называется скоростью кода, а величина W=1-R – называется избыточностью кода.

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

При задании линейного кода с помощью набора коэффициентов a_l,i записывается образующая матрица G. Матрица G имеет размер k x n. Первые k столбцов представляют собой единичную матрицу k x k, следующие n-k столбцов представляют совокупность коэффициентов a_l,i (матрица проверочных элементов).

Это запись образующей матрицы в канонической форме.

В строке матрицы проверочных элементов должно быть не менее чем (d_min-1) единиц, а расстояние Хэмминга между строками не менее (d_min-2), где d_min - кодовое расстояние.

При заданной информационной последовательности и образующей матрице кодовое слово V получают следующим образом

V_i=U_i при 1<=i<=k

и

V_i=U₁*a_1,i Å U₂*a_2,i Å …. Å U_k*a_k,i при k+1<=i<=n

Пример

Пусть разделимый линейный код (5,3) задан при помощи образующей матрицы G

Запишем в виде формул процедуру нахождения символов кодового слова, если задана некоторая информационная последовательность U=(u₁,u₂,u₃). Кодовое слово будет содержать 5 символов V=(v₁,v₂,v₃,v₄,v₅).

Если в информационной последовательности имеется только один символ 1 на j – ой позиции, а на остальных позициях находятся нули U=(000….1_j….0), то соответствующее кодовое слово V будет представлять собой j – ю строку матрицы G. Обозначим j – ю строку матрицы G, как g_j. Произвольное кодовое слово можно представить в виде суммы по модулю 2 строк образующей матрицы с номерами j, значения которых совпадают с номерами ненулевых разрядов в информационной последовательности.

Вернемся к примеру, приведенному выше. Пусть U=(101), тогда V=(10111), кодовое слово получилось как сумма по модулю 2 первой и третьей строк образующей матрицы.