birmaga.ru
добавить свой файл

1
Программа курса


«Теория информации и кодирования»
Лекции читаются на 4-м курсе, VII-семестр,

51 час, лектор доцент Салимов Ф.И.
Понятие информации, энтропии. Системы связи. Дискретные источники. Описание источника при помощи случайного процесса. Статистическая независимость. Марковские источники. Эргодичность. Эргодичность бернуллиевского источника.

Вывод формулы энтропии (по Фадееву). Взаимная информация, и её свойства. Свойства энтропии. Теорема о максимальном значении энтропии. Энтропия в единицу времени источника сообщений.

Задача кодирования дискретного источника кодами равной длины. Скорость кодирования. Высоковероятностные множества. Прямая и обратная теоремы кодирования дискретного источника кодами равной длины.

Задача кодирования источника кодами неравной длины. Стоимость кодирования. Однозначно дешифрируемые коды. Префиксные коды. Побуквенное кодирование. Необходимое и достаточное условие однозначной дешифрируемости кода. Полные коды. Теорема кодирования дискретного источника кодами неравной длины. Алгоритмы построения оптимальных кодов (Фано, Шеннона, Хаффмена). Построение бинарного оптимального кода при равновероятностном распределении входных вероятностей. Приложение результатов теории информации при доказательстве нижних и верхних оценок сложности реализации булевых функций в некоторых классах управляющих систем. Метод построения оптимального кода при условии, что неизвестно распределение вероятностей букв источника. Теорема Маркова об однозначной дешифрируемости кода. Адаптивные алгоритмы сжатия информации.

Дискретный канал без памяти. Двоичный симметричный канал. Скорость передачи информации в канале. Пропускная способность канала. Расширенный канал и его пропускная способность. Решающие схемы и группировки наблюдений. Вероятность ошибочной передачи информации. Неравенство Файнстейна. Прямая теорема кодирования канала без памяти. Неравенство Фано. Теорема обработки информации. Обращение теоремы кодирования.


Теория помехоустойчивого кодирования. Критерий максимального правдоподобия. Кодовое расстояние. Коды с проверкой на четность. Порождающая и проверочные матрицы. Синдром. Алгоритм декодирования для кодов с проверкой на четность. Линейные коды и алгоритм их декодирования. Граница Хэмминга. Код Хэмминга. Циклические коды. Кодирования и декодирование циклических кодов.
ЛИТЕРАТУРА


  1. Галлагер Р. Теория информации и надежная связь., М., Сов. Радио, 1979.

  2. Кричевский Е. Лекции по теории и информации, Новосибирск, НГУ, 1966.

  3. Колесник В., Полтырев Г. Курс теории информации, Наука, 1982.

  4. Файнстейн А. Основы теории информации, М., ИЛ, 1960.

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

  6. Бэрлекамп Алгебраическая теория кодирования, М., Мир, 1971.