А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 7
Текст из файла (страница 7)
КодРида { Соломона превращает эти элементов поля F в элементовтого же поля, после чего каждый из элементов мы заменяем его кодомАдамара и в итоге получаем битов.)В итоге параметры каскадного кода таковы: длина входного слова 2 ; длина выходного слова (2 ) ; кодовое расстояние (в расчёте насимвол) не меньше произведения кодовых расстояний, то есть (1 − ).Таким образом, мы можем достичь кодового расстояния, сколь угодноблизкого к 50% (при малом фиксированном ). При этом длина кодового+1+122123216. ÷ÅÒÏÑÔÎÏÓÔÎÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ËÏÄÏ× áÄÁÍÁÒÁслова ограничивается примерно квадратом длины кодируемого слова.(Такая граница представляет интерес лишь потому, что наш код описан явно | граница Варшамова { Гилберта позволяет получить линейныекоды с лучшими параметрами, которые можно использовать либо самипо себе, либо как внутренний код для кода Рида { Соломона, как в конструкции Форни.)16.
Вероятностное декодированиекодов АдамараПусть фиксировано некоторое значение < 1/4. Тогда, как мы знаем,возможно однозначное декодирование кода Адамара с исправлением до ошибок (на символ).Можно ли это делать за полиномиальное время? Постановка этоговопроса требует уточнения: полиномиальное время от чего? От длиныкодируемого слова или длины кодового слова? Поскольку мы кодируем + 1 битов с помощью 2 битов, разница весьма существенна.Тривиальный ответ таков: за полиномиальное от 2 время мы можемперебрать все 2 возможных кодируемых слов и найти нужное, а заполиномиальное от время мы сможем прочесть лишь пренебрежимомалую часть кодового слова, и вся эта часть может попасть в зону ошибок,так что декодирование невозможно.(Более аккуратное рассуждение: проведём декодирование для какогото одного случая, скажем, нулевого слова, потом посмотрим, какие позиции в кодовом слове мы прочли, и во всех кодовых словах эти позициисделаем нулевыми; доля ошибок будет невелика, а декодирование разрушено.)Другое возможное уточнение: говоря о декодировании слова длины2 за полиномиальное от время, будем предполагаеть, что это слово задано нам как «оракул»: по номеру бита (этот номер имеет длину ) нам сообщают значение соответствующего бита.
(Это уточнение необходимо, поскольку, скажем, давать на вход слово длины 2 на лентебессмысленно | в этом случае реально будет доступно лишь его началополиномиальной длины.)Оказывается, что в данной постановке задачи декодирование за полиномиальное время может быть выполнено вероятностным алгоритмом сосколь угодно малой вероятностью ошибки. Точная формулировка:+13317. ëÏÄÙ òÉÄÁ { íÁÌÌÅÒÁ. Для всякого < 1/4 и для всякого > 0 существует вероятностный алгоритм, который, получив число и (в виде оракула)кодовое слово длины 2 с не более чем 2 ошибок, работает полиномиальное от время и правильно декодирует слово с вероятностью неменее 1 − .(Заметим, что полином, ограничивающий время работы, зависит от и от : чем ближе к 1/4 и чем меньше , тем дольше работаеталгоритм.).
По условию мы можем найти значение неизвестнойаффинной функции : B → B, имеющей вид ( , . . . , ) = + + + . . . + в случайной точке с вероятностью ошибки не больше . Коэффициент можно записать как разность значений в двух точках, отличающихся попервой координате: = ( + 1, , . . . , ) − ( , . . . , ).Если в качестве ( , . . . , ) взять случайную равномерно распределённую точку, то сдвинутая точка ( + 1, .
. . , ) также будет равномернораспределена (хотя, конечно, эти две точки не будут независимы). Каждое из двух значений нам известно с вероятностью ошибки не больше2, поэтому правильное значение для будет получено с вероятностьюне меньше 1 − 2 > 50%.Повторяя это несколько раз (для независимых точек) и затем определяя ответ большинством, можно (как известно из теории вероятностей)быстро уменьшать вероятность ошибки и тем самым найти коэффициент со сколь угодно малой вероятностью ошибки. Аналогично найдём ивсе остальные , после чего уже можно находить (тоже голосованиемпо нескольким точкам).Теорема доказана..
Как известно из теории вероятностей, при таком повторении (и голосовании) вероятность ошибки убывает быстро, поэтому можносделать её, скажем, меньше 2− , оставив алгоритм полиномиальным по.ТеоремаДоказательство1011221112111110Замечание17. Коды Рида { МаллераКоды Рида { Соломона и коды Адамара являются двумя крайними случаями в семействе кодов, называемых кодами Рида { Маллера : в кодах3417.
ëÏÄÙ òÉÄÁ { íÁÌÌÅÒÁРида { Соломона мы рассматривали многочлены от одной переменной, нобольшой степени, а в кодах Адамара { от многих переменных, но первойстепени.В общем случае мы рассматриваем многочлены от переменных степени не выше над полем F . При этом степень понимается как суммарная степень по всем переменным. (При = 1 получаются коды Рида { Соломона, при = 1 | коды Адамара.) Алфавит состоит из символов(элементов поля); коэффициенты многочлена степени не выше образуют кодируемое слово, а значения этого многочлена во всех точках F |кодовое слово.Длина кодового слова равна , а длина кодируемого слова равначислу решений неравенства + . . . + 6 1в неотрицательных целых числах, то есть (решение такого неравенства задаётся разбиением ряда из объектов на + 1 групп с помощью перегородок; числа , .
. . , | числа объектов между перегородками; объекты справа от последней перегородки не входят ни в одно исоставляют разницу между частями неравенства).Оценка кодового расстояния основана на следующем простом алгебраическом утверждении:. Пусть F | поле из элементов, а ( , . .
. , ) | многочлен от переменных над этим полем, причём его степень (суммарнаяпо всем переменным) равна . Тогда доля точек ( , . . . , ) ∈ F , длякоторых ( , . . . , ) = 0,не превосходит / .. Лемма очевидна, если многочлен содержит член степени , в который входит только одна переменная. Тогда при любыхзначениях остальных переменных получается ненулевой многочлен степени , имеющий не более корней, так что на каждой прямой (когдавсе остальные переменные фиксированы) доля нулей не больше / , иостаётся их усреднить.К этому случаю можно пытаться сводить произвольный многочленлинейной невырожденной заменой переменных (которая не меняет суммарную степень); проще, однако, доказать утверждение леммы индукциейпо числу переменных. Для = 1 утверждение леммы очевидно (числокорней многочлена от одной переменной не превосходит его степени).+1Лемма111Доказательство3518.
ëÏÄÙ âþèДля произвольного рассуждаем так. Выделим какую-нибудь переменную, например, , и рассмотрим моном с максимальной степенью по . Пусть эта степень равна ; очевидно, 6 . Запишем как многочленпо , коэффициенты которого суть многочлены от , . . . , . Коэффициент при представляет собой некоторый многочлен ( , . . .
, ) степени не больше − . Случай − = 0 мы уже обсуждали. В общем случаедля равномерно распределённых случайных , . . . , вероятность события ( , . . . , ) = 0по предположению индукции не превосходит ( − )/ , а вероятностьсобытия ( , . . . , ) = 0, но ( , . . . , ) ̸= 0не превосходит / , поскольку для каждого набора значений , . . . , ,при которых ( , .
. . , ) ̸= 0, существует не более значений , прикоторых ( , . . . , ) = 0. (Так что даже и условная вероятность11122112122211 ( , . . . , ) = 0 при условии ( , . . . , ) ̸= 012не превосходит / .) Складывая вероятности, получаем искомую оценку/ . Лемма доказана.Таким образом, кодовое расстояние не меньше (1 − / ), то есть(1 − / ) в расчёте на один символ.
Например, при = 1 и = 2получается расстояние 50%, как мы уже видели для кодов Адамара.Ещё один пример: пусть = 2. Кодовое слово состоит из символов,а кодируемое слово из = ( + 1)( + 2)/2 ≈ /2 символов.Таким образом, коэффициент полезного действия кода примерно равен(1/2) / , что значительно хуже, чем у кодов Рида { Соломона при томже удельном кодовом расстоянии 1 − / . Зато размер алфавита теперьуже равен корню из длины кодового слова (а не самой этой длине).222+22218. Коды БЧХЭти коды названы БЧХ (в английском варианте | BCH) по именамсвоих изобретателей: Боуза (Bose), Чоудхури (Ray-Chaudhuri) и Хоквингема (Hocquenghem).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
