Полиномиальные коды(коды Рида-Маллера). Кодирование и декодирование

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования  
«Национальный исследовательский  
Нижегородский государственный университет им. Н.И. Лобачевского»

(ННГУ)

Институт информационных технологий, математики и механики

Кафедра алгебры, геометрии и дискретной математики

Направление подготовки: «Название направления»

Профиль подготовки: «Математика и компьютерные науки»

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА

Тема:

«Полиномиальные коды(коды Рида-Маллера). Кодирование  и декодирование. »

 

Допущена к защите Выполнил:

Заведующий кафедрой: студент группы 845

________________________ Хлыбова А.Е.

__________________________ __________________________ подпись                                                                                    подпись

Научный руководитель:

                                                                  Доцент кафедры АГиДМ,

                                                         к.ф.-м.н.

                                                                                                          Шевченко В.И.

____________________________

подпись

Нижний Новгород 
2017

 

 

 

 

 

 

Оглавление

Введение ........................................................................................................ 2

1.Определение основных понятий и обозначений............................ 6

2.Алгоритм кодирования кода Рида-Маллера ….5

3.Алгоритм I декодирования кода Рида-Маллера ................................….....7

4.Алгоритм II декодирования кода Рида-Маллера ……………………………

5.Заключение……………………………………………………………………..

6.Приложения……………………………………………………………………

7.Список литературы ..................................................................................... 15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 

Постановка задачи

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§ 1 Определения основных понятий и обозначений.

 

 

Определение. Группа (G,)- множество G с бинарной операцией “*” , для которых выполнены следующие аксиомы :

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

Определение. Группа G называется абелевой (или коммутативной) если для любых выполняется равенство

Определение. Подмножество группы называется подгруппой этой группы, если само множество  образует группу относительно операций группы 

Определение. Кольцо (R,+,)-множество   c двумя бинарными  операциями, одна из них называется сложением и обозначается как “+ “ , а другая называется умножением и обозначается “” , при  этом выполняются следующие аксиомы:

• множество R является абелевой  группой  относительно операции сложения, то есть аддитивной абелевой группой.
• для любых двух элементов  a из множества  R определено произведение ab, которое является элементом 
• для любых трёх элементов  a,b и c из множества  R a(bc)=(ab)c
• для любых трёх элементов a ,b и c из множества  R справедливы равенства a(b+c)=ab+ac и (b+c)a=ba+ca

Определение. Кольцо  называется коммутативным ,если коммутативна операция умножения.

Определение. Поле-коммутативное кольцо с единичным элементом относительно умножения , в котором каждый ненулевой элемент имеет мультипликативный обратный .

Определение. Пусть F некоторое поле, тогда  множество -векторное пространство над полем F, если для него выполняются следующие аксиомы:

• множество является абелевой  аддитивной  группой.
• для любого вектора v из и любого элемента a из поля F определено произведение av, являющееся вектором (элементы поля называются скалярами, а элементы -векторами).
• если u и v-векторы из множества , а a-скаляр, то a(u+v)=au+av.
• если v-вектор, а a и  d- скаляры , то (a+d)v=av+dv.
• если v-вектор, а a, d- скаляры , то (ad)v=(dv) и 1v=v.

Определение. Линейный код-некоторое множество векторов длины n , являющееся подпространством векторного пространства всех наборов длины  n.Где векторное пространство образованно совокупностью всех наборов  элементов поля длины n.

 Через будем обозначать поле характеристики два.

Определение. Булевой  функцией f () от  m переменных называется функция f, отображающая  линейной пространство в поле().

 Известно, что множество всех булевых функций  от m переменных образует  векторное  пространство 

Каждая булева функция f () может быть задана вектором её значений

 

Определение. Полиномом Жегалкина называется многочлен с коэффициентами из поля  
  
 
Степенью полинома называется максимальная степень монома, входящего в полином с ненулевым коэффициентом и обозначается .

Теорема. Каждая булева функция может быть представлена единственным образом полиномом Жегалкина. 

Определение. Для произвольных натуральных m и r, 0, кодом Рида-Маллера (RM(r,m)) порядка r и длины называется множество всех векторов значений булевых функций степень полинома Жегалкина которых не превосходит r, то есть

RM(r,m)=

Определение. Расстоянием Хемминга между парой векторов символически  называется число компонент, в которых они различаются .

Определение. Минимальным кодовым расстоянием кода V,символически    является число

 

Где минимум берётся по всем парам .

Определение. Весом Хемминга вектора называется число ненулевых  компонент этого вектора , обозначается через .

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

Известно также, что:

1. ;

2) Минимальное расстояние кода RM(r,m) равно .

3) Код , имеющий минимальное расстояние , обнаруживает ошибок и исправляет .

Таким образом код RM(r,m) исправляет   и  обнаруживает ошибок.

 

 

§2 Алгоритм кодирования кода Рида-Маллера .

 

 

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

 

 Порождающая матрица G кода имеет структуру

G=,

Где

,,…,

 

Следовательно, код можно  определить как код, базисом которого являются вектора .

Так, например, в случае кода  порождающая матрица G имеет вид .

 

 

А при m=4 матрица G принимает вид

 

	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

 

 

G=

 

Заметим, что код  состоит из всех векторов длины , а код -только из нулевого и единичного векторов.

Так, например, матрица G кода имеет вид

 

 

 

	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1
	0	0	0	0	0	0	0	0	0	0	1	1	0	0	1	1
	0	0	0	0	0	0	0	0	0	1	0	1	0	1	0	1
	0	0	0	0	0	0	1	1	0	0	0	0	0	0	1	1
	0	0	0	0	0	1	0	1	0	0	0	0	0	1	0	1
	0	0	0	1	0	0	0	1	0	0	0	1	0	0	0	1
	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1
	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	1
	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1
	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

 

 

 

 

 

Кодирование осуществляется путём умножения вектора сообщения на порождающую матрицу G. Другими словами кодирование представляет собой инъективное отображение  , S, .

Пример. Задан код   с характеристиками  
=5

Дано сообщение S=() , закодируем его. Для этого перемножим вектор S на порождающую матрицу G.Где G имеет вид

	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

                      SG=

Получаем вектор )

Таким образом наглядно показан алгоритм кодирования кода Рида-Маллера.

Написана программа кодирования , приведённая в приложении 1.

 

 

 

 

 

 

 

 

 

 

 

§ 3 АлгоритмI декодирования кода Рида-Маллера.

 

Декодирование по принципу максимального правдоподобия означает выбор из всех возможных  кодовых слов того слова y, которое находится на минимальном расстоянии Хэмминга от принятого слова y’, и лишь затем-восстановление исходного слова x из его кода y.

Рассмотрим применение принципа максимального правдоподобия к декодированию кода RM(1,m).

Пусть y’-принятое слово длины , возможно, содержащее ощибки, и пусть Y’ означает вектор, полученный из y’ заменой всех компонент 0 компонентами -1: