Автор работы: Пользователь скрыл имя, 14 Декабря 2017 в 20:58, дипломная работа
В данной курсовой работе будут рассмотрены коды Рида-Маллера. На сегодняшний день передача данных - наиболее развивающаяся область техники. И при передаче данных одной из самых распространённых проблем является возникновение ошибок при передаче информации .При решении этой проблемы одним из самых эффективных, а что главное недорогих методов является помехоустойчивое устройство. На решение проблем связанных с возникновением ошибок и направлены коды Рида-Маллера. Рассмотрим основные характеристики, а также механизм кодирования и декодирования сообщений с их помощью.
Введение ........................................................................................................ 2
1.Определение основных понятий и обозначений............................ 6
2.Алгоритм кодирования кода Рида-Маллера ….5
3.Алгоритм I декодирования кода Рида-Маллера ................................….....7
4.Алгоритм II декодирования кода Рида-Маллера ……………………………
5.Заключение……………………………………………………………………..
6.Приложения……………………………………………………………………
7.Список литературы ..................................................................................... 15
Если с-какое-то кодовое слово(будем обозначать это как , то оно, как отмечалось выше, является строкой двоичной матрицы Адамара или её дополнения . Тогда соответствующий вектор
Есть строка матрицы или ( будем обозначать это как или ). Расстояние равно расстоянию .
При вычислении скалярного произведения каждая несовпадающая компонента даст слагаемое -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 |
Получим вектор (2,2,2,10,−2,−2,−2,6,−2,−2,−2,
А исходное сообщение 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 |
Информация о работе Полиномиальные коды(коды Рида-Маллера). Кодирование и декодирование