double arrow

Кодирование информации линейным блоковым кодом


Задание линейных кодов с помощью порождающих и проверочных матриц

Линейные коды задаются с помощью порождающей G(x) и проверочной H(x) матриц. Эти матрицы связаны основным уравнением кодирования:

G(x)×H(x)T=0.

Матрица G(x) содержит k строк и n столбцов, ее элементами являются нули и единицы. В качестве строк матрицы G(x) выбираются любые ненулевые линейно независимые n-значные векторы, отстоящие друг от друга не менее чем на заданное кодовое расстояние d0.

Векторы v1, v2, …, vk называются линейно независимыми, если выполняется условие

c1 v1 + c2 v2 +…+ck vk = 0,

где сi={0, 1}, а сложение выполняется по модулю два. То есть, каким бы образом мы не суммировали различные строки матрицы G(x), не получим суммы, равной нулю. Все множество кодовых слов состоит из строк порождающей матрицы и всевозможных комбинаций этих строк, т.е. суммы по модулю два всех строк матрицы G(x) сначала попарно, затем по три и так далее до суммы всех k строк.

С точки зрения алгебры все кодовые слова образуют некоторое векторное пространство, базисом которого являются строки матрицы G(x).

Поскольку линейно независимые векторы могут быть выбраны произвольным образом, то, очевидно, можно построить множество матриц G(x) с одним и тем же кодовым расстоянием d0.




Свойство линейной независимости векторов инвариантно относительно двух следующих операций (выполняя эти две операции, кодовое расстояние не меняется):

1) возможна произвольная перестановка строк и столбцов в матрице G(x);

2) замена i-й строки на сумму i-й и j-й строк и т. д. (эту операцию нельзя осуществлять со столбцами матрицы G(x)).

Производя вышеуказанные операции, любую произвольную матрицу G(x) можно привести к так называемому приведенно-ступенчатому (каноническому) виду:

n
k , (1)

где Ik –единичная подматрица размерностью k×k,

H*T – транспонированная проверочная матрица (транспонировать – значит поменять местами строки и столбцы).

Исходя из основного уравнения кодирования, проверочная матрица имеет вид

l .
(2)

 
 
n


Пример:

Возьмем порождающую матрицу кода (7,4). В этой матрице количество строк равно 4 (k=4), а количество столбцов 7(n=7).

1 0 0 0 1 0 1

G(x)=0 1 0 0 1 1 1

0 0 1 0 1 1 0

0 0 0 1 0 1 1

Для того чтобы построить проверочную матрицу, необходимо транспонировать подматрицу G(x)* и к ней приписать единичную матрицу размером l×l. Проверочная матрица будет иметь размер l×n, l = n-k=7-4=3, т.е. матрица Н(x) имеет размер 3×7.

1 1 1 0 1 0 0

H(x)=0 1 1 1 0 1 0

1 1 0 1 0 0 1

Операция кодирования информации линейным кодом заключается в умножении информационного вектора Ak размерностью k на порождающую матрицу G(x); в результате получаем вектор

F(x)=Ak(x)×G(x).

Кодовую последовательность на выходе кодера можно записать в виде:



где a1a2a3...аk - информационные символы (логические 1 и 0),

b1b2b3...b1 - проверочные символы (логические 1 и 0).

Проверочные символы b1b2b3...bl формируются путем суммирования по модулю два информационных символов, стоящих на определенных позициях.

 
 

Алгоритм формирования проверочных символов в общем виде можно записать так:

где cj1cj2...cjk- коэффициенты принимающие значение логических 1 и 0.

Пример: Ak(x)=1010

1 0 0 0 1 0 1

G(x)=0 1 0 0 1 1 1

0 0 1 0 1 1 0

0 0 0 1 0 1 1

1 0 0 0 1 0 1

Следовательно, F(x)=Ak(x)×G(x)=[1010]* 0 1 0 0 1 1 1 = [1010 011]

0 0 1 0 1 1 0

0 0 0 1 0 1 1

Рассмотрим построение и реализацию устройства кодирования ЛБК (7,4).

Порождающая и проверочная матрицы этого кода имеют вид:

а1а2а3а4 b1b2b3

1 0 0 0 1 0 1 1 1 1 0 1 0 0

G(x)=0 1 0 0 1 1 1 H(x)=0 1 1 1 0 1 0

0 0 1 0 1 1 0 1 1 0 1 0 0 1

0 0 0 1 0 1 1

Этот код имеет d=3 и исправляет все одиночные ошибки и обнаруживает двойные. Символы а1234 – информационные символы, b1,b2,b3 – проверочные.

По матрице запишем проверочные уравнения:

b1= a1Åa2Åa3

b2= a2Åa3Åa4

b3= a1Åa2Åa4

Таким образом, кодер состоит из (n-k)=7-4=3 сумматоров по модулю два, выходы которых соответствуют (n-k) проверочным символам.

Устройство кодирования линейного группового кода (7, 4) приведено на рисунке.

Рисунок – Кодер линейного группового кода (6, 3)

Пусть подается сообщение (а1234)=1001. Тогда слово, передаваемое в канал связи, имеет вид (1001 110).







Сейчас читают про: