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

/* Пусть S(X) обозначает синдром полинома X^n-k+i(X).Тогда

S(X) = X^n-k+i R(X) + K(X) Q1(X).

Пусть,далее,в качестве многочлена F(X) выбран полином

F(X) = X^n-k+i + K(X) Q2(X), причём степень F(X) меньше степени K(X).Из этих соотношений получаем:

R(X) F(X) = S(X) + K(X) Q3(X).

Таким образом,предварительное умножение на X^n-k+i может быть проведено просто путём умножения полученного полинома на F(X),что осуществляется сдвигами его в регистре синдрома. */

ПРИМЕР.Полином K(X) = X^4 + X + 1 порождает (15,11)-код,исправляющий одиночную ошибку.Декодер Меггита для него имеет вид:

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

│                                        ┌─┐

│      ┌───────────┬─────────────────────┤+│<┐

│      │   ┌─┐    ┌─┐   ┌─┐    ┌─┐   ┌─┐ └─┘ │

│      └──>│ ├─┬─>┤+├──>│ ├─┬─>│ ├┬─>┤ ├┬─┘  │

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

│              └──┐  ┌──────┘     │     │    │

│                 │  │  ┌─────────┘     │    │

│                0│ 0│ 0│ 1┌────────────┘    │

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

│             │  схема "И"  │                │

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

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

Ap(X)  │          ┌──────────────┐ ┌─┐

───────┴─────────>│15-разрядн.РС ├>┤+├───────> A(X)

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

Предположим,чтотребуется укоротить этот код на 5 символов,с тем, чтобы получить (10,6)-код.Остаток от деления X^n-k+5 = X^9 на K(X)

равен:

F(X) = X^3 + X = X^9 + (X^5 + X^2 + X)*(X^4 + X + 1).

Тогда декодер Меггита для (10,6)-кода будет выглядеть следующим образом:

┌─────────────┬───────────────────────┐

│             │                       │

│  ┌──────────┼─────┬─────────────────┼───────────┐

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

│  └─>│ ├─┬─>┤+├──>│+├──>│ ├┬─>┤ ├┬─>┤+├──>│ ├┬─>│+│

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

│         │                 └──┐  │           │   │

│         └─────────────────┐  │  │  ┌────────┘   │

│                          0│ 0│ 0│ 1│            │

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

│                        │  схема "И"  │          │

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

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

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

─┴────────────────────>│10-разрядн.РС ├>┤+├───────> A(X)

Ap(X)                  └──────────────┘ └─┘

В В Е Д Е Н И Е   В   А Л Г Е Б Р У   П О Л Е Й   Г А Л У А .

ОПРЕДЕЛЕНИЕ.ГРУППОЙ G называется множество элементов с определённой для каждой пары элементов операцией,обозначаемой * ,обладающее следующими четырьмя свойствами:

1) ЗАМКНУТОСТЬ:для каждой пары a и b из множества элементов

c = a * b принадлежит множеству;

2) АССОЦИАТИВНОСТЬ:для всех a,b, и c из множества

a * ( b * c ) = (a * b ) * c;

3) СУЩЕСТВОВАНИЕ ЕДИНИЦЫ:в множестве существует элемент e,называемый единичным и такой,что  a * e = e * a = a  для любого элемента a множества;

4) СУЩЕСТВОВАНИЕ ОБРАТНЫХ ЭЛЕМЕНТОВ:для любого a из множества существует некоторый элемент d из множества,называемый обратным

a и таким,что  a * b = b * a = e.

Если группа G содержит конечное число элементов,то она называется

КОНЕЧНОЙ ГРУППОЙ,а число элементов G называется ПОРЯДКОМ G.

Группы,обладающие дополнительным свойством коммутативности

a * b = b * a  называются коммутативными или АБЕЛЕВЫМИ ГРУППАМИ.

ОПРЕДЕЛЕНИЕ.ПОЛЕМ называется множество с двумя определёнными на нём операциями - СЛОЖЕНИЕМ И УМНОЖЕНИЕМ,причём имеют место следующие аксиомы:

1)множество образует абелеву группу по сложению;

2)поле замкнуто относительно умножения,и множество ненулевых элементов образует абелеву группу по умножению;

3)закон дистрибутивности:

( a + b )c = ac + bc  для любых a,b и c из поля.

Единичный элемент относительно сложения принято обозначать через 0

и называть нулём,аддитивный обратный элементу a элемент - через -a;

единичный элемент относительно умножения обозначают через 1 и называют 1,мультипликативный обратный к элементу a элемент - через a^-1.