Теория информации и кодирования

Цели и задачи дисциплины

Цель дисциплины - дать студентам общие знания о теоретических основах, на которых базируются прикладные аспекты информатики, в том числе проблемы кодирования, передачи информации, анализа информационных систем. Задачи дисциплины: а) изучение новых научных результатов, научной литературы или научно-исследовательских проектов в соответствии с профилем объекта профессиональной деятельности, б) дать знания: об истории и развитии теории кодирования как научной дисциплины; об основных подходах к количественной оценке информации; о связи понятий информации и энтропии как меры неопределенности; о прикладном значении теории кодирования. в) сформировать умения: вычисления количества информации по заданному вероятностному распределению случайных событий; оценки предельных характеристик источника сообщений и канала связи; формирования оптимальных кодов при наличии и отсутствии шумов в системе передачи информации; оценки ошибок представления непрерывной информации в дискретной форме; г) привить навыки: применения знаний в области теории вероятностей и математической статистики к решению типовых задач теории кодирования; использования вычислительных методов и алгоритмов в задачах определения энтропии и количества информации, оценки предельных возможностей информационных систем, оптимального кодирования и передачи сигналов.

Краткое содержание дисциплины

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

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

Выпускник должен обладать:

ПК-6 Способен использовать математические методы при проектировании и разработке алгоритмических и программных решений в области обеспечения безопасности и защиты программных систем.