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

... an-2 также принадлежит этому коду.

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

Циклические коды удобно рассматривать,представляя комбинацию двоичного кода не в виде последовательностей нулей и единиц,а в виде полинома от фиктивной переменной Х,а именно:

b(X) = an-1 X^n-1 + an-2 X^n-2 + ... + a1 X + a0, где ai - цифры данной системы счисления (в двоичной системе 0 и 1), знак "+" - сумма по модулю два.

Так,например,двоичное семиразрядное число 1110101 может быть записано в виде полинома:

b(X) = 1*X^6 + 1*X^5 + 1*X^4 + 0*X^3 + 1*X^2 + 0*X + 1 =

X^6 + X^5 + X^4 + X^2 + 1.

Наибольшая степень Х в слагаемой с ненулевым коэффициентом называется СТЕПЕНЬЮ полинома.

В рассмотренном примере степень b(X) равна deg b(X) = 6.

О П Е Р А Ц И И   Н А Д   П О Л И Н О М А М И .

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

При этом сложение двоичных полиномов сводится к сложению по модулю два коэффициентов приравных степенях переменной Х.

ПРИМЕР.A(X) = X^5 + X^4 + X^3 + 1;

B(X) = X^7 + X^4 + X^3 + X^2;

A(X) + B(X) = X^5 + X^4 + X^3 + 1 + X^7 + X^4 + X^3 + X^2 =

= X^7 + X^5 + X^2 + 1.

Умножение производится по обычному правилу перемножения степенных функций,однако,полученные при этом коэффициенты при равных степенях переменной Х складываются по модулю два.

ПРИМЕР.A(X) = X^5 + X^2 + 1;

B(X) = X^3 + X + 1;

A(X) * B(X) = (X^5 + X^2 + 1)*(X^3 + X +1) =

X^5 + X^2 + 1

*

X^3 + X + 1

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

X^5 + X^2 + 1

X^6 + X^3 + X

X^8 + X^8 + X^3

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

X^8 + X^6 + X^2 + X   + 1

Деление осуществляется по правилам деления степенных функций,при этом операции вычитания заменяются операциями суммирования по модулю два.

ПРИМЕР.A(X) = X^5 + X^2 + 1;

B(X) = X^3 + X + 1;

X^5 + X^2 + 1   │X^3 + X + 1

+                 ├───────────

X^5 + X^3 + X^2 │X^2 + 1

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

X^3 + 1

+

X^3 + X + 1

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

X - остаток

A(X)/B(X) = X^2 + 1 + X/(X^3 + X + 1).

П О С Т Р О Е Н И Е   Ц И К Л И Ч Е С К И Х   К О Д О В .

Идея построения циклических кодов базируется на использовании неприводимых в поле двоичных чисел многочленов.

НЕПРИВОДИМЫМИ называются многочлены,которые не могут быть представлены в виде произведения многочленов низших степеней с коэффициентами из этого же поля.Они также,как и простые числа,не могут быть представлены произведением других чисел.Иными словами,неприводимые полиномы делятся без остатка только на себя или на единицу.Например:

X^3 + X^2 + 1.

Идея коррекции ошибок в циклических кодах базируется на том,что разрешённые комбинации кода делятся без остатка на некоторый образующий полином,который выбирается из числа неприводимых полиномов.

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

был неприводимым полиномом.Такие многочлены следует искать среди нечётных многочленов,т.е.среди полиномов,содержащих нечётное число единиц,так как из всех чётных полиномов легко выделить двучлен

(X + 1),т.е.чётные полиномы состоят минимум из двух сомножителей, т.е. не являются неприводимыми.

НЕПРИВОДИМЫЕ ПОЛИНОМЫ в теории циклических кодов ИГРАЮТ РОЛЬ ОБРАЗУЮЩИХ(генераторных,производящих),так как,если заданные кодовые комбинации умножить на выбранный неприводимый многочлен,то получим циклический код,корректирующие способноти которого определяются неприводимым полиномом.

1   С П О С О Б .

Пусть требуется закодировать одну из комбинаций четырёхзначного двоичного кода:

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

K(X) = X^3 + X + 1,т.е.1011.Затем умножаем A(X) на одночлен той же степени,что и образующий многочлен.От умножения многочлена на полином X^p степень каждого члена полинома повысится на p,что эквивалентно приписыванию p нулей со стороны младших разрядов полинома.