А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 10
Текст из файла (страница 10)
А мы уже видели, что в -мерном пространстве может бытьне более ( + 1) векторов, образующих друг с другом тупые углы.Теорема доказана.Заметим, что если разрешить каждому содержать ровно √ элементов, то углы из тупых станут неострыми, и вместо + 1 получится2 векторов.Возвращаясь к исходным параметрам: если минимальное расстояниекода : ˚ → ˚ равно , то код допускаетдекодирование ( +1)-спис√ком с исправлением менее чем − ( − ) ошибок.
√Доказанную теорему можно прочесть и так: при − > ( − ) вшаре радиуса может содержаться не более чем +1 элементов с попарными расстояниями или более. (Имеется в виду расстояние Хэммингав ˚ .)Для кода с кодовым расстоянием 50% (в частности, для кода Адамара) эта теорема устанавливаетвозможность декодирования списком при√доле ошибок 1 − 1/2 ≈ 29%, что лишь немного больше границы в 25%для однозначного декодирования. Однако (в отличие от случая однозначного декодирования) даваемая этой теоремой оценка отнюдь не является4623. ïÃÅÎËÁ äÖÏÎÓÏÎÁточной. Например, для кодов Адамара возможно декодирование спискомпри любой фиксированной доле ошибок, меньшей 1/2.
(Более точнуюоценку Джонсона мы приведём дальше.)22. Декодирование списком кодов АдамараПусть > 0 | произвольное положительное число.. Число кодовых слов кода Адамара, которые отличаются отданного слова не более чем в (1 − )-доле позиций, не превосходит 1/ .. Вспомним, что кодовые слова кода Адамара былиплюс-минус базисными векторами ортонормированного базиса в евклидовом пространстве, если рассматривать кодовые слова как последовательности единиц и минус единиц и определять скалярное произведение поформуле1⟨( , . . . , ), ( , .
. . , )⟩ = ∑ (при этом есть степень двойки, но сейчас это не важно) .Пусть | произвольное слово (рассматриваемое как последовательность единиц и минус единиц). Если слово отличается от него не болеечем в (1 − ) позициях, тоТеорема122Доказательство11312⟨, ⟩ > Теперь надо в качестве взять все базисные векторы (с плюсом и минусом) и оценить, для скольких из них такое возможно. Из пары векторов и − лишь один может удовлетворять этому неравенству; заменяя знакиу базисных векторов, можно считать, что это вектор с плюсом.По теореме Пифагора (которую в данном случае называют равенством Парсеваля) квадрат гипотенузы ⟨, ⟩ равен сумме квадратов сторон ⟨, ⟩, взятой по всем базисным векторам .
В нашем случае ⟨, ⟩ =1, поэтому количество , при которых ⟨, ⟩ > , не превосходит 1/ ,что и требовалось доказать.223. Оценка ДжонсонаПохожее утверждение можно доказать для любых кодов (над двухбуквенным алфавитом) с расстоянием около 50%. Вот точная формулиров3 Разложение по этому базису соответствует преобразованию Фурье на группе B =(Z/2Z) ; элементы базиса соответствуют характерам этой группы.4724. ïÃÅÎËÁ üÌÁÊÅÓÁ { âÁÓÓÁÌÙÇÏка:. Пусть код состоит из двоичных слов длины на рассто0.
Тогда он допускаетянии не меньше (1 − ) для некоторого >декодирование списком при доле ошибок (1 − √) и размере списка 2 .Мы сформулировали это утверждение в терминах кодов, но по существу речь идёт√ о точках в шаре: теорема утверждает, что в B шаррадиуса (1 − ) может содержать не более 2 точек с попарнымирасстояниями не меньше (1 − ) .. Как и в доказательстве оценки Плоткина, будем рассматривать последовательности единиц и минус единиц, являющиеся векторами единичной длины в евклидовом пространствеR .√Пусть шар с центром имеет радиус (1 − ) (в метрике Хэмминга)и содержит точки , .
. . , , причём расстояние (Хэмминга) между и не меньше (1 − ) при любых ̸= . В терминах скалярногопроизведения это означает, что√(, ) > и ( , ) 6 .Другими словами, угол между и острый и не слишком близок кпрямому, в то время как угол между и достаточно близок к прямомуили даже тупой.Мы хотим доказать, что 6 2 . Это было бы так, если бы углымежду и были тупыми или прямыми (см.
доказательство оценкиПлоткина). Чтобы свести дело к этому случаю, вычтем немного изкаждого . Для этого найдём , при которомТеорема12121212Доказательство12112( − , − ) = ( , ) − (( , ) + ( , )) + (, ) 6√√6 − 2 + = ( − ) 6 0,Видно, что всё подобрано так, что годится = √. Оценка Джонсонадоказана.Аналогичная (но более сложно доказываемая) оценка имеет местои для кодов над -буквенным алфавитом, только надо заменить 1/2 на( − 1)/ и увеличить константу при в оценке для размера списка.22224. Оценка Элайеса { БассалыгоОценку Джонсона можно использовать для улучшения границы Хэмминга. Напомним, что она получалась так: если код имеет расстояние ,4824. ïÃÅÎËÁ üÌÁÊÅÓÁ { âÁÓÓÁÌÙÇÏто шары радиуса /2 с центрами в кодовых словах не пересекаются, ипотому их суммарный объём не больше объёма всего пространства.Теперь мы возьмём шары большего радиуса, чем /2.
Про них уженельзя утверждать, что пересечений нет. Однако | при подходящем радиусе | оценка Джонсона позволяет утверждать, что любая точка покрыта небольшим числом шаров (поскольку шар с центром содержит небольшое число кодовых слов). Поэтому суммарный объём шаровпревосходит объём всего пространства в небольшое число раз.Конкретно: пусть код со словами длины в двухбуквенном алфавите имеет расстояние = (1 − ) . Шары радиуса (1 − √) могутпересекаться, но кратность пересечений не превосходит 2 . Получаемнеравенство√2 ( (1 − ), ) 6 2 · 2для кодов с расстоянием1122122 = (1 − ).12Переходя к логарифмам, используя приближённую формулу для (сшенноновской энтропией), деля на и пренебрегая множителем 2 (малым по сравнению с 2 при больших ), получаем асимптотическую границу, показанную на рис.
4 пунктирной линией. Эта граница называетсяграницей Элайеса { Бассалыго.21 /нет1/2есть?нет1/21 /Рис. 4. Граница Элайеса { Бассалыго.25. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁ4925. Декодирование спискомкодов Рида { СоломонаПусть ˚ = F | конечное поле из элементов. Код Рида { Соломона кодирует многочлен степени не выше (то есть набор из ( + 1) егокоэффициентов) значениями этого многочлена в точках поля. Кодовоерасстояние для такого кода равно − , поэтому для восстановлениямногочлена по испорченному набору значений достаточно иметь примерно ( + )/2 правильных значений в этом наборе.Как мы видели, для декодированиясписком (полиномиального раз√мера) достаточно иметь примерно правильных значений.
Сейчас мыдадим новое доказательство этого факта, из которого можно извлечь алгоритм декодирования.Идея доказательства: при декодировании кода Рида { Соломона мы искали многочлены ( ) и ( ), для которых пары ( , ) (точки и значения в этих точках) ложатся на кривую ( ) − ( ) = 0. Другими словами, мы искали многочлен (, ) степени 1 по переменной , которыйобращается в нуль в этих точках, а затем доказывали, что ( ) делитсяна ( ) и многочлен (, ) представляется в виде ( )( − ( )), где ( ) | частное от деления на | искомый ответ.Сейчас мы будем делать то же самое, но с двумя отличиями:∙ многочлен уже не обязательно первой степени по ;∙ требуется не просто обращение в нуль выражения ( , ), а обращение в нуль с некоторой кратностью .Говорят, что многочлен (, ) обращается в нуль в точке (, ) скратностью , если ( + , + ) как многочлен от и не имеетчленов степени меньше .
Кратность 1 означает просто (, ) = 0,кратность 2 означает, что и производные по и равны нулю, кратность 3 | обращение в нуль вместе со вторыми производными, и такдалее.Заметим, что обращение в нуль в данной точке есть линейное условие на коэффициенты многочлена ; обращение в нуль с кратностью представляет собой набор из 1 + 2 + . . .
+ = ( + 1)/2 условий. Тем самым мы можем подобрать искомый многочлен методомнеопределённых коэффициентов, если только этих коэффициентов больше, чем условий во всех точках. Если при этом степень многочлена будет не слишком велика, то его обращение в нуль на многих точкахкривой = ( ) (где | исходный многочлен) гарантирует, что онобращается в нуль на всей этой кривой.5025. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁЧтобы сформулировать точное утверждение, определим -взвешенмногочленов в F [, ]: моном имеет степень + ;степень многочлена | наибольшая из степеней мономов.
(Переменная считается имеющей вес , поскольку мы собираемся на её место подставлять многочлен степени .)Следующие леммы носят чисто алгебраический характер.. Пусть , . . . , и , . . . , | произвольные элементыполя F . Пусть , . . . , | произвольные натуральные числа. Если | натуральное число, для которогоную степеньЛемма 1111 > ∑ ( + 1),2=1то существует ненулевой многочлен (, ), который имеет -взвешенную степень меньше и обращается в нуль в точке ( , ) с кратностью (при всех = 1, .
. . , ).. Размерность пространства многочленов, имеющих -взвешенную степень меньше , равна числу решений неравенства + < в целых числаx , > 0. А это число не меньше площади треугольника,ограниченного прямыми + 6 , > 0, > 0, которая равна /2 (половина произведения катетов и / ). В самом деле, еслинарисовать этот треугольник на клетчатой бумаге и взять любую точку(, ) внутри него (не на границе), то эта точка попадает в клетку с левымнижним углом (⌊ ⌋, ⌊ ⌋).
Координаты этого левого нижнего угла целыеи удовлетворяют неравенству, поэтому число целых решений неравенстване меньше площади треугольника (ведь он покрыт клетками).Поэтому размерность пространства многочленов, у которых -взвешенная степень меньше , не меньше /2 . С другой стороны, числолинейных условий, выражающих обращение в нуль многочлена в точках ( , ) с кратностью , равно ( + 1) ∑2 ,что по условию леммы меньше размерности пространства многочленов.. Пусть ( , ), .
. . , ( , ) | набор из пар элементов поля F (все они различны, хотя одна из двух координат у некоторых парДоказательство22=1Лемма 21125. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁ51может совпадать). Пусть , . . . , | произвольные натуральные числа.Пусть многочлен (, ) имеет -взвешенную степень меньше и обращается в нуль в точке ( , ) с кратностью (при всех = 1, . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
