Кодирование и декодирование текстовой информации циклическим кодом с исправлением тройных одиночных ошибок

 

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ УКРАИНЫ

 

СЕВАСТОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

 

Кафедра

Информационных систем

 

 

 

 

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

по теме «Кодирование и декодирование текстовой информации циклическим кодом с исправлением тройных одиночных ошибок»

по дисциплине «Кодирование и защита информации».

 

 

 

 

  листов

 

 

 

 

 

Выполнил:

студент группы И-33д

Берёзин П.А.

 

Проверил:

Василенко В.А.

 

 

 

 

 

 

Севастополь

2001

 

АННОТАЦИЯ

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

Данная пояснительная записка содержит следующие разделы:

• введение;
• теоретическое обоснование метода в сравнении с другими методами;
• Описание функциональных возможностей программы
• структурная схема алгоритма кодирования и декодирования;
• Программная реализация
• заключение;
• библиографический список;
• приложение:

А - Текст программы;

Б - Тестовый пример.

 

Севастопольский государственный технический университет

(название высшего учебного заведения)

Кафедра информационных систем

Дисциплина Кодирование и защита информации

Специальность информационные управляющие системы и технологии

Курс  третий   Группа И-33д  Семестр пятый

 

ЗАДАНИЕ

на курсовой проект (работу) студента

Берёзина П. А.

(фамилия, имя, отчество)

1 Тема проекта (работы). Кодирование и декодирование текстовой информации циклическим кодом с исправлением тройных одиночных ошибок.

2 Срок сдачи студентом законченного проекта  1 ноября 2001г

3 Входные данные к проекту по усмотрению разработчика

 

 

 

 

I Содержание расчетно-пояснительной записки

1 Постановка  задачи

2 Теоретическое обоснование метода в сравнении с другими методами

3 Описание  функциональных возможностей программы

4 Структурная схема  алгоритма кодирования и декодирования

5 Программная  реализация

 

 

 

 

 

 

7) Дата выдачи задания  7 сентября 2001 года

 

КАЛЕНДАРНЫЙ ПЛАН

 

№ п/п	Название этапов курсо- вого проекта (работы)	Срок выполнения Этапов проекта	Примечания
1	Изучение методов ре-
	шения поставленной
	задачи	2.09 – 10.09
2	Составление алгорит-
	ма программы и разра-
	ботка интерфейса	10.9 – 15.09
3	Написание текста прог-
	раммы	15.09 – 10.10
4	Отладка программы на
	примерах	10.10 –20.10
5	Проведение вычисли-
	тельного эксперимента	20.10 –22.10
6	Оформление  поясни-
	тельной записки	22.10 – 30.10

 

Студент.

(подпись)

Руководитель Василенко В.А.

(подпись) (фамилия, имя, отчество)

 

 

 

<    7    >     сентября      2001 г.

 

СОДЕРЖАНИЕ

Введение 6

1 Постановка задачи 7

2 Теоретическое обоснование метода  в сравнении с другими методами 8

3 Описание функциональных возможностей  программы 10

4 Структурная схема алгоритма  кодирования и декодирования 11

5 Программная реализация 13

Заключение 14

Библиографический список 15

Приложение А 16

Приложение Б 29

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                            КУРСОВОЙ ПРОЕКТ

                                                                                                 Лит.         

Изм. Лист N докум. Подп. Дат  

Разраб.            Берёзин                         ПОЯСНИТЕЛЬНАЯ ЗАПИСКА     Т  Провер.     Василенко

                                                  Лист   Листов

Н.Контр                     Кафедра ИС 

Утв.                  Группа И-33д

ВВЕДЕНИЕ

 

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

 

1 ПОСТАНОВКА ЗАДАЧИ

 

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

 

2 Теоретическое обоснование метода в сравнении с другими методами

 

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

Первоначально циклические  коды они были созданы для упрощения  схем кодирования. Их эффективность обеспечила им широкое применение на практике.

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

Для образования циклического кода служат так называемые образующие полиномы, степень которых соответствует  количеству проверочных символов. Образующий полином – это всегда неприводимой многочлен, т. е. делящийся только сам на себя и на «1» и одновременно входящий в разложение двучлена x+1.

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

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

Для исправления ошибок необходимо разделить кодовую комбинацию на образующий многочлен и определить вес остатка. Если этот вес меньше или равен кратности исправляемых ошибок, то этот остаток складывают с принятой комбинацией и ошибка исправлена. Если вес больше кратности исправляемых ошибок W>t_и, то производим циклический сдвиг принятой кодовой комбинации на один разряд влево и эту сдвинутую комбинацию вновь делим на образующий полином и опять определяем вес остатка. Продолжаем процедуру до тех пор, пока не выполнится соотношение W<=t_и. После этого последнее делимое складываем с последним остатком и затем циклически сдвигаем эту сумму вправо по разрядно столько раз, сколько раз до этого осуществляли циклический сдвиг влево.

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

 

3 ОПИСАНИЕ ФУНКЦИОНАЛЬНЫХ  ВОЗМОЖНОСТЕЙ ПРОГРАММЫ

 

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

 

4 СТРУКТУРНАЯ  СХЕМА АЛГОРИТМА КОДИРОВАНИЯ  И ДЕКОДИРОВАНИЯ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

 

Для разработки программы  был выбран язык программирования высокого уровня Delphi 6.

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

Delphi позволяет без особых трудностей реализовать удобный и красивый пользовательский интерфейс, не пребигая к объёмному и трудоёмкому написанию низкоуровневого кода.

В проекте предполагается кодирование  информации вводимой пользователем, как  с клавиатуры, так и из специально подготовленного файла.

 

ЗАКЛЮЧЕНИЕ

 

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

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

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Конспект лекций по дисциплине “Кодирование и защита информации”.
2. Березюк Н. Т., Андрющенко А. Г., Мощинский С. С. и др. Кодирование информации (двоичные коды). – Харьков: Выща школа, 1978. – 252 с.
3. Кузьмин И. В., Кедрус В. А. Основы теории информации и кодирования. – Киев: Выща школа, 1977. – 280 с.
4. Цымбал В. П. Теория информации и кодирование. Киев, ”Вища школа”, 1997, 288 с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ  А