Учебно-методический комплекс по дисциплине «Основы теории информации и кодирования» Специальность 010801. 65 «Радиофизика и электроника»



Скачать 134.19 Kb.
Дата02.06.2016
Размер134.19 Kb.

Министерство образования и науки РФ

ФГБОУ ВПО «Алтайский государственный университет»

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



Учебно-методический комплекс по дисциплине

«Основы теории информации и кодирования»
Специальность 010801.65 – «Радиофизика и электроника»

Рассмотрено и утверждено

на заседании кафедры от 4.06.2012, протокол №8  

Барнаул


2012

СОДЕРЖАНИЕ




  1. Рабочая учебная программа дисциплины (отдельный файл)

  2. Методические указания по проведению преподавателями основных видов учебных занятий по дисциплине

  3. Задания для экзаменационного и межсессионного контроля знаний студентов (фонд оценочных средств);

  4. Материалы, устанавливающие содержание и порядок проведения итоговой аттестации по дисциплине;

  5. Методические указания студентам по изучению дисциплины, выполнению лабораторных практикумов, контрольных работ, домашних заданий и других видов учебной работы, включая выполнение курсовых проектов (работ);

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



  1. Методические указания по проведению преподавателями основных видов учебных занятий по дисциплине

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

Основными задачами курса являются:

овладение фундаментальными знаниями по теории информации и теории кодирования;

овладение технологиями кодирования и сжатия, восстановления и хранения информации;

приобретение практических навыков реализации кодирующих и декодирующих алгоритмов.



В результате изучения курса

- студент должен знать:

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

  2. основные принципы и способы кодирования и декодирования;

  3. характеристики кодов разного типа, понятие оптимального и помехоустойчивого кодирования;

  4. методы исследования кодов и их применений в ЭВМ и системах защиты информации. 

  5. основные классы кодов, их параметры и алгоритмы кодирования/декодирования;

  6. основные формально-математические модели каналов связи и способы их количественного описания;

  студент должен уметь:

  1. вычислять количество информации в сообщениях дискретного источника канала связи; 

  2. кодировать и декодировать сообщения источника одним из изученных кодов, оценивать его оптимальность и помехоустойчивость; 

  3. исследовать основные характеристики канала связи;

  4. оценивать количество информации, вероятность ошибки на выходе канала связи и вероятность ошибочного декодирования; 

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

Перечень дисциплин, усвоение которых студентам необходимо для изучения данной дисциплины.

Базовый курс информатики, курс методы программирования и прикладные алгоритмы, общематематические дисциплины, в т.ч. курс теории вероятностей и математической статистики, курс физики.


Курс предусматривает лекционные и практические занятия, а также самостоятельную работу студентов в размере ~50% от суммарного объема трудозатрат. По итогам изучения дисциплины студенты сдают экзамен.

Текущий и промежуточный контроль усвоения курса осуществляется посредством выполнения студентами лабораторных работ.

Итоговый контроль осуществляется в форме экзамена.

Для эффективного изучения теоретической части дисциплины необходимо:

- построить работу по освоению дисциплины в порядке, отвечающим изучению основных этапов, согласно приведенным темам лекционного материала;

- систематически проверять знания студентов по контрольным вопросам;

- систематически проверять усвоение содержания ключевых понятий;

- эффективно работать с источниками и литературой по соответствующим темам.

В рамках курса необходимо уделить особое внимание рассмотрению современных методов кодирования и сжатия данных, новым форматам данных, а также рассмотрению основ квантовой теории информации.

Для эффективного изучения практической части дисциплины настоятельно рекомендуется систематически контролировать выполнение лабораторных работ.



Планы лекционных занятий (распределение учебных часов и литература по темам приведены в РПД).

Раздел 1. Основы теории информации и кодирования

1.1. Общефизические основы теории информации. Термодинамика и энтропия. Информация и данные. Кодирование. Цифровые коды. Понятие об экономичном кодировании.

1.2. Вероятностный подход к измерению количества информации. Энтропия вероятностной схемы. Семантическая информация. Аксиомы Хинчина и Фаддеева. Условная энтропия. Взаимная информация и ее свойства. Источники информации. Энтропия источников. Дискретный источник без памяти. Теоремы Шеннона об источниках. Марковские и эргодические источники. Информационная дивергенция.

Раздел 2. Оптимальное кодирование и сжатие данных

2.1. Граница Симмонса. Оптимальное кодирование. Префиксные коды. Частотные алгоритмы. Кодирование Шеннона-Фэно. Кодирование Хаффмана. Арифметическое кодирование. Адаптивные методы и алгоритмы.

2.2. Словарные алгоритмы. Методы Лемпела-Зива.

2.3. Сжатие с потерями. Основные идеи, методы и форматы данных.

2.4. Основы методов фрактального сжатия.

Раздел 3. Теоретические основы передачи данных

3.1. Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона).

3.2. Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами.

3.3. Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование.

Раздел 4. Помехоустойчивое кодирование и контроль ошибок

4.1. Помехоустойчивое кодирование. Основные подходы. Неравенство Крафта-Макмиллана.

4.2. Матричное кодирование. Групповые коды. Совершенные и квазисовершенные коды. Код Хемминга.

4.3. Полиномиальные коды. Коды БЧХ. Коды Рида-Соломона. Циклические избыточные коды.

4.4. Сверточные коды. Турбо-коды.



4.5. Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография.

  1. Задания для экзаменационного и межсессионного контроля знаний студентов (фонд оценочных средств)


Перечень лабораторных работ:

    1. Шифрование подстановкой и раскрытие шифра методом частотного анализа.

    2. Кодирование методом Шеннона-Фано.

    3. Кодирование методом Хаффмана

    4. Арифметическое кодирование

    5. Адаптивные алгоритмы сжатия данных (конкретный алгоритм выбирается студентом).

    6. LZ-сжатие данных

    7. Код Хемминга

    8. Помехоустойчивое кодирование (конкретный алгоритм выбирается студентом).




Перечень индивидуальных заданий:

  1. Изучение и сравнительный анализ формата WebP.

  2. Изучение и сравнительный анализ формата WebM.

  3. Применение вейвлет-переобразований при сжатии данных с потерями.

  4. Фрактальное сжатие изображений.

  5. Основы квантовой теории информации. Квантовые алгоритмы.


Контрольные вопросы к экзамену по дисциплине:

  1. Общефизические основы теории информации. Термодинамика и энтропия. Информация, содержащаяся в экспериментальных данных и теоретическом законе.

  2. Информация и данные. Кодирование. Цифровые коды. Понятие об экономичном кодировании.

  3. Вероятностный подход к измерению количества информации. Энтропия Шеннона. Семантическая информация.

  4. Взаимная информация и информационная дивергенция. Энтропия источников. Теоремы Шеннона об источниках.

  5. Кодирование Шеннона-Фэно.

  6. Кодирование Хаффмана.

  7. Арифметическое кодирование.

  8. Адаптивные алгоритмы.

  9. Методы Лемпела-Зива.

  10. Сжатие с потерями. Основные методы и форматы данных.

  11. Основы методов фрактального сжатия.

  12. Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона).

  13. Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами.

  14. Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование.

  15. Помехоустойчивое кодирование. Неравенство Крафта-Макмиллана.

  16. Матричное кодирование.

  17. Групповые коды. Совершенные и квазисовершенные коды.

  18. Код Хемминга.

  19. Полиномиальные коды.

  20. Коды Боуза-Чоудхури-Хоккенгема.

  21. Циклические избыточные коды.

  22. Сверточные коды

  23. Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография.



  1. Материалы, устанавливающие содержание и порядок проведения итоговой аттестации по дисциплине

К экзамену по дисциплине допускаются студенты, выполнившие все предусмотренные настоящим УМК лабораторные работы.

Организация текущей аттестации

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



Организация итоговой аттестации с критериями оценивания:

Осуществляется в форме экзамена, на котором проверяются знания основных вопросов программы.

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

Оценка "хорошо" ставится в случае, если студент владеет знаниями теории и практики, показывает достаточное понимание сущности и взаимосвязи рассматриваемых процессов и явлений, но имеет некоторые недостатки в ответах.

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

Оценка "неудовлетворительно" ставится в случае, если имеет место неправильный ответ хотя бы на один из основных вопросов, грубые ошибки в ответе, непонимание сущности излагаемых вопросов, неуверенные  неточные ответы на дополнительные вопросы.



  1. Методические указания студентам по изучению дисциплины, выполнению лабораторных практикумов, контрольных работ, домашних заданий и других видов учебной работы, включая выполнение курсовых проектов (работ)

Практические занятия нацелены на приобретение навыков выбора и реализации кодирующих и декодирующих алгоритмов.

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


  1. Шифрование подстановкой и раскрытие шифра методом частотного анализа.

  2. Кодирование методом Шеннона-Фано.

  3. Кодирование методом Хаффмана.

  4. Арифметическое кодирование.

  5. LZ-сжатие данных. Разновидности алгоритмов. Особенности реализации.

  6. Сжатие с потерями. Анализ распространенных современных форматов данных использующих сжатие с потерями.

  7. Помехоустойчивое кодирование (особенности реализации алгоритмов).

Планы лабораторных занятий и методические рекомендации по подготовке к ним

    1. Шифрование подстановкой и раскрытие шифра методом частотного анализа.

Продемонстрировать уязвимость "шифра простой замены" по отношению к частотному анализу.

Выполнитиь частотный анализ открытого текста_1 (не менее 100 тыс. знаков). Выполнить шифрование простой заменой текста_2 (не менее 100 тыс. знаков). Выполнить частотный анализ шифротекста_2. Сопоставив результаты частотного анализа, восстановить ключ (таблицу подстановки). С использованием восстановленного ключа расшифровать случайно выбранную строку шифротекта_2.



    1. Кодирование методом Шеннона-Фано.

Выполнить сжатие данных методом Шеннона-Фано. Продемонстрировать на примерах преимущества и недостатки использованного алгоритма.

    1. Кодирование методом Хаффмана.

Выполнить сжатие данных методом Хаффмана. Продемонстрировать на примерах преимущества и недостатки использованного алгоритма.

    1. Арифметическое кодирование

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

    1. LZ-сжатие данных.

Выполнить сжатие данных при помощи словарно-ориентированного алгоритма (конкретную версию выбрать самостоятельно). Продемонстрировать на примерах преимущества и недостатки использованного алгоритма.

    1. Код Хемминга

Реализовать (7,4) и (9,5) коды Хемминга. Выполнить сравнительный анализ избыточности и корректирующей мощности кодов.

    1. Помехоустойчивое кодирование.

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

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



VI. Перечень специализированных аудиторий, кабинетов и лабораторий с указанием используемого в учебном процессе по дисциплине основного учебно-лабораторного оборудования, технических средств обучения и контроля.

Стандартно оборудованные лекционные и семинарские аудитории, компьютерные классы.

В лекционных аудиториях желательно наличие проекционного оборудования.

Для проведения практических занятий используется компьютерный класс, оснащенный персональными компьютерами класса PC с возможностью организации широкополосного доступа в Интернет.


Необходимое программное обеспечение.

Состав программного обеспечения компьютерного класса: операционная система с графической операционной оболочкой (Microsoft Windows, GNU/Linux), веб-браузер, компилятор процедурного языка программирования высокого уровня, интегрированный пакет прикладных программ офисного назначения (Microsoft Office, StarOffice/OpenOffice/LibreOffice), файловый менеджер, архиватор, программа просмотра графических изображений с конвертором форматов, мультимедийный проигрыватель с пакетом распространенных кодеков/контейнеров.


База данных защищена авторским правом ©psihdocs.ru 2016
обратиться к администрации

    Главная страница