А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 12
Текст из файла (страница 12)
. . , длины 2 каждый. Как и раньше, декодирование каскадного кода начинается с декодирования каждого блока поотдельности. Но в данном случае мы не будем выбирать какого-то одноговарианта декодирования, а рассмотрим все возможные варианты. А именно, для каждого блока и для любого элемента поля F посмотрим,насколько близко слово к коду Адамара элемента . Оба сравниваемых слова имеют длину 2 , и мы вычтем число несовпадений из числасовпадений; разность мы будем называть весом и обозначать . Если 6 0 (несовпадений не меньше, чем совпадений) то такой вариантдекодирования ( получилось искажением кода элемента ) мы сразуже отвергнем.
Для всех оставшихся вариантов веса неотрицательны.Получается максимум 2 положительных весов, поскольку каждый изиндексов , пробегает 2 значений (соответствующих 2 элементам поля).Эти веса будут использованы при декодировании внешнего кода. Мыбудем проводить алгебраическую кривую через все точки ( , ) ∈ F ,у которых веса положительны. (Заметим, что теперь у нас есть многоточек с одинаковой первой координатой, чего раньше не было.) В обозначениях последней теоремы предыдущего раздела: = 2 , 6 2 , = 2 .Остаётся понять, каким должно быть значение .
Чем оно больше, немутверждение теоремы слабее, поэтому его надо взять минимально возможным с соблюдением условия1212221222222 > ∑ ( + 1) = 2 ∑ ( + 1).2=1,(в левой части равенства используются обозначения предыдущего раздела, а справа подставлены их текущие значения). Правую часть можно5626. òÉÄ { óÏÌÏÍÏÎ ÐÌÀÓ áÄÁÍÁÒ: ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍзаписать как2 ∑ + ∑ .hi2,,Второе (меньшее) слагаемое оценим сверху, заменив все на их максимально возможное значение 2 , получится 2 .
Первое слагаемое будемоценивать более деликатным способом. Сгруппировав слагаемые с одними тем же (соответствующие одному блоку в конкатенации, но разнымвариантам его декодирования), получимih2 ∑ ∑ .42Теперь оценим отдельно каждую квадратную скобку (при фиксированном ). Вес представляет собой скалярное произведение кода Адамара элемента и слова , взятое с множителем 2 (скажем, еслискалярное произведение равно 1, то есть имеет место полное совпадение,вес равен 2 ). Остаётся вспомнить про неравенство Бесселя, согласнокоторому сумма квадратов скалярных произведений единичного векторас векторами ортонормированного набора не превосходит 1.
После учётакоэффициентов это даётhi2 ∑ ∑ 6 2 ∑ 2 = 2 · 2 · 2 = 2 .2224Таким образом, для применения теоремы из предыдущего раздела достаточно неравенства > 2 · 2 ,то есть√ > 2 2 .Таким образом, количество многочленов степени не выше 2 , набирающих вес или больше, невелико. Остаётся понять, что суммарный вес,набираемый многочленом, не меньше разницы между суммарным числомсовпадений и несовпадений в соответствующем кодовом слове, и тем самым можно выловить все кодовые слова, для которых эта разница междучислом совпадений и несовпадений больше√22 ,√то есть в расчёте на бит больше 2.
Поскольку эта разница есть 1 − 2 ,где | доля ошибок, условие на будет таким:√ < 12 1 − 2 .24225727. ÷ÅÒÏÑÔÎÏÓÔÎÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ÄÌÑ ËÏÄÏ× áÄÁÍÁÒÁПри этом число кодовых слов в списке оценивается величиной√/ = 22 /(2 ),что по порядку величины равно 2 , то есть корню из длины кодовогослова (немного лучше, √чем в оценке Джонсона).√Зато у нас вместо , как в оценке Джонсона, появляется 2.
Восновном это из-за того, что мы очень грубо оценивали сумму первыхстепеней. Сделаем это точнее: при каждом у нас имеется сумма 2чисел, сумма квадратов которых не превосходит 2 , так что их среднееквадратичное не превосходит 2/ . Среднее арифметическое не большесреднего квадратичного, поэтому сумма ∑ не больше 2 / (а раньшемы её оценивали как 2 , так что есть√ заметное улучшение).Отсюда ясно, что константу 2 в 2 можно (для достаточно больших ) заменить на сколь угодно близкую к единице.22232227. Вероятностное декодирование спискомдля кодов АдамараЕщё один результат, связанный с кодами Адамара | теорема Голдрайха и Левина о вероятностном декодировании списком (первоначальная формулировка была в терминах вычислительной криптографии, нопо существу она именно об этом).. Пусть < 1/2 и > 0.
Существует вероятностный полиномиальный алгоритм, который по данному и по данному слову длины2 указывает список полиномиальной длины, который с вероятностью неменее 1 − содержит все кодовые слова кода Адамара, отличающиеся от не более чем в 2 позиций.Эта формулировка требует трёх уточнений. Во-первых, полиномиальность означает, что время работы алгоритма (во всех случаях) ограниченонекоторым полиномом от . Во-вторых, слово (имеющее длину 2 )подаётся на вход алгоритма в виде «оракула» (алгоритм может запроситьзначение любого бита, указав его номер, то есть слово рассматриваетсякак функция : B → B, и алгоритм может её «вызывать»). В третьих,алгоритм указывает не сами кодовые слова кода Адамара (они имеютэкспоненциальную длину, и за полиномиальное от время их выписать нельзя), а их прообразы при кодировании (то есть слова из + 1битов, которые являются коэффициентами соответствующей аффиннойфункции).Теорема5827.
÷ÅÒÏÑÔÎÏÓÔÎÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ÄÌÑ ËÏÄÏ× áÄÁÍÁÒÁ. Будем считать, что = − при некотором > 0.Для доказательства теоремы мы построим алгоритм B, получающийна вход рациональные числа , > 0, натуральное число и (в виде оракула) функцию : B → B, и выдающий список B(, , , ) аффинныхфункций (то есть их коэффициентов). При этом алгоритм будет полиномиальным от , 1/ и 1/, если и достаточно просты, так что длиныих записей ограничены полиномом от 1/ и 1/ (это заведомо так, еслиони обратны к целым числам, и в дальнейшем мы рассматриваем толькотакие и ).Этот алгоритм будет обладать таким свойством:. Пусть : B → B | аффинная функция, а : B → B |произвольная функция, отличающаяся от не более чем в ( − )-долеаргументов.
Тогда вероятность того, что войдёт в список B(, , , ),не меньше 1 − .Прежде чем описывать алгоритм B и доказывать лемму, поясним еёсвязь с исходной формулировкой теоремы. Лемма говорит о вероятностипокрыть списком одну аффинную функцию, близкую к ; в теореме мыговорили о покрытии всех таких функций.
Но поскольку таких функциймало (что следует из свойств кода Адамара | при данном их не большенекоторой константы), то вероятность при переходе от леммы к теоремевозрастёт не сильно. (Кстати, тот факт, что функций немного, следует излеммы | если бы их было много, то список полиномиального размера,выдаваемый алгоритмом, не мог бы с высокой вероятностью покрыватьлюбую из них.)леммы. Итак, в роли алгоритма B мы имеем доступ к | «искажённому варианту» неизвестнойаффинной функции1Доказательство2Лемма12Построение алгоритма и доказательство ( , . . .
, ) = + + . . . + ,1011и должны отгадать коэффициенты , . . . , . Эти коэффициенты определяются значениями в + 1 точках0(0, 0, . . . , 0), (1, 0, . . . , 0), (0, 1, . . . , 0), . . . , (0, 0, . . . , 1)(и наоборот), и нам будет удобнее говорить о отгадывании этих значений.(На самом деле конкретный вид точек нам не важен, мы можем отгадывать значения в произвольных + 1 точках | и даже в произвольномполиномиальном числе точек.)5927. ÷ÅÒÏÑÔÎÏÓÔÎÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ÄÌÑ ËÏÄÏ× áÄÁÍÁÒÁПоскольку функция является аффинной, для любых и из Bвыполняется равенство ( ) = ( + ) − —( ),где — | линейная часть (без ). Пусть фиксировано, а пробегаетB .
Поскольку и совпадают по крайней мере в ( + )-доле позиций(что больше половины), то ( ) = большинство из ( + ) − —( ) ,и это большинство можно определить методом Монте-Карло, выбрав несколько случайных и проведя голосование среди выбранных значений.План этот на первый взгляд не имеет смысла, так как в правой частистоит —( ), которого мы всё равно не знаем (ведь — отличается от лишьотсутствием коэффициента ).Заметим, однако, что для нахождения большинства по методу Монте-Карло не обязательно, чтобы испытания были по-настоящему независимы.
Достаточно (хотя и с худшей оценкой на вероятность ошибки),чтобы они были попарно независимы. Именно, имеет место. Пусть события , . . . , попарно независимы и каждое из них имеет вероятность меньше − . Тогда вероятность того, что произойдёт половинаили больше событий, не превосходит1·10120Закон больших чисел для попарно независимых событий1122(и потому мала при больших ).В самом деле, рассмотрим индикаторы этих событий (случайные величины , равные единице, если случилось, и нулю в противномслучае).
Математическое ожидание каждого из индикаторов не больше− . Поэтому математическое ожидание суммы не больше ( − ).Теперь воспользуемся попарной независимостью: она гарантирует, чтодисперсия суммы ∑ равна сумме дисперсий; дисперсия не превосходит 1 (на самом деле даже 1/4), поэтому дисперсия суммы не превосходит .
Дисперсия есть математическое ожидание квадрата отклоненияот математического ожидания. Если произойдёт больше половины событий, то отклонение будет по крайней мере , а его квадрат | .Поэтому по неравенству Чебышёва вероятность такого события не больше = 1 · 1,11222 22226027. ÷ÅÒÏÑÔÎÏÓÔÎÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ÄÌÑ ËÏÄÏ× áÄÁÍÁÒÁчто и требовалось доказать.Откуда мы возьмём попарно независимые величины? Если взять (полностью) независимых векторов в B , то их частичные суммы (всего2 − 1 векторов) будут попарно независимы. Например, если , и | (полностью) независимые векторы, то семь векторов123 , , , + , + , + , + + 123121323123будут попарно независимы. (Скажем, при данном значении + все значения + равновероятны, поскольку не зависит от пары ( , ).)Геометрически: на случайных независимых равномерно распределённых векторов мы натягиваем параллелепипед, и 2 − 1 его вершин (несчитая нулевой) будут попарно независимы.Теперь уже можно объяснить идею доказательства: мы положим ( ) = большинство из ( + ) − —( ) ,1133212где | попарно независимые векторы (2 − 1 штук), а именно, ненулевые вершины параллелепипеда, натянутого на (полностью) независимыевекторы , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
