Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Помехоустойчивое кодирование. 2

Федеральное агентство по образованию

Государственное образовательное учреждение высшего

профессионального образования
«ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Кафедра «Информационная безопасность систем и технологий»

Отчет

о курсовом проекте

по дисциплине «Передача дискретных сообщений»

по теме:

«Помехоустойчивое кодирование»

Исполнитель КР Л.М. Мухутдинова

Руководитель КР

к.т.н., доцент Б.В. Султанов

Пенза 2011

Изм..

Лист

№ докум.

Подп.

Дата

Лист

ПГУ 4.090106.001 ПЗ

Разраб.

Мухутдинова

в С.А.

Провер.

Султанов Б.В.

Реценз.

Н.Контр.

Султанов Б.В.

Утв.

Помехоустойчивое кодирование

Лит.

Листов

Гр. 08ПТ3

РЕФЕРАТ

Отчет содержит 19 страницы, 4 таблицы, 1 рисунок, 2 источника.

КОДИРОВАНИЕ, КОД ХЕММИНГА, КОД РИДА-СОЛОМОНА, КОД БЧХ

Объектом исследования являются код Хемминга, код БЧХ, код Рида-Соломона.

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

В процессе работы было осуществлено кодирование информационных комбинаций кодом Хэмминга, БЧХ кодом и кодом Рида-Соломона.

В результате работы все задачи были решены и все требования задания были выполнены.

СОДЕРЖАНИЕ

Реферат 2

Задание на курсовую работу 4

Введение 5

Код Хемминга 6
Код БЧХ 10
Код Рида-Соломона 13

Заключение 18

Список используемых источников 19

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

ВЕДЕНИЕ

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

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

Курсовая работа состоит из 3 разделов.

Первый раздел посвящен исследованию кода Хемминга, для него найден порождающий многочлен, сформирована разрешённая кодовая
комбинация кода, в искажённом сообщении исправлена ошибка.

Во втором разделе рассматривается код БЧХ, для него найден
порождающий многочлен, сформирована разрешённая кодовая комбинация, построен регистр кодирующего устройства для кода БЧХ.

В третьем разделе исследован код Рида—Соломона, построены
таблицы представления, сложения и умножения элементов в поле
GF(8), найден порождающий многочлен, вычислены синдромы для
принятой комбинации, определено местонахождение и значение ошибки в ней.

1 Код Хемминга

Задача 1.2.16. Определить порождающий многочлен g(x) кода Хэмминга, скорость которого R ≥ r₀, где r₀ = 0,8, рассматривая его как код БЧХ, исправляющий одиночные ошибки. Сформировать разрешённую комбинацию систематического кода, соответствующую заданной информационной комбинации . Исправить ошибку в принимаемой кодовой комбинации .

Решение:

По скорости кода r₀ определяем значение длины кодовой комбинации n и значение длины информационной последовательности k разработанного кода из выражения 1:

Данное отношение удовлетворяет коду Хэмминга (31,26), где , .

Рассмотрим код Хэмминга как циклический код и определим порождающий полином g(х). При заданной длине кода n и кратности исправления ошибки вычислим m из формулы 2:

(2)

Откуда:

Из выражения находим, . В таблице минимальных неприводимых многочленов находим значение полинома:

Порождающая матрица определяется из выражения 3:

, (3)

где:

– единичная матрица размером ;

– матрица, строки которой определяются из выражения 4:

(4)

где:

– полином соответствующий i-той строке.

Для определения матрицы воспользуемся выражением (4). В результате вычислений получаем:

Производящая матрица будет иметь вид:

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

Проверочная матрица в систематическом виде строится на основе матрицы по формуле 5:

(5)

где:

– единичная матрица,

– транспонированная матрица .

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

В соответствии с этим синдромом определяем по матрице , что ошибка произошла в 31 разряде, следовательно, исправленная комбинация:

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

2 Код БЧХ

Задача 2.2.4. Определить порождающий многочлен g(x) примитивного кода БЧХ над GF(2) длины n = 2^m – 1, где m = 4, исправляющего ошибки кратностью t_и = 3. Сформировать разрешённую комбинацию систематического кода, соответствующую информационной комбинации a(x) = 11001. Построить регистр кодирующего устройства систематического циклического кода с порождающим многочленом g(x), привести таблицу, иллюстрирующую состояние ячеек в процессе работы регистра при поступлении на его вход информационного блока a(x). Определить, является ли разрешённой принимаемая кодовая комбинация V’(x) = 100101101011001.

Решение:

Для определения порождающего многочлена примитивного БЧХ кода была использована таблица минимальных многочленов. Определим значение параметров и из выражений:

;

Из таблицы минимальных многочленов в соответствии с и получаем:

Выполнив умножение соответствующих многочленов, получим:

Найдем кодовую комбинацию в соответствии с выражением 6:

, (6)

где:

– входная информационная последовательность;

– определяется из выражения ;

– находится как остаток от деления на по формуле 7:

(7)

Рассчитаем в среде Matlab:

Следовательно по формуле 6 равна:

Построим регистр кодирующего устройства систематического циклического кода (рисунок 1) на основе порождающего многочлена следующим образом. Длина регистра равна степени многочлена и соответствует десяти. Число обратных связей и сумматоров по |2| соответствует количеству коэффициентов порождающего многочлена равных единицы (за исключением старшего), т.е. . Перед ячейками, номера которых соответствуют индексам единичных коэффициентов, размещаются сумматоры по |2|.

Рисунок 1 – Регистр кодирующего устройства систематического циклического кода

В таблице 1 показано состояние ячеек в процессе работы регистра.

Таблица 1 – Таблица состояние ячеек в процессе работы регистра

Вход	Состояние ячеек
Вход	0	1	2	3	4	5	6	7	8	9
1	1	1	1	0	1	1	0	0	1	0
1	1	0	0	1	1	0	1	0	1	1
0	1	0	1	0	0	0	0	1	1	1
0	1	0	1	1	1	1	0	0	0	1
1	0	1	0	1	1	1	1	0	0	0

После поступления на вход регистра информационного блока в его ячейках формируется последовательность .

Для того, чтобы определить является ли разрешенной комбинация, следует найти остаток от деления принимаемой комбинации на порождающий многочлен . Если остаток равен нулю, комбинация является разрешенной, если остаток отличен от нуля, то принимаемая комбинация является неразрешенной. Осуществим деление в среде Matlab:

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

3 Код Рида-Соломона

Задача 3.1.1. Построить таблицы представления, сложения и умножения элементов в поле GF(q), где . Определить порождающий многочлен кода Рида-Соломона над этим полем, исходя из условия, что код должен исправлять неправильно принятых q-ичных символов. Сформировать разрешённую комбинацию систематического кода, соответствующую заданной информационной комбинации a(x) = 100101110 (456). Вычислить синдром, определить местонахождение и значение ошибки и устранить ошибку в принимаемой кодовой комбинации V’(x) = 100011110000111101111 (4360757).

Решение:

Определим параметры кода Рида-Соломона:

– длина кода;

– кодовое расстояние;

– максимальная степень полинома g(x);

– длина информационной последовательности.

Первым этапом решения задачи является построение таблицы представлений поля GF(8), построенного на основе многочлена с примитивным элементом .

Таблица 2 – таблицы представления элементов в поле GF(8)

Степенное обозначение	Многочленное обозначение	Кодовое обозначение	Десятичное обозначение
0	0	000	0
α⁰	1	001	1
α¹	z	010	2
α²	z²	100	4
α³	z+1	011	3
α⁴	z²+z	110	6
α⁵	z²+z+1	111	7
α⁶	z²+1	101	5

Таблица 3 – Таблица сложения элементов в поле GF(8)

+	0	1	α¹	α²	α³	α⁴	α⁵	α⁶
0	0	1	α¹	α²	α³	α⁴	α⁵	α⁶
1	1	0	α³	α⁶	α¹	α⁵	α⁴	α²
α¹	α¹	α³	0	α⁴	1	α²	α⁶	α⁵
α²	α²	α⁶	α⁴	0	α⁵	α¹	α³	1
α³	α³	α¹	1	α⁵	0	α⁶	α²	α⁴
α⁴	α⁴	α⁵	α²	α¹	α⁶	0	1	α³
α⁵	α⁵	α⁴	α⁶	α³	α²	1	0	α¹
α⁶	α⁶	α²	α⁵	1	α⁴	α³	α¹	0

Таблица 4 – Таблица умножения элементов в поле GF(8)

´	1	α¹	α²	α³	α⁴	α⁵	α⁶
0	0	0	0	0	0	0	0
1	1	α¹	α²	α³	α⁴	α⁵	α⁶
α¹	α¹	α²	α³	α⁴	α⁵	α⁶	α⁷
α²	α²	α³	α⁴	α⁵	α⁶	α⁷	α⁸
α³	α³	α⁴	α⁵	α⁶	α⁷	α⁸	α⁹
α⁴	α⁴	α⁵	α⁶	α⁷	α⁸	α⁹	α¹⁰
α⁵	α⁵	α⁶	α⁷	α⁸	α⁹	α¹⁰	α¹¹
α⁶	α⁶	α⁷	α⁸	α⁹	α¹⁰	α¹¹	α¹²

Так как , то каждый q-ичный символ кода состоит из трех двоичных элементов. Поэтому с учетом таблицы 2:

Далее вычислим порождающий многочлен :

Определим разрешенную комбинацию систематического кода .

определяется по формуле 7, воспользовавшись средой Matlab.

Отсюда разрешенная комбинация систематического кода равна:

10111101111

Определим является ли разрешенной комбинации . Если в соответствии с формулой 8 синдром содержащий – разрядов, то все разряды должны быть нулевыми:

где:

Вычисляем синдром для этой комбинации:

Локатор ошибок для данного кода будет иметь вид: . Найдем его коэффициенты из следующей системы уравнений:

Подставив в нее значения синдрома, получим:

Получим коэффициенты локатора ошибок: и .

Локатор ошибок имеет вид:

Для того, чтобы найти корни нужно в правую часть подставить вместо поочередно все ненулевые значения элементов поля . Те элементы поля, при подстановке которых полином принимает нулевое значение, являются его корнями. Получаем что: .

Отсюда находим числа , которые указывают расположения ошибок в принятой кодовой комбинации: .

Это значит, что ошибки находятся при 2 и 5 степенях многочленного представления принятой кодовой комбинации. Но кроме расположения ошибок необходимо выяснит их значение. Для этого решим систему:

Подставим в систему значения :

Коэффициенты – принадлежат многочлену ошибок . Запишем и сам многочлен :

Сложим многочлен ошибок с принятой кодовой комбинацией и получим исправленную комбинацию, которая является разрешенной:

ЗАКЛЮЧЕНИЕ

В процессе выполнения курсового проекта были изучены принципы кодирования кодом Хэмминга, БЧХ и Рида-Соломона. В соответствии с заданием были решены три задачи.

Таким образом, задание на курсовой проект выполнено в полном объёме.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1 Султанов Б.В., Иванов А.П., Геращенко С.М. Математические основы построения помехоустойчивых блочных кодов для защищённых телекоммуникационных систем: учебное пособие. – Пенза: Изд-во Пенз. гос. ун-та, 2007. – 64с.: ил. – Библиогр.: с.56.

2 Кузнецов Ю.А. Передача дискретных сообщений. Конспект лекций. – Пенза 2000г.