В качетве примера построения циклического кода по 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
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.