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

───────────────

X^5 + X^2 + X + 1

+

X^5 + X^3 + X^2

─────────────────

X^3 + X + 1

+

X^3 + X + 1

───────────

0 = R(X)

ВЫВОД:Первый и второй способы построения циклических кодов имеют различную аппаратную реализацию кодирующих и декодирующих устройств.

М А Т Р И Ч Н О Е   П Р Е Д С Т А В Л Е Н И Е

Ц И К Л И Ч Е С К И Х   К О Д О В .

Для формирования строк производящей матрицы по 1-МУ СПОСОБУ образования циклического кода берут комбинации простого k-разрядного кода A(X) содержащие единицу в одном разряде.Эти комбинации умножаются на X^n-k,определяется остаток R(X) от деления полученного произведения X^n-k*A(X) на образующий полином и записывается соответствующая строка матрицы в виде суммы произведения X^n-k*A(X) и остатка R(x).При этом производящая матрица Pn,k представляется двумя подматрицами - информационной Uk и дополнительной Hp:

Pn,k = │ Uk,Hp │.

Информационная подматрица Uk представляет собой квадратную единичную матрицу с количеством строк и столбцов,равным k.Дополнительная подматрица Hp содержит p = n - k столбцов и k строк и образована остатками R(X).

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

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

Информационная подматрица имеет вид:

│0 0 0 1│

│0 0 1 0│

Uk =  │0 1 0 0│.

│1 0 0 0│

Для получения первой строки дополнительной подматрицы первая строка информационной подматрицы умножается на X^3 и делится на образующий полином.Это соответствует выполнению операций 0001*1000/1101.

Остаток этих операций 101 и составит первую строку дополнительной подматрицы.Аналогично определяются остальные строки дополнительной подматрицы.

Окончательно производящая матрица имеет вид

│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│

При 2-м способе образования циклическогокода производящая матрица

Pn,k формируется путём умножения образующего полинома K(X) степени

p = n - k на одночлен X^k-1 и последующих k-1 сдвигов полученной комбинации.

Другой вариант построения производящей матрицы Pn,k - непосредственное умножение элементов единичной подматрицы на образующий многочлен.

Независимо от способа образования циклического кода и построения производящей матрицы корректирующие свойства кода определяются только выбранным образующим полиномом K(X).

В Ы Б О Р   О Б Р А З У Ю Щ Е Г О   П О Л И Н О М А .

При построении циклического кода вначале определяется число информационных разрядов k по заданному объёму кода.Затем находится наименьшая длина кодовых комбинаций n,обеспечивающая обнаружение или исправление ошибок заданной кратности.Эта задача сводится к нахождению нужного образующего полинома K(X).

СТЕПЕНЬ ОБРАЗУЮЩЕГО ПОЛИНОМА должна быть РАВНА числу проверочных разрядов p.

Поскольку в циклическом коде опознавателями ошибок являются остатки от деления полинома принятой комбинации на образующий полином, корректирующая способность кода будет тем выше,чем больше остатков может быть образовано в результате этого деления.

Наибольшее число остатков,равное 2^p - 1 (исключая нулевой),может обеспечить ТОЛЬКО НЕПРИВОДИМЫЙ полином степени p (т.е.не делящийся ни на какой другой полином).Это необходимое условие.

Достаточное условие обеспечения НАИБОЛЬШЕГО ЧИСЛА ОСТАТКОВ:образующий полином должен быть ПРИМИТИВНЫМ.(Определение примитивности полинома).

ПЕРВЫЙ СПОСОБ ВЫБОРА образующего полинома:

- по заданному числу информационных разрядов k определяется число проверочных разрядов p,необходимое для исправления однократных ошибок;

- по таблице находится примитивный полином степени p.

ВТОРОЙ СПОСОБ ВЫБОРА образующего полинома основан некоторых свойствах полиномов.

Во - первых,образующий полином должен быть делителем двучлена

(X^n + 1).