Коды Рида-Маллера

Обнаруживает все ошибки нечётной кратности и исправляет только однократной.

Коды первого порядка являются думальными кодами.

Ортогональный кот.

00010001 --- --------------------------

00000101 |--2 порядка |---3 порядка

00000011 --- |

00000001-----------------------------------

M32 K64

Является самодуальным кодом.

Метод мажоритарного декодирования

Sagemath.org

19.05.2012

Код с проверкой на чётность

x² x¹ x⁰

C1 00 0->0

C2 01 1->x+1

C3 10 1->x²+1

C4 11 0->x²+x

G =011

101

011->1001->110

C1 C2 C3

Найдём полином g(x) который является множителем,тнапример g(x)=x+1

(x+1)x²=x²+x

x²+x=1

Представление элементов …:

1. Векторное представление в виде векторов x²+1

2. Представление в виде полинома

3. Представление в виде степени примитивного элемента поля

4. Матриное представление

Два полинома называются сравнимыми если первый делится на второй нацело.

Найти 1+x²+x⁵(mod1+x²)=x

x^3+x+1

___________

(делитель)x^2+1 | x^5+x^2+1 (делимое)

x^5+x^3

____________

x^3+x^2+1

x^3+x

___________

x^2+x+1

x^2+1

______

x

Циклический сдиг на 1 позицию вправо является простым умножением многочлена степени n-1 на сногочлен x и нахождения остатка от деления на x^n-1 .

Осуществить еденичный правый циклический сдви слова [101]

Вектору соответствует 1+x³+x⁴(mod x⁴+1)=x+x³+x⁴(mod x⁴+1)

Поле где количество элементов простое число называется полем Голуа.

Полиномом поля gF(q)

Полином называется нормированным (monic polinom) (приведённый) если старший коэффициент при F-1=1;

Степень полинома – индекс старшего из коэффициентов. Степень не нулевого полинома всегда конечное число. Множество всех полиномов над полем gF(q) является кольцом с операциями сложения, умножения полиномов.

f(x)+g(x)=

Степень суммы не превышает степень большего из суммируемых полиномов.

(x⁴++x²+x+1)

Степень произведения полиномов равна сумме максимальных степеней.

Можно говорить что полином a(x) делится на полином b(x) если существует полином q(x) для которого справедливо следующее: b(x)q(x)=a(x)

Полином p(x) rкоторый делится только на p(x) или альфа, де альфа примитивный элемент поля g(x) называется неприводимым.

Полином называется нормированным

НОК a(x) b(x) это нормированный полином наименьшей степени на который делятся оба полинома.

Если НОД двух полиномов равен 1, то полиномы называются взаимнопростыми.

Для любого приведённого полинома p(x) не нулевой степени над полем a кольцо полиномов по модулю p(x) является множеством всех полиномов степени меньшей чем p(x) вместе с опрециями сложения и умножения по модулю p(x). Колльцо полиномов g(x) по модулю p(x) является расширением поля gf(q^m) когда p(x) является нормированным не приводимым полиномом в степени m.

25.05.2012

LFSR

1. Чётное количество тригеров

2. Все связи взаимнопростые (НОД=1)

GF

*x -> сдвиг в лево

mod x -> xor

2-2^x –> сдвиг в право

X=2³+1=7

X⁷+1=(x+1)(x²+x+1)(x³+x²+1)

Все полиномы, которые будут иметь степень тройки будут являтся примитивными.

q4------q1-o--q2---q3--- x³+x+1

| | | |

|----------------------

Примитивный полином нельзя разложить на множители тойже степени, с другой стороны он является делителем элемента xⁿ+1, де n=2^m+1, m – старшая степень нашего полинома.

Любой полином можно представить в виде произведения неприводимых нормированных полиномов.

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

1. Полином f(x) , x-a делитель когда f(x)=a

2. Полином f(x) в кольце F(x) в степене 2 или 3 является неприводимым тогда и только тогда когда a не равно нулю. Для всех из кольца.

3. Для любого поля в степени x^x-1=(x-1)(x^n-1+x^n-2…x+1)

Ross N. Williams элементарное руководство по CRC – алгоритмам обнаружения ошибок

Для любого циклического кода заданного полиномом g(x)^m обнаруживается пакет ошибок длины L если L-1 меньше m.

Если =m то обнаруживается 1-2^-(m-1)

Если >m то обнаруживается 1-2^-m

Для простых кодов с проверкой на чётность порождающий полином равен

Циклический код g(x)=x+1

Для кода хэминга порождающий полином задаётся из неприводимого полинома g(x)=(x+1))p(x).