15.3. МЯГКОЕ ДЕКОДИРОВАНИЕ БЛОКОВЫХ КОДОВ

Вероятность ошибки декодирования минимизируется одновременным выбором демодуляции и декодирования. Модулятор отображает кодовых слов в сигналов где

Выходной сигнал канале где Передаваемый сигнал, реализация шума, представляется своими отсчетами при По этим отсчетам демодулятор и декодер должны восстановить кодовое слово, а затем и информационные символы.

Плотность распределения вероятностей вектора при условии, что передан сигнал дается выражением

причем предполагается, что отсчеты шума представляют собой независимые одинаково распределенные гауссовские случайные величины с дисперсией По принятому сигналу приемник максимального правдоподобия определяет значение при котором максимально, и объявляет, что было передано сообщение.

Однако поскольку шум предполагается гауссовским, приемник максимального правдоподобия идентичен приемнику минимального евклидова расстояния. Этот приемник находит значение при котором евклидово расстояние

минимально, и объявляет, что было передано сообщение.

Далее, если энергия одинакова для всех то приемник минимального евклидова расстояния может быть заменен корреляционным приемником. Он вычисляет совокупность коэффициентов корреляции

и затем принимает решение в пользу того кодовою слова у которого при всех После этого по восстанавливаются информационные символы. Поскольку очень велико, обычно даже этот приемник довольно непрактичен и поэтому переходят к более компактным схемам, схемам меньшей сложности.

На рис. 15.3 предлагается несколько вариантов приемника. Если модулятор и кодер фиксированы, то выбор самого верхнего варианта приводит к наименьшей частоте ошибок на символ, а самого нижнего — к наибольшей. Может создаться впечатление, что по мере возможности всегда желательпо реализовать нриемник максимального правдоподобия. Но это, вообще говоря, не так Часто целесообразнее затратить имеющиеся ресурсы на более

Рис. 15.3. Возможные варианты приемника.

мощный код и более мощный модулируемый сигнал, а для декодирования использовать подоптимальную процедуру.

В общем случае возможность использования в декодере мягкого решения приводит к необходимости выбора между передачей большего количества информации от демодулятора к декодеру при одновременном использовании более простого кода и передачей меньшего количества информации от демодулятора к декодеру при одновременном использовании более сильного кода. Первый экстремальный случай — демодулятор принимает жесткое решение; при этом последовательность вещественных чисел превращается демодулятором в последовательность -ичных символов, к которой можно успешно применить мощную технику алгебраического декодирования. Не представляет трудностей использование той же техники в случае, когда демодулятор может производить стирания. Второй экстремальный случай — демодулятор вообще не принимает решения; при этом вся информация в принятом сигнале сохраняется и передается декодеру.

В хорошо сконструированной системе связи сложность демодулятора и сложность декодера сбалансированы. С другой стороны, демодулятор принимает окончательное решение по

возможности на уровне символов; с другой стороны, он передает декодеру достаточно информации, чтобы качественные характеристики системы оставались достаточно высокими. Сохраняется также возможность использования каскадных кодов. Тогда соотношения между сложностью и качеством можно рассматривать на трех уровнях обработки в демодуляторе и на двух уровнях декодера. Используя мягкое решение в сочетании с малой длиной кода во внутреннем декодере и жесткое решение с исправлением ошибок и стираний во внешнем декодере, корректирующем оставшиеся ошибки и отказы внутреннего декодера, можно получить отличное соотношение между сложностью и качеством декодирования.

Изучим частный случай декодера мягкого решения, использующий алгоритм обобщенного минимального расстояния (ОМР-алгоритм). Этот алгоритм мы опишем дважды: сначала для двоичных кодов, используя некоторые геометрические построения, а затем для кодов над произвольным полем Галуа. В первом случае в демодулятор поступает последовательность двоичных чисел на фоне шумов. Принимаемый демодулятором двоичный бит описывается вещественным числом представляющим оценку принятого символа в сочетании с доверительным уровнем. Если равно —1, то принятый бит равен 0 с максимальным доверительным уровнем; если то принятый бит равен единице с максимальным доверительным уровнем. Если 5; представлено в виде числа, характеризуемого знаком и величиной, то можно считать, что его знак представляет оценку бита на выходе демодулятора, а абсолютная величина - доверительный уровень оценки.

Мы уже рассмотрели два частных случая. Если величины на выходе демодулятора принимают значения ±1, то демодулятор является демодулятором жесткого решения, а декодер исправляет лишь ошибки. Если на выходе демодулятора величины принимают лишь значения ±1 или 0, то демодулятор является демодулятором жесткого решения со стиранием, а декодер исправляет ошибки и стирания. В данном параграфе мы рассмотрим ОМР-алгоритм, который оперирует с величинами принимающими любое значение между Этот алгоритм декодирования может использоваться с любым демодулятором, выходные символы которого лежат в интервале

После обработки принятого сигнала демодулятором на его выход поступает принятый вектор

Если в канале не произошло ошибок и демодулятор приписал максимальный доверительный уровень каждому биту, то символы принятого вектора равны — 1 в тех позициях, в которых

символы переданного кодового слова равны нулю, и равны в тех позициях, в которых символы равны единице.

Пусть с вектор в -мерном евклидовом пространстве, такой, что его компоненты определяются выражением

Это выражение описывает отображение кодовых слов из Сохраним за название кодового слова. Евклидово расстояние между принятым словом и кодовым словом равно

Если состоит лишь из символов жесткого решения то евклидово расстояние связано с хэмминговым расстоянием соотношением

где компоненты вектора равны 0, если и равны 1, если частности, для любых двух кодовых слов

Минимальное евклидово расстояние кода и минимальное хэммингово расстояние связаны соотношением

Опишем ОМР-декодер с помощью скалярного произведения предварительно выразив евклидово расстояние кода через скалярное произведение. Мы можем переписать его в виде

Для фчксированного минимизация по эквивалентна максимизации скалярного произведения по поскольку не зависит от равно для любого кодового слова. Минимизация евклидова расстояния интуитивно понятнее, но при вычислениях лучше максимизировать скалярное произведение.

Декодеру, исправляющему только ошибки, предшествует демодулятор. который принимает лишь жесткие решения. При этом Следовательно, нахождение на минимальном евклидовом расстоянии от эквивалентно нахождению на минимальном хэмминговом расстоянии от Неравенству

удовлетворяет не более одного кодового слова Следовательно, не более чем одно кодовое слово с, удовлетворяет неравенству

Наконец, так как равно в случае демодулятора с жестким решением, то

и не более чем одно кодовое слово удовлетворяет неравенству

где минимальное хэммингово расстояние кода. Декодирование с исправлением только ошибок эквивалентно нахождению того единственного кодового слова для которого

если такое кодовое слово существует. Возможно, что решения не существует и декодер не в состоянии найти кодовое слово. Такой декодер неполон, но он будет указывать, что соответствующие конфигурации ошибок являются неисправляемыми.

Если действия демодулятора сводятся к жесткому решению или стиранию, или 0. По тем же причинам, что и выше, декодирование с исправлением ошибок и стираний эквивалентно нахождению того единственного кодового слова для которого

если такое кодовое слово существует. Как и ранее, соответствующий декодер полон.

Следующая теорема утверждает, что те же условия существования справедливы и при мягком решении.

Теорема 15.3.1. Каков бы ни был вектор с компонентами, лежащими в интервале в двоичном коде с длиной и минимальным хэмминговым расстоянием существует не более одного кодового слова для которого

Доказательство. Пусть — некоторое кодовое слово, удовлетворяющее приведенному выше неравенству, и пусть любое другое кодовое слово. Тогда отличается от с, по меньшей мере в позициях. Пусть

тогда

Но величина удовлетворяет неравенству

так как она равна сумме не более слагаемых, ни одно из которых не превышает единицу. Поэтому в силу неравенства следовательно, что завершает доказательство теоремы.

В качестве примера рассмотрим двоичный -код у которого равно 2. Этот пример достаточно прост для графической иллюстрации теоремы 15.3.1. На рис. 15.4 изображен куб в трехмерном евклидовом пространстве, содержащий возможные принятые векторы В том же пространстве показаны четыре кодовых слова. Штриховкой в одном из углов выделена совокупность удовлетворяющая условию которая декодируется в кодовое слово, лежащее в этом углу. Теорема утверждает, что если построить аналогичные области для каждого из четырех кодовых слов, то эти области не будут пересекаться. Используя эти четыре области декодирования, можно построить ОМР-декодер - Заметим, что указанные четыре области не заполняют куб полностью. Остающаяся в центре область является тетраэдром, и если

Рис. 15.4. Область декодирования ОМР-алгоритму для двоичного -кода.

попадает в этот тетраэдр, то декодирование объявляется неудачным. Декодер является неполным, и его области декодирования лежат в евклидовом пространстве.

ОМР-декодер находит единственное кодовое слово, удовлетворяющее теореме 15.3.1, если опо существует; в противном случае декодирование объявляется неудачным. Конечно, находить это кодовое слово, вычисляя все скалярных произведений, непрактично. Опишем практический способ нахождения этого кодового слова. Идея состоит в следующем.

Мы уже знаем, как построить декодеры, исправляющие ошибки и стирания, полученные в результате жестких решений. Любой декодер, исправляющий ошибки и стирания, можно дополнить внешней петлей обработки данных. Основываясь на информации мягкого решения, этот модернизированный декодер вычисляет последовательность пробных векторов жесткого решения со стиранием. Для каждого I от 0 до он стирает I компонент, для которых минимальны. (Если для некоторых в силу равенства нескольких компонент выбор этих I компонент неоднозначен, то соответствующее I опускается.) Совокупность нестертых компонент отображается в нули или единицы в зависимости от знака При этом над формируется вектор со стираниями.

Декодируем используя декодер, исправляющий ошибки и стирания. Если декодирование дало кодовое слово то проверим выполнение неравенства Если это неравенство выполняется, то объявляется ОМР-декодированным кодовым словом. В противном случае I увеличивается и процедура повторяется до тех пор, пока I не превзойдет ; в последнем случае декодирование объявляется неудачным.

На рис. 15.5 представлен ОМР-алгоритм в недвоичном случае. Теоремы 15.3.2 и 15.3 4 утверждают, что ОМР-алгоритм, представленный на рис. 15.5, в самом деле декодирует в единственное ОМР-кодовое слово. Заметим, что алгоритм, изображенный на рисунке, проверяет неравенство лишь при четных Этого достаточно, так как при изменении числа стираний на два число ошибок, которые можно исправить, изменяется на единицу.

Теорема 15.3.2. Если то хотя бы одно слово удовлетворяет неравенству

Доказательство следует из доказательства теоремы 15.3.4, являющейся более общей формой нашей теоремы.

Теперь обобщим ОМР-декодеры на недвоичные коды. Сложность ОМР-декодера приблизительно в раз выше, чем декодера для кода, исправляющего ошибки и стирания.

Рис. 15.5. (см. скан) ОМР-алгоритм

Понятие обобщенного расстояния естественным образом распространяется на недвоичные сигналы точно так же, как распространяется хэммингово расстояние. Как при определении хэммингова расстояния, так и при определении обобщенного расстояния недвоичная природа символов игнорируется и задача сводится

к двоичной, при которой лишь учитывается, совпадают или нет два символа, а их величины не принимаются во внимание. ОМР-декодер в недвоичном случае почти не меняется.

На выход демодулятора поступают -ичные символы, каждый из которых характеризуется своей оценкой элементом н доверительным уровнем измеряющим надежность оценки. Если равно единице, то принятый символ равен с максимальным доверительным уровнем; если равно 0, принятый символ равен с минимальным доверительным уровнем.

Как и в двоичном случае, для алгоритма декодирования не важно, какое правило демодулятор использует для нахождения Он даже может всегда полагать равным единице — в этом случае он является демодулятором с жестким решением; он может полагать равным 0 или 1 — в этом случае он является демодулятором с жестким решением и со стиранием. Возможно также использование для нахождения более сложной доверительной меры.

В двоичном случае мы смогли дать геометрическую интерпретацию декодирования, используя знак а для обозначения оценки переданного двоичного символа. В -ичном случае такой геометрической интерпретации не существует. Для определения скалярного произведения введем обозначение для любого

Затем определим произведение

использование которого позволяет доказать -ичный вариант теоремы 15.3.1. Это определение удобно, но неточно, поскольку зависит и от а.

Теорема 15.3.3. В коде над с длиной и минимальным, расстоянием существует хотя бы одно кодовое слово для которого

Доказательство аналогично доказательству теоремы 15.3.1.

Алгоритм декодирования в недвоичном случае таков же, как и в двоичном. Для любого I из интервала сотрем компоненты, для которых минимальны. При этом получим над слово со стираниями. Начиная с I, равного 0, декодируем используя декодер, исправляющий ошибки и стирания. Для декодирования в с, проверяется неравенство Если оно удовлетворяется, то , объявляется

ОMP-декодированным кодовым словом. Если оно не удовлетворяется, т. е. если 1-е декодирование оказывается неудачным, то увеличим будем повторять процедуру до тех пор, пока I не превысит в этом последнем случае декодирование объявляется неудачным. Следующая теорема обосновывает эту процедуру.

Теорема 15.3.4. Если для кодового слова выполняется неравенство то хотя бы одно слово удовлетворяет неравенству

Доказательство. Достаточно доказать теорему для I, пробегающих значения от 0 до поскольку ясно, что утверждение теоремы не может выполняться при Упорядочим по их величине. Пусть

и

Тогда так что вектор К ведет себя как вероятностное распределение. Более того,

и поэтому

Допустим, что при всех Тогда

что противоречит предположению теоремы. Поэтому теорема доказана.