А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 11
Текст из файла (страница 11)
, ).(Пока всё как в лемме 1.) Пусть, наконец, многочлен ( ) имеет степеньне больше и∑{ | ( ) = } > (сумма весов точек ( , ), через которые проходит его график, не меньше ). Тогда (, ( )) является нулевым многочленом (равен нулю вкольце многочленов от одной переменной).. Многочлен ( ) = (, ( )) (как многочлен отодной переменной ) имеет степень меньше . Если ( , ) являетсякорнем (, ) кратности , а ( ) = , то многочлен ( ) имееткорень кратности .
Поэтому у многочлена число корней с учётомкратности не меньше , а степень меньше . Следовательно, = 0, чтои утверждает лемма.. Пусть (, ) | многочлен от двух переменных, а ( ) |от одной переменной, причём (, ( )) = 0. Тогда (, ) делится намногочлен − ( ) в кольце многочленов от двух переменных.(Равенство (, ( )) = 0 понимается как равенство в кольце многочленов, то есть как равенство нулю всех коэффициентов; это, вообщеговоря, более сильное утверждение, чем равенство во всех точках, еслиэлементов в основном поле мало.). Рассмотрим (, ) как многочлен от , коэффициенты которого являются многочленами от , и разделим его уголком на − ( ).
Поскольку старший коэффициент делителя равен единице, приэтом не появится никаких дробей, частное будет многочленом от и , аостаток | многочленом от (поскольку делитель имеет степень 1 по ,остаток имеет степень 0 по ). Таким образом, (, ) = ( − ( )) (, ) + ( ).Подставив теперь ( ) вместо , получим, что ( ) | нулевой многочлен, что и требовалось доказать.Теперь всё готово, чтобы вернуться к декодированию списком. Пустьимеется точек ( , ).
Нас интересует, сколько различных многочленовстепени не больше могут проходить через из них (для данных , и ).Чтобы оценить это число, рассмотрим целое положительное (покапроизвольное) и положим = = . . . = . (Кажется странным, что1ДоказательствоЛемма 3Доказательство125225. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁвообще нужны кратности, если они все равны. Тем не менее, как мыувидим, это полезно.)Чтобы применить лемму 1, нужно выбрать натуральное , для которого > ∑ ( + 1) = ( + 1),то естьp > ( + 1).Применение леммы 1 даёт многочлен (, ), имеющий -взвешеннуюстепень меньше и обращающийся в нуль с кратностью во всех точках( , ).Если многочлен имеет степень не выше и проходит через точекиз числа ( , ), причём2=1> ,то (, ( )) = 0 по лемме 2 и (, ) делится на − ( ) по лемме 3.Из курса алгебры известно, что в кольце F [, ] разложение на множители однозначно, так что число делителей вида − ( ) у многочлена (, ) меньше / (иначе суммарная -взвешенная степень произведения достигнет , ведь имеет взвешенную степень ).Собирая всё вместе (считая равным и поделив обе части неравенства на ), получаем такое утверждение:.
Еслиp > (1 + 1/ ) ,то количество различных многочленов степени не выше , проходящихчерез или более точек среди ( , ), . . . , ( , ), меньше / .√Видно, что эта теорема применима при > ; чем ближе это неравенство к равенству, тем большее придётся брать (и тем слабее будетоценка на число различныхмногочленов). Ещё из неё видно, например,√что при = (1 + ) и = ( ) число различных многочленов степени меньше , проходящих через точек из , есть (1).В следующем разделе нам потребуется аналогичное утверждение дляслучая произвольных весов:.
Пусть , . . . , и , . . . , | произвольные элементыполя F . Пусть , . . . , | произвольные натуральные числа. Пустьнатуральные числа и таковы, чтоТеорема1Теорема1111 > ∑ ( + 1).2=15325. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁТогда количество многочленов ( ) степени не выше , для которыхнабираемый ими вес∑{ | ( ) = )}не меньше , не превосходит / .В самом деле, по лемме 1 можно найти многочлен (, ), обращающийся в нуль в ( , ) с кратностью и имеющий -взвешенную степеньменьше ; по лемме 2 выполнено равенство (, ( )) = 0 для любогомногочлена степени не выше , набирающего вес не меньше ; по лемме 3 (, ) делится на − ( ) для всех этих многочленов и потомуих число меньше / .Приведённое доказательство после некоторого дополнительного анализа даёт полиномиальный алгоритм декодирования списком кодов Рида { Соломона (время работы алгоритма ограничено полиномом от параметров , , и размера поля ).
Надо только научиться раскладыватьна множители многочлены в F [, ] или хотя бы выделять из них всемножители вида − ( ).Вообще-то известны полиномиальные алгоритмы для полного разложения на множители (произвольного вида) многочленов от несколькихпеременных над конечным полем. Но нам достаточно уметь выделятьмножители специального вида, поэтому мы приведём простое рассуждение специально для этого случая.Пусть нам дан многочлен (, ) и пусть (, ) | некоторая точка,где он обращается в нуль: (, ) = 0. Посмотрим на производную повторому аргументу .
Если в точке (, ) она не обращается в нуль,то можно действовать как в курсе анализа, где к уравнению (, ) = 0в окрестности точки (, ) применяют теорему о неявной функции инаходят функцию , для которой ( ) = и (, ( )) = 0; приэтом высшие производные функции можно найти, зная соответствующие производные функции .Поскольку у нас поле конечной характеристики, то лучше действоватьнепосредственно в терминах коэффициентов многочлена. Сдвигом по и можно свести дело к случаю = 0, = 0. Запишем многочлен (, )по степеням : (, ) = ( ) + ( ) + ( ) + ( ) + . . .Равенство (, ( )) = 0 даёт нам уравнения на коэффициенты многочлена ( ) = + + + .
. . (свободного члена у ( ) нет, таккак по предположению (0) = 0). Приравнивая свободные члены в0 = (, ( )) = ( ) + ( ) ( ) + ( ) ( ) + ( ) ( ) + . . . ,201212323332012335426. òÉÄ { óÏÌÏÍÏÎ ÐÌÀÓ áÄÁÍÁÒ: ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍполучаем равенство (0, 0) = 0, то есть (0) = 0. Приравнивая коэффициенты при , получаем линейное уравнение на , при этом коэффициент равен (0) = ′ (0, 0), что не равно нулю по нашему предположению. Приравнивая члены с , получаем линейное уравнение на стем же коэффициентом (0), и так далее.Так мы можем определять коэффициенты в порядке возрастаниястепеней, и вопрос только в том, получится ли многочлен или ряд.
Поскольку мы заранее знаем верхнюю оценку на степень многочлена ( ),при которой − ( ) только и может быть делителем (, ), то достаточно получить коэффициенты до этой границы и затем сделатьпроверку (подстановкой в ).Переберём все пары (, ), для которых (, ) = 0 и ′ (, ) ̸= 0,и выполним для каждой такой пары указанную процедуру. В результатемы найдём все делители вида − ( ), кроме тех , которые целикомпроходят через точки с нулевой производной ′ . Но эти являютсярешениями уравнения ′ (, ( )) = 0, и мы можем считать (рассуждаяпо индукции), что они нам уже известны.
(При этом степень уменьшаетсяна единицу, так что алгоритм остаётся полиномиальным.)01122126. Рид { Соломон плюс Адамар:декодирование спискомРассматривая код Адамара в разделе 15, мы уже упоминали о возможности использовать его в качестве внутреннего кода, когда внешнимявляется код Рида { Соломона. Сейчас мы используем методы предыдущего раздела (декодирование кода Рида { Соломона с весами), чтобы получить алгоритм декодирования списком для такого каскадного кода.Напомним параметры рассматриваемого кода. Мы используем полеF из 2 элементов, обозначаемых , . . .
, . Внешний код Рида { Соломона кодирует 2 элементов поля, рассматривая их как коэффициенты многочлена степени меньше 2 и беря значения ( ), . . . , ( ).Внутренний код Адамара кодирует каждое из этих значений (то есть слово из битов) словом из 2 битов.Результирующий каскадный код кодирует слово из 2 битов, разбивая его на 2 блоков по битов, и затем заменяя каждый блок наего код Адамара. Получается 2 блоков по 2 битов в каждом, всего 2 битов.Кодовое расстояние (удельное, в расчёте на бит кодового слова) для2121225526.
òÉÄ { óÏÌÏÍÏÎ ÐÌÀÓ áÄÁÍÁÒ: ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍвнешнего кода равно 1 − , а для внутреннего равно 1/2, поэтому дляконкатенации оно равно (1 − ).Оценка Джонсона говорит теперь, что декодирование списком возможно с долей ошибок (1 − √) и длиной списка 2 · 2 (удвоеннаядлина кодового слова). Покажем, что такой список можно получить с помощью описанной в предыдущем разделе техники (набором весов вдольалгебраической кривой).Итак, пусть имеется некоторое слово длины 2 , для которого мыхотим составить список близких к нему кодовых слов. Разобьём слово на 2 блоков , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
