Задание 2. Используя метод шифрования перестановками, зашифровать данное сообщение: «Преобразование сообщений», используя в качестве шаблона прямоугольник с числом столбцов 4.

Институт информационных технологий

Специальность «Программное обеспечение информационных технологий»

КОНТРОЛЬНАЯ РАБОТА

По курсу «Теория преобразования и передачи измерительной информации»

Вариант № 2

Студент-заочник 2 курса

Группы №181022

ФИО Виктор

Адрес:

Тел:

Минск, 2012

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

Эффективное кодирование с использованием алгоритма Хаффмана:

Дано сообщение «Преобразование сообщений», отсюда следует, что символов 12: «Пробел», А, Е, И, М, Н, О, Р, Т, Ф, Ц, Я с вероятностями:

Построим дерево Хаффмана, для данного сообщения.

По методике Хаффмана, это сообщение будет выглядеть следующим образом: 110100100100111011110000101100110001001100110001111011010

Эффективное кодирование с использованием алгоритма Шеннона – Фэно:

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

Буква	Частота	1	2	3	4	5	Код
И	4/17	0 0 0	0				00	1	0,24
О	2/17		1 1	0			010	2	0,24
Р	2/17			1			011	3	0,35
пробел	1/17	1 1 1 1 1 1 1 1 1	0 0 0 0	0 0	0		1000	4	0,24
А	1/17				1		1001	5	0,29
Е	1/17			1 1	0		1010	6	0,35
М	1/17				1		1011	7	0,41
Н	1/17		1 1 1 1 1	0 0	0		1100	8	0,47
Т	1/17				1		1101	9	0,53
Ф	1/17			1 1 1	0		1110	10	0,59
Ц	1/17				1 1	0	11110	11	0,65
Я	1/17					1	11111	12	0,71

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

По методике Шеннона – Фэно, это сообщение будет выглядеть следующим образом:

1101101001001100111111000001100111001001110111001111100000

Задание 2. Используя метод шифрования перестановками, зашифровать данное сообщение: «Преобразование сообщений», используя в качестве шаблона прямоугольник с числом столбцов 4.

Шифрование проводится в следующем порядке:

1.) Шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m.

2.)Зашифрованный текст выписывается колонками в порядке возрастания номеров колонок, задаваемых ключевой последовательностью.

3.)Заполняется новый блок и т.д.

Блок будет размером 4*6

По шифру простой перестановки, мы получаем следующее:

Шифртекст: тинмиеяфао оцрири

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

Шифртекст: Тинмио оцририеяфа