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