Файл: Методические указания по выполнению контрольной работы Введение Изучение дисциплины Теория кодирования.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 04.02.2024

Просмотров: 32

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

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

Федерального государственного бюджетного образовательного учреждения

высшего профессионального образования



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

  2. Выбираются два свободных узла дерева с наименьшими весами.

  3. Создается их родитель с весом, равным их суммарному весу.

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

  5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

Варианты заданий:

Вариант 1. Закодировать по Фано сообщения, имеющие следующие вероятности:

сообщение
1
2
3
4
5
6
7

вероятность
0,4
0,2
0,1
0,1
0,1
0,05
0,05

Представить два способа кодирования.
Вариант 2. Закодировать по Хаффману сообщения, имеющие следующие вероятности:

сообщение
1
2
3
4
5
6
7

вероятность
0,5
0,2
0,1
0,05
0,05
0,05
0,05

Представить два способа кодирования.

Вариант 3. Проведите кодирование по методу Хаффмана алфавита из четырех букв, вероятности которых равны 0,4; 0,3; 0,2 и 0,1. Представить два способа кодирования.

Вариант 4. Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Осуществите кодирование по методу Хаффмана. Представить два способа кодирования.

Вариант 5.
Закодировать французский алфавит, используя коды Фано. Представить только табличный способ кодирования. Таблица встречаемости букв алфавита представлена в Приложении 1.

Вариант 6. Закодировать немецкий алфавит, используя коды Фано. Представить только табличный способ кодирования. Таблица встречаемости букв алфавита представлена в Приложении 1.

Вариант 7. Алфавит состоит из двух букв, АиБ, встречающихся с вероятностями P (А)= 0,8 и Р(Б)= 0,2. Примените метод Хаффмана к кодированию всевозможных двухбуквенных и трехбуквенных комбинаций. Представить два способа кодирования.

Вариант 8. Алфавит состоит из двух букв, АиБ, встречающихся с вероятностями P (А)= 0,8 и Р(Б)= 0,2. Примените метод Хаффмана к кодированию всевозможных двухбуквенных и трехбуквенных комбинаций. Представить два способа кодирования.

Вариант 9. Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Проведите кодирование по методу Хаффмана. Представить два способа кодирования.

Вариант 10. Проведите кодирование по методам Фано и Хаффмана пяти букв, равновероятно встречающихся. Представить два способа кодирования.

Вариант 11. Закодировать испанский алфавит, используя коды Фано. Представить только табличный способ кодирования. Таблица встречаемости букв алфавита представлена в Приложении 1.

Вариант 12. Закодировать итальянский алфавит, используя коды Фано. Представить только табличный способ кодирования. Таблица встречаемости букв алфавита представлена в Приложении 1.

Вариант 13. Закодировать по Хаффману сообщения, имеющие следующие вероятности:

сообщение
1
2
3
4
5
6

вероятность
0,4
0,3
0,1
0,1
0,05
0,05

Представить два способа кодирования.

Вариант 14. Закодировать по Фано сообщения, имеющие следующие вероятности:

сообщение
1
2
3
4
5
6
7
8

вероятность
0,5
0,1
0,1
0,1
0,05
0,05
0,05
0,05

Представить два способа кодирования.

Вариант 15. Закодировать французский алфавит, используя коды Фано. Представить только табличный способ кодирования. Таблица встречаемости букв алфавита представлена в Приложении 1.

Задание 2.4 Коды Хэмминга

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

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

Задание: Используя код Хэмминга необходимо закодировать свое полное имя.
Примерный перечень вопросов к экзамену


  1. Предмет, цели и задачи дисциплины.

  2. История цифровых и символьных вычислений.

  3. Возникновение средств связи и передача сообщений.

  4. Достоверность передаваемых сообщений.

  5. Развитие теории кодирования.

  6. Понятие помехоустойчивого кодирования.

  7. Прикладные аспекты теории кодирования.

  8. Понятие информации.

  9. Формы представления информации.

  10. Символьная информация. Знаки.

  11. Графическая информация.

  12. Сообщение и информация.

  13. Правило интерпретации.

  14. Языковые сообщения.

  15. Информационные меры.

  16. Структурная мера информации.

  17. Непрерывная и дискретная информация.

  18. Геометрическая мера информации.

  19. Комбинаторная мера информации.

  20. Аддитивная мера информации.

  21. Статическая мера информации.

  22. Семантическая мера информации.

  23. Понятие о спектре непрерывных сообщений.

  24. Дискретизация непрерывных сообщений.

  25. Обобщенный канал передачи информации.

  26. Пропускная способность канала передачи данных.

  27. Информационная модель канала.

  28. Пропускная способность дискретного канала без помех.

  29. Пропускная способность дискретного канала с помехами.

  30. Пропускная способность непрерывного канала с помехами.

  31. Пропускная способность передачи информации и ее согласования с потоком информации от источника.

  32. Шенноновская модель дискретного канала и его пропускная способность.

  33. Классификация кодов.

  34. Основные характеристики кодов.

  35. Корректирующая способность.

  36. Связь корректирующей способности кода с кодовым расстоянием.

  37. Определение количества корректирующих символов.

  38. Избыточность.

  39. Понятие минимального кодового расстояния.

  40. Коды с обнаружением ошибок (коды с четным количеством единиц, коды с удвоением единиц, инверсный код).

  41. Разрешенные и запрещенные комбинации.

  42. Способы разбиения на подмножества.

  43. Принцип построения кодов Хэмминга для коррекции одиночных и обнаружения двоичных ошибок.

  44. Корректирующие свойства кода Хэмминга.

  45. Основные принципы построения кодов Грея.

  46. Определение циклического кода.

  47. Циклические коды: порождающий полином, порождающая матрица.

  48. Код Рида-Соломона.

  49. Код БЧХ.

  50. Информация как объект юридической и физической защиты.

  51. Государственные информационные ресурсы.

  52. Защита государственной тайны как особого вида защищаемой информации.

  53. Защита интеллектуальной собственности и коммерческой тайны.

  54. Нормативно-правовая база защиты компьютерных сетей от несанкционированного доступа.

  55. Компьютерные преступления и особенности их расследования.

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

  57. Понятие криптографического протокола. Основные типы протоколов.

  58. Классы преобразований: подстановки, перестановки, гаммирование, блочные шифры.

  59. Цифровой дайджест и хэш-функция.

  60. Подстановочные и перестановочные шифры. Шифры Цезаря, Виженера, Вернома.

  61. Электронная цифровая подпись: основные понятия и определения.

  62. Электронная подпись на основе алгоритма RSA.

  63. Алгоритм цифровой подписи Эль-Гамаля (EGSA). Алгоритм цифровой подписи DSA.

  64. Отечественный стандарт цифровой подписи.


Учебно-методическое и информационное обеспечение учебной дисциплины

    1. Рекомендуемая основная литература

№

Название
Количество единиц в библиотеке

1.
Тихонов В.А. Информационная безопасность: концептуальные правовые, организационные и технические аспекты / В.А. Тихонов, В.В. Райх. – М.: Гелиос АРВ, 2006. – 527 с.
5

2.
Шумский А.А. Системный анализ в защите информации / А.А. Шумский, А.А. Шелупанов. – М.: Гелиос АРВ, 2005. – 221 с.
40

3.
Кудряшов Б. Д. Теория информации: [учебное пособие для вузов по направлению "Информационные системы"] / Кудряшов Б. Д. - СПб.: Питер, 2009. - 314с.
10




    1. Рекомендуемая дополнительная литература

№

Название
Количество единиц в библиотеке



Зубов А.Ю. Совершенные шифры: доп. гл. курса криптографии / А. Ю. Зубов. – М.: Гелиос АРВ, 2003. – 160 с.
3



Бабенко Л.К. Защита информации с использованием смарт-карт и электронных брелоков / Л.К. Бабенко, С.С. Ищуков, О.Б. Макаревич. – М.: Гелиос АРВ, 2003. – 352 с.
55



Торокин А.А. Инженерно-техническая защита информации. М.: Гелиос АРВ, 2005.- 959 с.
40



Умняшкин С. В. Теоретические основы цифровой обработки и представления сигналов: [учебное пособие для вузов по направлению "Информатика и вычислительная техника"] / Умняшкин С. В. - М.: Форум, Инфра-М, 2008. - 302с.
1



Потемкин В.Г. Система инженерных и научных расчетов MATLAB 5.х. в 2-х т.: Учеб.-справ. пособие. – М.: ДИАЛОГ-МИФИ, 1999.
1



Теория информации и кодирование: учебное пособие для вузов по специальности "Информ. системы" / Самсонов Б. Б., Плохов Е. М., Филоненко А. И., Кречет Т. В. - Ростов н/Д: Феникс, 2002. - 287с.
30



Артюшенко В. М. Цифровое сжатие видеоинформации и звука: [учебное пособие для вузов по специальности "Информ. системы и технологии"] / Артюшенко В. М., Шелухин О. И., Афонин М. Ю., под ред. В. М. Артюшенко - М.: Дашков и К', 2003. - 425с.
18



Шабунин Л. В. Алфавитное кодирование: конспект лекций / Шабунин Л. В., Шабунин А. Л., [отв. ред. Л. В. Шабунин] ; Чуваш. гос. ун-т им. И. Н. Ульянова - Чебоксары: ЧувГУ, 2010. - 100с.
114



Панин В. В. Основы теории информации: учебное пособие для вузов / Панин В. В. - 3-е изд., испр. - М.: Бином. Лаб. знаний, 2009. - 438с.
5



Воробьев Л. В. Системы и сети передачи информации: учебное пособие для вузов по специальностям "Компьютерная безопасность" и др. / Давыдов А. В., Воробьев Л. В. - М.: Академия, 2009. - 329с.
10



Логачев О. А. Булевы функции в теории кодирования и криптологии: Изд-во МЦНМО / Логачев О. А., Сальников А. А., Ященко В. В., Ин-т пробл. информ. безопасности МГУ - М.: Изд-во МЦНМО, 2004. - 469с.
1



Фомичев В. М. Дискретная математика и криптология: курс лекций / Фомичев В. М., под общ. ред. Н. Д. Подуфалова - М.: ДИАЛОГ-МИФИ, 2003. - 397с.
1



Свирид Ю.В. Основы теории информации: Курс лекций / Свирид Ю.В. - Минск: БГУ, 2003. - 139с.
1



Основы организационного обеспечения информационной безопасности объектов информатизации / С.Н. Семкин, Э.В. Беляков, С.В. Гребенев, В.И. Казачок. – М.: Гелиос АРВ, 2005. – 186 с.
8




    1. Программное обеспечение и Интернет-ресурсы




  1. http://gouspo.ru – материалы по «Теории кодирования»;

  2. http://tc.nsu.ru/uploads/codingtheory.pdf - учебник по «Теории кодирования» в формате pdf;

  3. http://www.libedu.ru/l_b/potapov_v_n_/teorija_informacii__kodirovanie_diskretnyh_verojatnostnyh_istochnikov_.html - книга по «Теории кодирования» в формате djvu;

  4. http://metod.vt.tpu.ru/lab/huffman - интерактивное обучение алгоритму кодирования Хаффмана.

Приложение 1

Буква алфавита
Французский язык
Немецкий язык
Английский язык
Испанский язык
Итальянский язык

A
7.68
5.52
7.96
12.90
11.12

B
0.80
1.56
1.60
1.03
1.07

C
3.32
2.94
2.84
4.42
4.11

D
3.60
4.91
4.01
4.67
3.54

E
17.76
19.18
12.86
14.15
11.63

F
1.06
1.96
2.62
0.70
1.15

G
1.10
3.60
1.99
1.00
1.73

H
0.64
5.02
5.39
0.91
0.83

I
7.23
8.21
7.77
7.01
12.04

J
0.19
0.16
0.16
0.24
-

K
-
1.33
0.41
-
-

L
5.89
3.48
3.51
5.52
5.95

M
2.72
1.69
2.43
2.55
2.65

N
7.61
10.20
7.51
6.20
7.68

O
5.34
2.14
6.62
8.84
8.92

P
3.24
0.54
1.81
3.26
2.66

Q
1.34
0.01
0.17
1.55
0.48

R
6.81
7.01
6.83
6.95
6.56

S
8.23
7.07
6.62
7.64
4.81

T
7.30
5.86
9.72
4.36
7.07

U
6.05
4.22
2.48
4.00
3.09

V
1.27
0.84
1.15
0.67
1.67

W
-
1.38
1.80
-
-

X
0.54
-
0.17
0.07
-

Y
0.21
-
1.52
1.05
-

Z
0.07
1.17
0.05
0.31
1.24

Смотрите также файлы