Лабораторный практикум_1Мышеву2_отпр

УДК 519.711.4(076.5)

Мышев А.В. Лабораторный практикум по курсу «Теория кодирования информации». Обнинск: ИАТЭ НИЯУ МИФИ, 2010, - 33 с.

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

13 EMBED Equation.3 1415

Илл.5. Табл.7. Библиограф. 15 назв.
Рецензенты: к.ф.-м.н. В.А. Чепурко
с.н.с. В.Н. Яхрюшин



Темплан 2010, поз. 15




© ИАТЭ НИЯУ МИФИ, 2010 г.
© А.В. Мышев, 2010 г.

Введение

Основной целью лабораторного практикума является:
получение базовых знаний по методологии выполнения
лабораторных работ;
побуждение и развитие мотиваций к конструктивному и
фундаментальному освоению основ курса «Теория кодирования информации»;
информационный мониторинг по регламенту выполне-
ния лабораторных работ: возможные формы и объёмы выполнения лабораторных работ (индивидуальная, углубленная, обязательная); порядок их выполнения – контрольные точки и сроки сдачи; формы отчетности – оформление отчета и приём с экрана монитора;
описание примеров базовых алгоритмов для выполнения
лабораторных работ.

Лабораторный практикум» отражает общую схему, основные моменты при выполнении лабораторных работ, определение и выбор языка программирования и возможных программных приложений для разработки алгоритмов процедур компьютерных технологий кодирования информации и визуализации результатов анализа.13 EMBED Equation.3 1415
Лабораторные и практические занятия проводятся как индивидуальные лабораторные работы в соответствии с выбранной формой приобретения теоретических знаний и практических навыков по разработке и реализации компьютерного кодирования в каналах передачи и хранения в виде программных компонент и средств визуализации: отладки, тестирования, верификации и валидации программных компонент технологий кодирования и декодирования; восприятия обрабатываемой информации на основе технологий научной визуализации и интеллектуального анализа.
Возможные темы обязательных лабораторных работ и результаты выхода отражены в табл. 1.
В практикуме отражены основные сведения, которые необходимы для успешного и полноценного выполнения лабораторных работ. Так как в полном и «неопределенном» объёме всю информацию, с которой придется работать студенту, отразить и тем более разместить, в таком маленьком практикуме нельзя, то необходимо, что настоятельно и рекомендуется, самостоятельно изучить предложенную литературу и другие источники по теме изучаемой дисциплины и по другим дисциплинам учебного цикла. Структура и материал лабораторного практикума отражает всю необходимую информацию по методам, алгоритмам и способам кодирования и декодирования информации в каналах хранения и передачи, которыми необходимо пользоваться для выполнения лабораторных работ.
Цикл и регламент выполнения лабораторных работ включают в себя не только аудиторные занятия, но и самостоятельную подготовку по общему и индивидуальному планам. Общий план самостоятельной подготовки включает в себя изучение в рамках Госстандарта математического аппарата линейной алгебры и дискретной математики. Индивидуальный план предполагает разработку и реализацию каждым студентом программных компонент решения конкретной задачи в виде компьютерных технологии, не используя стандартные библиотеки или приложения для кодирования и декодирования информации.
Занятия по выполнению лабораторных работ в аудиториях кафедры и университета проводятся с консультативным и контрольным участием преподавателя.
Самостоятельная подготовка включает в себя изучение материала рекомендательного характера, выполнение индивидуальных заданий по курсу и более глубокое самостоятельное ознакомление с определенными темами, необходимыми для реализации индивидуального задания, а также самостоятельную работу с определенными темами (табл.2).


Таблица 1
Темы лабораторных работ и результаты выхода

Тема практического занятия
Количество часов

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

4

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

7

Технологии построения кодеров и декодеров информационных объектов на основе моделей дискретных каналов о помехах.
Выход: алгоритм и программный компонент компьютерной технологии помехоустойчивого кодирования в каналах передачи и хранения.

6


По курсу «Теория кодирования информации» на электронных носителях кафедры КССТ имеется следующая информация:
программа по курсу «Теория кодирования информации»
методические указания;
копии источников литературы по курсу;
лабораторный практикум;
варианты лабораторных работ.
Критериями выбора программной среды и средств, используемых в учебном процессе по данному курсу, являются, во-первых, обязательный практический уровень владения студентом техникой и технологией программирования и



Таблица 2
Темы для самостоятельной работы

Неделя
Тема
Форма контроля
Литература

1 - 3
Линейная алгебра и дискретная математика (линейные пространства и комбинаторика)
Тестирование по вопросам темы (преподавателем).
Ильин В.А., Поздняк Э.Г. Линейная алгебра , М.: Физматлит, 2002, - 320с.

3 - 8
Алгоритмы сжатия информации на основе префиксных методов кодирования
Контрольная работа по теме
Ватолин Д. и др. Методы сжатия данных. Устройство архиваторов, сжатие изображения и видео. М.:Диа- лог-МИФИ, 2002, - 381с.

8 - 12
Помехоустойчивое кодирование в технологиях виртуализации информационных каналов
Тестирование программного компонента кодера и декодера
Питерсон У. и др. Коды, исправляющие ошибки, М.: Мир, 1976, - 593 с.



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

Лабораторная работа №1

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

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

Общие требования

Критерий проверки. Студент должен знать языки программирования высокого и низкого уровней, и уметь владеть техникой и технологией программирования в объеме требований Госстандарта по соответствующим дисциплинам. Разработанный программный компонент должен реализовывать следующие функции:
ввод-вывод файловых структур с внешних устройств в ОЗУ и обратно, определенных и описанных в виде бинарных полей;
реализовать преобразования информационного объекта
на бинарном поле ОЗУ;
реализовать кодирование файла и его запись на внешнее
устройство;
реализовать декодирование файла и его запись на внеш-
нее устройство.
При этом студент должен приобрести следующие знания и навыки:
овладеть методами криптографической защиты инфор-
мации в каналах хранения и передачи;
приобрести навыки разработки алгоритмов процедур
технологий криптографической защиты в информационных каналах;
уметь разрабатывать и реализовывать программные
компоненты компьютерных технологий криптографической защиты информации;
освоить навыки анализа и оценки сложности защиты и
надежности продукта.

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

Структура и объем отчета. Отчет должен содержать, во-первых, программный компонент готового продукта согласно постановке задачи и варианту задания, во-вторых, листинга отчета. Структура листинга отчета включает в себя постановку задачи, описание используемых методов решения, описание алгоритмов программных компонентов, результат расчетов и анализа, графики и таблицы, выводы, приложения и др.
Сроки представления - в течение первого месяца.
Литература
Мышев А.В. Основы прикладной теории кодирования
информации. Учеб. пособие по курсу «Теории кодирования информации». – Обнинск, ИАТЭ, 1999, - 77с.
Самсонов Б.Б. и др. Теория информации и кодирования.
– Ростов-на-Дону, Феникс, 2002, - 288с.
Электронные копии лекций, методичек и др. на накопи-
телях сервера кафедры.

Приложение 1

Основные понятия и определения

Бит – базовая единица измерения информации в каналах хранения и передачи, имеющая в них соответственно логические и физические прототипы.
Логическим прототипом бита является символическое обозначение его образа, т.е. множество символов базового алфавита, в физической среде информационного канала. Например, для булевой логики – это ноль и единица, символические образы которых определяются символами 0 и 1.
Физическими прототипами бита в каналах хранения являются физические состояния элементов среды хранения, а в каналах передачи - сигналы определенной длительности и уровня. Например, в полупроводниковом ОЗУ физическим прототипом бита будет триггер, состояние которого (напряжение на выходе) будут соответствовать его логическим прототипам 0 и 1; в НМД (накопитель на магнитном диске) это область на поверхности диска, намагниченность которой будет соответствовать логическим прототипам 0 и 1. Аналогично и на других накопителях информации с другой физической средой.
Бинарное информационное множество – это множество элементов базового алфавита, образующих логическую структуру в виде сегмента памяти в физической среде канала хранения или поток логически и функционально связанных данных в канале передачи.
В каналах передачи и хранения любой информационный объект (файлы и другие логические структуры) рассматриваются как бинарные информационные множества, на которых определяются информационные пространства, задаваемые в виде кортежа <Х,Nm>, где Х - множество символьных цепочек алфавита Nm, который представляет собой множество бинарных цепочек длиной m битов.
Информационное пространство в виде кортежа <Х,Nm> является математической моделью информационного объекта, определенного как бинарное множество. Тогда вероятностно-статистической характеристикой информационного объекта (IO) в <Х,Nm> для заданного алфавита Nm будет таблица информационной насыщенности IO, которая представляет собой дискретное распределение вероятностей букв Nm в IO.
В качестве количественной меры информации IO используем следующие оценки. Во-первых, шенноновское определение энтропии, которое задается в виде выражения
In = -13 EMBED Equation.3 1415 , (1.1)
где pi – это вероятность появления i-ой буквы алфавита Nm в информационном объекте IO, |М| - мощность алфавита Nm .
Во-вторых, В – энтропия, которая в отличии от шенноновской определена на метрическом вероятностном пространстве и задается следующим выражением:
13 EMBED Equation.3 1415 (1.2)13 EMBED Equation.3 1415
013 EMBED Equation.3 1415
·ij13 EMBED Equation.3 14151 - рандомизированная мера на метрическом вероятностном пространстве, которая определяется выражением (хотя можно использовать множество и других)

·ij = | pij- pj | (1.3)
Количественная характеристика информации на основе В – энтропии отражает степень насыщенности IO буквами Nm с учетом их близости по вероятности, т.е. она позволяет оценить «информационную геометрию» IO.
Под количественной мерой неопределенности представления информационного объекта IO фиксированной длины, определенного на <Х,Nm>, понимается ансамбль, порождаемый IO на <Х,Nm>. Ансамбль в этом случае представляет собой дискретное распределение вероятностей возможного представления IO элементами его таблицы информационной насыщенности. В качестве выражений для получения оценок количественной меры неопределенности используются также выражения (1.1) и (1.2), в которых pi -вероятность i-го представления IO в таблице возможных представлений, а М – это множество возможных представлений IO или объем таблицы представления. Поясним это на следующем примере.
Пусть задан IO из трех букв {abc}. Тогда таблица информационной насыщенности будет иметь следующий вид:
Буквы
pi

а
1/3

b
1/3

c
1/3


Количественные оценки информации имеют следующие значения (основание log3):
Iu=1; Bu=0 .
Таблица возможных представлений IO

Возможные представления

pi

abc
1/6

bac
1/6

cab
1/6

bca
1/6

acb
1/6

cba
1/6


Количественные оценки меры неопределенности представления будут иметь следующие значения (основание log3).
Iн=0,7746; Bн=0 .

Определение 1. Кодовым бинарным словом длины m называется цепочка из m битов.
Определение 2. Кодом называется множество кодовых слов.
Определение 3. Кодовое расстояние 13 EMBED Equation.3 1415(Ci,Ci+1) по Хеммингу между кодовыми словами Ci и Ci+1 определяется как количество позиций, в которых значения битов не совпадают.
Тогда в качестве интегральной характеристики IO можно использовать геометрическую информационную размерность, которая определяется следующим выражением:
df = 13 EMBED Equation.3 1415 (1.4)

где 13 EMBED Equation.3 1415= d(Ci, Ci+1) - кодовое расстояние между соседними словами Сi и Сi+1 , а 13 EMBED Equation.3 1415 - минимальное расстояние между парами соседних кодовых слов в IO.

Приложение 2

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

Основными критериями криптографической защиты являются оценки сложности построения алгоритмов схем декодирования и степени надежности защиты информационного объекта на бинарных полях в каналах хранения и передачи. Факторами, обеспечивающими высокие показатели таких критериев для методов криптозащиты на бинарных полях, являются факторы неопределенности, которые обусловлены построением (введением) моделей неопределенности в схемы и алгоритмы декодирования. Это связано с тем, что, определяя IО как бинарное поле, мы работаем с ним на физическом и виртуальном уровнях, а это придает таким технологиям информационной защиты особую уникальность, неповторимость и оригинальность, которые проявляются в том, что в модели алгоритмов и схем технологий хранения и передачи в информационных каналах вводятся эвристические и нетривиальные схемы и алгоритмы.
Для методов прямой подстановки Вижинера и других аналогичных словарных способов построения алгоритмов шифрования (дешифрования) эти особенности проявляются в том, что для входных и выходных алгоритмов при построении словарей используются различные конструкции. Словарь в компьютерных технологиях защиты представляет собой матрицу типа А(2,L), состоящую из двух строк: первая строка – это элементы входного алфавита, а вторая – выходного. Элементами строк являются бинарные цепочки как постоянной, так и переменной длины. Сложность построения алгоритмов декодирования в этом случае повышается за счет того, что «хакер» не знает схемы, по которой разрабатывать технологию взлома, а прямой перебор – это равносильно тому, что выпить море информации, а результат такого способа утоления жажды печален. Степень надежности и передачи повышается за счет того, что статистических закономерностей букв неизвестного алфавита и неидентифицированных букв нет. Здесь присутствуют факторы другого порядка.
Для построения алгоритмов компьютерных технологий защиты на основе методов преобразования на бинарных полях отмеченные факторы обязательно учитываются. Например, можно использовать линейные преобразования между кодовыми словами исходного IO и кодируемого. Пусть аi – кодовые слова исходного IO, а bi – кодируемого, тогда можно реализовать следующий алгоритм:

bi+1=
·11ai+1 +
·12ai+2 +
·13ai+3 ,
bi+2=
·21ai+1 +
·22ai+2 +
·23ai+3 (1.5)
bi+3=
·31ai+1 +
·32ai+2 +
·33ai+3 ,

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


ЛАБОРАТОРНАЯ РАБОТА №2

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

Цель работы – разработка и реализация компьютерных технологий сжатия информации на основе методов кодирования и способов виртуализации в каналах передачи и хранения в виде готового программного продукта, приобретение базовых знаний построения моделей алгоритмов и процедур программных компонент таких технологий, освоение навыков интеллектуального анализа информационных объектов на уровне их «физического и виртуального» представления, оценки эффективности и конкурентоспособности технологии продукта.
Этапы выполнения работы
Разработка моделей алгоритмов и процедур программного компонента сжатия информационного объекта (файлы и другие логические структуры) согласно заданию.
Реализация (см. лаб. раб.№1) программного интерфейса ввода-вывода файловых структур с внешних устройств (ВУ) в ОЗУ и обратно с учетом особенностей периферии.
Разработка логических схем моделей построения заголовков словарей и алгоритмы их реализации.
Реализация п.3 в виде элемента технологической цепочки общего программного компонента технологии сжатия.
Реализация алгоритмов программных компонент преобразования файлов на бинарных полях памяти.
Отладка программных компонент.
Тестирование и контрольные примеры.
Расчеты и анализ. Выводы.
Прием-сдача программного компонента в диалоговом режиме.

Общие требования

Критерии проверки. Студент должен знать языки программирования высокого уровня (это упростит разработку и реализацию проекта) и низкого уровня (это сделает продукт более эффективным), уметь владеть техникой программирования в объеме требований Госстандарта по соответствующим дисциплинам.
Разработанный программный компонент должен реализовывать следующие функции:
ввод-вывод файловых струкрур с ВУ в ОЗУ и обратно,
определенных и описанных, как бинарные объекты;
реализация преобразования информационного объекта в
виртуальном адресном пространстве бинарного поля ОЗУ;
реализация сжатия (архивации) файла и его запись на ВУ
реализация распаковки файла и его запись на ВУ;
реализация процедуры анализа файла на предмет опти-
мизации выбора параметров его сжатия и определения интегральных характеристик.

Отчетность. Разработанный и оттестированный программный компонент в виде готового продукта, который принимает преподаватель, ведущий занятия, а также листинг отчета.
Примечание. При сдаче-приеме проекта студент должен, во-первых, продемонстрировать работу программного компонента на тестовых примерах и исходных данных, которые задаются преподавателем; во-вторых, ответить на тестовые вопросы, квалифицированно сделать обоснование и анализ получаемых результатов.
Структура и объем отчета. Отчет должен содержать программный компонент готового продукта согласно постановке задачи и варианту задания, листинг отчета. Структура листинга отчета включает в себя: постановку задачи, описание используемых методов решения, описание алгоритмов программных компонентов, результат расчетов и анализа, графики и таблицы, выводы, приложения и др.
Сроки представления - в течение второго месяца.
Литература
Мышев А.В. Основы прикладной теории кодирования
информации. Учеб. пособие по курсу «Теории кодирования информации». – Обнинск, ИАТЭ, 1999, - 77с.
Мышев А.В. Модели активной памяти в технологиях
виртуализации каналов хранения и передачи информации // Программные системы и продукты, 2010, №1, - с.54-59.
Ватолин Д. и др. Методы сжатия данных. Устройство
архиваторов, сжатие изображения и видео. - М.: Диалог-МИФИ, 2002, - 384с.
Электронные копии лекций, методичек и др. на накопи-
телях сервера кафедры.

Приложение 1

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

Основной информационной и статистической характеристикой кодируемого (сжимаемого) объекта является таблица информационной насыщенности (см. лаб. работу №1).
Основным элементом в схеме алгоритма кодирования (сжатия) и декодирования (разсжатия) информационных объектов (файлов) как бинарного множества, на котором определено (задано) информационное пространство типа <Х, Nm> (см. лаб. работу №1), является словарь, представляющий собой матрицу типа А(2,L). Входной алфавит словаря задается элементами первой строки, которые представляют собой бинарные цепочки фиксированной длинны, а выходной алфавит – это элементы второй строки, определенные как бинарные цепочки переменной длины. Словарь в функциональной структуре программного компонента задается в виде сегмента памяти, который представляет собой логическую и структурированную область памяти, которую назовем заголовком. Поэтому разработка логической схемы заголовка является важным элементом в технологической цепочке построения кодера и декодера.
Основным моментом является построение модели алгоритма и процедуры формирования элементов выходного алфавита словаря. Здесь их необходимо рассматривать как виртуальные объекты и работать как с данными типа битовой строки, т.к. такой тип данных поддерживают все современные процессоры и любая среда (высокого и низкого уровней) программирования.

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

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

Знаки
Вероятности
Вспомогательные столбцы



1
2
3
4
5
6
7

Z1
0,22
0,22
0,22
0,26
0,32
0,42
0,58
1

Z2
0,2
0,20
0,20
0,22
0,26
0,32
0,42


Z3
0,16
0,16
0,16
0,20
0,22
0,26



Z4
0,16
0,16
0,16
0,16
0,20




Z5
0,1
0,10
0,16
0,16





Z6
0,1
0,10
0,10






Z7
0,04
0,06







Z8
0,02









Кодовое древо для формирования элементов выходного алфавита строится на основе матрицы вероятностей. Из точки (первый элемент последнего столбца), соответствующий вероятности 1, направляем две ветви, причем ветви с большей вероятностью присваиваем – 1, а с меньшей – 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до вероятности каждого элемента входного алфавита. На рис. 3.1 показана иллюстрация этого процесса.
После построения кодового древа, двигаясь сверху вниз записываем, (определяем) элементы выходного алфавита. Словарь будет иметь следующий вид, в котором символы Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8 первой строки обозначают буквы входного алфавита и соответствующие им бинарные цепочки фиксированной длины, а бинарные цепочки переменной длины во второй строке – это буквы выходного алфавита.


Z1
Z2
Z3
Z4
Z5
Z6
Z7
Z8

01
00
111
110
100
1011
10101
10100


13 EMBED Equation.3 1415

Рис.3.1.



Приложение 2

Методы эффективного кодирования
коррелированных цепочек символов

Метод l-грамм
Методы Шеннона-Фано и Хаффмена не учитывают корреляционные связи между символами, входящими в состав следующих друг за другом сочетаний. Естественно, они проявляются тем меньше, чем больше символов входит в каждое сочетание.
Отмеченный недостаток устраняется при кодировании по методу диаграмм триграмм или l - грамм. l - граммой называется сочетание l - символов входного алфавита в сообщении или тексте.
В процессе кодирования исходного информационного объекта (текста) l - грамма непрерывно (со сдвигом в один или более символов) перемещается по тексту сообщения:
первая l-грамма

a1 a2 a3 a4 . . .an

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

ЛАБОРАТОРНАЯ РАБОТА №3

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

Цель работы – разработка и реализация компьютерных технологий помехоустойчивого кодирования информации на основе синтеза традиционных методов избыточного кодирования и способов виртуализации каналов передачи и систем хранения в виде готового программного продукта; приобретение базовых знаний применения методов избыточного кодирования для создания моделей алгоритмов и процедур программных компонент таких технологий; освоение навыков применения теории кодов, исправляющих ошибки для решения практических задач защиты (физической и конфиденциальной) информации в каналах передачи и системах хранения на основе технологий виртуализации; освоение методологии анализа и оценки эффективности и степени надежности помехоустойчивой защиты разрабатываемой технологии.
Этапы выполнения работы
Разработка модели алгоритмов и процедур программ -
мных компонентов помехоустойчивого кодирования ин-формационного объекта в кодировании каналов передачи и хранения согласно схеме, определенной в задании.
Реализация (см. лаб. раб. №1 и №2) программного ин-
терфейса ввода - вывода файловых структур с ВУ в ОЗУ и обратно с учетом особенностей периферии.
Реализация моделей алгоритмов и процедур технологий
кодера и декодера на бинарных полях в виде программных компонент.
Разработка и реализация программного оконного диало-
гового интерфейса для ввода исходных данных, записи закодированного информационного объекта на ВУ и чтения в ОЗУ.
Отладка программных компонент.
Тестирование и контрольные примеры.
Расчеты и анализ. Выводы.
Прием-сдача программного компонента в диалоговом режиме.

Общие требования

Критерии проверки. Студент должен знать языки программирования высокого уровня (это упростит разработку и реализацию проекта) и низкого уровня (это сделает проект более эффективным), умение владеть техникой программирования в объеме требований Госстандарта по соответствующим дисциплинам.
Разработанный программный компонент должен реализовывать следующие функции:
ввод-вывод информации, имеющий организацию в виде
файловых структур, с ВУ в ОЗУ и обратно, который позволяет определить и описать ее тип, как бинарное поле или строка;
реализация преобразования информационного объекта в
виртуальном адресном пространстве бинарного поля ОЗУ;
реализация помехоустойчивого кодирования исходного
файла с его записью на ВУ индивидуального компьютера или передачей по сети;
реализация декодирования «запрещенного» объекта и
выявление возможных ошибок;
реализация процедуры оптимизации выбора параметров
с целью повышения надежности и эффективности помехоустойчивого кодирования;
реализация контроль правильности кодирования и деко
дирования по схеме кода.

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

Литература

Мышев А.В. Основы прикладной теории кодирования
информации. Учеб. пособие по курсу «Теории кодирования информации». – Обнинск, ИАТЭ, 1999, - 77с.
Мышев А.В. Модели активной памяти в технологиях
виртуализации каналов хранения и передачи информации // Программные системы и продукты, 2010, №1, - с.54-59.
Морелос - Сарагоса Р. Искусство помехоустойчивого
кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005г., - 320 с.
Электронные копии лекций, методичек и др. на накопи-
телях сервера кафедры.

Приложение 1

Кодирование для исправления ошибок: основные положения
Все коды, исправляющие ошибки, основаны на одной общей идее: для исправления ошибок, которые могут возникнуть в процессе передачи или хранения информации, к ней добавляется некоторая избыточность. По основной схеме, используемой на практике, избыточные символы дописываются за информационными, образуя кодовую последовательность или кодовое слово (codeword). На рисунке №1 показана геометрическая иллюстрация процедуры формирования блокового кода (bloch code). Такое кодирование называют систематическим (systematic).

Рис.1. Систематическое блоковое кодирование для исправления ошибок

Это означает, что информационные символы всегда появляются на первых k позициях кодового слова. Символы на оставшихся (n - k) позициях являются различными функциями от информационных символов, обеспечивающими тем самым избыточность, необходимую для обнаружения или исправления ошибок. Множество всех кодовых последовательностей называют кодом, исправляющим ошибки (error correcting code).

Приложение 2.

Корректирующая способность кода и его связь с кодовым расстоянием

Двоичный код С, представляющий собой множество 2n символьных последовательностей длины n исправляющий ошибки, если передает по информационному каналу не все возможные векторы, может обладать свойством помехоустойчивости. Код С является подмножеством n - мерного двоичного пространства R2 = {0,1}n таких, что его элементы максимально удалены друг от друга. В информационном пространстве V2 расстояние определяется как число позиций, в которых два вектора не совпадают. Пусть 13 EMBED Equation.3 14151 = (х1,0;х1,1;х1,n-1) и 13 EMBED Equation.3 14152 = (х2,0,х2,1,,х2,n-1) два вектора в V2, тогда хеммингово расстояние между векторами 13 EMBED Equation.3 14151 и 13 EMBED Equation.3 14152 , которое обозначим, как dx(x1,x2), равно

dx(x1,x2) = |{i:х1, i
·x2,i, 0
·i
·n}|, (1.1)

где через |A| обычно обозначают число элементов в множестве А.
Для кода С минимальное хеммингово расстояние dmin определяется, как минимум хеммингова расстояния по всем возможным парам различных кодовых слов:

dmin = min {dx (V1, V2)| V1
· V2 }. (1.2)
V1, V2 13 EMBED Equation.3 1415C

Пример. Простейшим примером является код повторения длины 3. Каждый информационный бит повторяется три раза. Таким образом, сообщение «0» кодируется вектором V1 =(000), а сообщение «1» - вектором V2 = (111). Так как два вектора различаются в трех позициях, то dx (V1,V2) =3. На рисунке №1 показано графическое представление этого кода. Трехмерное двоичное пространство соответствует 23=8 вершинам трехмерного единичного куба. Хеммингово расстояние между кодовыми словами V1 = (000) и V2 = (111) равно числу вершин, через которые проходит соединяющий их путь. Это эквивалентно числу координат, которые необходимо изменить, чтобы преобразовать V1 в V2 и наоборот. Таким образом, dmin = 3.
Двоичное векторное пространство V2 обычно называют хемминговым пространством. Пусть V - кодовое слово кода с Хемминговой сферой St(V) радиуса t с центром в точке V является множество векторов (точек) в V2 на расстоянии, меньшем или равном t от центра V.

St(V) ={x13 EMBED Equation.3 1415C| dx(x,V)
· t}. (1.3)

Следует заметить, что число слов в St(V) равно:

|St(V)| = 13 EMBED Equation.3 1415, (1.4)

где 13 EMBED Equation.3 141513 EMBED Equation.3 1415=13 EMBED Equation.3 1415Cni = 13 EMBED Equation.3 1415. (1.5)

Корректирующей способностью (error correcting capability) t кода С называют наибольший радиус хемминговой сферы St(V) для всех кодовых слов Vt
· C такой, что для любых различных пар Vi , Vj
· C соответствующие им хемминговы сферы не пересекаются, т.е.

13 EMBED Equation.3 1415t = max {l| Sl(Vi)13 EMBED Equation.3 1415 Sl(Vj) = 0, Vi
· Vj } (1.6)
Vi, Vj 13 EMBED Equation.3 1415l

Это соответствует более распространенному определению

t = [(dmin - 1)/2], (1.7)

где через [Х] обозначается целая часть Х, т.е. целое число меньше или равное х.
Отметим, что для определения минимального кодового расстояния произвольного кода С в соответствии с выражением (1.3) необходимо вычислить все 2k(2k-1) расстояний между различными парами кодовых слов. Это практически трудноразрешимая процедура даже для сравнительно коротких кодов.

Приложение 3

Порождающая и проверочная матрицы

Если С - двоичный линейный (n, k, dmin) код, который образует k - мерное подпространство, имеющее базис (V0,V1,,Vk-1) такой, что любое кодовое слово V13 EMBED Equation.3 1415C может быть выражено через базис:

V = U0V0 + U1V1 ++ Uk-1Vk-1, (1.8)

где Ui 13 EMBED Equation.3 1415 {0,1}, 0
· i
· k
Уравнение (1.8) может быть записано через породающую матрицу G и векторное сообщение U=(U0,U1,,Uk-1)

V=UG , (1.9)

где G = 13 EMBED Equation.3 1415=13 EMBED Equation.3 1415 (1.10)


Так как G является k - мерным векторным пространством в V2 , то существует 13 EMBED Equation.3 1415- мерное дуальное пространство (dual space) С
·, которое порождается строками матрицы Н, называемой проверочной матрицей (parity chech matrix), такой что GHT =0, где через HT обозначается транспонированная матрица Н. Следует заметить, что любое кодовое слово V13 EMBED Equation.3 1415C удовлетворяет условию

VHT =0. (1.11)

Уравнение (1.11) является фундаментальным для декодирования линейных кодов.
Линейный код С
·, который генерируется матрицей Н, является линейным (n, n-h, d
·min) кодом, который называется дуальным коду С.

Содержание


Введение 3
Лабораторная работа №1. Разработка и реализация программного компонента компьютерной технологии криптографической защиты файловых структур в каналах хранения и передачи. 7
Приложение 1. Основные понятия и определения. 9
Приложение 2. Особенности методов криптографической защиты информации на бинарных полях для каналов хранения и передачи. 13
ЛАБОРАТОРНАЯ РАБОТА №2. Разработка и реализация программного компонента компьютерной технологии сжатия файловых структур в каналах хранения и защиты. 14
Приложение 1. Некоторые инструкции и рекомендации для разработки компьютерных технологий сжатия на основе методов эффективного кодирования некоррелированных цепочек символов. 17

Приложение 2. Методы эффективного кодирования коррелированных цепочек символов. 21
ЛАБОРАТОРНАЯ РАБОТА №3. Разработка и реализация программного компонента компьютерной технологии помехоустойчивого кодирования каналах передачи и хранения. 22
Приложение 1. Кодирование для исправления ошибок: основные положения. 25
Приложение 2. Корректирующая способность кода и его связь с кодовым расстоянием. 26
Приложение 3. Порождающая и проверочная матрицы. 28









13PAGE 15


13PAGE 14615







Приложенные файлы

  • doc 23631546
    Размер файла: 428 kB Загрузок: 0

Добавить комментарий