А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104)
Текст из файла
А. Ромащенко, А. Румянцев, А. ШеньЗаметки по теории кодированияМоскваИздательство МЦНМО, 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.ПредисловиеСлово «кодирование» в названии этой книжки не означает шифрования(сохранения сообщения в секрете) | этим занимается не теория кодирования, а криптография, которой мы не касаемся); не идёт речь такжео теоретических и практических проблемах перехода от одной кодировкисимволов к другой. Основной вопрос теории кодирования | как записатьсообщение в такой форме, чтобы искажение некоторой части записи (например, при передаче данных) не помешало восстановлению сообщенияв исходной форме.кодер = ( ) каналсвязи′≈′′декодер = ( )Имеется в виду, что исходное сообщение (последовательность битовили других символов) преобразуется в некоторую другую (более длинную) последовательность .
Затем передаётся по каналу связи с помехами (или хранится на ветхом носителе), превращаясь при этом в ′ .Наконец, из ′ извлекается сообщение ′ , которое должно совпадать сисходным ( ).Например, мы можем повторить каждую букву сообщения три раза,получив втрое более длинное сообщение . Если одна из букв в слове испортится, это не помешает восстановить . В этом примере алгоритмкодирования (кодер) утраивает каждую букву, а алгоритм декодирования (декодер) берёт наиболее частую букву в каждой тройке.
Этотпростейший код позволяет исправлять одну ошибку. (А для исправлениядвух ошибок достаточно повторять каждую букву пять раз.)Придумывая код (способы кодирования и декодирования), мы хотимсразу многого:∙ чтобы код позволял исправлять возможно большее число ошибок;∙ чтобы избыточность кода (насколько длиннее ) была бы поменьше;∙ наконец, чтобы кодирование и декодирование выполнялись бы простыми алгоритмами.Эти требования к коду во многом противоречат друг другу, и различные варианты компромисса между ними и составляют предмет теории4Предисловиекодирования.
(Отметим сразу же, что повторение символов, о которомшла речь | далеко не наилучший способ!)Вопрос о том, при каких сочетаниях параметров (избыточность и число исправляемых ошибок) такое возможно, до сих пор остаётся открытым, хотя придумано множество различных кодов, часто с использованием сложной математической техники (например, алгебраической геометрии). Вместе с тем многие важные результаты можно изложить, ограничиваясь лишь начальными сведениями из алгебры (многочлены и поля,векторные пространства над полем из двух элементов). Такое изложениеи составляет предмет этой книжки, предназначенной для первого знакомства (будущих) программистов и математиков с основными результатамитеории кодирования.
В неё включены также некоторые более новые результаты (декодирование списком, теорема Голдрайха { Левина, связь сэкспандерами).***Большая часть этих заметок была сделана участниками семинара кафедры математической логики и теории алгоритмов механико-математического факультета МГУ в 2004/5 учебном году, разбиравшими записи лекций Мадху Судана в Массачусетском технологическом институте(по выложенным в интернете на домашней странице Судана материалам,см. http://theory.csail.mit.edu/~madhu).
Рассказывали на семинаре в основном А. Ромащенко и А. Румянцев, текст подготовил к печатиА. Шень.Мы благодарны Мадху Судану за любезное разрешение использоватьего материалы при подготовке текста, и предупреждаем, что возможныеошибки в этом пересказе целиком на нашей совести. Мы благодарим также Григория Кабатянского и Сергея Еханина, которые посмотрели этоттекст и указали на некоторые (ныне исправленные) ошибки.А. Ромащенко, А. Румянцев, А. Шень51.
ëÏÄÙ Ó ÉÓÐÒÁ×ÌÅÎÉÅÍ ÏÛÉÂÏË: ÐÏÓÔÁÎÏ×ËÁ ÚÁÄÁÞÉ1. Коды с исправлением ошибок:постановка задачиПусть ˚ | конечный алфавит (множество букв ). Через ˚ мы обозначаем множество всех слов (конечных последовательностей букв) длины в алфавите ˚. Расстояние Хэмминга между двумя словами . . . и .
. . из ˚ определяется как число позиций, в которых эти словаотличаются (число тех , при которых ̸= ).Рассмотрим отображение : ˚ → ˚ при < как способ кодирования информации при её передаче. Получив на вход слово ∈ ˚ , мыпередаём по каналу связи слово (). В процессе передачи некоторыесимволы слова () могут быть искажены. Несмотря на это, мы хотим,чтобы было возможно восстановить исходное слово .
Другими словами,мы хотим, чтобы () нельзя было спутать с (′ ) даже после того, какнекоторые буквы в обоих словах искажены. Если разрешается искажатьне более позиций (в каждом слове), то для однозначного восстановления необходимо и достаточно, чтобы расстояние между () и (′ )было 2 + 1 или больше.Более формально, кодом называется отображение : ˚ → ˚ . Значения этого отображения называются кодовыми словами. Минимальноеиз расстояний ( (), (′ )) при ̸= ′ называется минимальнымрасстоянием кода . Код с минимальным расстоянием позволяет исправлять = ⌊( − 1)/2⌋ ошибок, поскольку при таком шары радиуса с центрами в кодовых словах не пересекаются.
(Шар радиуса с центромв слове ∈ ˚ определяется как множество всех слов, отличающихся от не более чем в позициях. Через ⌊ ⌋ обозначается целая часть числа , то есть наибольшее целое число, не превосходящее .)Такая «помехоустойчивость» кода возникает, как говорят, за счёт «избыточности» при передаче информации: вместо символов мы передаём символов, при этом > . Чем больше и чем ближе к , темлучше код. Конечно, эти два требования противоречат друг другу и однодостигается за счёт другого.Задачу построения оптимального кода при данных ˚, и можноинтерпретировать геометрически: в метрическом пространстве ˚ нужноупаковать без пересечений как можно больше шаров радиуса .
Другойвариант формулировки: требуется найти как можно больше точек с попарными расстояниями 2 + 1 или больше. После того как шары (ихцентры) выбраны, можно взять , равное целой части логарифма числатаких шаров (точек) по основанию |˚| (число букв во входном алфавите),1162. âÁÚÏ×ÙÅ ÏÃÅÎËÉи произвольно сопоставить слова длины с центрами шаров. (Число выбрано максимально возможным, при котором шаров хватит.)Выбор этого соответствия (между кодируемыми словами и их кодами)безразличен, пока мы не интересуемся сложностью алгоритмов кодирования и декодирования.
Алгоритм кодирования вычисляет функцию , тоесть по входному слову даёт ( ). Алгоритм декодирования с исправлением ошибок получает на вход слово , отстоящее от некоторогокодового слова ( ) на расстояние не больше , и даёт на выходе.Естественно, мы хотим, чтобы алгоритмы кодирования и декодированиябыли не очень сложными и работали быстро.2. Базовые оценкиПри каких значениях параметров = |˚|, , , код : ˚ → ˚ , исправляющий ошибок, существует, а при каких нет? Две самые простыеоценки (с той и другой стороны) таковы.Граница ХэммингаЕсли код с указанными параметрами существует, то (, ) 6 .Здесь через (, ) обозначается объём (число элементов) шара радиуса в пространстве слов длины в алфавите из букв.
(Очевидно, числоэлементов в шаре не зависит от того, какой у него центр.)В самом деле, если код существует, то шаров с центрами в кодовыхсловах помещаются в пространстве из элементов без пересечений.Логарифмируя, можно переписать это неравенство (которое называюттакже оценкой Хэмминга или границей Хэмминга ) в таком виде: + log (, ) 6 1.Первое слагаемое можно назвать «коэффициентом полезного действия»кода: оно представляет собой отношение длины передаваемой информации к общей длине кода.
(В литературе его часто называют «скоростьюкода»).В англоязычной литературе границу Хэмминга часто называют volumebound (volume | объём).72. âÁÚÏ×ÙÅ ÏÃÅÎËÉГраница ГилбертаЕсли( − 1) (2, ) < ,то существует код с параметрами , , , .В самом деле, будем выбирать кодовые слова одно за другим произвольным образом, следя лишь за тем, чтобы расстояния между нимибыли больше 2 .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
