Министерствообразования и науки Украины
ПОЯСНИТЕЛЬНАЯЗАПИСКА
к курсовомупроекту
на тему:«Методы сжатия цифровой информации. Метод Лавинского»
по курсу«Кодирование и защита
информации»
2004
Содержание
/>
Введение
1. Постановка задачи
2. Обзор существующих методов решениязадачи
2.1 Сжатие и кодирование информации винформационно вычислительных комплексах (ИВК)
2.2 Сжатие с восстановлением
2.3 Методы сжатия цифровой информациис повторяющимися фрагментами
3. Выбор и обоснование решения задачи
4. Теоретическое обоснование методаЛавинского
5. Программное обеспечение иинформационный выбор метода
Заключение
Библиографический список
Приложение А
Приложение Б
/>Введение
В наши дни все большеераспространение получает обработка и хранение информации при помощи ЭВМ. Приэтом одной из важнейших задач является сохранение ее целостности, т.е. защитаот потери данных, как при их передаче, так и в некоторых случаях при хранении.
Метод Лавинскогоотносится к простейшим методам сжатия информации (числовых массивов) и оносуществляет сжатие путем уменьшения разрядности числа (исходного). Метод темлучше функционирует, чем больше массив и разность между числами в немсоставляет малую величину.
/>1. Постановка задачи
Составить программусжатия по методу Лавинского, показать её возможности на выбранном Вами примере.
Программный продуктпредусматривает сжатие массива, прочитанного из файла, по методу Лавинского,т.е. уменьшения разрядности чисел содержащихся в исходном файле. Этодостигается путем преобразования символов файла в биты и запись их в новыйфайл.
Деархивация строится наоснове того, что в новый (сжатый файл) перед каждым символом записывается номерграницы к которой это число относится, а размер для каждой границы естьконстанта умноженная на номер границы.
2. Обзор существующихметодов решения задачи
2.1 Сжатие икодирование информации в информационно вычислительных комплексах (ИВК)
ИВК – это набор,состоящий из одного или нескольких ЭВМ, снабженных устройствами хранения, вводавывода и передачи информации. ИВК имеет отдельные устройства, разнесенные междусобой.
Информационная сетьпредставляет собой набор ИВК, соединенных между собой каналами передачиинформации (каналы могут быть любой протяженности). Для того, чтобы сеть моглафункционировать, она снабжается набором протоколов и интерфейсов.
Протокол – некотороемножество информационных функций и алгоритмов обработки информации, которыеприняты в той или иной сети.
Интерфейс – некотороесоединение или канал между отдельными функциональными частями сети. Интерфейсыбывают физические и программные.
Физический интерфейс –набор шин, для передачи сигналов, и электрических устройств для управленияпрохождения сигналов по этим шинам. Большинство физических интерфейсов — стыки.
Программный интерфейс –часть программного обеспечения сети, отвечающая за передачу информации от узлак узлу.
Сети могут быть гомогеннымии гетерогенными (однородными и разнородными).
В гомогенных сетяхиспользуются однотипные ЭВМ и однотипные программное обеспечение.
В гетерогенных сетяхпротоколы, кроме всего прочего, согласуют разнородное программное обеспечение,а интерфейсы согласуют физические пороги сигналов.
Все универсальные сетиявляются гомогенными.Сеть чаще всего является открытой системой.
Открытой называется такаясистема, которая может взаимодействовать с другими системами. Для того, чтобыоткрытая система нормально функционировала она должна обеспечивать семь уровнейэтого функционирования:
прикладной
представительский
сеансовый
транспортный
сетевой
канальный
физический
Прикладной уровеньфункционирования предполагает унификацию и /> />
стандартизацию управляющихсигналов, форматы информационных кадров, методов кодирования и защиты от ошибоки основные служебные посылки.
Ф1 и Ф2 – флаги;
А – адрес;
З О – защита от ошибок.
Представительский уровеньунифицирует форму представления информации, то есть тип сигналов, вид кодов,способы защиты от ошибок и правила семиотики (науки о знаках) для выбраннойзнаковой системы.
Сеансовый уровеньунифицирует длительность сеансов связи между узлами сети, служебную информациюдля вызова или организации таких сеансов, способ стыковки между функциональнымичастями при сеансе связи.
Транспортный уровеньунифицирует собственно передачу информации, то есть ее скорость или время,способ передачи (параллельно, последовательно или смешанно) информации и видымодемов и аппаратуры передачи данных.
Сетевой уровеньунифицирует (стандартизует) прохождение сигналов по очередям, вид этихочередей, способ обслуживания, разновидности персональной защиты и доступа(ключи, пароли, шифры).
Канальный уровеньунифицирует прохождение сигналов по каналу с помощью унификации инициализации,синхронизации и аппаратуры защиты от ошибок.
Физический уровеньпроводит унификацию физических сигналов по уровню (амплитуде), частоте, фазе ипо виду модуляции сигналов.
В открытых сетях, в видуогромных объемов проходящей информации, производится сжатие информации.Существует сжатие без восстановления и с восстановлением. Сжатие безвосстановления предполагает, что передается алфавитно-цифровая информация,которая тем или иным способом уменьшается в объеме и на приемной сторонепринимается сжатый объем. А при сжатии с восстановлением приемник получаетисходный текст, при условии, что передавался сжатый текст. В общем случае,сжатие (компрессия) данных представляет собой процесс выделения из исходногоинформационного массива его информативной части путем отбрасывания некоторыхсимволов, несущих минимальное число этой информации. Сжатие производится до техпор, пока информативность сохраняется. Простейший способ сжатия безвосстановления для текстовой информации на естественном языке, предполагаетналичие словаря запретов, который поддерживается сетью и доводится до всехабонентов. В него входят одно, двух и трехбуквенные слова с минимальнойинформативностью, которые из текста исключаются. Из текста, начиная от концаслова к началу, убирают все гласные и часть согласных до наличия еще в словенеобходимого смысла. Первые три согласные несут 84% информации.
Если информацияпредставлена в цифровом виде, то в этом случае задают длину блока, до которогонеобходимо ее сжать.
Весь текст бьется наблоки заданной длины или меньшей и затем производится либо сложение их помодулю два, либо двоичное сложение и передается их сумма.
/>
Если информация нецифровая, а текстовая, то можно использовать тот же метод, если каждую буквузакодировать некоторым кодом равномерной длины./> />
В том случае, если длина блока,кодирующего букву меньше, чем требуемая длина блока для передачи, сложениепроизводится при ступенчатом сдвиге одной буквы относительно другой на однупозицию влево, начиная от первой буквы слова к последней.
2.2 Сжатие свосстановлением
Методы сжатия свосстановлением должны обеспечить переход к исходному сообщению при заданном КСЖ.
n1 – число символов висходном сообщении
/>
n2 – число символов всжатом сообщении
Простейшим способомтакого сжатия является способ хранения атрибутов в виде битовой матрицы.
Передаются толькоединицы, которые оговариваются либо частотой, либо временем и т. д.
/>
2.3 Методы сжатияцифровой информации с повторяющимися фрагментами
/>
Предполагается, чтоинформация записывается в файлы. Первая часть применима для тех информационныхмассивов, в которых повторяющиеся фрагменты стоят в начале строки. В этомслучае используется символ пропуска r, весь массив передается одной строкой.
123456r7r41r2
Восстановление начинаетсяот конца к началу, при известном количестве символов в строке. Запись каждойстроки производится до символа пропуска.
/>
Далее сверху вниззаписываем символы предыдущей строки.
Второй способиспользуется для тех массивов, в которых повторы не только в начале строки:используется символ r исимвол конца строки k.
/>
Если массив строкодинаковой длины содержит несколько повторяющихся фрагментов в различных местахстроки, то в этом случае вводятся символы, обозначающее количество пропусков иможно не использовать символ r конца строки.
/>
Восстановление начинают спервой исходной строки, где количество пропусков определяется предыдущейстрокой.
Если информация анкетноготипа, записанная в алфавитно-цифровой форме, то можно использовать вместо частиповторяющегося текста два значка (символа). Один из символ повтора, а второй –сколько букв пропущено при повторе.
/>
2.4 Зонное сжатие
Метод зонного сжатияиспользуют для текстовых массивов с учетом символов естественного алфавита изнаков препинания.
28 = 256
предложено использоватьчетыре бита (полубайт) для записи каждой буквы, тем самым создавая некоторыйалфавит из шестнадцати букв, где каждая ячейка дает нам m = 24 = 16
162 = 256
Мы наши шестнадцать буквделим на некоторое количество зон:
0000 4 0100 8 1000 1 0001 5 0101 9 1001 2 0010 6 0110 A 1100 3 0011 7 0111 B 1011 C 1100 D 1101 E 1110 F 1110
Для русского алфавитадостаточно 13 букв, распределенных по трем зонам.
0…С – имена букв
D…F – имена зон
С учетом вероятностипоявления букв друг с другом в тексте, таблица для русского алфавита выглядитследующим образом: D E F Space З Ц 1 О У Ж 2 Е Д Х 3 А Я Ч 4 Р Ь Э 5 П Ф Ю 6 Т Ы , 7 Н Щ . 8 В Ш ; 9 И Б : A С Г ! B М К ? C Л Й -
Сжатие определяетсянахождением букв в одной или в соседних зонах. И вероятность нахождения буквыгде-либо по отношению к другой букве:
а – вероятностьнахождения буквы в зоне D/> />
б – вероятность нахождениябуквы в зоне E
в – вероятностьнахождения буквы в зоне F
Каждая буква записываетсядвумя символами:
номер зоны
номер буквы
если рядом стоящие буквыпопадают в одну зону, то номер зоны пишется только один раз, а буквы чередуем.
/>
В некоторых случаях можноиспользовать сочетание из двух и более букв в таблице, разделенные по зонам,принцип разделения можно оставить тем же.
Любой из перечисленныхметодов сжатия используется тогда, когда он дает максимальный эффект, которыйопределяется величиной коэффициента сжатия или объемом сэкономленной памяти.
3. Выбор и обоснованиерешения задачи
4. Теоретическоеобоснование метода Лавинского
Данный метод предполагаетсжатие последовательности чисел путём разбиения последовательности наравномерные интервалы и отыскание числа не в его натуральном виде путемперебора всех подряд, а с помощью порядкового номера отсчета от ближайшейграницы.
Сам метод состоит вследующем. Пусть имеем некоторое количество чисел М и максимальное по длинечисло L. Очевидно, что для хранения в натуральном виде этих чисел необходимоследующее количество ячеек
Q = M * log 2 L (1)
Лавинский предложилмножество М разбить на N интервалов. Интервалы между собой равные и тогдаочевидно, что для хранения самих чисел необходим следующий объем памяти
Q’ = M * log 2 (L / N) (2)
И нам необходимо хранитьинформацию об этих самых границах
Q” = (M – 1) * log 2 (N — 1) (3)
В целом объем памятинеобходимый для самих чисел и памяти будет следующим
Q = Q’ + Q” (4)
Взяв производную из (4),для нахождения оптимального разбиения последовательности и приравняв ее нулю,получим
N ОПТ = М / ln M (5)
Формула (5) определяет оптимальноеколичество интервалов. Для определения величины самого интервала мы всеколичество возможных вариантов относим к количеству самого интервала, то естьдля определения количества символов в интервале используем следующую формулу
C = 2 [log2 N] / N (6)
Для нахождения самогоинтервала (номер границы) используем следующее отношение
К = Х / С (7),
где Х – искомое число внатуральном виде.
После этого само числозаписывается, как порядковый отсчет этой границы и определяет экономию памятикак
D Q = QИСХ – QОПТ (8)
Пусть интервал 128, Х =200, тогда К = 1.56. К лежит 2> K> 1, значит код числа составит 200 – 127= 73.
/>5 Программная реализация
Для разработки программыбыл выбран язык программирования высокого уровня Delphi 5.0 (Object Pascal).
Он весьма полно выражаетидеи структурного программирования. Это проявляется в том, что Delphi можетуспешно использоваться для записи программ на разных уровнях ее детализации, неприбегая к помощи блок-схем или специального языка проектирования программ.Средства языка Delphi позволяют осуществлять достаточный контроль правильностииспользования данных различных типов и программных объектов как на этапетрансляции, так и на этапе ее выполнения.
Delphi позволяет безособых трудностей реализовать удобный пользовательский интерфейс, не пребегая кнаписанию низкоуровневого кода.
В программе есть так жевозможность считать данные для кодирования из файла.
Заключение
В ходе выполнениякурсовой работы были закреплены знания, полученные в ходе изучения дисциплины«Кодирование и защита информации». Работа выполнена в соответствии спостановкой задачи на курсовое проектирование.
Для проверкиработоспособности программы и правильности обработки входных данных разработантестовый пример. Тестирование программы подтвердило, что программа правильновыполнила обработку данных и выдает верные результаты.
Библиографический список
Конспект лекций по дисциплине“Кодирование и защита информации”.
Березюк Н. Т., Андрющенко А. Г.,Мощинский С. С. и др. Кодирование информации – Харьков: Выща школа, 1978. – 252с.
Кузьмин И. В., Кедрус В. А. Основытеории информации и кодирования. – Киев: Выща школа, 1977. – 280 с.
Цымбал В. П. Теория информации икодирование. Киев, ”Вища школа”, 1997, 288 с.
Приложение А