МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

Основы теории сжатия и кодирования информации

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

Распределение часов по семестрам

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

Программу составил(и):
к.ф.-м.н., доцент кафедры радиофизики и теоретической физики, Райкин Роман Ильич

Рецензент(ы):
к.ф.-м.н., доцент кафедры прикладной физики, электроники и информационной безопасности, Рудер Давыд Давыдович

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

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 03.04.03 РАДИОФИЗИКА (уровень магистратуры) (приказ Минобрнауки России от 30.10.2014г. №1417)

составлена на основании учебного плана:
03.04.03 Радиофизика
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

Рабочая программа одобрена на заседании кафедры
Кафедра радиофизики и теоретической физики

Протокол от 06.06.2019 г. № 9/2018-19
Срок действия программы: 2019-2020 уч. г.

Заведующий кафедрой
д.ф.-м.н., профессор Лагутин Анатолий Алексеевич


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2019-2020 учебном году на заседании кафедры

Кафедра радиофизики и теоретической физики

Протокол от 06.06.2019 г. № 9/2018-19
Заведующий кафедрой д.ф.-м.н., профессор Лагутин Анатолий Алексеевич


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 1 ОПК-3 Л1.3, Л2.3
1.3. Изучение леционного материала, основной и дополнительной литературы. Сам. работа 1 20 ОПК-2, ОПК-3 Л1.3, Л2.3
Раздел 2. Оптимальное кодирование и сжатие данных
2.1. Оптимальное кодирование; префиксные коды; неравенство Крафта; линейные коды; параметры кодов и их границы; корректирующие свойства кодов; циклические коды; БЧХ - коды; код Хемминга; сверточные коды; математическая модель канала связи; пропускная способность канала связи; прямая и обратная теоремы кодирования. Лекции 1 3 ОПК-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.
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. Помехоустойчивое кодирование.
Реализовать один из рассмотренных алгоритмов помехо-устойчивого кодирования. Продемонстрировать на при-мерах преимущества и недостатки использованного ал-горитма.

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