Теория кодирования

все курсы

Теория кодирования

Курс находится на модерации. Данные могут быть неактуальны.

3.3

11 недель

Тип обучения

Курс

Зач. единицы

Сертификат

1 800 ₽ для получения

Стоимость курса

бесплатно

нет рассрочки

Теория кодирования — изучение свойств кодов и их пригодности для достижения поставленной цели. Кодирование информации — это процесс её преобразования из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения, автоматической переработки и сохранения от несанкционированного доступа. К основным проблемам теории кодирования относят вопросы взаимной однозначности кодирования и сложности реализации канала связи при заданных условиях. В этой связи, теория кодирования преимущественно рассматривает следующие направления: сжатие данных, прямая коррекция ошибок, криптография, физическое кодирование, обнаружение и исправление ошибок. Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей. Студентам МФТИ для получения бесплатного доступа к тестовым заданиям и экзамену необходимо написать на openedu@mipt.ru письмо с указанием названия курса, логина на openedu, и скриншотом личного кабинета, на котором виден статус обучения.

Вас будут обучать

Дайняк Александр Борисович

курсов

Кандидат физико-математических наук Должность: Преподаватель

Образовательная организация

Московский физико-технический институт

1 отзыв

Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира.

Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.

Основой образования в МФТИ является уникальная «система Физтеха», сформулированная Петром Капицей: кропотливый отбор одаренных и склонных к творческой работе абитуриентов; участие в обучении ведущих научных работников; индивидуальный подход к отдельным студентам с целью развития их творческих задатков; воспитание с первых шагов в атмосфере технических исследований и конструктивного творчества с использованием потенциала лучших лабораторий страны.

Среди выпускников МФТИ — нобелевские лауреаты Андрей Гейм и Константин Новоселов, основатель компании ABBYY Давид Ян, один из авторов архитектурных принципов построения вычислительных комплексов Борис Бабаян.

Открытое образование

3.7

31 отзыв

Новый элемент системы российского образования — открытые онлайн-курсы — cможет перезачесть любой университет. Мы делаем это реальной практикой, расширяя границы образования для каждого студента. Полный набор курсов от ведущих университетов. Мы ведём системную работу по созданию курсов для базовой части всех направлений подготовки, обеспечивая удобное и выгодное для любого университета встраивание курса в свои образовательные программы
«Открытое образование» – это образовательная платформа, предлагающая массовые онлайн-курсы ведущих российских вузов, которые объединили свои усилия, чтобы предоставить возможность каждому получить качественное высшее образование.

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

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

Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова.
Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона, Плоткина.
Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса—Бассалыго.
Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
Остаточный код. Граница Грайсмера—Соломона—Штиффлера.
Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
Коды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча.
Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.
Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Спилмана.
Теоремы Шеннона для вероятностной модели канали.
Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема Мак-Элиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации в задаче MAX-SAT.