Основы теории сжатия и кодирования информации - Рабочая программа дисциплины - 03.04.03. Радиофизика - Направления подготовки

Закреплена за кафедрой	Кафедра радиофизики и теоретической физики
Направление подготовки	03.04.03. Радиофизика
Профиль	Электромагнитные волны в средах
Форма обучения	Очная
Общая трудоемкость	3 ЗЕТ
Учебный план	03_04_03_ЭМВС-2-2020

Курс (семестр)	1 (1)	Итого
Недель	15
Вид занятий	УП	РПД	УП	РПД
Лекции	18	18	18	18
Лабораторные	12	12	12	12
Сам. работа	78	78	78	78
Итого	108	108	108	108

1. Цели освоения дисциплины

1.1.	Цель курса «Теория информации» состоит в освоении студентами основ теории информации и теории кодирования, а также в получении знаний о современных технологиях передачи и преобразования информации. Основными задачами курса являются: овладение фундаментальными знаниями по теории информации и теории кодирования; овладение технологиями кодирования и сжатия, восстановления и хранения информации; приобретение практических навыков реализации кодирующих и декодирующих алгоритмов.

1.1.

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

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.В

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

ОПК-2	готовностью руководить коллективом в сфере своей профессиональной деятельности, толерантно воспринимая социальные, этнические, конфессиональные и культурные различия
ОПК-3	способностью к свободному владению знаниями фундаментальных разделов физики и радиофизики, необходимых для решения научно-исследовательских задач
ПК-1	способностью использовать в своей научно-исследовательской деятельности знание современных проблем и новейших достижений физики и радиофизики
ПК-2	способностью самостоятельно ставить научные задачи в области физики и радиофизики и решать их с использованием современного оборудования и новейшего отечественного и зарубежного опыта
В результате освоения дисциплины обучающийся должен
3.1.	Знать:
3.1.1.	основные понятия и теоремы теории информации и кодирования; основные принципы и способы кодирования и декодирования; характеристики кодов разного типа, понятие оптимального и помехоустойчивого кодирования; методы исследования кодов и их применений в ЭВМ и системах защиты информации. основные классы кодов, их параметры и алгоритмы кодирования/декодирования.
3.2.	Уметь:
3.2.1.	вычислять количество информации в сообщениях дискретного источника канала связи; кодировать и декодировать сообщения источника одним из изученных кодов, оценивать его оптимальность и помехоустойчивость; оценивать количество информации, вероятность ошибки на выходе канала связи и вероятность ошибочного декодирования; выбирать, реализовывать и применять кодирующие и декодирующие алгоритмы для различных классов задач.
3.3.	Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.	навыками реализации кодирующих и декодирующих алгоритмов; навыками сравнительного анализа кодов и алгоритмов.основными.

4. Структура и содержание дисциплины

Код занятия	Наименование разделов и тем	Вид занятия	Семестр	Часов	Компетенции	Литература
Раздел 1. Основы теории информации и кодирования
1.1.	Энтропия вероятностной схемы; аксиомы Хинчина и Фаддеева; условная энтропия; взаимная информация и ее свойства;	Лекции	1	2	ОПК-3	Л2.2, Л1.3, Л1.1
1.2.	Источники информации; энтропия источников; дискретный источник без памяти; теоремы Шеннона об источниках; марковские и эргодические источники; информационная дивергенция; граница Симмонса;	Лекции	1	2	ОПК-3	Л1.3, Л2.3
1.3.	Изучение леционного материала, основной и дополнительной литературы.	Сам. работа	1	20	ОПК-2, ОПК-3	Л1.3, Л2.3
Раздел 2. Оптимальное кодирование и сжатие данных
2.1.	Оптимальное кодирование; префиксные коды; неравенство Крафта; линейные коды; параметры кодов и их границы; корректирующие свойства кодов; циклические коды; БЧХ - коды; код Хемминга; сверточные коды; математическая модель канала связи; пропускная способность канала связи; прямая и обратная теоремы кодирования.	Лекции	1	2	ОПК-3	Л2.2, Л1.3, Л1.1, Л2.3
2.2.	Шифрование подстановкой и раскрытие шифра методом частотного анализа.	Лабораторные	1	2	ОПК-2, ПК-1, ПК-2	Л1.1
2.3.	Кодирование методом Шеннона-Фано.	Лабораторные	1	1	ОПК-2, ПК-1, ПК-2	Л1.1
2.4.	Кодирование методом Хаффмана.	Лабораторные	1	1	ОПК-2, ПК-1, ПК-2	Л1.1
2.5.	Арифметическое кодирование.	Лабораторные	1	2	ОПК-2, ПК-1, ПК-2	Л1.1
2.6.	Словарные алгоритмы. Методы Лемпела-Зива.	Лекции	1	1	ОПК-3	Л1.1
2.7.	LZ-сжатие данных. Разновидности алгоритмов. Особенности реализации.	Лабораторные	1	2	ОПК-2, ПК-1, ПК-2	Л1.1
2.8.	Сжатие с потерями. Основные идеи, методы и форматы данных.	Лекции	1	1	ОПК-3	Л1.3, Л1.1
2.9.	Сжатие с потерями. Анализ распространенных современных форматов данных использующих сжатие с потерями.	Лабораторные	1	2	ОПК-2, ПК-1, ПК-2	Л1.3, Л1.1
2.10.	Основы методов фрактального сжатия.	Лекции	1	2	ОПК-3
2.11.	Работа с лекционным материалом, основной и дополнительной литературой. Выполнениие лабораторных работ.	Сам. работа	1	20	ПК-1, ПК-2	Л1.1
Раздел 3. Теоретические основы передачи данных
3.1.	Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона).	Лекции	1	1	ОПК-3	Л1.1, Л1.2
3.2.	Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами.	Лекции	1	1	ОПК-3	Л1.1, Л1.2
3.3.	Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование.	Лекции	1	1	ОПК-3	Л1.1, Л1.2
3.4.	Работа с лекционным материалом, основной и дополнительной литературой. Выполнение лабораторных работ.	Сам. работа	1	18	ОПК-3	Л1.1, Л1.2, Л2.3
Раздел 4. Помехоустойчивое кодирование и контроль ошибок
4.1.	Помехоустойчивое кодирование. Основные подходы. Неравенство Крафта-Макмиллана.	Лекции	1	1	ОПК-2, ОПК-3	Л1.1, Л1.2, Л2.3
4.2.	Матричное кодирование. Групповые коды. Совершенные и квазисовершенные коды. Код Хемминга.	Лекции	1	1	ОПК-3	Л1.1, Л1.2, Л2.3
4.3.	Полиномиальные коды. Коды БЧХ. Коды Рида-Соломона. Циклические избыточные коды.	Лекции	1	1	ОПК-2, ОПК-3	Л1.1, Л1.2, Л2.3
4.4.	Сверточные коды. Турбо-коды.	Лекции	1	1	ОПК-3	Л1.1, Л1.2, Л2.3
4.5.	Помехоустойчивое кодирование (особенности реализации алгоритмов).	Лабораторные	1	2	ОПК-2, ПК-1, ПК-2	Л1.1, Л1.2
4.6.	Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография.	Лекции	1	1	ОПК-2, ОПК-3	Л1.3, Л2.1
4.7.	Работа с лекционным материалом, основной и дополнительной литературой. Выполнение лабораторных работ.	Сам. работа	1	20	ПК-1, ПК-2	Л1.3, Л1.1, Л1.2, Л2.1

5. Фонд оценочных средств

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

1. Общефизические основы теории информации. Термодинамика и энтропия. Информация, содержащаяся в экспериментальных данных и теоретическом законе.
2. Информация и данные. Кодирование. Цифровые коды. Понятие об экономичном кодировании.
3. Вероятностный подход к измерению количества информации. Энтропия Шеннона. Семантическая информация.
4. Взаимная информация и информационная дивергенция. Энтропия источников. Теоремы Шеннона об источниках.
1. Кодирование Шеннона-Фэно.
2. Кодирование Хаффмана.
3. Арифметическое кодирование.
4. Адаптивные алгоритмы.
5. Методы Лемпела-Зива.
6. Сжатие с потерями. Основные методы и форматы данных.
7. Основы методов фрактального сжатия.
8. Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона).
9. Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами.
10. Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование.
11. Помехоустойчивое кодирование. Неравенство Крафта-Макмиллана.
12. Матричное кодирование.
13. Групповые коды. Совершенные и квазисовершенные коды.
14. Код Хемминга.
15. Полиномиальные коды.
16. Коды Боуза-Чоудхури-Хоккенгема. Коды Рида-Соломона.
17. Циклические избыточные коды.
18. Сверточные коды.
19. Турбо-коды.
20. Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография.
21. Основы технологии "Блокчейн"

5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)

Изучение и сравнительный анализ формата WebP.
Изучение и сравнительный анализ формата WebM.
Применение вейвлет-переобразований при сжатии данных с потерями.
Фрактальное сжатие изображений.
Основы квантовой теории информации. Квантовые алгоритмы.
Основы технологии "Блокчейн"

5.3. Фонд оценочных средств для проведения промежуточной аттестации

См. прилагаемый файл.

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

6.1. Рекомендуемая литература
6.1.1. Основная литература
	Авторы	Заглавие	Издательство, год	Эл. адрес
Л1.1	Иордан В.И., Гуляев П.Ю.	Основы теории информации и кодирования: учеб. пособие :	Барнаул : Изд-во АлтГУ, 2004
Л1.2	Сидельников В. М.	Теория кодирования:	М.: Физматлит, 2008	biblioclub.ru
Л1.3	Балюкевич Э.Л.	Теория информации: Учебно-методический комплекс	М.: Евразийский открытый институт // ЭБС "ONLINE", 2009	biblioclub.ru
6.1.2. Дополнительная литература
	Авторы	Заглавие	Издательство, год	Эл. адрес
Л2.1	Хренников А. Ю.	Введение в квантовую теорию информации:	М.: Физматлит, 2008	e.lanbook.com
Л2.2	Ю. Н. Мальцев, Е. П. Петров	Элементы дискретной математики: Элементы комбинаторики, теории графов, теории кодирования и криптографии: [учеб. пособие]	Барнаул: Изд-во АлтГУ, 2004
Л2.3	Чечёта С. И.	Введение в дискретную теорию информации и кодирования:	М.: МЦНМО, 2011	biblioclub.ru
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
	Название		Эл. адрес
Э1	В.В. Лидовский. Теория информации. [Электронный ресурс]: Московский центр непрерывного математического образования. Режим доступа: http://www.mccme.ru/free-books/izdano/2004/it_ebook1.pdf 10.10.2011.
Э2	Все о сжатии данных, изображений и видео. [Электронный ресурс]. Режим доступа: http://www.compression.ru 10.10.2012.
Э3	Курс на Едином образовательном портале АлтГУ		portal.edu.asu.ru
6.3. Перечень программного обеспечения
Компилятор языка прграммирования высокого уровня и среда разработки.
6.4. Перечень информационных справочных систем

7. Материально-техническое обеспечение дисциплины

Аудитория	Назначение	Оборудование
001вК	склад экспериментальной мастерской - помещение для хранения и профилактического обслуживания учебного оборудования	Акустический прибор 01021; виброизмеритель 00032; вольтметр Q1202 Э-500; вольтметр универсальный В7-34А; камера ВФУ -1; компьютер Турбо 86М; масспектрометр МРС -1; осциллограф ЕО -213- 2 ед.; осциллограф С1-91; осциллограф С7-19; программатор С-815; самописец 02060 – 2 ед.; стабилизатор 3218; терц-октавный фильтр 01023; шкаф вытяжной; шумомер 00026; анализатор АС-817; блок 23 Г-51; блок питания "Статрон" – 2 ед.; блок питания Ф 5075; вакуумный агрегат; весы; вольтметр VM -70; вольтметр В7-15; вольтметр В7-16; вольтметр ВУ-15; генератор Г-5-6А; генератор Г4-76А; генератор Г4-79; генератор Г5-48; датчик колебаний КВ -11/01; датчик колебаний КР -45/01; делитель Ф5093; измеритель ИМП -2; измеритель параметров Л2-12; интерферометр ИТ 51-30; источник "Агат" – 3 ед.; источник питания; источник питания 3222; источник питания ЭСВ -4; лабораторная установка для настройки газовых лазеров; лазер ЛГИ -21; М-кальк-р МК-44; М-калькул-р "Электроника"; магазин сопротивления Р4075; магазин сопротивления Р4077; микроскоп МБС -9; модулятор МДЕ; монохроматор СДМС -97; мост переменного тока Р5066; набор цветных стекол; насос вакумный; насос вакуумный ВН-01; осциллограф С1-31; осциллограф С1-67; осциллограф С1-70; осциллограф С1-81; осциллоскоп ЕО -174В – 2 ед.; пентакта L-100; пирометр "Промень"; пистонфон 05001; преобразователь В9-1; прибор УЗДН -2Т; скамья оптическая СО 1м; спектограф ДФС -452; спектограф ИСП -51; стабилизатор 1202; стабилизатор 3217 – 4 ед.; стабилизатор 3218; стабилизатор 3222 – 3 ед.; станок токарный ТВ-4; усилитель мощности ЛВ -103 – 4 ед.; усилитель У5-9; центрифуга ВЛ-15; частотомер Ч3-54А; шкаф металлический; эл.двигатель; электродинамический калибратор 11032
Помещение для самостоятельной работы	помещение для самостоятельной работы обучающихся	Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ
Учебная аудитория	для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик	Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)

8. Методические указания для обучающихся по освоению дисциплины

Практические занятия нацелены на приобретение навыков выбора и реализации кодирующих и декодирующих алгоритмов.
При выполнении практических заданий и итоговых индивидуальных заданий используются электронные учебно-методические материалы по курсу, размещенные на образовательном портале АлтГУ (http://http://portal.edu.asu.ru)

Перечень тем, выносимых на практические занятия.
1. Шифрование подстановкой и раскрытие шифра методом частотного анализа.
2. Кодирование методом Шеннона-Фано.
3. Кодирование методом Хаффмана.
4. Арифметическое кодирование.
5. LZ-сжатие данных. Разновидности алгоритмов. Особенности реали-зации.
6. Сжатие с потерями. Анализ распространенных современных форматов данных использующих сжатие с потерями.
7. Помехоустойчивое кодирование (особенности реализации алгоритмов).

Планы лабораторных занятий и методические рекомендации по подготовке к ним
1. Шифрование подстановкой и раскрытие шифра методом ча-стотного анализа.
Продемонстрировать уязвимость "шифра простой заме-ны" по отношению к частотному анализу.
Выполнитиь частотный анализ открытого текста_1 (не менее 100 тыс. знаков). Выполнить шифрование простой заменой текста_2 (не менее 100 тыс. знаков). Выполнить частотный анализ шифротекста_2. Сопоставив результа-ты частотного анализа, восстановить ключ (таблицу под-становки). С использованием восстановленного ключа расшифровать случайно выбранную строку шифротекста_2.
2. Кодирование методом Шеннона-Фано.
Выполнить сжатие данных методом Шеннона-Фано. Продемонстрировать на примерах преимущества и недостат-ки использованного алгоритма.
3. Кодирование методом Хаффмана.
Выполнить сжатие данных методом Хаффмана. Продемонстрировать на примерах преимущества и недостатки использованного алгоритма.
4. Арифметическое кодирование
Выполнить арифметическое кодирование. В случае, если в предыдущей работе был использован неадаптивный ме-тод Хаффмана, применить адаптивное арифметическое кодирование. Продемонстрировать на примерах пре-имущества и недостатки использованного алгоритма.
5. LZ-сжатие данных.
Выполнить сжатие данных при помощи словарно-ориентированного алгоритма (конкретную версию выбрать самостоятельно). Продемонстрировать на примерах преимущества и недостатки использованного алго-ритма.
6. Код Хемминга
Реализовать (7,4) и (9,5) коды Хемминга. Выполнить сравнительный анализ избыточности и корректирующей мощности кодов.
7. Помехоустойчивое кодирование.
Реализовать один из рассмотренных алгоритмов помехо-устойчивого кодирования. Продемонстрировать на при-мерах преимущества и недостатки использованного ал-горитма.

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