А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 9
Текст из файла (страница 9)
Многочлен однозначно определяется своими значениями в 8 точках этогополя (и, с другой стороны, однозначно определяется 8 коэффициентами , , . . . , ). Условие « принимает лишь значения 0 и 1» запишетсякак система уравнений = , = , = , = , = , = , = , = .Наложив ограничение = 0, мы получим код размерности 7 (одно уравнение на 8 переменных) с расстоянием 2.
Легко понять, что это за код:поскольку расстояние равно 2, то в уравнение обязаны входить все переменные, и это уравнение есть проверка на чётность (сумма по модулю 2равна нулю).Следующее ограничение = 0. Оно соответствует трём уравнениями уменьшает размерность кода до 4 (или больше, если уравнения былибы зависимыми | как мы увидим, это не так). Из уравнения = видно, что в этом случае и = 0, так что кодовое расстояние будет неменьше 4. Выбросив любой бит, мы не изменим размерность кода (поскольку по условию чётности он определялся остальными) и уменьшимрасстояние не более чем на 1. Получится код длины 7 и размерности 4 скодовым расстоянием не меньше 3 | всё как у кода Хэмминга. (Отсюдаследует, что уравнения были независимыми, поскольку код Хэмминга итак заполняет всё пространство и больше кодовых слов просто не поместится.)Чтобы убедиться, что это и есть код Хэмминга, надо выяснить, какот значений многочлена в точках поля перейти к его коэффициентам.87602727625235214326224121007626554119.
âþè É èÜÍÍÉÎÇЭто делается по интерполяционной формуле Лагранжа: ( ) = ∑ () ( ),∈Fгде | многочлен (степени меньше ), равный 1 в точке и 0 востальных точках поля. В данном случае в качестве такого многочленаможно взять ( ) = ( − ) − + 1.В самом деле, при ̸= первое слагаемое равно 1 (порядок мультипликативной группы поля, равный − 1, делится на порядок любого еёэлемента), и многочлен обращается в нуль (наше поле характеристики 2).Разложение ( − ) − по биному Ньютона даёт (в поле характеристики 2) многочлен − + − + − + . .
. + − + − .В этом можно убедиться, вспомнив, что в строке треугольника Паскаля,номер которой на единицу меньше степени двойки, все члены нечётные.А можно домножить записанную сумму на ( − ), получится − ,что равно ( − ) (поскольку возведение в квадрат, а также в любуюстепень двойки, перестановочно со сложением).Так или иначе, мы можем теперь записать более конкретно условияобращения в нуль коэффициентов и в терминах значений многочлена . Как видно из формулы Лагранжа и формулы для , = ∑ (), = ∑ ().11123227766∈F1∈FПоэтому условие на представляет собой проверку на чётность (это мыи так знаем из общих соображений). Условие на представляет собойравенство∑ () = 0∈Fв поле F, которое можно рассматривать как векторное пространство размерности 3 над F .
При этом семь ненулевых элементов превращаютсяв семь ненулевых векторов из F , то есть в векторы(0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1),и условия на коэффициенты () при ̸= 0 будут те самые, что былив коде Хэмминга. Поэтому из кода БЧХ получается код Хэмминга, еслиотбросить (0), как мы и говорили.762324220. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍВ этом примере мы считали, что = 3 ( = 8), но всё сказанноеочевидно переносится и на случай произвольного .20. Декодирование спискомДо сих пор мы требовали, чтобы исправление ошибок происходилооднозначно.
Посмотрим, что будет, если ослабить это требование и разрешить до вариантов декодирования (при некотором ). Более формально, множество кодовых слов должно быть таким, чтобы любой шаррадиуса содержал не более кодовых слов. В этом случае мы говорим,что код допускает декодирование списком длины (с исправлением ошибок).Как и раньше, нас интересует возможность построения такого множества при заданных параметрах (размер алфавита), (длина кодируемого слова), (длина кодовых слов), (число возможных ошибок) и,наконец, .
(Случай = 1 соответствует прежней постановке задачи.)Аналог границы Хэмминга теперь выглядит так: (, ) 6 .В самом деле, шары радиуса в количестве штук содержат по (, )элементов каждый и покрывают множество из элементов не более чемв слоёв.В логарифмической шкале: + log (, ) 6 1 + log .Таким образом, если рассматривать не слишком большие (скажем, полиномиальные от ), то граница почти не сдвигается.Зато сдвигается другая граница: указанное только что необходимоеусловие существование кода оказывается почти что достаточным.
А именно, верно такое утверждение (теорема Элайеса):. Пусть выполнено неравенство Хэмминга (в прежней форме,для = 1): (, ) 6 .Тогда существует код, допускающий декодирование списком длины ,где = ( log ).Точнее говоря, нам годится любое , при котором ! > ; поскольку ! ≈ (/2,718 .
. .) , это даёт оценку = ( log ).Теорема4320. äÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ. Покажем, что случайно выбранный код допускаетдекодирование списком длины с положительной вероятностью (или,другими словами, что число кодов, не допускающих такого декодирования, меньше общего числа кодов).Всего кодов (точнее, отображений ˚ → ˚ ) имеется ( ) . Подсчитаем число плохих | тех, где некоторое слово покрывается (илиболее) шарами. Плохое отображение можно задать, указав∙ плохое слово (покрытое или более шарами) [ вариантов];∙ индексы покрывающих шаров [подмножество размера в множестве˚ , всего вариантов];∙ центры покрывающих шаров (= кодовые слова, попадающие в шаррадиуса с центром в точке, выбранной на первом шаге) [ точек вшаре, всего (, ) вариантов];∙ остальные кодовые слова [ − точек, всего ( ) − вариантов].Таким образом, общее число плохих отображений не превосходит ( (, )) ( ) − 6 ( )! ( (, )) ( ) −(на последнем шаге мы использовали оценку 6 ( )/ !, которая получается из формулы для числа сочетаний, если все множители в числителе заменить на наибольший).
Таким образом, всё будет хорошо, если ( )! ( (, )) ( ) − < ( ) ,что после сокращений даёт1 − ! ( (, )) < ( ) .По предположению теоремы (, ) 6 (граница Хэмминга), поэтому достаточно неравенства < !, как мы и говорили. Теоремадоказана..
Если немного уменьшить пропускную способность конструируемого кода, предположив, что + log (, ) 6 1 − < 1,(для маленькой константы > 0), то в левой части оценок добавитсямножитель (( − ) ) , меньший единицы, поскольку тогда (, ) 6 − = ( − ) ,Доказательство(1Замечание(1))4421. ëÏÄÏ×ÏÅ ÒÁÓÓÔÏÑÎÉÅ É ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍи останется неравенство (( − ) ) < ! ,которое выполняется при = (1) (величина зависит от выбора и , но не растёт с ростом ). В самом деле, достаточно взять , прикотором · ( − ) 6 1.Мы доказали существование кодов, декодируемых списком, вблизиграницы Хэмминга, но не указали явно этих кодов. Сложность описанияпостроенных кодов экспоненциальна, не говоря уже о времени кодирования и декодирования.21. Кодовое расстояние и декодированиеспискомПусть имеется код : ˚ → ˚ с минимальным расстоянием между кодовыми словами.
Мы уже знаем, что он позволяет декодировать ошибок при < /2. Переходя от различающихся позиций к совпадающим, можно переформулировать это так. Пусть известно, что любые двакодовых слова совпадают максимум в (= − ) позициях. Тогда длялюбого слова ∈ ˚ не более одного кодового слова может совпасть с более чем в ( + )/2 (= − /2) позициях.В этих же обозначениях удобно формулировать утверждение о декодировании списком, заменив среднее арифметическое на среднее геометрическое:. Пусть любые два кодовых слова (из ˚ ) совпадают максимум в позициях.
Тогда для любого слова√ ∈ ˚ не более чем + 1слов могут совпадать с ним более чем в позициях.(Заметим, что среднее геометрическое меньше среднего арифметического, так что всё согласовано.). Пусть слова , . . . , совпадают со словом более чем в √ позициях (каждое в своих). Пусть ⊂ {1, 2, . . .
, } |номера позиций,где совпадает с . Тогда каждое из множеств содержит более √ элементов, а пересечение ∩ при ̸= содержитне более элементов.Рассмотрим характеристические функции множеств как случайные величины на вероятностном пространстве {1, . . . , } (с равномернымТеоремаДоказательство121. ëÏÄÏ×ÏÅ ÒÁÓÓÔÏÑÎÉÅ É ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÓÐÉÓËÏÍ45распределением). Напомним, что корреляция двух случайных величин и определяется как⟨, ⟩ = E[( − E )( − E )],где E | математическое ожидание (в данном случае | среднее арифметическое чисел). Другими словами, корреляция и есть скалярноепроизведение − E и − E.Раскрывая скобки и пользуясь линейностью математического ожидания, получаем, что⟨, ⟩ = E( ) − (E )(E ).Для случая, когда случайные величины | индикаторы событий (равныединице, если событие произошло, и нулю, если не произошло), получаем формулу⟨ , ⟩ = Pr[ и ] − Pr[ ] Pr[ ];корреляция равна нулю, когда события независимы.√√ В данном случае вероятность каждого события больше / =/ , а вероятность пересечения любых двух не больше / , так чтокорреляции отрицательны.Теперь вспомним, что корреляции можно записать как скалярные произведения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
