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

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

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

(ННГУ)

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

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

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

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

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

Тема:

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

 

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

Заведующий кафедрой: студент группы 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:

 

Если с-какое-то кодовое слово(будем обозначать это как , то оно, как отмечалось выше, является строкой двоичной матрицы Адамара или её дополнения . Тогда соответствующий вектор

 

Есть строка матрицы или ( будем обозначать это как или ). Расстояние равно расстоянию .

При вычислении скалярного произведения каждая несовпадающая компонента даст слагаемое -1, а каждая совпадающая даст 1.Таким образом,

,

Где  -число совпадений компонент и , –число несовпадений , –длина слова, .

Там, где значения минимально, скалярное произведение максимально.

Так как

).

Алгоритм декодирования принятого вектора  следующий:

1)Умножить матрицу Адамара  на столбец .

2)Найти максимальную по  абсолютной величине компоненту  полученного вектора.Пусть её номер будет.

3)Если эта компонента  положительно, определить кодовое  слово , ближайшее к , как равное  -ой строке двоичной матрице Адамара.

В противном случае будет дополнением к этой строке.

После этого для восстановления исходного сообщения по достаточно воспользоваться уравнениями из системы с номерами 0,1,…,:

 

То есть  

 

 

 

И так далее.

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

 

В зависимости от знака наибольшей компоненты скалярного произведения мы получим , равное 0(при ) или 1(при ).В первом случае вектор , будет подвектором , во втором дополнением к подвектору.

 

 

 

 

 

Рассматривается код Рида-Маллера первого порядка, то есть RM(1,m). Порождающая матрица G этого кода имеет вид

 

 

Таким образом, RM(1,m)   состоит из всех векторов значений функций вида  .

Для кода  RM(1,m) длина кодового слова  n=.

При передаче или хранении на кодовый вектор из RM(1,m)   накладывается вектор ошибок,в результате получаем вектор

Задача декодирования состоит в том, чтобы по векторуопределить ближайший к нему в метрике Хемминга  вектор  

Описание алгоритма.

Определим матрицу размерности следующим образом

, где , где

Известно, что матрица Адамара назовём матрицу

 

 

Где матрица адамара строящаяся по рекуррентному правилу

,

 

 

А через J обозначена матрица из одних единиц того же размера, что и .

Операция сложения здесь, конечно, означает обычное сложение целых чисел.

 

 

Пусть Строки и столбцы матрицы будем индексировать элементами множества

Известно, что, если и ),то

 ), где

 

Последнее равенство показывает, что индекс координаты вектора с максимальным значением определяет вектор   значений функции , который наиболее близок в метрике Хемминга к вектору .Таким образом , декодирование кода RM(1,m)   можно свести к умножению вектора с действительными координатами на матрицу Адамара . Исходя из стандартного определения умножения вектора на матрицу, сложность   вычисления произведения   , оценивается сверху величиной .

 

Пример 1. Задан код    с характеристиками  
=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=

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

На этот вектор накладывается вектор ошибок

Декодируем вектор = 1001100110011110 (код должен исправлять до 3-х ошибок

Преобразуем по формуле= 2−1: 

 

= (1,−1,−1,1,1,−1,−1,1,1,−1,−1,1,1,1,1,−1).

 

Умножим на матрицу Адамара в поле вещественных чисел

1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
1	-1	1	-1	1	-1	1	-1	1	-1	1	-1	1	-1	1	-1
1	1	-1	-1	1	1	-1	-1	1	1	-1	-1	1	1	-1	-1
1	-1	-1	1	1	-1	-1	1	1	-1	-1	1	1	-1	-1	1
1	1	1	1	-1	-1	-1	-1	1	1	1	1	-1	-1	-1	-1
1	-1	1	-1	-1	1	-1	1	1	-1	1	-1	-1	1	-1	1
1	1	-1	-1	-1	-1	1	1	1	1	-1	-1	-1	-1	1	1
1	-1	-1	1	-1	1	1	-1	1	-1	-1	1	-1	1	1	-1
1	1	1	1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1
1	-1	1	-1	1	-1	1	-1	-1	-1	1	-1	1	-1	1	1
1	1	-1	-1	1	1	-1	-1	-1	1	-1	-1	1	1	-1	1
1	-1	-1	1	1	-1	-1	1	-1	1	1	-1	-1	1	1	-1
1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	1	1	1	1
1	-1	1	-1	-1	1	-1	1	-1	1	-1	1	1	-1	1	-1
1	1	-1	-1	-1	-1	1	1	-1	-1	1	1	1	1	-1	-1
1	-1	-1	1	-1	1	1	-1	-1	1	1	-1	1	-1	-1	1

 

 

Получим вектор (2,2,2,10,−2,−2,−2,6,−2,−2,−2,6,2,2,2,−6). Его наибольшая по модулю компонента 10 -третья при нумерации с нуля. Следовательно, ближайшим кодовым словом будет третья строка двоичной матрицы Адамара (опять же при нумерации с 0), то есть вектор = 1001100110011001.

А исходное сообщение S восстановится по компонентам так:

 

 

 

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

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

 

произведения матриц , каждая из которых имеет малое число ненулевых элементов.

 

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

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

Лемма . Равенство будет выполнено, если в качестве матриц взять матрицу , где -  единичная матрица порядка .

Каждая матрица имеет в каждом столбце и строке по два ненулевых элемента .

Следствие .Умножение вектора с действительными координатами на матрицу может быть реализовано за операций сложения и умножения  в поле действительных чисел R.

Отсюда непосредственно вытекает

Теорема. Сложность алгоритма декодирования по максимуму правдоподобия кода Рида-Маллера первого порядка не более, чем O().

 

Пример2.  Декодируем вектор y′ = 1001100110011110 (код должен исправлять до 3-х ошибок).

Для этого вычисляем матрицы , где j=1,2,3,4,m=4

 

         

Для первой матрицы     

 

 

 

1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0	1	0	0	0	0
0	0	0	0	1	0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	1	0	0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	1	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	1
1	1	0	0	0	0	0	0	-1	0	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	1	0	0	0	0	0	0	-1	0	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	1	0	0	0	0	0	0	-1	0	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	1	0	0	0	0	0	0	-1	0
0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	-1

Для второй  матрицы     

 

1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0	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	-1	0	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	-1	0	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	-1	0	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	1	0	0	0	0	0	0	1	0	0	0	1	0	0	0
0	0	1	0	0	0	0	0	0	1	0	0	0	1	0	0
0	0	0	1	0	0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	1	0	0	1	0	0	0	-1	0	0	0
0	0	0	0	0	0	1	0	0	1	0	0	0	-1	0	0
0	0	0	0	0	0	0	1	0	0	1	0	0	0	-1	0
0	0	0	0	0	0	0	0	1	0	0	1	0	0	0	-1

Для третей  матрицы     

 

 

1	0	1	0	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	0
1	0	-1	0	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	0
0	0	0	0	1	0	1	0	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	0	1	0	-1	0	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	0	0	0	0	0	1	0	1	0	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	0	1	0	-1	0	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	0	0	0	0	0	1	0	1	0
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	0	1	0	-1	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	-1