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

Так как deg K(X) = 3,то информационная комбинация A(X) умножается на X^3:

A(X)*X^p = (X^3 + X^2 + 1)*X^3 = X^6 + X^5 + X^3 = 1101000.

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

Значение корректирующих разрядов находят в результате деления

A(X)*X^p на K(X):

X^6 + X^5 + X^3 │X^3 + X + 1

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

X^6 + X^6 + X^3 │X^3 + X^2 + X + 1

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

X^5 + X^4

+

X^5 + X^3 + X^2

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

X^4 + X^3 + X^2

+

X^4 + X^2 + X

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

X^3 + X

+

X^3 + X + 1

───────────

1

В результате деления (A(X)*X^3)/K(X) = X^3 + X^2 + X + 1 + 1/(X^3

+ X + 1),или в общем виде (A(X)*X^p)/K(X) = Q(X) + R(X)/K(X),где

Q(X) - частное,а R(X) - остаток от деления A(X) на K(X).

Последнее выражение можно переписать в следующем виде:

A(X)*X^p = Q(X)*K(X) + R(X),или

F(X) = Q(X)*K(X) = A(X)*X^p + R(X).

Для расматриваемого примера

F(X) = (X^3 + X^2 + X + 1)(X^3 + X + 1) =

(X^3 + X^2 + 1)*X^3 + 1,или в двоичном представлении

F(X) = 1111*1011 = 1101000 + 001 = 1101001.

Полином 1101001 и есть искомая кодовая комбинация,где 1101 - информационная часть,а 001 - контрольные символы.

Заметим,что этот полином делится на образующий полином K(X) без остатка.Проверим это:

1101001 -> X^6 + X^5 + X^3 + 1│X^3 + X + 1

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

X^6 + X^4 + X^3    │X^3 + X^2 + X + 1

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

X^5 + X^4 + 1

+

X^5 + X^3 + X^2

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

X^4 + X^3 + X^2 + 1

+

X^4 + X^2 + X

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

X^3 + X + 1

+

X^3 + X + 1

───────────

0

О С Т А Т К И   О Т   Д Е Л Е Н И Я   П О Л И Н О М О В

Я В Л Я Ю Т С Я   О П О З Н А В А Т Е Л Я М И   О Ш И Б О К

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

Таким образом,по остатку от деления кодовой комбинации на образующий полином судят о наличии в ней ошибок:если остаток равен нулю ошибок нет,если остаток не равен нулю - ошибки есть.

Мы рассмотрли ПЕРВЫЙ СПОСОБ ПОСТРОЕНИЯ ЦИКЛИЧЕСКОГО КОДА:кодовая комбинация циклического (n,k) - кода получается путём умножения простой кодовой комбинации степени (k-1) на одночлен X^n-k и добавления к этому произведению остатка,полученного от деления полученного произведения на образующий полином K(X) степени (n-k).

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

2   С П О С О Б .

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

A(X) = X^3 + X^2 + 1,т.е.1101.

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

Искомая кодовая комбинация в этом случае определяется как произведение полиномов A(X) и K(X).

X^3 + X^2 + 1

*

X^3 + X   + 1

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

X^3 + X^2 + 1

+

X^4 + X^3 + X

X^6 + X^5 + X^3

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

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

Итак,искомая кодовая комбинация в данном примере имеет вид:

F(X) = A(X)*K(X) = X^6 + X^5 + X^4 + X^3 + X^2 + X + 1,или в двоичном представлении 1111111.

Таким образом,второй способ построения циклического кода предполагает умножение простой кодовой комбинации степени (k-1) на образующий полином K(X) степени (n-k).

Как и при первом способе,по остатку от деления кодовой комбинации на образующий полином судят о наличии в ней ошибок:если остаток равен нулю,ошибок нет;в противном случае ошибки имеют место.

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

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

Например,в рассмотренном нами примере исходные символы A(X) пределяются путём деления F(X) на K(X):

F(X) = X^6 + X^5 + X^4 + X^3 + X^2 + X + 1│X^3 + X + 1  = K(X)

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

X^6 + X^4 + X^3                    │X^3 + X^2 + 1= A(X)