Реферат: Задачи изучения дисциплины (необходимый комплекс знаний и умений). 2 Иметь представления о: алгебраических методах построения кодов, исправляющих ошибки

ТЕОРИЯ ИНФОРМАЦИИ

Кафедра теории вероятностей и математической статистики факультета физико-математических и естественных наук Российского университета дружбы народов


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


Объем учебной нагрузки:36 часов – лекции, 36 часов – лабораторные занятия

Цель курса
1. Цель и задачи дисциплины

1.1. Цель преподавания дисциплины

Основная цель изучения дисциплины – дать углубленное представление о приложениях алгебраических и вероятностных методов в теории информации и кодирования. Особое место уделяется циклическим кодам и кодам Рида-Соломона.

^ 1.2. Задачи изучения дисциплины (необходимый комплекс знаний и умений).

1.2.1. Иметь представления о:

алгебраических методах построения кодов, исправляющих ошибки;

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

методах сжатия данных;

1.2.2. Знать:

принципы построения кодов, исправляющих ошибки;

методы сжатия данных.

1.2.3. Уметь:

формализовать задачи кодирования;

анализировать коды, связанные с математической формализацией задачи кодирования.

^ 1.2.4. Иметь опыт:

формализации задач кодирования;

анализ и синтез методов, связанных с математической формализацией задач кодирования.

Содержание курса

Тема 1 Энтропия

Понятие энтропии. Свойства энтропии. Примеры.

Понятия и свойства совместной и условной энтропии. Примеры.

Понятия относительной энтропии и взаимной информации. Теорема о взаимной информации и энтропии. Цепное правило для энтропии, относительной энтропии и взаимной информации. Примеры.

Неравенство Ианцена и ее следствия. Некоторые неравенства и их применение в теории информации. Неравенство Фано. Примеры.

Асимптотическое свойство эквипартиции и его применение в сжатии данных.

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

Тема 2 Сжатие данных

Примеры кодов. Неравенство Крафта и его обобщение.

Оптимальные коды.

Коды Хоффмана и коды Шеннона. Коды Шеннона-Фано-Элайеса. Оптимальность кодов Хоффмана. Примеры.

Арифметическое кодирование. Кодирование Лемплея-Зива. Примеры.

Тема 3 Дискретные каналы без памяти

Двоичный симметричный канал.

Пропускная способность канала.

Тема 4 Непрерывные источники и каналы

Дифференциальная энтропия.

Пропускная способность канала и принцип Шеннона. Примеры.

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

Линейные блочные коды. Порождающая матрица. Синдромное декодирование. Расстояние Хэмминга, совершенные коды и граница Хэмминга. Расширенные коды Хэмминга.

Циклические коды. Определение и общие свойства. Систематические циклические коды. Порождающая матрица и матрица контроля четности. Схемная реализация циклического кодирования. Синдром циклических кодов и контроль ошибок. Примеры: циклические коды Хэмминга, двоичный код Голлея, CRC коды, укороченные коды, АТМ.

Сверточные коды и их структура. Декодирование по максимуму правдоподобия.

Циклические коды. Определение и общие свойства. Систематические циклические коды. Порождающая матрица и матрица контроля четности. Схемная реализация циклического кодирования. Синдром циклических кодов и контроль ошибок. Примеры: циклические коды Хэмминга, двоичный код Голлея, CRC коды, укороченные коды, АТМ.

Дискретные преобразования Фурье в конечных полях.

Коды Рида-Соломона. Декодирование кодов Рида-Соломона.

Тематика курсовых работ

Курсовые работы по данной дисциплине не предусмотрены.


Литература

Основная

Вернер М. Основы кодирования, - М.: Техносфера, 2004, - 286с.

Яглом А.М., Яглом И.М. Вероятность и информация. - М.: Наука, 1973.

Шеннон К. Математическая теория связи. – В сб.: Работы по теории информации и кибернетики. - М.: ИЛ, 1963.

Галлагер Р. Теория информации и надежная связь. - М.: «Советское радио», 1974.

Дополнительная

Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов исправляющих ошибки. - М.: Связь, 1979.

Лидл Р., Нидеррайтер Г. Конечные поля, т. 1, 2, - М.: Мир, 1988.


Программа составлена

М.С.Аль-Натор,

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