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

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

Лекции читаются на 4-м курсе, VII-семестр,

51 час, лектор доцент

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

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

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

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

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

Теория помехоустойчивого кодирования. Критерий максимального правдоподобия. Кодовое расстояние. Линейные коды и алгоритм их декодирования. Код Хэмминга. Циклические коды. Кодирование и декодирование циклических кодов.

Л И Т Е Р А Т У Р А

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

1979.

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

3. урс теории информации, Наука, 1982

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

5. оды, исправляющие ошибки, М., Мир, 1976.

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