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

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

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

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

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

Отчет

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

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

по теме:

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

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

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

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

Пенза 2011

Изм..

Лист

№ докум.

Подп.

Дата

Лист

2

ПГУ 4.090106.001 ПЗ

Разраб.

Мухутдинова 

в С.А.

Провер.

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

Реценз. 

Н.Контр.

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

Утв. 
 

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

Лит.

Листов

19

Гр. 08ПТ3

РЕФЕРАТ 

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

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

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

     

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

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

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

     СОДЕРЖАНИЕ 

    Реферат 2

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

    Введение 5

1. Код Хемминга 6
2. Код БЧХ 10
3. Код Рида-Соломона 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|.  

0

5

1

7

2

4

3

6

8

9

Рисунок 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