girniy.ru 1

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

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Московский физико-технический институт (государственный университет)»

МФТИ (ГУ)


«Утверждаю»

Проректор по учебной работе

_______________ Д.А.Зубцов

«___»______________ 20___ г.


Рабочая УЧЕБНАЯ Программа


По дисциплине: Избранные главы теории кодирования

По направлению: 010900 «Прикладные математика и физика»

Профиль подготовки: инфокоммуникационные и вычислительные системы и технологии

Факультет радиотехники и кибернетики

Кафедра проблем передачи и обработки информации

Курсы: 4 (бакалавриат)

Семестры: весенний Экзамен: 8 семестр


Трудоёмкость: вариативная часть – 3 зач.ед.,

в том числе:

лекции: вариативная часть – 64 часа

самостоятельная работа: вариативная часть – 14 часов

подготовка к экзамену: вариативная часть – 1 зач.ед.


ВСЕГО АУДИТОРНЫХ часов 64


Программу составили д.т.н., доцент Зигангиров К.Ш., д.ф.-м.н. Кабатянский К.Ш.


Программа обсуждена на заседании кафедры 28 мая 2012 года


Заведующий кафедрой А.П. Кулешов

академик РАН

Объем учетной нагрузки и виды отчетности





Вариативная часть, в том числе:

3 зач.ед.


Лекции

64 часа


Самостоятельные занятия

14 часов


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


нет

Итоговая аттестация


экзамен в 8-м семестре (1 зач.ед.)

ВСЕГО

3 зач.ед. (78 часов + 1 зач.ед.)



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



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

Задачи:

  • фундаментальная подготовка студентов в области теории информации и теории кодирования;

  • построение у студентов навыков применения теории информации и теории кодирования при конструировании и исследовании телекоммуникационных сетей и систем;

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



  1. Место дисциплины в структуре ООП бакалавриата



Дисциплина «Избранные главы теории кодирования» включает в себя разделы, которые могут быть отнесены к вариативной части цикла Б.3 УЦ ООП.

Дисциплина «Избранные главы теории кодирования» базируется на циклах Б.2 и Б.3 в базовой и вариативной частях.

  1. Компетенции, формированию которых способствует освоение дисциплины


Освоение дисциплины «Избранные главы теории кодирования» способствует формированию следующих общекультурных и общепрофессиональных интегральных компетенций бакалавра:


а) общекультурные (ОК):


  • способность анализировать научные проблемы и физические процессы, использовать на практике фундаментальные знания, полученные в области естественных наук (ОК-1);

  • способность осваивать новую проблематику, терминологию, методологию и овладевать научными знаниями и навыками самостоятельного обучения (ОК-2);

  • способность логически точно, аргументировано и ясно строить устную и письменную речь, формулировать свою точку зрения; владение навыками ведения научной и общекультурной дискуссий (ОК-4).

б) профессиональные (ПК):

  • способность применять в своей профессиональной деятельности знания, полученные в области физических и математических дисциплин, включая дисциплины: информатика, программирование и численные методы; физические основы получения, хранения, обработки и передачи информации; высшая математика (ПК-1);

  • способность понимать сущность задач, поставленных в ходе профессиональной деятельности, и использовать соответствующий физико-математический аппарат для их описания и решения (ПК-3);

  • способность использовать знания в области физических и математических дисциплин для дальнейшего освоения дисциплин в соответствии с профилем подготовки (ПК-4);

  • способность применять теорию и методы математики для построения качественных и количественных моделей (ПК-8);

  • способность работать в коллективе исполнителей над решением конкретных исследовательских и инновационных задач (ПК-9).



  1. Знания, умения и навыки, формированию которых способствует освоение дисциплины



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

а) знать:

- основные понятия и утверждения теории информации;


- основные понятия и утверждения теории кодирования;

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

б) уметь:

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

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

в) владеть:

- навыком освоения большого объема информации;

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

  1. Структура и содержание дисциплины



Лекции

№ п.п.

Тема

Число аудиторных часов

Число часов самостоятельной работы

1

Введение. Передача данных.

Передача данных и хранение информации.

Методы модуляции.

Каналы связи. Модели каналов.

Прием сигналов. Обнаружение сигналов.

4

1

2

Элементы теории информации и кодирование дискретных источников сообщений.

Основные определения и соотношения теории информации. Метод типов.

Кодирование дискретных источников сообщений.

Универсальное кодирование.

6

1

3


Общая теория блоковых кодов.

Блоковые коды – основные характеристики.

Линейные коды, двойственность. Коды Хэмминга и симплекс-коды.

Метод случайного кодирования и пропускная способность канала.

Задачи сложности в теории кодирования.

8

2

4

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

Коды Рида-Соломона и коды БЧХ как их подкоды.

Алгоритмы декодирования (списочного) кодов Рида-Соломона.

Полиномы Жегалкина и коды Рида-Маллера, их декодирование.

Годы Гоппы и введение в алгебро-геометрические коды.

Каскадные конструкции.

10

2

5

Коды на графах.

Коды на графах и вычислительное дерево.

Блоковые коды с малой плотностью проверок (КМПП) на четность.

Характеристики блоковых КМПП.

Алгоритмы итеративного декодирования блоковых КМПП.

Методы анализа блоковых КМПП. Пороги.

Обобщенные блоковые КМПП.

Коды на экспандерах(расширителях)

10

2

6

Общая теория свер(х:-)точных кодов.

Сверточные коды – основные определения и характеристики.

Методы декодирования сверточных кодов.

Апостериорно-вероятностное декодирование сверточных кодов.

Конструкции турбо кодов.

Итеративное декодирование турбо кодов.

Многоуровневые турбо коды.

10

2


7

Сверточные КМПП.

Построение сверточных КМПП.

Сверточные перемежители.

Конвеерное декодирование сверточных КМПП.

Анализ порогов сверточных КМПП.

Другие итеративно декодируемые сверточные КМПП.

8

2

8

Другие приложения кодов.

Коды, дискретная геометрия и сигналы.

Коды и защита информации(post-quantum cryptography).

Коды для каналов с множественным доступом и задачи поиска.

8

2

ВСЕГО

64 часа

14 часов

ИТОГО

78 часов



Виды самостоятельной работы

№ п.п.

Темы

Количество часов

1

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

7

2

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


7

3

Подготовка к экзамену

1 зач.ед.

ВСЕГО

14 часов + 1 зач.ед.



  1. Образовательные технологии




п/п

Вид занятия

Форма проведения занятий

Цель

1

Лекция

Изложение теоретического материала

Получение теоретических знаний по дисциплине

2

Самостоятельная работа студента

Самостоятельная работа

Получение дополнительных знаний и подготовка к экзамену



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



Перечень контрольных вопросов для сдачи экзамена в 8-ом семестре

п.п.

Тема

1

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


2

По какому критерию выбираются в настоящее время помехоустойчивые коды и методы их декодирования при построении систем передачи данных?

3

На чем были сосредоточены усилия ученых, работавших в области теории кодирования в 60-80 гг. прошлого века, и каковы проблемы, решаемые современными исследователями в этой области?

4

Дайте определение сверточного кода. Какие методы декодирования сверточных кодов вы знаете?

5

Как определяется свободное расстояние сверточного кода? Сформулируйте границы для свободного расстояния. От чего они зависят?

6

Какие коды используются в турбо-кодах в качестве компонентных кодов?

7

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

8

Какие два класса блоковых кодов с малой плотностью проверок (КМПП) на четность вы знаете?

9

Опишите асимптотические характеристики блоковых КМПП кодов при длинах кодов, стремящихся к бесконечности.

10

Какие итеративные алгоритмы декодирования КМПП кодов вы знаете? Сравните их сложности.

11

Опишите алгоритм построения сверточных КМПП кодов.

12

Как ведут себя сверточные КМПП коды когда память кода стремится к бесконечности? В частности, куда стремятся пороги? Сравните их поведение с поведением порогов блоковых КМПП кодов.




  1. Материально-техническое обеспечение дисциплины




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

Обеспечение самостоятельной работы: электронные ресурсы, конспекты.

  1. Учебно-методическое и информационное обеспечение дисциплины



Основная литература




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

2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир. 1976.

3. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир. 1986.

4. Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные понятия. МЦНМО, 2003.

5. Сагалович Ю.Л. Введение в алгебраические коды. М.: Минобразования РФ, Агентство по печати; МФТИ; ИППИ РАН, 2007.

6. Сидельников В.М. Теория кодирования. М.: Физматлит, 2008.


7. Ромащенко А., Румянцев А., Шень А. Заметки по теории кодирования. МЦНМО, 2011.

8. Johannesson R., Zigangirov K.Sh. Fundamentals of convolutional coding. IEEE Press. 1999.