Методические рекомендации для практических работ по учебной дисциплине ОП.12 Основы теории информации Специальности 09.02.06 Сетевое и системное администрирование

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА – Российский технологический университет» РТУ МИРЭА

Колледж приборостроения и информационных технологий

СОГЛАСОВАНО Заместитель директора по МР _______________ Е.В. Садыкова «___» ___________ 2021 г.

УТВЕРЖДАЮ Директор колледжа ПИТ _______________ О.В. Книга «___» ___________ 2021 г.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

для выполнения практических (лабораторных работ)

учебной дисциплины ОП.12 Основы теории информации

специальность 09.02.06 Сетевое и системное администрирование

Москва

2021

Одобрена Предметно-цикловой комиссией Сетевого администрирования и инфокоммуникационных систем Протокол № ________________ От «___» ____________ 202_ г. Председатель предметно-цикловой комиссии _________ А.В. Беседин подпись ФИО

Методические рекомендации разработаны в соответствии с рабочей программой учебной дисциплины, утвержденной директором колледжа (31.08.2021г)

Составитель:

Беседин Андрей Владимирович, преподаватель

Колледжа приборостроения и информационных технологий

ПЕРЕЧЕНЬ

лабораторных/практических работ по учебной дисциплине

общепрофессионального цикла

ОП.12 Основы теории информации

по специальности 09.02.06 Сетевое и системное администрирование

для студентов 2 курса

на 2021-2022 учебный год

№ п/п	Название ПР	Количество часов
1	Способы хранения обработки и передачи информации.	2
2	Измерение количества информации.	4
3	Вероятностный подход к измерению дискретной и непрерывной информации.	4
4	Применение теоремы отчетов.	4
5	Интерполяционная формула Уиттекера-Шеннона, частота Найквиста.	4
6	Энтропийное кодирование.	4
7	Практическое применение различных алгоритмов сжатия. Сравнение и анализ архиваторов. Кодирование Хаффмана.	4
8	Адаптивное арифметическое кодирование.	4
9	Практическое применение криптографии. Изучение и сравнительный анализ методов шифрования.	2

Составил преподаватель Беседин А.В.

Дата____________________

Подпись________________

ПРАКТИЧЕСКАЯ РАБОТА № 1

Тема: Способы хранения обработки и передачи информации.

Цель:

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

Задачи:

1. Ознакомиться с теоретической частью;

2. Обработать, сохранить и передать данные при помощи технических средств информации;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

1. Технологии сбора и хранения информации

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

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

Рисунок 1.1 - Технические средства, позволяющие осуществлять сбор информации

1. Технологический процесс обработки информации

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

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

• характер и сложность решаемой задачи;

• алгоритм преобразования информации;

• используемые технические средства;

• сроки обработки данных;

• используемые системы контроля;

• число пользователей и т. д.

В общем случае технологический процесс обработки информации включает процедуры, представление на рисунке 1.2.

Рисунок 1.2 – Процедуры технологического процесса обработки информации

1. Способы обработки информации

Современные информационные технологии позволяют обрабатывать информацию централизованным и децентрализованным (т. е. распределенным) способами.

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

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

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

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

1. Режимы обработки информации на компьютере

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

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

Задачи, решаемые в пакетном режиме, характеризуются следующими свойствами:

• алгоритм решения задачи формализован, вмешательства пользователя не требуется;

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

• расчет выполняется для большинства записей входных файлов;

• длительное время решения задачи — как правило, обусловлено большими объемами обрабатываемых данных;

• регламентность — задачи решаются с заданной периодичностью.

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

1. Технологии передачи и представления информации

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

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

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

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

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

Для представления переданной или хранимой информации потребителю используются процессы воспроизведения и отображения.

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

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

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

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

Прежде чем, например, на мониторе, появится информация в доступной для человека форме, компьютером будет автоматически осуществлена следующая последовательность операций:

• преобразование данных, представленных в машинной форме, в вид, приемлемый для экранного отображения;

• согласование формы представления данных с параметрами монитора;

• воспроизведение в соответствии с возможностями воспроизводящего устройства (т. е. в данном примере — монитора).

Порядок выполнения практической работы:

1. Создание досье группы. Заранее заготовить материал: фотографии, текст.

2. Сфотографировать своих однокурсников.

3. Включить компьютер.

4. Создать общую папку на сервере.

5. Сканировать фотографии и сохранить в общую папку.

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

7. Оформить каждый лист на одного человека. Записать данные: дата рождения, номер школы, хобби.

8. Сохранить данные на жесткий диск в свою папку под именем досье группы.

9. Ответить на контрольные вопросы.

10. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Что такое сбор информации и каково его предназначение?

2. Что понимается под технологией сбора информации?

3. Чем отличаются понятия «информация» и «данные»?

4. Назовите основные требования к сбору данных и к хранимым данным.

5. Перечислите основные средства сбора текстовой, графической, звуковой и видеоинформации. Какие еще средства сбора информации вам известны?

6. Какие еще методы сбора данных вам известны?

7. В чем заключается процедура хранения информации?

8. Перечислите основные требования к структурам хранения.

9. Что такое база данных?

10. В чем различие между базой и банком данных?

11. Что такое резервное копирование и для чего оно осуществляется?

12. Что такое архивное копирование и в чем его отличие от резервного копирования?

13. Что такое базовая информационная технология?

14. В чем заключается различие между централизованным и децентрализованным способами обработки информации?

15. Какие режимы обработки информации вам известны?

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Способы обработки, сохранения и передачи данные при помощи технических средств информации.	1. Строить структуры подразделений объекта защиты. 2. Обработать, сохранить и передать данные при помощи технических средств информации.

ПРАКТИЧЕСКАЯ РАБОТА № 2

Тема: Измерение количества информации.

Цель:

Научиться измерять и вычислять информацию, а также и работать с носителями информации.

Задачи:

1. Ознакомиться с теоретической частью;

2. Решить задачи на измерение и вычисление количества информации;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

1 байт = 8 битов.

Существуют еще более крупные единицы измерения информации. Переход к более крупным единицам измерения информации (килобайт, мегабайт, терабайт, петабайт, эксабайт). Байт наиболее удобная единица измерения информационного объема сообщения, состоящего из последовательности символов компьютерного алфавита. Однако она мала при подсчете емкости информационных носителей. По аналогии с физическими единицами измерения (например, 1 килограмм = 1000 грамм) подбираем по таблице целых степеней двойки значение близкое к тысячи. Это значение равно 1024. Поэтому:

• 1 Кбайт (один килобайт) = 1024 байт;

• 1 Мбайт (один мегабайт) = 1024 Кбайт;

• 1 Гбайт (один гигабайт) = 1024 Мбайт.

Что представляют единицы измерения:

• 5 бит – буква в клетке кроссворда;

• 1 байт – символ, введенный с клавиатуры;

• 6 байт – средний размер слова, в тексте на русском языке;

• 50 байт – строка текста;

• 2 Кбайта – страница машинописного текста;

• 100 Кбайт – фотография в низком разрешении;

• 1 Мбайт – небольшая художественная книга;

• 100 Мбайт – метровая книга с полками;

• 1 Гбайт – прочитывает человек за всю жизнь;

• 3 Гбайт – час качественной видеозаписи.

Для сохранения информации используют носители информации: флэш-накопители, флэш-карты, диски разных форматов, съемные жесткие диски.

Содержательный (вероятностный) подход к определению количества информации.

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

1 бит – количество информации, которое содержится в сообщении, которое уменьшает неопределённость знаний в 2 раза.

Пример 1. При бросании монеты возможны 2 события (случая) – монета упадёт орлом или решкой, причём оба события равновероятны (при большом количестве бросаний количество случаев падения монеты орлом и решкой одинаковы). После получения сообщения о результате падения монеты неопределённость знаний уменьшилась в 2 раза, и, поэтому, количество информации, полученное при этом равно 1 бит.

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

Единицы измерения информации. Перевод единиц измерения.

1 бит – количество информации, которое содержится в сообщении, которое уменьшает неопределённость знаний в 2 раза.

1 бит – наименьшая единица информации. Более крупные единицы – байт, килобайт, мегабайт, гигабайт.

Система единиц измерения информации:

• 1 байт = 8 бит;

• 1 Кбайт = 210 байт = 1024 байт;

• 1 Мбайт = 210 Кбайт = 1024 Кбайт = 220 байт;

• 1 Гбайт = 210 Мбайт = 1024 Мбайт = 220 кбайт = 230 байт.

Информационный объём носителей информации:

• Дискета – 1,44 Мбайт; компакт-диск  700 Мбайт;

• DVD-диск – до 17 Гбайт (стандарт – 4,7 Гбайт);

• жёсткий диск – от 20 Гбайт до 80 Гбайт и более (стандарт 80 Гбайт);

• Flash-память – 256 Мбайт – 2 Гбайт.

Примеры перевода единиц:

1) 5 байт = 5 * 8 бит = 40 бит;

2) 24 бита = 24*8 байта = 3 байта;

3) 4 Кбайт = 4 * 1024 байт = 4096 байт;

4) 16384 бита = 16384 : 8 байт = 2048 байт;

1. 2048 байт : 1024 = 2 Кбайта.

Вычисление количества информации для равновероятных событий.

Если события равновероятны, то количество информации можно рассчитать по формуле

N = 2I,

(2.1)

где N – число возможных событий,

I – количество информации в битах.

Формула была предложена американским инженером Р. Хартли в 1928 г.

Вычисление количества информации для событий с различными вероятностями.

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

1. В коробке 20 карандашей, из них 15 красных и 5 чёрных. Вероятность вытащить наугад красный карандаш больше, чем чёрный.

2. При случайном падении бутерброда вероятность падения его маслом вниз (более тяжёлой стороной) больше, чем маслом вверх.

3. В пруду живут 8000 карасей, 2000 щук и 40000 пескарей. Самая большая вероятность для рыбака – поймать в этом пруду пескаря, на втором месте – карася, на третьем – щуку.

Количество информации в сообщении о некотором событии зависит от его вероятности. Чем меньше вероятность события, тем больше информации оно несёт.

P = K/N,

(2.2)

где К – количество случаев реализации одного из исходов события,

N – общее число возможных исходов одного из событий

2I = log2(1/p),

(2.3)

где I – количество информации,

p – вероятность события.

Что такое логарифм?

Логарифмом числа а по основанию b называется показатель степени, в которую надо возвести число a, чтобы получить число b.

alogab = b, a 0, b 0, a ≠ 1

(2.4)

Вычисление логарифмов чисел по основанию 2 с помощью электронного калькулятора

log26 = log6 / log2,

(2.5)

где log6 и log2 – десятичные логарифмы.

Программа вычисления логарифма числа 6 по основанию 2 ( log₂6 ) с помощью инженерного калькулятора: 6, log, / , 2, log, =.

Количество информации в случае различных вероятностей событий определяется по формуле Шеннона (американский учёный, 1948 г.)

(2.6)

где Pi – вероятность i-го события, N – количество возможных событий.

Порядок выполнения практической работы:

1. Решите следующие задачи:

Задача 1. В коробке 32 карандаша, все карандаши разного цвета. Наугад вытащили красный. Какое количество информации при этом было получено?

Задача 2. В школьной библиотеке 16 стеллажей с книгами, на каждом – по 8 полок. Ученику сообщили, что нужный учебник находится на 2-ой полке 4-го стеллажа. Какое количество информации получил ученик?

Задача 3. Загадывают число в диапазоне от 1 до 200. Какое наименьшее количество вопросов надо задать, чтобы наверняка отгадать число. На вопросы можно отвечать только «Да» или «Нет».

Задача 4. В коробке 50 шаров, из них 40 белых и 10 чёрных. Определить количество информации в сообщении о вытаскивании наугад белого шара и чёрного шара.

Задача 5. В озере живут караси и окуни. Подсчитано, что карасей 1500, а окуней - 500. Сколько информации содержится в сообщениях о том, что рыбак поймал карася, окуня, поймал рыбу?

1. Ответить на контрольные вопросы.

2. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Какое количество информации несет в себе жесткий диск емкостью 4 терабайта, если производитель рассчитывает 1000 за 1024?

2. Чем отличается вероятностный подход к измерению информации от алфавитного?

3. Какие единицы измерения информации используют для флэш-накопителей?

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Формулы для измерения количества информации	Применять на практике формулы для измерения количества информации

ПРАКТИЧЕСКАЯ РАБОТА № 3

Тема: Вероятностный подход к измерению дискретной и непрерывной информации.

Цель:

Научиться вычислять вероятности событий (появление символов в сообщении), рассчитывать энтропию и избыточность.

Задачи:

1. Ознакомиться с теоретической частью;

2. Вычисление вероятности событий (появление символов в сообщении), расчёт энтропии и избыточности;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

Количество информации по Хартли и Шеннону

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

При этом наложено ряд ограничений:

1. Рассматриваются только дискретные сообщения.

2. Множество различных сообщений конечно.

3. Символы, составляющие сообщения равновероятны и независимы.

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

I=log mk=log N

(3.1)

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

P=1/N.

(3.2)

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

I=logP.

(3.3)

В силу статистической независимости символов, вероятность сообщения длиной в k символов равна

,

(3.4)

где p_i - количество определённого символа.

Если iй символ повторяется в данном сообщении k_i раз, то

,

(3.5)

так как при повторении i символа k_i раз k уменьшается до m. Из теории вероятностей известно, что, при достаточно длинных сообщениях (большое число символов k) k_i ≈ k * p_i и тогда вероятность сообщений будет равняться

.

(3.6)

Тогда окончательно получим

.

(3.7)

Данное выражение называется формулой Шеннона для определения количества информации.

Формула Шеннона для количества информации на отдельный символ сообщения совпадает с энтропией. Тогда количество информации сообщения, состоящего из k символов будет равняться

I = K * H,

(3.8)

где K - общее количество букв и символов в сообщении.

Количество информации, как мера снятой неопределенности.

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

Количество информации, приобретаемое при полном выяснении состояния некоторой физической системы, равно энтропии этой системы

(3.9)

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

.

(3.10)

Избыточность информации

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

Энтропия реальных сообщений H_р рассчитывается по формуле

 ,

(3.11)

где N — количество символов в используемом алфавите (мощность алфавита).

Энтропия оптимальных сообщений  H_о рассчитывается по формуле

 ,

(3.12)

Допустим, нужно передать сообщение, содержащее количество информации, равное I. Источнику, обладающему энтропией на букву, равной H_р, придется затратить некоторое число n_р, то есть

.

(3.13)

Если энтропия источника была бы Н₀, то пришлось бы затратить меньше букв на передачу этого же количества информации

I= n0 * H0, .

(3.14) (3.15)

Таким образом, часть букв n_р  n_о являются как бы лишними, избыточными. Мера удлинения реальных сообщений по сравнению с оптимально закодированными и представляет собой избыточность D.

(3.16)

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

Частотные характеристики текстовых сообщений

Важными характеристиками текста являются повторяемость букв, пар букв (биграмм) и вообще m-ок (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных, и некоторые другие. Замечательно, что эти характеристики являются достаточно устойчивыми.

Идея состоит в подсчете чисел вхождений каждой n^m возможных m-грамм в достаточно длинных открытых текстах T=t₁t₂…t_l, составленных из букв алфавита {a₁, a₂, ..., a_n}. При этом просматриваются подряд идущие m-граммы текста

t1t2...tm, t2t3... tm+1, ..., ti-m+1tl-m+2...tl.

(3.17)

Если – число появлений m-граммы a_i1a_i2...a_im в тексте T, а L общее число подсчитанных m-грамм, то опыт показывает, что при достаточно больших L частоты

(3.18)

для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (a_i1a_i2...a_im) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

Для русского языка частоты (в порядке убывания) знаков алфавита, в котором отождествлены E c Ё, Ь с Ъ, а также имеется знак пробела (-) между словами, приведены в таблице 3.1.

Таблица 3.1 - Частоты (в порядке убывания) знаков алфавита.

- 0.175 О 0.090 Е, Ё 0.072 А 0.062 И 0.062 Т 0.053 Н 0.053 С 0.045 Р 0.040 В 0.038 Л 0.035

К 0.028 М 0.026 Д 0.025 П 0.023 У 0.021 Я 0.018 Ы 0.016 З 0.016 Ь, Ъ 0.014 Б 0.014 Г 0.013

Ч 0.012 Й 0.010 Х 0.009 Ж 0.007 Ю 0.006 Ш 0.006 Ц 0.004 Щ 0.003 Э 0.003 Ф 0.002

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

Порядок выполнения практической работы:

1. Необходимо написать следующее сообщение.

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

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

По формуле

X=pi/K,

(3.19)

где K - общее количество букв и символов в сообщении,

p_i - количество определённого символа.

3. Далее по формуле Шеннона (3.9) вычислите количество информации в передаваемом сообщении.

1. Вычислите энтропию реальных сообщений H_р по формуле 3.11 и энтропию оптимальных сообщений  H_о по формуле 3.12.

2. Вычислите избыточность D по формуле 3.16.

3. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Дать определение понятие энтропия?

2. Что означает вероятностный способ измерения информации?

3. Что означает статическое определение вероятности?

4. Запишите уравнение Хартли?

5. Какие основные разработки внес в основу теории информации Шеннон?

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Формулы Хартли и Шеннона. 3. Вычисление вероятности событий (появление символов в сообщении). 4. Расчёт энтропии и избыточности.	1. Вычислять вероятности событий (появление символов в сообщении), рассчитывать энтропию и избыточность.

ПРАКТИЧЕСКАЯ РАБОТА № 4

Тема: Применение теоремы отчетов.

Цель:

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

Задачи:

1. Ознакомиться с теоретической частью;

2. Изучение возможности синтезирования сигналов по дискретным отсчетам в соответствии с теоремой Котельникова;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

Теорема Котельникова

В 1933 году В. А. Котельниковым доказана теорема отсчетов, имеющая важное значение в теории связи: непрерывный сигнал с ограниченным спектром можно точно восстановить (интерполировать) по его отсчетам , взятым через интервалы , где – верхняя частота спектра сигнала.

В соответствии с этой теоремой сигнал можно представить рядом Котельникова

(4.1)

Таким образом, сигнал , можно абсолютно точно представить с помощью последовательности отсчетов , заданных в дискретных точках , как показано на рисунке 4.1.

Рисунок 4.1 – Сигнал и его отсчеты

Функции

(4.2)

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

(4.3)

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

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

Функция вида

(4.4)

называется функцией отсчетов, график показан на рисунке 4.2.

Рисунок 4.2 – Функция отсчетов

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

На основании теоремы Котельникова может быть предложен следующий способ дискретной передачи непрерывных сигналов:

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

,( ).

(4.5)

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

Можно показать, что энергия сигнала находится по формуле

(4.6)

Для сигнала, ограниченного во времени, данное выражение преобразуется к виду

(4.7)

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

Порядок выполнения практической работы:

1. Изобразить сигналы, синтезируемые в практической работе:

а) синусоидальный сигнал частотой 5кГц;

б) видеоимпульсы прямоугольной формы длительностью 0,25; 0,5; 1,0 мс;

в) видеоимпульсы пилообразной формы длительностью 0,5 мс; 1,0 мс.

2. Рассчитать и построить идеальные выборочные сигналы для сигналов, указанных в п. 1а, 1б, 1в, при f_выб=5, 10, 20, 40 кГц.

3. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Сформулируйте теорему Котельникова для сигналов с ограниченным спектром.

2. Объясните погрешности синтезирования реальных сигналов по дискретным отсчетам.

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Построение синусоидальных сигналов, видеоимпульсов прямоугольной формы, видеоимпульсов пилообразной формы.	1. Строить синусоидальные сигналы, видеоимпульсы прямоугольной формы, видеоимпульсы пилообразной формы. 2. Рассчитать и строить идеальные выборочные сигналы для сигналов.

ПРАКТИЧЕСКАЯ РАБОТА № 5

Тема: Интерполяционная формула Уиттекера-Шеннона, частота Найквиста.

Цель:

Научиться выполнять расчеты по теореме отчетов и определять пропускную способность дискретного канала.

Задачи:

1. Ознакомиться с теоретической частью;

2. Выполнить расчеты по теореме отчетов;

3. Определить пропускную способность дискретного канала;

4. Оформить отчет о выполнении практической работы.

Теоретическая справка:

Пусть на вход аналогово-цифрового преобразователя поступает гармонический сигнал с частотой f (период T = 1/f). Частоты исходного сигнала

Проведем дискретизацию входного аналогового сигнала с периодом дискретизации T_д меньшим половины периода входного сигнала T (рисунок 5.1).

Рисунок 5.1 – Дискретизация входного аналогового сигнала

Очевидно, что дискретные отсчеты сигнала однозначно не отображают форму исходного сигнала, в частности по получившимся точкам можно построить гармонический сигнал с периодом T_искаж., отличающимся от периода исходного сигнала T. Период T_искаж больше периода исходного сигнала T, соответственно частота меньше, частоты исходного сигнала f (рисунок 5.2).

Рисунок 5.2 – Сравнение частот

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

Пример 2

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

Рисунок 5.3 - Отсчеты сигнала равные нулю

Пример 3

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

Рисунок 5.4 - Гармонический сигнал, соответствующий исходному

Таким образом, для адекватного восстановления гармонического сигнала по дискретным отсчетам, частота дискретизации должна быть не меньше половины частоты сигнала. Частота равная половине частоты дискретизации называется частотой Найквиста f_N = f_Д/2.

Данное утверждение можно обобщить следующим образом:

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

fд 2·Fmax .

(5.1)

Данное утверждение известно как теорема Котельникова (в западной литературе теорема Найквиста-Шеннона) или теорема отсчетов. В различных источниках в формулировке данной теоремы могут быть различия, основным из которых является знак сравнения в формуле 1: fд ≥ 2·F_max или fд 2·F_max. Мы придерживаемся формулировки со знаком строго больше, так как при частоте оцифровки равной максимальной частоте в спектре возникают неоднозначности начальной фазы и амплитуды.

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

Пропускная способность непрерывного канала

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

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

,

(5.2)

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

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

.

(5.3)

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

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

.

(5.4)

График отношения

(5.5)

изображен на рисунке 5.5. Заметим, что при малом отношении

, ,

(5.6)

а пропускная способность канала связи прямо пропорциональна этому отношению.

Рисунок 5.5 – Пропускная способность непрерывного канала

При большом отношении в формуле (5.4) можно пренебречь единицей и считать, что

,

(5.7)

т.е. зависимость пропускной способности непрерывного канала от отношения сигнал/шум логарифмическая.

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

Определим пропускную способность стандартного канала тональной частоты, имеющего границы эффективно передаваемых частот кГц, среднюю мощность сигнала на выходе 56 мкВт при средней мощности помехи 69000 пВт.

Согласно формулы (5.4), при заданных параметрах

, [бит/с].

(5.8)

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

Для типовых непрерывных каналов многоканальной связи основные технические характеристики и пропускная способность, вычисленная по формуле Шеннона (5.4), при отношении сигнал/шум 20 дБ, приведены в таблице 5.1.

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

Таблица 5.1 - Характеристики типовых каналов многоканальной связи.

Таблица 5.2 - Производительность источников сообщений.

Например, первичный сигнал телевизионного вещания имеет вид

(5.9)

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

Порядок выполнения практической работы:

1. Число символов алфавита m = 4. Вероятности появления символов равны соответственно p1 = 0,15; p2 = 0,4; p3 = 0,25; p4 = 0,2. Длительности символов t1 = 3с; t2 = 2с; t3 = 5с, t4 = 6с. Чему равна скорость передачи сообщений, составленных из таких символов?

2. Сообщения составлены из пяти качественных признаков (m = 5). Длительность элементарной посылки t = 20мс. Определить, чему равна скорость передачи сигналов и информации.

3. Определить пропускную способность бинарного канала связи, способного передавать 100 символов 0 или 1 в единицу времени, причем каждый из символов искажается (заменяется противоположным) с вероятностью р = 0,01.

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

5. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Что такое пропускная способность канала передачи информации? Чем отличается пропускная способность от скорости передачи информации по каналу связи?

2. Чем отличается информационная скорость передачи от технической, и в каких единицах эти скорости измеряются?

3. Как изменяется пропускная способность дискретного канала связи при воздействии на канал помех.

4. Сформулируйте основную теорему Шеннона о кодировании для канала без помех.

5. Сформулируйте и поясните теорему Шеннона о кодировании для канала с помехами.

6. Приведите выражение пропускной способности для дискретного канала без помех и с помехами.

7. Сформулируйте и поясните теорему отсчетов (Котельникова)

8. Какие параметры влияют на объем сигнала.

9. От чего зависит пропускная способность непрерывного канала связи.

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

11. Какова скорость отображения информации приемным устройством отображения информации.

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Теорему отчетов. 3. Определение пропускной способности дискретного канала.	1. Выполнять расчеты по теореме отчетов. 2. Определять пропускную способность дискретного канала.

ПРАКТИЧЕСКАЯ РАБОТА № 6

Тема: Энтропийное кодирование.

Цель:

Научиться вычислять энтропию случайной величины.

Задачи:

1. Ознакомиться с теоретической частью;

2. Вычислить энтропию случайной величины;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

Энтропия в теории информации — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Так, возьмём, например, последовательность символов, составляющих какое-либо предложение на русском языке. Каждый символ появляется с разной частотой, следовательно, неопределённость появления для некоторых символов больше, чем для других. Если же учесть, что некоторые сочетания символов встречаются очень редко, то неопределённость ещё более уменьшается (в этом случае говорят об энтропии n-ого порядка. Концепции информации и энтропии имеют глубокие связи друг с другом, но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу.

Энтропия независимых случайных событий x с n возможными состояниями (от 1 до n) рассчитывается по формуле

.

(6.1)

Эта величина также называетсясредней энтропией сообщения. Величина называется частной энтропией, характеризующей только i-e состояние.

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

Шеннон вывел это определение энтропии из следующих предположений:

• мера должна быть непрерывной; т. е. изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение энтропии;

• в случае, когда все варианты (буквы в приведенном примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать полную энтропию;

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

Шеннон показал, что любое определение энтропии, удовлетворяющее этим предположениям, должно быть в форме

,

(6.2)

где K — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (H = − p₁ log₂ p₁ − … − p_n log₂ p_n), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надежной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидания «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д.

В общем случае b-арная энтропия (где b равно 2,3,... ) источника = (S, P) с исходным алфавитом S = {a₁, …, a_n} и дискретным распределением вероятности P = {p₁, …, p_n} где p_i является вероятностью a_i (p_i = p(a_i)) определяется формулой

.

(6.3)

Определение энтропии Шеннона очень связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между понятиями энтропии в термодинамике и теории информации. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

СВОЙСТВА ЭНТРОПИИ

1.Энтропия является вещественной и неотрицательной величиной.

2.Энтропия – величина ограниченная.

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

4.Энтропия максимальна, когда все состояния источника равновероятны.

5. Энтропия источника и с двумя состояниями u1 и u2 изменяется от нуля до единицы, достигая максимума при равенстве их вероятностей

р(и1) = р= р(u2) = 1 — р = 0,5.

(6.4)

6.Энтропия объединения нескольких статистически независимых источников информации равна сумме энтропии исходных источников.

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

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

Дифференциальной энтропией случайной величины X называется величина

HД(x)=H(x)-H(y)= -

(6.5)

Если произвести квантование случайных величин Х₁, Х₂…Х_n по уровню с числом уровней квантования равным m , то возможное число реализаций длительностью Т_n станет конечным и равным М = тⁿ.

Каждая из реализаций С₁, С₂,….С_i,…С_m будет иметь определенную вероятность появления в эксперименте по наблюдению реализаций. Тогда неопределенность (энтропия) и количество информации в реализации (в среднем по всем реализациям) определяются равенством

,	(6.6)
	(6.7)

Энтропия и количество информации на одну степень свободы (на одну выборку) равны

.

(6.8)

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

=(Hmax-Hu)/Hmax,

(6.9)

где Н_u – энтропия рассматриваемого источника,

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

Так, для дискретного источника с М элементами

Hmax=logM.

(6.10)

Выполнение расчетных задач

Задача №1

Доказать, что H(x,y)≤H(x)+H(y).

Решение:

(6.11)

По определению,.

Для статистически зависимых событий .

- это частная энтропия Y при условии, что известно состояние X=x_i.

Наличие информации о состоянии X не может увеличить неопределенность состояния Y, но может уменьшить его в случае зависимости Y от X. Значит, условная энтропия не больше безусловной энтропии , то есть . Тогда средняя условная энтропия

(6.12)

то есть .

Значит,

Задача №2

Показать, что для регулярной марковской цепи энтропия H(x)^(r) за r шагов равняется энтропии за один шаг, умноженной на число шагов r.

Решение:

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

(6.13)

и предельным стационарным распределением вероятностей состояний .

В стационарном режиме энтропия за один шаг не зависит от номера шага и равна

,

(6.14)

- стационарная вероятность k-го состояния,

(6.15)

энтропия в k-м состоянии.

Энтропия за r шагов равна сумме энтропий за каждый шаг. Так как энтропия за каждый шаг одинакова, то сумма энтропий равна

.

(6.16)

Задача 3

Измерительное устройство вырабатывает вре­менные интервалы, распределенные случайным образом в пределах от 100 до 500 мс. Как изменится энтропия случайной величины при изменении точности измерения с 1 мс до 1 мкс?

Ответ: Энтропия увеличивается примерно на 10 бит

Решение.

При точности 1мс дискретная случайная величина Х – результат измерения – может равновероятно принимать одно из значений. Энтропия равна .

При точности 1мкс дискретная случайная величина Х – результат измерения – может равновероятно принимать одно из значений. Энтропия равна .

Изменение энтропии

бит.

Энтропия увеличилась примерно на 10 бит.

Порядок выполнения практической работы:

1. Найдите энтропию для числа белых шаров при извлечении двух шаров из урны, содержащей два белых и один черный шар.

2. Найдите энтропию для числа козырных карт при извлечении двух карт из колоды в 36 карт.

3. Какую степень неопределенности содержит опыт угадывания суммы очков на извлеченной кости из полного набора домино?

4. Найдите энтропию для числа тузов при извлечении трех карт из карт с картинками.

5. Найдите дифференциальную энтропию для равномерного распределения.

6. Найдите дифференциальную энтропию для показательного закона распределения, если известно, что случайная величина х принимает значение меньше единицы с вероятностью 0,5.

7. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Как определяется энтропия дискретных случайных величин?

2. Приведите примеры энтропий для классических законов распределения.

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Вычисление энтропии случайной величины.	Вычислять энтропию случайной величины

ПРАКТИЧЕСКАЯ РАБОТА № 7

Тема: Практическое применение различных алгоритмов сжатия. Сравнение и анализ архиваторов. Кодирование Хаффмана.

Цель:

Закрепить теоретические знания и получить практические навыки архивирования и разархивирования информации алгоритмом сжатия группы KWE, алгоритмом сжатия RLE и алгоритмом сжатия Хаффмана.

Задачи:

1. Ознакомиться с теоретической частью, предоставленной на лекционном занятии;

2. Получить практические навыки архивирования и разархивирования информации алгоритмом сжатия группы KWE, алгоритмом сжатия RLE и алгоритмом сжатия Хаффмана;

3. Оформить отчет о выполнении практической работы.

Порядок выполнения практической работы:

Вариант № 1

Задание 1. Заархивировать следующее текстовое сообщение:

В поле Поля-Полюшка полет поле-полюшко. Сорняков не будет в поле, если полет поле Поля

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

22233345667778889900000

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

Стоит_*_$ &е№!_$_*е№&а_=_*+№*_=_!+

*’ – ‘поп’

‘!’ – ‘колпак’

‘=’ – ‘под’

‘№’ – ‘,_’

‘&’ – ‘копн’

‘$’ – ‘на’

‘+’ – ‘ом’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

7 4 5 3 8 1 0 7 1 2

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

абракадабра

Определить коэффициент сжатия.

Вариант № 2

Задание 1. Заархивировать следующее текстовое сообщение:

Ужа_ужалила_ужица._Ужу_с_ужицей_не_ужиться._Уж_уж_от_ужаса_стал_уже_–_ужа_ужица_съест_на_ужин

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

15151538383899999262626261414441222

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

*_!а_!о!а,_*_№_!о№

*’ – ‘около’

‘!’ – ‘кол’

‘№’ – ‘ворот’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

4 9 8 1 5 7 14 6

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

видео-ввод-вывод

Определить коэффициент сжатия.

Вариант № 3

Задание 1. Заархивировать следующее текстовое сообщение:

Говорил попугай попугаю: "Я тебя, попугай, испугаю". Отвечает ему попугай: "Испугай, попугай, испугай!"

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

ппппуууууугштттооорркк

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

*и,_*а,_пока!,!№л&_–_и_мы№м&

*’ – ‘кос’

‘!’ – ‘_роса’

‘№’ – ‘_до’

‘&’ – ‘ой’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

н 3 д 3 л 2 ц 5 ч 2 й 2 м 7

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

маммограммами

Определить коэффициент сжатия.

Вариант № 4

Задание 1. Заархивировать следующее текстовое сообщение:

Бык тупогуб, тупогубенький бычок, у быка бела губа тупа

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

ввнкккккббббббббддддаааааеффф

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

!рос*,_а№_–=а._Старый_наш_ Енох_!+*,=у_+№

*’ – ‘_горох’

‘!’ – ‘в_огороде_’

‘№’ – ‘_за_речкой’

‘=’ – ‘_гречк’

‘+’ – ‘рвал’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

к 6 е 9 я 4 з 7 ю 2 х 1

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

тутти-фрутти

Определить коэффициент сжатия.

Вариант № 5

Задание 1. Заархивировать следующее текстовое сообщение:

Стоит_поп_на_копне,_колпак_на_попе,_копна_под_попом,_поп_под_колпаком

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

77775558000000011

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

В_*_$я-$%а_*т_*-$%о._Сорняков_не_будет_в_*,_если_*т_*_$я

поле’ – ‘*’

‘пол’ – ‘$’

‘юшк’ – ‘%’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

2 3 4 1 5 1 6 2 7 3 8 3 9 2 0 5

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

фифти-фифти

Определить коэффициент сжатия.

Вариант № 6

Задание 1. Заархивировать следующее текстовое сообщение:

Около кола колокола, около ворот коловорот

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

44444444485555555141414141414

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

ужа&лила$+.%у@$цей#е$ться._№№от&са_=ал%е_–&$+@ъе=#а$н

_ужа’ – ‘&’

‘_ужи’ – ‘$’

‘_уж’ – ‘%’

‘уж_’ – ‘№’

‘ца’ – ‘+’

‘ст’ – ‘=’

‘_н’ – ‘#’

‘_c’ – ‘@’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

15 3 38 3 9 5 26 4 14 2 4 2 1 1 2 3

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

тюлюлюкающую

Определить коэффициент сжатия.

Вариант № 7

Задание 1. Заархивировать следующее текстовое сообщение:

Коси, коса, пока роса, роса долой – и мы домой

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

ннндддллцццццччййммммммм

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

Говорил&_по%№Я_тебя,&,_ис%"._Отвечает_ему&№$,&,_$!"

_попугай’ – ‘&’

‘испугай’ – ‘$’

‘пугаю’ – ‘%’

‘:_"’ – ‘№’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

п 4 у 6 г 1 ш 1 т 3 о 3 р 2 к 2

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

шурум-бурум

Определить коэффициент сжатия.

Вариант № 8

Задание 1. Заархивировать следующее текстовое сообщение:

В_огороде_рос_горох,_а_за_речкой_–_гречка._Старый_наш_Енох_в_огороде_рвал_горох,_гречку_рвал_за_речкой

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 2. Заархивировать следующее сообщение:

ккккккеееееееееяяяязззззззююх

Какой метод архивирования вы использовали? Сравните размер фразы до и после сжатия. Определить коэффициент сжатия.

Задание 3. Разархивировать следующее сжатое сообщение:

&$,$енький_бычок,_у_&%бел%губ%тупа

бык’ – ‘&’

‘_тупогуб’ – ‘$’

‘а_’ – ‘%’

Определить коэффициент сжатия.

Задание 4. Разархивировать следующее сжатое сообщение:

в 2 н 1 к 5 б 8 д 4 а 4 е 1 ф 3

Определить коэффициент сжатия.

Задание 5. Представить один из возможных вариантов кодирования по алгоритму Хаффмана по заданному тексту:

лукуруку

Определить коэффициент сжатия.

Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• вывод о проделанной работе.

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Принцип архивирования и разархивирования информации алгоритмом сжатия группы KWE, алгоритмом сжатия RLE и алгоритмом сжатия Хаффмана	Архивировать и разархивировать информации алгоритмом сжатия группы KWE, алгоритмом сжатия RLE и алгоритмом сжатия Хаффмана

ПРАКТИЧЕСКАЯ РАБОТА № 9

Тема: Адаптивное арифметическое кодирование.

Цель:

Познакомиться с различными кодировками звуковой информации и с характеристиками звуковых файлов.

Задачи:

1. Ознакомиться с теоретической частью;

2. Познакомиться с различными кодировками звуковой информации и с характеристиками звуковых файлов;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

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

Именно звуковая плата (карта) преобразует аналоговый сигнал в дискретную фонограмму и наоборот, «оцифрованный» звук – в аналоговый (непрерывный) сигнал, который поступает на вход динамика.

Рисунок 9.1 – Схема записи и воспроизведения звука

При двоичном кодировании аналогового звукового сигнала непрерывный сигнал дискретизируется, т.е. заменяется серией его отдельных выборок - отсчётов. Качество двоичного кодирования зависит от двух параметров: количества дискретных уровней сигнала и количества выборок в секунду. Количество выборок или частота дискретизации в аудиоадаптерах бывает различной: 11 кГц, 22 кГц, 44,1 кГц и др. Если количество уровней равно 65536, то на один звуковой сигнал рассчитано 16 бит (216). 16-разрядный аудиоадаптер точнее кодирует и воспроизводит звук, чем 8-разрядный.

Количество бит, необходимое для кодирования одного уровня звука, называется глубиной звука. Объём моноаудиофайла (в байтах) определяется по формуле:

(9.1)

где v – частота дискретизации в Гц,

G – глубина звука в битах,

T – время в секундах.

При стереофоническом звучании объём аудиофайла удваивается, при квадрофоническом звучании – учетверяется.

По мере усложнения программ и увеличения их функций, а также появления мультимедиа-приложений, растёт функциональный объём программ и данных. Если в середине 80-х годов обычный объём программ и данных составлял десятки и лишь иногда сотни килобайт, то в середине 90-х годов он стал составлять десятки мегабайт. Соответственно растёт объём оперативной памяти.

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

а) 44.1 кГц;

б) 11 кГц;

в) 22 кГц;

г) 32 кГц

и разрядностью 16 бит.

Решение.

а) Если записывают моносигнал с частотой 44.1 кГц, разрядностью 16 бит (2 байта), то каждую минуту аналого-цифровой преобразователь будет выдавать 441000 * 2 * 60 = 529 000 байт (около 5 Мб) данных об амплитуде аналогового сигнала, который в компьютере записываются на жесткий диск.

Если записывают стереосигнал, то 1 058 000 байт (около 10 Мб).

Порядок выполнения практической работы:

1. Какой объем памяти требуется для хранения цифрового аудиофайла с записью звука высокого качества при условии, что время звучания составляет 3 минуты?

2. Какой объем данных имеет моноаудиофайл, длительность звучания которого 1 секунда, при среднем качестве звука (16 бит, 24 кГц)?

3. Рассчитайте объем стереоаудиофайла длительностью 20 секунд при 20-битном кодировании и частоте дискредитации 44.1 кГц. Варианты: 44,1 Mb, 4.21 Mb, 3,53 Mb.

4. Оцените информационный объем моноаудиофайла длительностью звучания 20 с, если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно 8 бит и 8 кГц;

5. Рассчитайте время звучания моноаудиофайла, если при 16-битном кодировании и частоте дискретизации 32 кГц его объем равен 700 Кбайт;

6. Запишите звуковой моноаудиофайл длительностью 20 с, с "глубиной" кодирования 8 бит и частотой дискретизации 8 кГц.

7. Определите качество звука (качество радиотрансляции, среднее качество, качество аудио-CD) если известно, что объем стериоаудиофайла длительностью звучания в 10 сек. Равен 940 Кбайт;

8. Оцените информационный объем стериоаудиофайла длительностью звучания 30 с, если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно 8 бит и 8 кГц;

9. Запишите звуковой файл длительностью 30с с "глубиной" кодирования 8бит и частотой дискретизации 8 кГц. Вычислите его объем и сверьтесь с полученным на практике значением.

10. Аналоговый звуковой сигнал был дискретизирован сначала с использованием 256 уровней интенсивности сигнала (качество звучания радиотрансляции), а затем с использованием 65536 уровней интенсивности сигнала (качество звучания аудио-CD). Во сколько раз различаются информационные объемы оцифрованного звука?

11. Оцените информационный объем моноаудиофайла длительностью звучания 1 мин. если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно:

16 бит и 48 кГц.

12. Запишите звуковой моноаудиофайл длительностью 1 минута с "глубиной" кодирования 16 бит и частотой дискретизации 48 кГц.

13. Подсчитать объем файла с 10 минутной речью записанного с частотой дискретизации 11025 Гц при 4 разрядном кодировании

14. Подсчитать время звучания звукового файла объемом 3.5 Мбайт содержащего стереозапись с частотой дискретизации 44100 Гц, 16-ти разрядном кодировании.

15. Определите количество уровней звукового сигнала при использовании 8-битных звуковых карт. Варианты: 256, 512,1024, 65 536.

16. Приведите пример:

а) аналогового способа представления звуковой информации;

б) дискретного способа представления звуковой информации.

17. Подготовить презентацию, демонстрирующую возможности звуковых форматов midi, wav, mp3, mod.

18. Перечислите параметры, от которых зависит качество двоичного кодирования звука.

19. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. С какими звуковыми форматами вы встречаетесь чаще в повседневной жизни?

2. Дайте определение аудиоадаптеру?

3. Что значит оцифровка звука?

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Различные кодировки звуковой информации. 3 Характеристики звуковых файлов.	Работать с различными кодировками звуковой информации и с характеристиками звуковых файлов.

ПРАКТИЧЕСКАЯ РАБОТА № 9

Тема: Практическое применение криптографии. Изучение и сравнительный анализ методов шифрования.

Цель:

Исследование простейших методов криптографической зашиты информации.

Задачи:

1. Ознакомиться с теоретической частью;

2. Исследовать простейшие методы криптографической зашиты информации;

3. Оформить отчет о выполнении практической работы.

Теоретическая справка:

Под конфиденциальностью понимают невозможность получения информации из преобразованного массива без знания дополнительной информации (ключа).

Аутентичность информации состоит в подлинности авторства и целостности.

Криптоанализ объединяет математические методы нарушения конфиденциальности и аутентичности информации без знания ключей.

Алфавит - конечное множество используемых для кодирования информации знаков.

Текст - упорядоченный набор из элементов алфавита. В качестве примеров алфавитов можно привести следующие:

• алфавит Z_{33 - 32} буквы русского алфавита (исключая "ё") и пробел;

• алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

• двоичный алфавит - Z₂ = {0, 1};

• восьмеричный или шестнадцатеричный алфавит.

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

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

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

Пространство ключей K - это набор возможных значений ключа.

Обычно ключ представляет собой последовательный ряд букв алфавита. Следует отличать понятия "ключ" и "пароль". Пароль также является секретной последовательностью букв алфавита, однако используется не для шифрования (как ключ), а для аутентификации субъектов.

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

Зашифрованием данных называется процесс преобразования открытых данных в зашифрованные с помощью шифра, а расшифрованием данных - процесс преобразования закрытых данных в открытые с помощью шифра.

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

Шифрованием называется процесс зашифрования или расшифрования данных. Также термин шифрование используется как синоним зашифрования. Однако неверно в качестве синонима шифрования использовать термин "кодирование" (а вместо "шифра" - "код"), так как под кодированием обычно понимают представление информации в виде знаков (букв алфавита).

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

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

Криптоанализ - наука (и практика ее применения) о методах и способах вскрытия шифров.

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

Шифры простой замены

Система шифрования Цезаря - частный случай шифра простой замены. Метод основан на замене каждой буквы сообщения на другую букву того же алфавита, путем смещения от исходной буквы на K букв.

Греческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером 5*5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в зашифрованное сообщение букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.

Схема шифрования Вижинера. Таблица Вижинера представляет собой квадратную матрицу с n² элементами, где n — число символов используемого алфавита. На рисунке показана верхняя часть таблицы Вижинера для кириллицы. Каждая строка получена циклическим сдвигом алфавита на символ. Для шифрования выбирается буквенный ключ, в соответствии с которым формируется рабочая матрица шифрования.

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

Процесс шифрования осуществляется следующим образом:

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

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

3. полученный текст может разбиваться на группы по несколько знаков.

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

Дальше осуществляется непосредственное шифрование в соответствии со вторым правилом, а именно: берем первую букву шифруемого текста (М) и соответствующую ей букву ключа (К); по букве шифруемого текста (М) входим в рабочую матрицу шифрования и выбираем под ней букву, расположенную в строке, соответствующей букве ключа (К),— в нашем примере такой буквой является Ч; выбранную таким образом букву помещаем в зашифрованный текст. Эта процедура циклически повторяется до зашифрования всего текста.

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

Расшифровка текста производится в следующей последовательности:

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

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

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

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

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

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

С целью повышения стойкости шифрования можно использовать усовершенствованные варианты таблицы Вижинера. Приведем только некоторые из них: во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке.

В качестве ключа используется случайность последовательных чисел. Из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10. Эти строки используются в соответствии с чередованием цифр в выбранном ключе.

Известны также и многие другие модификации метода.

Алгоритм перестановки

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

Самая простая перестановка — написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ.

получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЪ ТСУП

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

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительные изменения, будет выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

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

Во время Гражданской войны в США в ходу был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки незначащими буквами).

П У С Т Ь Б У Д Е Т Т А К К А

К М Ы Х О Т Е Л И К Л М Н О П

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП

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

Шифры сложной замены

Шифр Гронсфельда состоит в модификации шифра Цезаря числовым ключом. Для этого под буквами сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Зашифрованное сообщение получают примерно также, как в шифре Цезаря, но используют не одно жестко заданное смещение а фрагменты ключа.

Пусть в качестве ключа используется группа из трех цифр – 314, тогда сообщение

С О В Е Р Ш Е Н Н О С Е К Р Е Т Н О

3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 3 1 4

Ф П Ё С Ь З О С С А Х З Л Ф З У С С

В шифрах многоалфавитной замены для шифрования каждого символа исходного сообщения применяется свой шифр простой замены (свой алфавит).

АБВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭЮЯ_

А

АБВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭЮЯ_

Б

_АБВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭЮЯ

В

Я_АБВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭЮ

Г

ЮЯ_АБВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭ

.

…………

Я

ВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭЮЯ_АБ

_

БВГДЕЁЖЗИКЛМНОПРСТУФХЧШЩЪЫЬЭЮЯ_А

Каждая строка в этой таблице соответствует одному шифру замены аналогично шифру Цезаря для алфавита, дополненного пробелом. При шифровании сообщения его выписывают в строку, а под ним ключ. Если ключ оказался короче сообщения, то его циклически повторяют. Зашифрованное сообщение получают, находя символ в колонке таблицы по букве текста и строке, соответствующей букве ключа. Например, используя ключ АГАВА, из сообщения ПРИЕЗЖАЮ ШЕСТОГО получаем следующую шифровку:

ПРИЕЗЖАЮ_ШЕСТОГО

АГАВААГАВААГАВАА

ПОИГЗЖЮЮЮШЕПТНГО

Такая операция соответствует сложению кодов ASCII символов сообщения и ключа по модулю 256.

Порядок выполнения практической работы:

1. Придумайте 3 фразы, каждая минимум из 7 слов. Реализуйте шифрование этой фразы всеми перечисленными видами шифрования.

2. Оформить отчет.

Отчет должен быть оформлен в текстовом редакторе и содержать:

• наименование работы;

• цель работы;

• задание;

• последовательность выполнения работы;

• ответы на контрольные вопросы;

• вывод о проделанной работе.

Контрольные вопросы:

1. Где применяется криптография?

2. Какой смысл в Шифре Гронсфельда?

3. С помощью системы шифрования Цезаря зашифровать свое имя?

Критерий оценки:

Студент должен:

ЗНАТЬ	УМЕТЬ
1. Теоретическую часть для выполнения практической работы. 2. Простейшие методы криптографической зашиты информации.	Исследовать простейшие методы криптографической зашиты информации

2