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

Тема 3. Кодирование дискретных источников сообщений
Алфавитное кодирование. Однозначно декодируемые, префиксные и суффиксные коды. Теорема о соответствии между префиксными кодами и кодовыми деревьями. Необходимое и достаточное условие существования префиксного кода с заданными длинами кодовых слов – неравенство Крафта. Необходимое и достаточное условие однозначного декодирования – неравенство Мак-Миллана.
Задача оптимального кодирования. Теорема об оценке средней длины оптимального префиксного кода. Теорема о пределе средней длины кодового слова при кодировании длинных блоков.
Алгоритмы Фано и Хаффмана. Леммы о строении оптимального кода. Теорема об оптимальности кода Хаффмана.
Тема 4. Дискретные каналы связи
Математическая модель канала связи и его информационные характеристики. Дискретный стационарный канал без памяти (ДКБП). Примеры – двоичный симметричный канал, канал со стиранием.
Определение пропускной способности. Теоремы о пропускной способности последовательного соединения, параллельного соединения и суммы двух ДКБП.
Симметричные каналы связи. Утверждения о пропускной способности симметричных каналов. Примеры вычисления пропускной способности. Геометрическое представление пропускной способности.
Тема 5. Теоремы кодирования для дискретных каналов без памяти
Скорость передачи информации. Декодер общего вида и решающие области. Ошибочное декодирование, условная и средняя вероятности ошибочного декодирования.
Неравенство Фано. Свойства функции Фано. Обратная теорема кодирования для ДКБП.
Типичные входные и выходные векторы и пары векторов. Декодер типичных пар. Леммы о совместной асимптотической равнораспределённости. Прямая теорема кодирования для ДКБП.
Тема 6. Коды, исправляющие ошибки
Задача помехоустойчивого кодирования при передаче информации по каналу связи с шумом. Блоковые коды. Декодирование по методу максимума правдоподобия и в ближайшее кодовое слово, условия эквивалентности этих методов. Леммы о связи числа ошибок, гарантированно обнаруживаемых и исправляемых при использовании блокового кода, с минимальным кодовым расстоянием. Примеры – код с повторением, код с проверкой на чётность.
Определение линейного кода, дуального кода, их параметры. Порождающая и проверочная матрицы линейного кода, их свойства. Свойства системы столбцов проверочной матрицы. Комбинаторная эквивалентность кодов, систематические коды. Таблица стандартного расположения, алгоритм декодирования.
Таблица Слепяна, алгоритм декодирования. Синдромы и их свойства, алгоритм декодирования с использованием синдромов. Теорема о максимальности вероятности правильного декодирования при использовании таблицы Слепяна.
Граница Синглтона. Коды с максимально допустимым расстоянием. Верхняя граница Хэмминга. Плотно упакованные коды.
Понятие циклического кода. Соответствие между векторами и многочленами, между циклическими кодами и идеалами факторкольца кольца многочленов.