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

Специалитет 2019/2020

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Компьютерная безопасность)

Кто читает: Кафедра компьютерной безопасности

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 4-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Преподаватели: Миронкин Владимир Олегович

Специальность: 10.05.01. Компьютерная безопасность

Язык: русский

Кредиты: 3

Контактные часы: 40

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

Аннотация

Данная дисциплина относится к вариативной профильной части Профессионального цикла (Major), проводится на 4 курсе обучения и является обязательной. Для освоения учебной дисциплины студенты должны владеть базовыми знаниями и компетенциями, полученными при изучении следующих дисциплин: Теория вероятностей и математическая статистика, Теория информации, Системы и сети передачи информации. Результаты освоения дисциплины используются в дальнейшем при изучении таких дисциплин, как Компьютерные системы и сети, Модели безопасности компьютерных систем, Криптографические методы защиты информации, Компьютерные системы и сети.

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

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

Планируемые результаты обучения

Знать базовые понятия теории кодирования
Знать методы кодирования дискретных источников информации
Знать основные методы сжатия информации
Знать основные методы восстановления информации
Уметь строить модели источников информации
Уметь оценивать пропускную способность канала связи
Уметь строить оптимальные и помехоустойчивые коды для каналов с шумом
Владеть навыками кодирования дискретных источников информации
Владеть навыками применения методов сжатия информации
Владеть навыками применения методов восстановления информации

Содержание учебной дисциплины

Кодирование дискретных источников сообщений.
Алфавитное кодирование. Однозначно декодируемые, префиксные и суффиксные коды. Теорема о соответствии между префиксными кодами и кодовыми деревьями. Необходимое и достаточное условие существования префиксного кода с заданными длинами кодовых слов – неравенство Крафта. Необходимое и достаточное условие однозначного декодирования – неравенство Мак-Миллана. Задача оптимального кодирования. Теорема об оценке средней длины оптимального префиксного кода. Теорема о пределе средней длины кодового слова при кодировании длинных блоков. Алгоритмы Фано, Шеннона и Хаффмана. Леммы о строении оптимального кода. Теорема об оптимальности кода Хаффмана.
Теоремы кодирования для дискретных каналов без памяти
Скорость передачи информации. Декодер общего вида и решающие области. Ошибочное декодирование, условная и средняя вероятности ошибочного декодирования. Неравенство Фано. Свойства функции Фано. Обратная теорема кодирования для ДКБП. Типичные входные и выходные векторы и пары векторов. Декодер типичных пар.Леммы о совместной асимптотической равно распределённости. Прямая и обратная теорема кодирования для ДКБП.
Коды, исправляющие ошибки
Задача помехоустойчивого кодирования при передаче информации по каналу связи с шумом. Блоковые коды. Декодирование по методу максимума правдоподобия и в ближайшее кодовое слово, условия эквивалентности этих методов. Леммы о связи числа ошибок, гарантированно обнаруживаемых и исправляемых при использовании блокового кода, с минимальным кодовым расстоянием. Определение линейного кода, дуального кода, их параметры. Порождающая и проверочная матрицы линейного кода, их свойства. Примеры – код с повторением, код с проверкой на чётность. Свойства системы столбцов проверочной матрицы. Комбинаторная эквивалентность кодов, систематические коды. Таблица стандартного расположения, алгоритм декодирования. Граница Синглтона. Коды с максимально допустимым расстоянием. Верхняя граница Хэмминга. Плотно упакованные коды. Порождающий и проверочный многочлены циклического кода, их свойства. Связь порождающего и проверочного многочленов циклического кода с порождающей и проверочной матрицами.Порождающий и проверочный многочлены циклического кода, их свойства. Связь порождающего и проверочного многочленов циклического кода с порождающей и проверочной матрицами. Алгоритмы кодирования и декодирования для циклического кода. Задание циклического кода. Семейство кодов Хэмминга и их параметры.

Элементы контроля

Самостоятельная работа 1
Самостоятельная работа 2
Самостоятельная работа 3
Самостоятельная работа 4
Самостоятельная работа 5
Контрольная работа
Аудиторная активность
Экзамен

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.1 * Аудиторная активность + 0.2 * Контрольная работа + 0.04 * Самостоятельная работа 1 + 0.04 * Самостоятельная работа 2 + 0.04 * Самостоятельная работа 3 + 0.04 * Самостоятельная работа 4 + 0.04 * Самостоятельная работа 5 + 0.5 * Экзамен

Программа дисциплины