Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 27

В качетве примера построения циклического кода по 1-му способу в матричном представлении мы рассматривали P7,4 код с образующим полиномом K(X) = X^3 + X^2 + 1.

Производящая матрица для такого кода имеет вид

│0 0 0 1   1 0 1│

│0 0 1 0   1 1 1│

P7,4 = │0 1 0 0   0 1 1│

│1 0 0 0   1 1 0│

Она состоит из двух подматриц.Информационная подматрица Uk представляет собой единичную квадратную транспонированную матрицу.Дополнительная подматрица Hp образована остатками от деления каждой строки,умноженной на X^p,на образующий полином.

Остальные кодовые комбинации P7,4 кода получаются поразрядным суммированием соответствующих строк производящей матрицы.

Однакокодовые комбинации циклического кода Pn,k, построенные по

1-му способу,могут быть получены гораздо проще,используя ГЕНЕРАТОР

РЕГИСТРА СДВИГА С ЛИНЕЙНЫМИ ОБРАТНЫМИ СВЯЗЯМИ.

Пусть H(X) = (X^n + 1)/K(X),где K(X)-образующий полином циклического кода,p = deg K(X).

H(X) = hkX^k + hk-1X^k-1 + ... + h1X + h0, hk = 1.

┌─┐      ┌─┐      ┌─┐         ┌─┐       ┌─┐      ┌─┐

┌──── │+│──────│+│──────│+│────... ─│+│───────│+│──────│+│─<───┐

│     └─┘      └─┘      └─┘         └─┘       └─┘      └─┘     │

│      │        │        │           │         │        │      │

│      │        │        │           │         │        │      │

│    ┌────┐   ┌────┐   ┌────┐     ┌────┐     ┌───┐   ┌───┐   ┌───┐

│    │hk-1│   │hk-2│   │hk-3│     │ h3 │     │ h2│   │h1 │   │h0 │

│    └────┘   └────┘   └────┘     └────┘     └───┘   └───┘   └───┘

│      │        │        │           │         │       │       │

│┌───┐ │  ┌───┐ │  ┌───┐ │           │   ┌───┐ │ ┌───┐ │  ┌───┐│

└│   │─┴─ │   │─┴─ │   │─┴─────...───┴───│   │─┴─│   │─┴──│   │┴─>

└───┘    └───┘    └───┘                 └───┘   └───┘    └───┘

Выход

Рис.Генератор регистра сдвига.

Полином H(x) называется ПРОВЕРОЧНЫМ ПОЛИНОМОМ ЦИКЛИЧЕСКОГО КОДА и определяет структуру генератора регистра сдвига,с помощью которого могут быть получены кодовые комбинации Pn,k кода.

k

__     j

/*Теорема.Пусть h(X) = >  h  X  ,h0 <> 0,hk=1 и n - наименьшее це--  j

i=0

лое положительное число,для которого полином X^n-1 делится на h(X).

Пусть,далее,g(X) = (X^n-1)/h(X).Тогда решения рекурентных соотношений

k

__

>  h  a    = 0

--  j  i+j

j=0

периодичны с периодом n,и совокупность,составленная из первых периодов во всех возможных решений,рассматриваемых по модулю X^n-1:

a(X) = a0 X^n-1 + a1 X^n-2 + ... + an-2X + an-1, совпадают с идеалом,порождённым полиномом g(X) в алгебре полиномов по модулю X^n - 1.*/

Генератор регистра сдвига будет генерировать некоторую двоичную последовательность с периодом,равным n,если его начальное состояние не равно нулю.

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

ПРИМЕР.Пусть K(X) = X^3 + X^2 + 1.Код P7,4.Тогда H(X) = (X^7 + 1)/

/(X^3 + X^2 + 1) = X^4 + X^3 + X^2 + 1.

Генератор регистра сдвига будет иметь вид

┌─┐   ┌─┐

┌────│+│<──│+│<─────────┐

│    └─┘   └─┘          │

│ ┌─┐ │ ┌─┐ │ ┌─┐   ┌─┐ │

└─│ │─┴>│ │─┴>│ │──>│ │─┴────>

└─┘   └─┘   └─┘   └─┘

Ранее мы получили производящую матрицу P7,4 кода с образующим полиномом K(X) = X^3 + X^2 + 1

│0 0 0 1   1 0 1│

│0 0 1 0   1 1 1│

P7,4 = │0 1 0 0   0 1 1│

│1 0 0 0   1 1 0│

Пусть начальное состояние генератора будет равно 1 0 0 0,что соответствует первой строке матрицы P7,4.Тогда в результате 7 сдвигов получим то же самое состояние 1 0 0 0,а на выходе будем иметь последовательность:

Состояния регистра     Последовательность на выходе а)      б)               а)     б)

НУ   1000    1100               0      0

1   1100    0110               0      0

2   0110    1011               0      1

3   1011    0101               1      1

4   0101    0010               1      0

5   0010    0001               0      1

6   0001    1000               1      0

7   1000    1100