Курсовая работа

КОДЕК ХЭММИНГА

Категория:

Курсовая работа

Дисциплина:

Прикладная теория кодирования

Город:

Беларусь, Минск

Учебное заведение:

БГУИР, Факультет инфокоммуникаций

Стоимость работы:

80 руб.

Оценка: 10
Объем страниц: 20
Год сдачи: 2022
Дата публикации: 09.11.2022

Фрагменты для ознакомления

СОДЕРЖАНИЕ

Введение. 3

1 Основные сведения о принципах построения и декодирования помехоустойчивых кодов. 4

1.1 Базовые понятия помехоустойчивого кодирования и декодирования. 4

1.2 Принцип построения помехоустойчивых кодов. 4

2 Расчет параметров кодека. 7

3 Разработка кодека. 8

3.1 Разработка структурной схемы кодека. 8

3.2 Разработка функциональной схемы кодера. 8

3.3 Разработка функциональной схемы канала передачи данных с ошибками. 11

3.4 Разработка функциональной схемы декодера. 11

Заключение. 13

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

Приложение А (обязательное) структурная схема кодека хэмминга. 15

Приложение Б (обязательное) функциональная схема кодера. 16

Приложение В (обязательное) функциональная схема канала. 17

Приложение Г (обязательное) функциональная схема декодера. 18

 

ВВЕДЕНИЕ

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

Ричард Хэмминг постоянно вел активные научные исследования, однако знаменитой стала его единственная работа в области теории информации, составляющая по своему объему ничтожный процент его научного творчества. Эта статья быстро получила мировую известность и принесла ему заслуженную славу.

 Одним из важнейших разделов теории информации является теория кодирования, основы которой были заложены Хэммингом. Шеннон установил, что по каналу связи информация может передаваться безошибочно в том случае, если скорость передачи не превышает его пропускной способности. Однако доказательство Шеннона носило неконструктивный характер. Более поздние его исследования и другого американского ученого С. О. Райса показали, что практически любой случайно выбранный код позволяет достичь теоретического предела помехоустойчивости приёма сообщений. Однако такой код имел высокую сложность декодирования: число операций, необходимых для декодирования принятой кодовой комбинации, возрастал экспоненциально росту его длины.

Хэмминг был первым, кто предложил конструктивный метод построения кодов с избыточностью и простым декодированием [1].

Код Хэмминга – это блочный код, позволяющий исправлять одиночные и фиксировать двойные ошибки.

Идея кодов Хэмминга заключается в разбиении данных на блоки фиксированной длины и вводе в эти блоки контрольных бит, дополняющих до четности несколько пересекающихся групп, охватывающих все биты блока. Ричард Хемминг рассчитал минимальное количество проверочных бит, позволяющих однозначно исправлять однократные ошибки.

Целью курсовой работы является изучение особенностей кода Хэмминга и построение его кодека. Задача данной работы состоит в построении кодера, канала и декодера, а также в вычислении параметров кода Хэмминга и получении навыков в построении функциональных и структурных схем в программе Logisim.

 

1 ОСНОВНЫЕ СВЕДЕНИЯ О ПРИНЦИПАХ ПОСТРОЕНИЯ И ДЕКОДИРОВАНИЯ ПОМЕХОУСТОЙЧИВЫХ КОДОВ

1.1 Базовые понятия помехоустойчивого кодирования и декодирования

Кодированием и декодированием (в широком смысле) называют любое преобразование сообщения в сигнал и обратно, сигнала в сообщение, путем установления взаимного соответствия. Преобразование следует считать оптимальным, если в конечном итоге производительность источника и пропускная способность канала окажутся равными, т.е. возможности канала будут полностью использованы. Данное преобразование разбивается на два этапа:

  • модуляция-демодуляция, позволяющая осуществить переход от непрерывного сигнала радиоканала к дискретному;
  • кодирование-декодирование (в узком смысле), во время которого все операции выполняются над последовательностью символов.

В свою очередь, кодирование-декодирование делится на два противоположных по своим действиям этапа:

  • устранение избыточности в принимаемом от источника сигнале (экономное кодирование);
  • внесение избыточности в передаваемый по каналу цифровой сигнал (помехоустойчивое или избыточное кодирование) для повышения достоверности передаваемой информации [2].

 

1.2 Принцип построения помехоустойчивых кодов

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

 На этот вопрос дает ответ теорема Шеннона о пропускной способности непрерывного канала связи, из которой следует, что пропускная способность непрерывного канала увеличивается с расширением его полосы, но при оптимальном (в широком смысле) кодировании. Поэтому следует ожидать повышения достоверности передачи при заданной скорости и отношении сигнал/шум в канале при внесении избыточности. Однако не существует оптимального кодека для сообщения, не фиксированного по длительности. Тем не менее, избыточное кодирование стало широко применяться в целях повышения качества передачи, преимущественно в последние десятилетия, когда проблема создания сложных вычислительных устройств в малых габаритах была практически решена.

 

3 РАЗРАБОТКА КОДЕКА

3.1 Разработка структурной схемы кодека

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

Для того, чтобы создать структурную схему кодека в программе Logisim, которая является графическим инструментом для разработки и моделирования логических схем, необходимо нажать на кнопку создания новой схемы и скомпоновать ранее созданные схемы кодера, канала и декодера. Структуру файлов при построении кодека можно увидеть на рисунке 3.1.

Структура файлов при построении кодека в программе Logisim
Рисунок 3.1- Структура файлов при построении кодека в программе Logisim

 

3.2 Разработка функциональной схемы кодера

Для осуществления кодирования информации кодек Хэмминга должен быть оснащен функциональной частью, которая называется кодер.

Информация, которая представленная в виде последовательности «0» и «1», разбивается на блоки длиной k бит, называемые информационными векторами. В условии данной курсовой работы сказано, что k = 22. Каждый блок кодируется независимо, а результатом кодирования будет блок длиной n бит, называемый кодовым словом.

Проверочная матрица имеет размерность , в курсовой работе используется укороченный код Хэмминга, поэтому для начала составим проверочную матрицу полного кода (31;26;3) (см. рисунок 3.2).

Чтобы получить проверочную матрицу укороченного кода (27;22;3), необходимо исключить произвольные столбцы. Их количество равно Т. Согласно расчету, произведенному в разделе 2, Т = 4.

Таким образом, проверочная матрица для укороченного кода (27;22;3) показана на рисунке 3.3.

Проверочная матрица для кода (31;26;3)
Рисунок 3.2- Проверочная матрица для кода (31;26;3)

 

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

[1] Ричард Хэмминг и начало теории кодирования [Электронный ресурс]. – Режим доступа: https://www.computer-museum.ru/galglory/hamming.htm

[2] Помехоустойчивое кодирование и декодирование в дискретных КПС [Электронный ресурс]. – Режим доступа: https://ru.bmstu.wiki

[3] Прикладная теория кодирования [Электронный ресурс]. - Режим доступа: https://elib.psu.by

 

ПРИЛОЖЕНИЕ А
Структурная схема кодека Хэмминга

Структурная схема кодека
Рисунок А.1-Структурная схема кодека
15