Способ построения кодовых последовательно­стей с использованием порождающей матрицы

Кодовая последовательность ЦК при заданной порождающей матрице G_k,n(x) и заданном информационном блоке Q(x) формируется по правилу, т. е.произведения вектора-строки Q(x), содержащего k информационных двоичных символов, на порождающую матрицу G(x) размером k×n. При этом, если используется каноническая (приведенно-ступенчатая) G(x), то будут формироваться кодовые последовательности систематического разделимого ЦК. Порождающая матрица G(x) строится довольно просто, если задан образующий полином Р(х) и длина кодовой последовательности п.

Пример: Сформировать кодовую последовательность ЦК с параметрами, если,Q(x)=x+1.

Переводим Р(х) из записи в форме полинома в двоичную форму записи, т.е.Далее формируем первую строку порождающей матрицы G_5,10(х) следующим образом: двоичную последовательность 110101 дополняем справа четырьмя нулями; в результате получаем разрешенную кодовую последовательность вида 1101010000 длиной n=10 двоичных симво­лов. Следующий шаг - выполнение (k-1)=(5-l)=4 циклических сдвига двоичных символов первой строки G(x).

В результате получаем следующую порождающую матрицу

F(x)=Q(x)*P(x)=(x+1)(x⁵+x⁴+x²+1)=x⁶+x⁵+x³+x+x⁵+x⁴+x²+1=x⁶+x⁴+x³+x²+x+1 (0001011111)

или

1101010000

0110101000

F(x)=Q(x)*G_5,10(x)=00011* 0011010100 = 0001011111

0001101010

0000110101

Пример: Рассмотрим способ формирования кодовых последовательностей ЦК с использованием единичной матрицы и остатков от деления

Для рассмотрения сущности формирования кодовых после­довательностей ЦК используем данные предыдущего примера.

Так как k = 5, то используем следующие единичные векторы:

Записываем Q₁(x)...Q₅(x) в виде единичной подматрицы размером (5x5).

Далее определяем проверочные символы: каждой строки по сле­дующей методике: делими берем остатки от деления для первой строки – от первого такта деления, т.е. R₁(x), для второй строки – после двух тактов деления, т. е. R₂(x) и т. д. Полученные символы дописываем к соответствующим строкам единичной подматрицы:

10000 10101

01000 11111

F(x)=Q(x)*G_5,10(x)=00011* 00100 01011 = 0001110000

00010 00011

00001 10011

Назначение и способы построения провероч­ной матрицы циклического кода

Проверочные матрицы H_l,n(x) ЦК могут использоваться для выбора как способов кодирования информации, так и алгоритмов декодирования. Проверочные матрицы ЦК могут быть построены с использованием порождающей матрицы G_k,n(x), единичной матрицы проверок и проверочного полинома h(x).

Сущность способа построения проверочной матрицы Н_l,n(x) c использованием канонической порождающей матрицы G_k,n(x) состоит в следующем.

Пусть задана следующая каноническая порождающая матрица ЦК с параметрами (n,k,do)=(7,4,3) вида:

1000 101

G_4,7(x) = 0100 111

0010 110

0001 011

Первый столбец проверочной матрицы Н_3,7(х) для данного кода записываем, используя проверочные символы первой строки G_4,7(x), а второй, третий и четвертый столбцы H_3,7(x) формируем путем записи проверочных символов второй, третьей и четвертой строк G_4,7(x) и далее записываем три столбца единичной подматрицы. В результате получаем следующую проверочную матрицу:

а₁а₂а₃а₄ b₁b₂b₃

1110 100

H_3,7(x) = 0111 010

1101 001

Ненулевые символы строк проверочной матрицы определяют позиции информационных символов, участвующие в формировании проверочных уравнений. Так для построенной проверочной матрицы H_3,7(x) можно сформировать следующие три проверочных уравнения: b₁=а₁a₂a₃,b₂=а₂a₃a₄,b₃=а₁a₂a_4.

Принцип построения проверочной матрицы с использова­нием единичной подматрицы и остатков от деления аналогичен принципу построения порождающей матрицы. Количество ос­татков от деления х^п+1 на Р(х) должно быть равно количеству строк единичной подматрицы.

Сущность принципа построения проверочной матрицы ЦК с использованием проверочного полинома h(x) состоит в следующем. Первоначально определяем проверочный полином как отношение х^п+1 на Р(х), т.е. Полученный полином переводим в двоичную форму записи, записываем в виде первой строки проверочной матрицы Н_l,k(х) идополняем нулями до количества столбцов, равное п. Далее выполняем (l-1) циклический сдвиг двоичных символов пер­вой строки.

Пример: Построить проверочную матрицу ЦК с пара­метрами

Решение:

1) определяем проверочный полином

2) переводим h(x) в двоичную форму записи h(x) – 11101;

3) записываем 11101 в виде первой строки Н_3,7(х) и дополняем справа двумя нулевыми символами до n=7;

4) выполняя (l-1)=(3-1)=2 циклических сдвига двоичных символов первой строки Н_3,7(х) строим проверочную матрицу Н_3.7(х) следующего вида:

Проверочные уравнения: b₁=а₁a₂a₃,

b₂=а₂a₃a₄,

b₃= а₃a₄b₁= а₃a₄ а₁a₂a₃= а₁a₂a_4.