А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 5
Текст из файла (страница 5)
. . , делятсяна три категории (задаваемые тремя указанными неравенствами на ).Количество таких индексов обозначим через ( ), ( ) и ( ) соответственно. Нам достаточно доказать, что при некотором (из промежутка0 . . . ) выполняется неравенство ( )+2 ( ) < . (Реальная ситуацияможет быть даже немного лучше, если блок с большим числом ошибокне был принят за другой блок, а был сочтён неизвестным.)Чтобы доказать существование такого значения , достаточно установить, что среднее значение величины ( ) + 2 ( ) меньше . Приусреднении мы считаем все значения от 0 до равновероятными, тоесть речь идёт просто о среднем арифметическом. А кодируемое слово,его код и внесённые в него ошибки (и, тем самым, числа ) мы считаемфиксированными.В силу аддитивности математического ожидания (линейности среднего арифметического) можно вычислить средний вклад каждого отдельного , а потом сложить их по всем .
Итак, пусть фиксировано некоторое (и, тем самым, значение ).∙ Если 6 , то в третью категорию мы попасть не можем, а вовторую попадём, когда < . Вероятность этого события (она же |вклад в интересующее нас среднее) есть /( + 1).∙ Если > , то мы попадём либо во вторую категорию, либо втретью | последнее случится, если > − .
Вероятность последнегособытия равна( + 1) − ( − ) , +1поэтому математическое ожидание вклада позиции в + 2 не превосходит1 1 + + 1 −+1 + = 2 +2 −+ 1 + 6 ++1 < 1222121122222222222222222211. ôÅÏÒÅÍÁ æÏÒÎÉ(мы использовали при оценке, что 2 +1 6 : таково соотношение между числом исправляемых ошибок и кодовым расстоянием для внутреннегокода).Заметим, что полученная только что оценка верна (хотя и тривиальна)при > .Таким образом, среднее в обоих случаях не превосходит / дляданного и ∑ / в сумме, что по предположению леммы меньше (ведь ∑ есть общее число ошибок в кодовом слове каскадного кода).Лемма доказана.22222111.
Теорема ФорниБудем рассматривать двоичные коды с возрастающей длиной кодового слова и требовать, чтобы доля исправляемых ошибок (/ в нашихобозначениях) и коэффициент полезного действия кода (/ в нашихобозначениях) были отделены от нуля.Существование таких кодов очевидно следует из оценки Варшамова { Гилберта.Но если мы хотим, чтобы алгоритмы кодирования и декодированиябыли бы достаточно эффективны (скажем, полиномиальны по , длинекодового слова), требуется более сложная конструкция.В двух словах эта конструкция (Форни, середина 1960-х годов) такова: рассмотрим конкатенацию двух кодов, причём внешним является кодРида { Соломона, а внутренний ищется перебором кодовых слов, как вдоказательстве оценки Варшамова { Гилберта. Если внутренний код имеет длину кодового слова (log ), то его поиск и алгоритмы кодирования/декодирования будут экспоненциальными от log , но полиномиальными по .Объясним это более подробно.
При построении каскадного кода коэффициенты полезного действия перемножаются, как и доли исправляемыхошибок (даже если не использовать улучшенный алгоритм декодирования из предыдущего раздела). Поэтому нам нужно всего лишь, чтобыдля каждого из двух кодов коэффициент полезного действия и доля исправляемых ошибок были отделены от нуля.Для наглядности возьмём какой-нибудь пример с конкретными значениями параметров.
Фиксируем натуральное и рассмотрим поле F из2 элементов. Кодируемое слово будет состоять из 2 − блоков (числоблоков | половина размера поля). Каждый блок содержит битов, то12311. ôÅÏÒÅÍÁ æÏÒÎÉесть представляет собой элемент поля F. Мы считаем блоки коэффициентами многочлена степени меньше 2 − . Внешним кодом является кодРида { Соломона: от коэффициентов этого многочлена мы переходим кего значениям во всех 2 точках поля.
При этом число блоков удваивается.Далее мы кодируем по отдельности каждый блок с помощью внутреннего кода. Будем считать, что при кодировании блок удлиняется вдвое (из битов получается 2 ). Граница Варшамова { Гилберта (рис. 1 на с. 9)показывает, что при этом можно добиться кодового расстояния 10% (отдлины кодового слова, в данном случае 2 ) и исправления 5% ошибок.В итоге конкатенация кодов увеличивает число битов в 4 раза и имеет кодовое расстояние 5% (от длины слова). При этом тривиальный алгоритм декодирования позволяет исправлять 1,25% ошибок, а улучшенный | 2,5%.Осталось оценить сложность алгоритмов кодирования и декодирования. Элементы поля размера 2 можно представить -битовыми строками.
Вспомним построение этого поля, известное из курса алгебры. Егоможно получить, профакторизовав кольцо многочленов F [ ] по неприводимому многочлену степени . (Здесь F = {0, 1} | поле из двухэлементов.) Как найти этот неприводимый многочлен? Сейчас у нас большой запас времени и можно просто испробовать все многочлены степени , проверяя их неприводимость перебором возможных делителей. Это нелучший способ проверки неприводимости | для этого существует болееэффективный алгоритм Берлекэмпа, но использовать его не обязательно, поскольку многочленов 2 и возможных делителей ещё меньше, такчто перебор будет полиномиальным по длине кодируемого слова, равной 2 − .
После отыскания такого многочлена операции в поле выполняются за полиномиальное от время (что даже лучше, чем нужно). Так чтоединственная сложная операция | это поиск кода, выполняемый при доказательстве оценки Варшамова { Гилберта. Но и он полиномиален по 2(по крайней мере в двух доказательствах из трёх приведённых нами | негодится доказательство со случайным кодом, так как там вероятностноепространство имеет размер двойной экспоненты).Декодирование внутреннего кода при этом происходит с помощью перебора всех кодовых слов внутреннего кода (что допустимо, так как ихне более 2 ).. Вместо использования поля из 2 элементов можно былобы (с чуть худшими параметрами) использовать поле вычетов по простому модулю между 2 и 2 .
Такое простое число существует («посту1221Замечание+12412. ëÏÄ æÏÒÎÉ { ÷ÏÚÅÎËÒÁÆÔÁ { àÓÔÅÓÅÎÁлат Бертрана», он же теорема Чебышёва), и найти его можно перебором(полиномиальное от 2 число вариантов).12. Код Форни { Возенкрафта { ЮстесенаИнтересная модификация конструкции Форни из предыдущего раздела была предложена Юстесеном. Её идея в том, что мы не обязаныиспользовать один и тот же внутренний код для всех блоков. Более того,если для некоторой малой части блоков мы выберем неудачный внутренний код, это тоже не страшно (хотя и приведёт к некоторому уменьшениюкодового расстояния конкатенации).Оказывается, что можно (следуя Возенкрафту) предложить очень простое семейство кодов, большинство из которых хорошие.
А именно, пустьF | поле из 2 элементов, представленных -битовыми строками. Длякаждого ∈ F рассмотрим код : ↦→ (, · )(к произвольным битам дописываются ещё битов, получаемые из первых умножением на в смысле поля F). Мы будем считать, что сложениев поле F соответствует побитовому сложению строк по модулю 2. (Именно так и получается при построении поля как факторкольца.) Тогда код является линейным (для любого элемента ∈ F).Не всегда код хорош. Например, при = 0 мы дописываем нули,что совсем бессмысленно; при = 1 мы дублируем каждый бит слова ,что тоже ничего хорошего не даёт. Но оказывается, что при малых > 0доля тех ∈ F, при которых кодовое расстояние кода больше ,близка к единице.
Это следует из такой леммы:. Доля тех ∈ F, при которых код имееткодовое расстояние не более , не превосходит (, ) .2Поскольку (, ) ≈ 2 / , при малых / это отношение, примерноравное 2 / − , близко к нулю.леммы Возенкрафта совсем просто. Пусть кодовоерасстояние для не больше . Поскольку код линеен, это значит, чтонайдётся такое ненулевое слово , при котором общее количество единиц в битовых строках и не больше . В частности, слова и Лемма Возенкрафта22(2(2()1)Доказательство)2512. ëÏÄ æÏÒÎÉ { ÷ÏÚÅÎËÒÁÆÔÁ { àÓÔÅÓÅÎÁнаходятся в шаре радиуса с центром в нуле.
Тогда коэффициент представим в виде дроби, числитель и знаменатель которой лежат в указанном шаре, а таких дробей не больше, чем квадрат числа элементовшара, то есть (, ) . А всего в поле F имеется 2 элементов, что идаёт указанную оценку.Теперь можно построить каскадный код Форни { Возенкрафта { Юстесена, используя для внутреннего кодирования коды . Конкретноэто выглядит так. Как и в конструкции Форни, мы начинаем с 2 − блоков длины , рассматривая блоки как элементы поля F. Эти элементымы считаем коэффициентами некоторого многочлена степени меньше2 − . Затем мы берём значения многочлена во всех точках ∈ F иподвергаем их внутреннему кодированию. В данном случае к значению ( ) мы применяем код , то есть рассматриваем пару2211( ( ), ( ))как слово длины 2 . Все эти слова вместе и образуют кодовое словодлины 2 2 .Этот код имеет коэффициент полезного действия 25% (удлиняет слова в четыре раза). Кодовое расстояние этого кода (делённое на длинукодового слова, то есть в расчёте на один символ) отделено от нуля, каки в конструкции Форни.Это можно доказать примерно так: при некотором > 0 доля тех ∈ F, при которых кодовое расстояние кода (в расчёте на символ)меньше , не превосходит 1%.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
