Четверг, 16.20 – 17.55, ауд. 782, с 3 октября

Специальный курс для студентов 3-5 курсов, читается в осеннем и весеннем семестрах.

Лекции – 68 часов.
Экзамен в весеннем семестре.
За курс отвечает кафедра нелинейных динамических систем и процессов управления.
Автор программы: проф. Шоломов Л.А.

 

Аннотация

 

В курсе излагаются классические результаты теории информации, связанные с информационными характеристиками случайных величин и их свойствами, сжатием данных, конструктивными методами помехоустойчивого кодирования, передачей информации при наличии помех. Наряду с ними значительное внимание уделяется новому направлению исследований – теории недоопределенной информации. Рассматривается также подход А.Н. Колмогорова к основаниям теории информации, связывающий информацию и сложность.

Для понимания материала достаточно знания некоторых элементарных фактов теории вероятностей, линейной и общей алгебры. Более углубленные математические сведения (например, элементы теории Галуа) излагаются непосредственно в курсе. Предназначен для студентов, начиная с третьего курса, и аспирантов.

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

Во вторую часть курса (весенний семестр) входит изучение теории помехоустойчивого кодирования, рассмотрение линейных и циклических кодов, изложение конструктивных методов построения кодов с хорошими корректирующими свойствами, изучение задачи надежной передачи данных в статистической постановке, рассмотрение характеристик системы передачи информации, доказательство теоремы Шеннона о скорости передачи при наличии помех, изложение алгоритмического подхода А.Н. Колмогорова к введению информационных характеристик индивидуальных последовательностей, сравнение статистического и алгоритмического подходов в применении к полностью определенным и к недоопределенным данным.

 

 

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

 

Лекции, осенний семестр

1. Мера информации

Общая схема передачи данных. Источник. Канал. Кодирование источника и канала, декодирование. Задачи сжатия данных и помехоустойчивого кодирования. Детерминированная и вероятностная постановки задач.

Информационные характеристики. Вогнутые функции, неравенство Иенсена. Случайный опыт. Энтропия случайного опыта. Свойства энтропии: неотрицательность, вогнутость, экстремальное свойство. Произведение случайных опытов. Неравенство для энтропии произведения. Условная энтропия. Правило сложения энтропий. Соотношение условной и безусловной энтропий. Мера информации. Ее свойства: неотрицательность, симметрия, ограниченность энтропией, невозрастание при преобразованиях.

2. Сжатие данных

Алфавитное кодирование. Разделимые коды. Свойство префикса. Представление деревьями. Неравенство Крафта. Теорема Макмиллана. Характеристика кодирования. Оптимальное кодирование Хаффмена. Метод кодирования Шеннона, связь средней длины кода с энтропией.

Сжатие данных. Блоковое кодирование, его характеристика. Теорема Шеннона о сжатии данных. Оценка полиномиального коэффициента через энтропийную функцию. Универсальное кодирование. Алгоритмы сжатия Лемпела-Зива. Постановка задачи кодирования с заданным критерием верности. Эпсилон-энтропия и W-энтропия. Принцип Шеннона.

 

3. Информационные свойства недоопределенных данных

Информационные характеристики. Недоопределенные символы и данные. Доопределение и частичное доопределение. Энтропия недоопределенного опыта. Устранение неопределенных символов. Явный вид энтропии в специальных случаях. Вычисление энтропии. Свойства энтропии недоопределенных данных: неотрицательность, условие равенства нулю, верхняя оценка, вогнутость. Энтропия произведения опытов. Сравнение свойств энтропии недоопределенных данных и энтропии Шеннона.

Условная энтропия недоопределенного опыта относительно всюду определенного. Правило сложения энтропий для этого случая. Информация во всюду определенном опыте относительно недоопределенного. Несимметрия меры информации.

Сжатие недоопределенных данных. Комбинаторная энтропия недоопределенных данных. Верхняя оценка методом случайного кодирования. Асимптотика комбинаторной энтропии. Задача кодирования недоопределенных источников. Теорема о сжатии недоопределенных данных. Распространение принципа Шеннона на недоопределенные данные. Эффект Нечипорука и его обобщение.

4. Некоторые алгоритмы для недоопределенных данных

Преобразования. Приведение. Функциональные преобразования. Информационно эквивалентные преобразования. Адекватный источник. Максимально определенный адекватный источник. Его единственность, построение. Понижение размерности недоопределенных данных. Декомпозиция.

Частичное доопределение. Частичное доопределение на основе совершенного хеширования. Хеширование делением с остатком. Линейное хеширование. Тестовый подход. Расширение тестового подхода. Градиентная процедура. Применение градиентной процедуры к задаче доопределения. Оценка мощности доопределяющего множества. Эффективизация градиентной процедуры с использованием проверочных матриц линейных кодов (Коспанов и Носков).

 

Лекции, весенний семестр

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

Кодирование и декодирование. Равномерные коды. Расстояние Хемминга. Кодовое расстояние и его связь с возможностью обнаружения и исправления ошибок. Границы мощности кодов. Верхняя граница Хемминга. Нижняя граница Гилберта. Другие типы расстояний в задачах исправления ошибок. Расстояние Варшамова. Расстояние Левенштейна. Арифметическое расстояние.

Линейные коды. Линейный код. Порождающая матрица. Приведенно-ступенчатая форма матрицы. Систематический код. Проверочная матрица линейного кода и ее связь с порождающей матрицей. Выражения для кодового расстояния линейных кодов. Граница Варшамова-Гилберта. Декодирование линейных кодов. Примеры линейных кодов. Код c проверкой на четность. Обобщенный код Хемминга. Коды Рида-Маллера. Их параметры.

Циклические коды. Циклический код. Порождающий многочлен. Общий способ построения циклических кодов. Вид порождающей матрицы. Проверочный многочлен. Вид проверочной матрицы. Нахождение приведенно-ступенчатой формы порождающей матрицы. Ее единственность. Кодирование циклических кодов. Декодирование. Примеры циклических кодов.

6. Конструктивное построение кодов

Поля Галуа. Поле Галуа GF(q). Порядок элемента. Порядок произведения элементов с взаимно простыми порядками. Многочлены над GF(q). Единственность разложения на неприводимые многочлены. Разложение многочлена –1 над GF(q). Существование примитивного элемента поля. Поле вычетов по модулю неприводимого полинома. Простое подполе и его единственность. Минимальный многочлен и его свойства. Разложение многочлена –1 над простым полем. Примитивный многочлен. Единственность и существование поля Галуа заданного порядка Построение поля Галуа и минимальных многочленов.

Конструкции кодов. Задание циклического кода совокупностью корней. Циклический код Хемминга. Его порождающий многочлен. Коды Боуза-Чоудхури-Хоквингема. Задание и построение. Кодовое расстояние и избыточность БЧХ-кодов.

Коды для других типов искажений. Код Варшамова-Тенненгольца для исправления несимметричной ошибки. Использование этого кода для исправления выпадения либо вставки символа (Левенштейн). Код Брауна для исправления арифметической ошибки.

7. Передача информации при наличии помех

Характеристики системы передачи информации. Вероятность ошибки. Скорость передачи. Пропускная способность канала. Двоичный симметричный канал и его пропускная способность. Пропускная способность несимметричного канала общего вида и канала со стиранием.

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

8. Алгоритмическая информация

Сложность по Колмогорову. Некоторые сведения из теории алгоритмов. Универсальная частично рекурсивная функция. Относительная сложность по заданной частично рекурсивной функции. Теорема оптимальности. Относительная сложность и сложность по Колмогорову. Их невычислимость. Мощностные нижние оценки сложности и относительной сложности. Мажоранты сложности для слов заданной длины и слов с заданным частотным составом букв. Оценки сложности и относительной сложности слов из заданных частотных классов через энтропийную функцию и условную энтропию.

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

Литература

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

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

2. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука, 1980.

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

4. Колмогоров А.Н. Алгоритм, информация, сложность. – М.: Знание, 1991.

5. Шоломов Л.А. Информационные свойства недоопределенных данных //Дискретная математика и ее приложения: Сборник лекций. Вып. IV. – М.: Изд. ИПМ РАН, 2007. С. 26-50.

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

1. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2006.

2. Чисар И., Кернер Я. Теория информации: Теоремы кодирования для дискретных систем без памяти. – М.: Мир, 1985.

3. Левенштейн В.И. Элементы теории кодирования // Дискретная математика и математические вопросы кибернетики. Т. 1. – М.: Наука, 1974. С. 207-302.

4. Шеннон К.Э. Работы по теории информации и кибернетике. – М.: ИЛ, 1963.

5. Яглом А.М., Яглом И.М. Вероятность и информация. – М.: КомКнига, 2006.

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

7. Кричевский Р.Е. Сжатие и поиск информации. М.: Радио и связь, 1989.