Читать онлайн «Заметки по теории кодирования»

А. Ромащенко, А. Румянцев, А. Шень Заметки по теории кодирования Москва Издательство МЦНМО, 2011 ББК 22. 1 Р47 Ромащенко А. Е. , Румянцев А. Ю. , Шень А. Р47 Заметки по теории кодирования. | М. : МЦНМО, 2011. | 80 с. ISBN 978-5-94057-750-8 В этих заметках, написанных по материалам лекций М. Судана в Массачусет- ском технологическом институте (с его любезного разрешения), излагаются базовые результаты теории кодирования, а также некоторые более новые её достижения, представляющие интерес для computer science. Книга рассчитана на математиков и программистов (начиная со студентов младших курсов), впервые знакомящихся с теорией кодирования. ББК 22. 1 Оригинал-макет предоставлен авторами. Книга является свободно распространяемой; электронная версия доступна по адресу ftp://ftp. mccme. ru/users/shen/coding. zip (исходные тексты) и ftp://ftp. mccme. ru/users/shen/coding. pdf (файл книги) Андрей Евгеньевич Ромащенко Андрей Юрьевич Румянцев Александр Шень Заметки по теории кодирования Редакторы И. П. Разенштейн, В. В. Шувалов Подписано в печать 31. 03. 2011 г. Формат 60 × 90 1/16. Бумага офсетная. Печать офсетная. Гарнитура тип таймс. Печ. л. 5. Тираж 1000 экз. Заказ Ђ Издательство Московского центра непрерывного математического образования 119002, Москва, Большой Власьевский пер. , 11. Тел. (499) 241-74-83. Отпечатано с готовых диапозитивов в ООО «Красногорская типография». 143400, Московская область, г. Красногорск, Коммунальный квартал, д. 2. c ○ Ромащенко А. Е. , Румянцев А. Ю. , ISBN 978-5-94057-750-8 Шень А. , 2011. Предисловие Слово «кодирование» в названии этой книжки не означает шифрования (сохранения сообщения в секрете) | этим занимается не теория коди- рования, а криптография, которой мы не касаемся); не идёт речь также о теоретических и практических проблемах перехода от одной кодировки символов к другой. Основной вопрос теории кодирования | как записать сообщение в такой форме, чтобы искажение некоторой части записи (на- пример, при передаче данных) не помешало восстановлению сообщения в исходной форме. 𝑥 кодер 𝑐 𝑦 = 𝑐 (𝑥 ) канал декодер 𝑑 𝑥 = 𝑑 (𝑦 ) ′ ′ связи 𝑦 ′ ≈𝑦 Имеется в виду, что исходное сообщение 𝑥 (последовательность битов или других символов) преобразуется в некоторую другую (более длин- ную) последовательность 𝑦 . Затем 𝑦 передаётся по каналу связи с по- мехами (или хранится на ветхом носителе), превращаясь при этом в 𝑦 ′ . Наконец, из 𝑦 ′ извлекается сообщение 𝑥 ′ , которое должно совпадать с исходным (𝑥 ). Например, мы можем повторить каждую букву сообщения 𝑥 три раза, получив втрое более длинное сообщение 𝑦 . Если одна из букв в слове 𝑦 испортится, это не помешает восстановить 𝑥 . В этом примере алгоритм кодирования (кодер) 𝑐 утраивает каждую букву, а алгоритм декодиро- вания (декодер) 𝑑 берёт наиболее частую букву в каждой тройке.