Перекодирование текстовой информации

Министерство образования РФ

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

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

по теме «Перекодирование текстовой информации»

РЕФЕРАТ Объектом исследования является помехоустойчивое кодирование, а так же декодирование информации с коррекцией одиночных ошибочных битов по методу Хемминга 15−11.

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

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

Перед выполнением работы были разработан алгоритм, который позволил создать максимально эффективный и удобный в обращении программный продукт.

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

• Введение

1. Сведения об используемых языках программирования

• 1.1 Язык С и его особенности

1.2 Преимущества Ассемблера

• 2. Интерфейс
• 2.1 Интерактивный режим работы

2.2 Взаимодействие пользователя с программным интерфейсом

2.3 Диагностические сообщения

• 3. Программная реализация

Заключение

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

• Приложения

Введение

Основной задачей, поставленной в курсовом проектировании, является разработка программы, которая позволила бы осуществлять работу с файлами и их последующее помехоустойчивое кодирование-декодирование по методу Хемминга-15,11 в интерактивном режиме.

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

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

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

первая — является прослойкой между ОС и функцией кодирования-декодирования, а именно осуществляет работу с файлами, а так же информирует об ошибках ввода-вывода (невозможность открытие файлов, записи в конечный файл), а так же о других системных ошибках, таких как, например, нехватка оперативной памяти для выделения буфера;

вторая — это внешние функции кодирования-декодирования. Функции созданы на языке низкого уровня Ассемблере;

третья часть — это реализация интерактивного интерфейса.

1. Сведения об используемых языках программирования

1.1 Язык С и его особенности

Язык C является универсальным языком программирования. Он тесно связан с операционной системой UNIX, так как эта операционная система и ее программное обеспечение написано именно на этом языке. Сам язык, однако, не связан с какой-либо одной операционной системой или машиной, т. е. является системно-независимым; и хотя его называют языком системного программирования, так как он удобен для написания операционных систем, он с равным успехом может использоваться при написании больших вычислительных программ, программ для обработки текстов и баз данных. Язык C — это язык достаточно низкого уровня.

В такой характеристике нет ничего оскорбительного; это просто означает, что C имеет дело с объектами того же вида, что и большинство ЭВМ, а именно с символами, числами и адресами. Они могут объединяться и пересылаться посредством обычных арифметических и логических операций, осуществляемых реальными ЭВМ. В языке C отсутствуют операции, имеющие дело непосредственно с составными объектами, такими как строки символов, множества, списки или с массивами, рассматриваемыми как целое. Наконец, сам по себе C не обеспечивает никаких возможностей ввода-вывода: здесь нет операторов READ или WRITE, как в языке Pascal, и никаких встроенных методов доступа к файлам. Все эти механизмы высокого уровня должны обеспечиваться явно вызываемыми функциями. Аналогично, язык C предлагает только простые, последовательные конструкции потоков управления: проверки, циклы, группирование и подпрограммы, но не мультипрограммирование, параллельные операции, синхронизацию или сопрограммы. Хотя отсутствие некоторых из этих средств может выглядеть как некая неполноценность, но удержание количества ключевых элементов языка в скромных размерах дает реальные преимущества. Так как лексикон языка C относительно мал, он не требует многотомных трудов для своего описания и может быть быстро выучен. Отсюда же следует и относительная лёгкость написания компилятора для любой ОС и процессорной архитектуры, что обеспечивает высокую степень мобильности языка.

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

1.2 Преимущества Ассемблера

программный интерфейс помехоустойчивый декодирование

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

Язык ассемблера необходим также в тех случаях, когда главными являются рабочие характеристики программы. К рабочим характеристикам могут относиться либо время выполнения, как в нашем случае, либо размер программы.

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

2. Интерфейс

2.1 Интерактивный режим работы

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

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

2.2 Взаимодействие пользователя с программным интерфейсом

В процессе составления мною алгоритма программы было решено организовать текстовый интерфейс.

1. При запуске созданного мною программного продукта вы должны увидеть главное меню программы:

1. Закодировать файл

2. Раскодировать файл Выход — Esc

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

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

Пользователь может выбрать один из трех предложенных пунктов, а именно:

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

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

3. Выход При выборе этого пункта происходит завершение программы с выходом в ОС.

При выборе пункта меню «Закодировать файл» или «Раскодировать файл» в рабочей области на экране появятся новые сообщения:

Введите имя входного файла:

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

Для возврата в предыдущее меню нажмите клавишу Enter или Return (т.е. оставьте поле ввода имени файла пустым).

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

Введите имя выходного файла:

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

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

2.3 Диагностические сообщения

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

Основные сообщения: «Не могу открыть файл с именем …»

Возникает при попытке открыть несуществующий файл с исходными данными.

Так же может являться следствием ограничения прав конкретного пользователя в системах с разграничением доступа (UNIX, Windows NT, 2000 и т. д.) или же файл может быть уже открыт другой программой. Следует указать другой путь.

Если такое сообщение об ошибке возникает при попытке ввести имя выходного файла, то основной причиной является попытка задать такое местонахождение файла, которое является областью «только для чтения» (устройства чтения компакт-дисков, защищенные от записи дискеты). Следует указать другой путь.

«Файл … успешно перекодирован в …»

Файл был успешно закодирован-декодирован с помощью метода Хемминга-15,11. Если при декодировании возникали ошибки, то все они по возможности были исправлены. В связи с тем, что используется кодирование информации с помощью метода Хемминга-15,11, то гарантируется исправление лишь однобитовых ошибок.

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

Основную информацию о принципе работы программы можно узнать из блок-схемы, представленной в приложениях С и D, а так же из исходного текста программы, расположенном в приложениях A и B. Предложенное в этой главе описание служит лишь маленьким подспорьем, т.к. поясняет лишь некоторые моменты.

Программа условно разделяется на 4 логических части:

1. Работа с файлами

2. Блоки реализации интерфейса

3. Блоки обработки ошибок

4. Внешние функции кодирования-декодирования.

Рассмотрим каждую из них, а так же их взаимодействие:

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

2. Интерфейс служит для облегчения взаимодействия программы с пользователями. Интерактивный «дружественный» интерфейс позволяет существенно уменьшиться время освоения программного продукта. Интерфейс реализован в текстовом режиме (textmode (C80)), что является следствием проведенного анализа на качество восприятия информации в различных режимах, а так же большей простотой в реализации, чем графического, при практически одинаковом результате.

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

4. Внешние функции кодирования и декодирования базируются на алгоритме Хемминга. Основой этого алгоритма является добавление проверочных разрядов в исходную кодовую комбинацию при кодировании и проверке полученного четырехразрядного синдрома при декодировании. Если полученный синдром равен нулю, то в кодовой комбинации не содержится ошибок, иначе значение синдрома указывает на номер искаженного бита. После запуска программы пользователь может выбрать один из трех предложенных вариантов: вызов функции кодирования, вызов функции декодирования или пункт выхода из программы. При выборе первых двух пунктов появляются поля запроса, в которых необходимо ввести имена входного и выходного файлов. Производиться попытка открытия исходного файла; если это по каким-либо причинам не удается, то выводится соответствующее сообщение об ошибке и предлагается осуществить повторный ввод. Осуществляется попытка открытия выходного файла на запись, в случае неудачи выводится сообщение об ошибке и предлагаться осуществить повторный ввод. Затем в память считывается блок информации размером 32 бита (4 байта) для кодирования и 48 бит (6 байт) для раскодирования из исходного файла. Вызывается внешняя функция обработки файла. При кодировании исходные данные длиной 32 бита делятся на 3 части, состоящие из 11 бит каждая. Каждая часть раздельно кодируется по методу Хемминга-15,11. Затем каждые закодированные части по 15 бит дополняются незначащим битом до слова (16 бит) и сохраняются в выходном буфере. При декодировании исходные данные длиной 48 бит (6 байт) делятся на 2 слова (16 бит). Для каждого из слов составляется синдром, и, в случае, когда он не нулевой, исправляется ошибочный бит. Затем из исправленных слов выделяется по 11 информационных бит, которые затем и формируют выходные 32 бита. Если вызванная функция проверки открытого файла на конец возвращает ненулевое значение, то происходит выдача сообщения об успешном перекодировании с последующим возвратом в главное меню.

Заключение

В результате проведенной работы был создан программный продукт, предназначенный для кодирования-декодирования файлов любого объема и содержания по методу Хемминга-15,11. Преобразование файлов выполняется с высокой скоростью благодаря использованию языка ассемблер для реализации функции обработки.

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

Разработанная программа может быть использована в большинстве известных ОС, таких, как Windows 9x-Me-NT-2000;Xp, а также, конечно, в среде MS-DOS, PC-DOS и т. д. Русскоязычные пользователи любого уровня подготовки найдут её интересной.

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

Березин Б.И., Березин С. Б. Начальный курс С и С++. — М.: Диалог-МИФИ, 1996.

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. — М.: Мир, 1976. — 594 с.

Шеннон К. Э. Теория связи в секретных системах. В кн. К. Э. Шеннона. «Работы по теории информации и кибернетике». — М.: ИЛ, 1963.

ПРИЛОЖЕНИЯ

Приложение А

Листинг программы

#include

#include

#include

#include

#include

#include

extern void far hem1511(const char far*, char far*); // функция перекодировки

extern void far unhem1511(const char far*, char far*); // функция перекодировки

int rabota (int);

main ()

{

char ch, end;

textmode (C80);

_setcursortype (_NOCURSOR);

textcolor (WHITE);

clrscr ();

cprintf («1. Закодировать файлrn2. Раскодировать файлrnВыход — Esc»);

end=1;

while (end≠0)

{

ch=getch ();

switch (ch)

{

case '1': rabota (1); clrscr ();

cprintf («1. Закодировать файлrn2. Раскодировать файлrnВыход — Esc»);break;

case '2': rabota (2); clrscr ();

cprintf («1. Закодировать файлrn2. Раскодировать файлrnВыход — Esc»);break;

case 27: end=0;

}

}

return 0;

}

int rabota (int mode)

{

unsigned char *in_buffer[6],*out_buffer[6], in_name[MAXPATH], out_name[MAXPATH];

FILE *file_in, *file_out;

short int num;

file_in=NULL; file_out=NULL;

while (file_in==NULL)

{

textcolor (WHITE);

cprintf («rnВведите имя входного файла: «);

textcolor (YELLOW);

in_name[0] = 254;

_setcursortype (_SOLIDCURSOR);

cgets (in_name);

if (in_name[1]==0)

{

_setcursortype (_NOCURSOR);

textcolor (WHITE);

return 1;

}

_setcursortype (_NOCURSOR);

file_in = fopen (&in_name[2], «rb»);

if (file_in==NULL)

{

textcolor (LIGHTRED);

cprintf («rnНе могу открыть файл с именем %s» ,&in_name[2]);

textcolor (WHITE);

}

}

while (file_out==NULL)

{

textcolor (WHITE);

cprintf («rnВведите имя выходного файла: «);

textcolor (LIGHTMAGENTA);

out_name[0] = 254;

_setcursortype (_SOLIDCURSOR);

cgets (out_name);

if (out_name[1]==0)

{

_setcursortype (_NOCURSOR);

textcolor (WHITE);

return 1;

}

_setcursortype (_NOCURSOR);

file_out = fopen (&out_name[2], «wb»);

if (file_out==NULL)

{

textcolor (LIGHTRED);

cprintf («rnНе могу открыть файл с именем %s» ,&out_name[2]);

textcolor (WHITE);

}

}

do

{

if (mode==2)

{

num=fread (in_buffer, 6, 1, file_in); // чтение буфера

if (num) {

unhem1511((char far*)in_buffer, (char far*)out_buffer); // конвертация буфера

fwrite (out_buffer, 4, 1, file_out);

}

}

else

{

num=fread (in_buffer, 4, 1, file_in); // чтение буфера

if (num) {

hem1511((char far*)in_buffer, (char far*)out_buffer); // конвертация буфера

fwrite (out_buffer, 6, 1, file_out);

}

}

}

while (!feof (file_in));

fclose (file_out); fclose (file_in);

textcolor (LIGHTCYAN);

cprintf («rnФайл %s успешно перекодирован в %s» ,&in_name[2],&out_name[2]);

_setcursortype (_NOCURSOR); textcolor (WHITE);

getch ();

return 0;

}

Приложение Б Листинг функции перекодирования

masm

.modelSMALL

.code

.386

public_hem1511, _unhem1511

_hem1511proc far; функция закодирования

arg inbuf: dword, outbuf: dword; аргументы функции — два дальних указателя

pushbp

movbp, sp; адресуем стек через bp

pushsi; сохраняем используемые регистры

pushdi

pushds

pushes

ldssi, [inbuf]

lesdi, [outbuf]

cld

xoreax, eax

xorebx, ebx

xorecx, ecx; формируем информационные биты

lodsd

movcx, 3

num1:

xorebx, ebx

shrdebx, eax, 1

shreax, 1

shrebx, 1

shrdebx, eax, 3

shreax, 3

shrebx, 1

shrdebx, eax, 7

shreax, 7

shrebx, 17

pushcx

callprov; функция определения проверочных битов

pushax

xorax, ax

moval, dl

xorbx, ax; устанавливаем первый проверочный бит

moval, dh

shlal, 1

xorbx, ax; второй

moval, cl

shlal, 3

xorbx, ax; четвертый

moval, ch

shlal, 7

xorbx, ax; восьмой

movax, bx

stosw

popax

popcx

loopnum1

popes

popds

popdi

popsi; восстанавливаем регистры

popbp

ret

_hem1511endp

_unhem1511proc far; функция раскодирования

arg inbuf: dword, outbuf: dword; в параметрах — два указателя

pushbp

movbp, sp

pushsi

pushdi

pushds

pushes

ldssi, [inbuf]

lesdi, [outbuf]

cld

xorebp, ebp

xoreax, eax

movcx, 3

num2:

lodsw

movbx, ax

pushcx

callprov

xorax, ax

pushbx

shrdax, bx, 1; формируем биты синдрома

rorbx, 1

shrax, 15

xordl, al; нулевой

subal, al

shrdax, bx, 1

rorbx, 2

shrax, 15

xordh, al; первый

subal, al

shrdax, bx, 1

rorbx, 4

shrax, 15

xorcl, al; второй

subal, al

shrdax, bx, 1

rorbx, 8

shrax, 15

xorch, al; третий

popbx

xorax, ax

oral, dl; формируем синдром из полученных битов

shldh, 1

oral, dh

shlcl, 2

oral, cl

shlch, 3

oral, ch

testal, al

jznormal; если синдром равен 0, то переходим на normal

xorcx, cx; помещаем синдром в cl

movcl, al

deccl

rorbx, cl

xorbx, 1; исправляем ошибку

rolbx, cl

normal:

popcx

xorax, ax

shrbx, 2

shrdax, bx, 1

shrbx, 2

shrdax, bx, 3

shrbx, 4

shrdax, bx, 7

shrax, 5

orebp, eax

rorebp, 10

;loop num2

deccx

jnznum2

moveax, ebp

stosd

popes

popds

popdi

popsi; восстанавливаем регистры

popbp

ret

_unhem1511endp

provproc near

; bx — входные 16 бит

; в регистрах dl, dh, cl, ch, — проверочные биты

; dl — первый, dh — второй, cl — четвертый, ch — восьмой

; получаем по очереди каждый бит и складываем с необходимыми проверочными битами

pushax

pushbx

xorax, ax

xorcx, cx

xordx, dx

rorbx, 2

shrdax, bx, 1; получаем 3 бит

shrax, 15

xordl, al; складываем с первым битом

xordh, al; складываем со вторым битом

subal, al

rorbx, 2

shrdax, bx, 1;5

shrax, 15

xordl, al

xorcl, al

subal, al

rorbx, 1

shrdax, bx, 1;6

shrax, 15

xordh, al

xorcl, al

subal, al

rorbx, 1

shrdax, bx, 1;7

shrax, 15

xordl, al

xordh, al

xorcl, al

sub al, al

rorbx, 2

shrdax, bx, 1;9

shrax, 15

xordl, al

xorch, al

sub al, al

rorbx, 1

shrdax, bx, 1;10

shrax, 15

xordh, al

xorch, al

subal, al

rorbx, 1

shrdax, bx, 1;11

shrax, 15

xordl, al

xordh, al

xorch, al

subal, al

rorbx, 1

shrdax, bx, 1;12

shrax, 15

xorcl, al

xorch, al

subal, al

rorbx, 1

shrdax, bx, 1;13

shrax, 15

xordl, al

xorcl, al

xorch, al

subal, al

rorbx, 1

shrdax, bx, 1;14

shrax, 15

xordh, al

xorcl, al

xorch, al

subal, al

rorebp, 1

shrdax, bx, 1;15

shrax, 15

xordl, al

xordh, al

xorcl, al

xorch, al

popbx

popax

ret

provendp

end

Приложение В Алгоритм работы программы

Приложение Г Алгоритм работы внешних функций преобразования