Министерство образования республики Беларусь
Учреждение образования
«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»
Институт информационных технологий
Специальность «Программное обеспечение информационных технологий»
Контрольная работа
По курсу «Теория преобразования и передачи измерительной информации»
Вариант № 4
Студент-заочник 2 курса
Группы №181022
ФИО Дарья
Адрес:
Тел:
Минск, 2012
Задание 1. С использованием алгоритмов Хаффмана и Шеннона - Фэно произвести эффективное кодирование данного сообщения: «Проверочные биты». При кодировании распределение вероятностей различных букв сообщения определить из анализа сообщения.
Эффективное кодирование с использованием алгоритма Хаффмана:
Дано сообщение
«Преобразование сообщений», отсюда
следует, что символов 13: «Пробел», Б, В,
Е, И, Н, О, П, Р, Т, Ч, Ы с вероятностями:
Построим дерево Хаффмана, для данного сообщения.
Пробел Ч
По методике Хаффмана, это сообщение будет выглядеть следующим образом: 11011000110010010100011111111001010100000000100111110101
Эффективное кодирование с использованием алгоритма Шеннона – Фэно:
По этой методике код строится следующим образом. Буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей. Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним – 0. Каждая из полученных групп разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
-
Буква
Частота
1
2
3
4
Код
Е
2/16
0
0
0
0
0
0
0
000
1
0,125
О
2/16
1
001
2
0,25
Р
2/16
1
1
0
010
3
0,375
Ы
2/16
1
011
4
0,5
пробел
1/16
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1000
5
0,313
Б
1/16
1
1001
6
0,375
В
1/16
1
1
0
1010
7
0,438
И
1/16
1
1011
8
0,5
Н
1/16
1
1
1
1
0
0
0
1100
9
0,563
П
1/16
1
1101
10
0,625
Т
1/16
1
1
0
1110
11
0,688
Ч
1/16
1
1111
12
0,75
Для получения таким образом кода среднее число двоичных символов, приходящихся на одну букву, равно:
По методике Шеннона – Фэно, это сообщение будет выглядеть следующим образом:
11010100011010000010111111000110001000100110111110011
Задание 2. Используя метод шифрования перестановками, зашифровать данное сообщение: «Преобразование сообщений», используя в качестве шаблона прямоугольник с числом столбцов 4.
Шифрование проводится в следующем порядке:
1.) Шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m.
2.)Зашифрованный текст выписывается колонками в порядке возрастания номеров колонок, задаваемых ключевой последовательностью.
3.)Заполняется новый блок и т.д.
Блок будет размером 4*6
|
П |
Р |
О |
В |
|
Е |
Р |
О |
Ч |
|
Н |
Ы |
Е |
|
|
Б |
И |
Т |
Ы |
|
Ключ: 2 4 1 3 |
|||
По шифру простой перестановки, мы получаем следующее:
Шифртекст: Пенбррыиооетвч ы
Широко распространена разновидность шифра маршрутной перестановки, называемая ``шифром вертикальной перестановки'' (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. По ключу мы получаем следующее:
Шифртекст: ооетпенбвч ыррыи
Задание 3. Используя шифрование с ключом, закодировать сообщения, используя в качестве ключа слова: Алгоритм, Разряд, Кодирование.
Шифрование с ключом: