А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 4
Текст из файла (страница 4)
Многочлен ( ) = ( ) ( ) имеет степень меньше + . Таким образом, верна. Существуют многочлены ( ) степени и ( ) степенименьше + , для которых ~( ) ( ) = ( ) во всех точках.Удобно договориться, что старший коэффициент многочлена (при ) равен единице, а остальные могут быть произвольными. (То, что страший коэффициент равен единице, автоматически означает, что многочлен ( ) имеет степень ровно ). Тогда лемму 1 можно считать утверждением о разрешимости некоторой системы линейных уравнений. Неизвестными в ней являются остальные коэффициентов многочлена и + коэффициентов многочлена (всего + 2 штук), а уравнений в ней (что не меньше + 2 , хотя нам это и не важно).Тем самым некоторые многочлены, удовлетворяющие условиям леммы 1, можно найти, решив эту систему.
Правда, пока мы не знаем, какони связаны с «настоящими» и . Об этом говорит. Пусть ~ ( ) и ~ ( ) | произвольные многочлены, удовлетворяющие условиям леммы 1 (это значит, что они имеют нужные степени и равенство ~( )~ ( ) = ~ ( ) выполняется во всех точках). Тогда(а) ~ делится на ~ в кольце многочленов F [ ];~ ~ равно исходному (и искомому) многочлену .(б) частное /. Многочлены ~ и ~ имеют степень меньше + .Они совпадают во всех тех точках, где = ~, а таких точек как минимум − > + , поэтому эти многочлены равны.Применяя эти две леммы, мы получаем алгоритм декодирования кодовРида { Соломона.
Оба его этапа | и решение системы линейных уравнений, и деление многочленов, | выполняются за время, полиномиальноеот и log .. Это утверждение требует некоторых пояснений. Делов том, что поле F | вещь абстрактная. Оно единственно с точностью до изоморфизма, но не имеет какого-то «канонического» представления. Можно доказать, что его элементы можно представить числами0, .
. . , − 1 таким образом, что операции сложения, вычитания, умноЛемма 1Лемма 2ДоказательствоЗамечание 1189. ëÁÓËÁÄÎÙÅ ËÏÄÙжения и деления выполняются за полиномиальное от log время . Прииспользовании такого представления алгоритм декодирования и будет полиномиальным от и log .Можно рассматривать также задачу о декодировании сошибками и пропусками (или, как обычно говорят, «стираниями»).
Подпропуском мы понимаем позицию, в которой буква неизвестна. (Это лучше, чем неверная буква, так как мы хотя бы знаем, в какой позициипроблема.) Видно, что для декодирования кода Рида { Соломона нужно,чтобы число пропусков плюс удвоенное число ошибок не превосходило − (поскольку пропуск одной позиции даёт снова код Рида { Соломонас заменой на − 1).
Так что пропуск считается за пол-ошибки («двапереезда | как один пожар»).Всем хороши эти коды, но только они требуют достаточно большого алфавита (размер алфавита должен быть не меньше длины кодовыхслов, да ещё быть степенью простого числа). Уменьшить алфавит можно, используя конструкцию каскадных кодов, описываемую в следующемразделе.2Замечание 2.9.
Каскадные кодыПусть имеется некоторый код с большим алфавитом ˚. Можно ли егопеределать в код с меньшим (скажем, двоичным) алфавитом? Например,пусть ˚ содержит 2 букв. Тогда можно записать каждую букву из ˚ спомощью блока из битов. При этом код ˚ → ˚ превратится в кодB → B .Кодовое расстояние при этом не уменьшится. В самом деле, если дляисходного кода оно было , то теперь два кодовых слова отличаются покрайней мере в блоках, а отличие в блоке означает отличие хотя бы водном бите этого блока.Общая длина кодовых слов, однако, возрастёт (в раз), так что допустимый процент ошибок в кодовом слове уменьшится в раз.2 Если | простое число, то это совсем просто (для деления надо использовать алгоритм Евклида).
Если | степень простого числа (других полей не бывает), то есть = для простого и некоторого > 1, то такое поле изоморфно фактор-кольцу F [ ] по идеалу, порождённому неприводимым над F многочленом степени , и сложность только втом, как найти такой неприводимый многочлен (умножать, делить и применять алгоритм Евклида для многочленов можно быстро). Алгоритмы поиска неприводимых многочленов |целая наука; оказывается, что это можно делать детерминированно за полиномиальное от и время, а вероятностно | за полиномиальное от log и (то есть от log ) время.1910.
äÅËÏÄÉÒÏ×ÁÎÉÅ ËÁÓËÁÄÎÙÈ ËÏÄÏ×Более надёжный двоичный код получится, если кодировать буквы алфавита ˚ блоками не из битов, а из большего числа битов, причёмиспользовать при этом какой-либо код, исправляющий ошибки.В общем случае такая конструкция «каскадного кода», или «конкатенации» двух кодов, применима к кодам : ˚ → ˚ и : ˚ → ˚ ,если |˚ | = |˚ | . Тогда каждую букву алфавита ˚ можно рассматривать как блок из символов алфавита ˚ и кодировать блоком из символов алфавита ˚ .Формально, определим конкатенацию «внешнего» кода и «внутреннего» кода как код : ˚ → ˚ .Чтобы найти значение на слове длины , составленном из букв алфавита ˚ , это слово надо разбить на блоков длины .
Если эти блокисчитать буквами алфавита ˚ , получится слово длины в алфавите ˚ .Применив к нему код , получим слово из блоков длины . Остаётсязакодировать каждый из этих блоков по отдельности кодом , получив блоков длины , или всего букв алфавита ˚ .. Кодовое расстояние конкатенации кодов не меньше произведения их кодовых расстояний.В самом деле, рассмотрим два различных кодовых слова в конкатенации. Каждое из них состоит из блоков длиной . Условие на код гарантирует, что имеется по крайней мере различных блоков. (Через , мы обозначаем кодовые расстояния кодов и .) Условие накод гарантирует, что в каждой паре различных блоков имеется (какминимум) отличающихся букв, всего получается различий.Таким образом, каскадный код позволяет исправлять около /2ошибок (половина кодового расстояния).
Но как именно это сделать?121112221122212222121 21 22212212111112212122Теорема1211121222121210. Декодирование каскадных кодовПусть код является конкатенацией кодов и . Имея алгоритмыдекодирования для и , можно предложить следующий естественныйалгоритм декодирования для : декодировать каждый блок с помощью -декодирования, а к полученному слову применить -декодирование.Чтобы этот алгоритм работал, в декодируемом слове должно быть не1122212010.
äÅËÏÄÉÒÏ×ÁÎÉÅ ËÁÓËÁÄÎÙÈ ËÏÄÏ×более блоков с более чем ошибками (где и | допустимыечисла ошибок для кодов и ). Это заведомо будет так, если общеечисло ошибок (во всех блоках) не больше . Учитывая, что ≈ /2,мы видим, что такой алгоритм позволяет исправлять примерно /4ошибок, что составляет четверть кодового расстояния и вдвое меньшемаксимально допустимого числа ошибок (которое примерно равно половине кодового расстояния).Более устойчивый к ошибкам (и тем не менее достаточно эффективный) алгоритм декодирования возможен, если в качестве внешнего кода(как часто бывает) применяется код Рида { Соломона.
Годится и любойдругой код, который позволяет эффективно декодировать слова с ошибками и пропусками, причём пропуск считается за пол-ошибки. В этомслучае удаётся исправлять до ошибок (что соответствует приведённой выше оценке для минимального расстояния каскадного кода).Делается это так. Код позволяет исправлять = ⌊( − 1)/2⌋ошибок. Пусть дан некоторый «порог» в диапазоне 0 . . . . (Как еговыбирать, мы обсудим дальше.) Получив для декодирования блоковпо символов в каждом, мы применяем алгоритм -декодирования ккаждому блоку в отдельности, а затем для проверки применяем алгоритм кодирования и смотрим, в скольких позициях есть отличие.
Еслиполученное кодовое слов отличается от исходного блока более чем в позициях (а также если алгоритм декодирования вообще не дал результата), то этот блок объявляется «неизвестным». Более того, если числоотличий в блоке больше порога , то блок также объявляется неизвестным. Результаты декодирования остальных («известных») блоков вместе синформацией о том, какие блоки неизвестны, подаются на вход алгоритмадекодирования кода | который, по предположению, умеет работатьс пропусками и ошибками, если + 2 < .. Если общее число ошибочных позиций (среди поданныхна вход описанного алгоритма) меньше , то описанный процесс позволит правильно декодировать исходное слово хотя бы при одном значениипараметра .Прежде чем доказывать лемму, заметим, что она не говорит, как найтихорошее значение параметра | но это и не нужно.
Мы можем перепробовать все значения (их число заведомо не превосходит , поэтомуэтот перебор не повредит полиномиальности алгоритма) и затем проверить полученные результаты с помощью кодирования (правильный должен давать менее /2 отличий).Осталось доказать лемму. Предположим, что некоторое выбрано.1211221211222222122211Лемма1112222110.
äÅËÏÄÉÒÏ×ÁÎÉÅ ËÁÓËÁÄÎÙÈ ËÏÄÏ×Пусть | истинное число ошибок в -м блоке (при = 1, 2, . . . , ).Числа нам неизвестны, но мы знаем, что:∙ если 6 , то -й блок декодирован правильно (и сочтён известным);∙ если < < − , то -й блок объявлен неизвестным (мы не моглипринять его за другой блок и счесть известным, так как если расстояниедо другого центра шара не больше , то расстояние до нашего центра неменьше − по неравенству треугольника);∙ наконец, если > − , то с -м блоком может быть всякое (онможет быть сочтён неизвестным или быть принятым за другой блок).Таким образом, для данного все индексы = 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
