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

Теорема 15.3.4. Если для кодового слова с выполняется неравенство v-Cr > п - d*, то хотя бы одно слово vO, / = О,... d* - 1, удовлетворяет неравенству

v()-c,>n-d.

Доказательство. Достаточно доказать теорему для /, пробегающих значения от О до п, поскольку ясно, что утверждение теоремы не может выполняться при ld*.

Упорядочим щ по их величине. Пусть

ui г 1 < « - 1.

Л„ = 1 - ас.

Тогда О < < 1 и Yi"=oi = , так что вектор к ведет себя как вероятностное распределение. Более того,

и поэтому

Допустим, что v()-c,.<! п ~~ d* при всех /. Тогда

V-C = Т Kv-Cr <{n-d)Th = n-d\ 1=0 ;=о

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

15.4. МЯГКОЕ] ДЕКОДИРОВАНИЕ СВЕРТОЧНЫХ КОДОВ

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

мягкого решения алгоритмов последовательного декодирования. Отложим изучение последовательного декодирования до следующего параграфа, а в настоящем параграфе займемся алгоритмом Витерби с демодулятором с мягким решением. Затем изучим сверточные коды Унгербёка, имеющие большое евклидово свободное расстояние; поэтому они полезны для каналов, ограниченных по полосе. Коды Унгербёка больше подходят для каналов, ограниченных по полосе, чемкоды, построенные из соображений возможно большего хэммингова свободного расстояния.

Алгоритм Витерби отыскивает на решетке путь, ближайший к принятому слову. Расстояние принятого слова от пути на решетке определяется как сумма расстояний вдоль последовательных ребер. Мера расстояний выбирается произвольно, за исключением того, что она должна удовлетворять требованию аддитивности. Поэтому, хотя алгоритмВитерби, введенный в § 12.8, использует хэммингово "расстояние, тот же алгоритм применим и при любом другом определении расстояния. Неявляется даже необходимым, чтобырасстояние было" метрикой.

АлгоритмВитербихор ошоиспользоватьв"техслучаях, когда шум в каналестационарен илегкомоделируется. Пусть"С7 Г*)- условная вероятностьтого, что на" выходе демодулятора наблюдается символ""!; при условии, что на вход канала поступил символс. Даже если с выбран из дискретного алфавита малого объема, демодулятор мягкого решения может иметь для v больший алфавит - быть может, непрерывный алфавит или алфавит двоичных чисел из т битов. Возьмем некоторый кадр принятого слова. Он состоит из «о компонент, обозначаемых через Vi, i = \, щ. Выберем некоторое ребро решетки. Оно состоит из Ло компонент кодового слова, обозначаемых через Си г = 1, щ. Расстояние кадра кодового слова с от соответствующего кадра принятого слова V определяется логарифмической функцией правдоподобия

Эта функция, называемая метрикой ребра (или метрикой пути), обладает свойствами расстояния, хотя иие является истинной метрикой.

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

Витерби возрастает очень мало при его перестройке на мягкое решение.

Если входные символы канала - вещественные или комплексные числа, а шум в канале - аддитивный гауссовский независимый, то

Q(vic)= П

Lr- ехр

Для гауссовского канала максимизация логарифмической функции правдоподобия эквивалентна минимизации евклидова расстояния. В качестве метрик ребер используем евклидово расстояние

На практике во многих каналах с мягким решением, не являющихся гауссовскими, Q (v с) неизвестно, но евклидово расстояние по-прежнему используется для вычисления метрик ребер. Соответствующий декодер является декодером по минимуму евклидова расстояния. Он не является декодером максимального правдоподобия, но практичен. Алгоритм Витерби с мягким решением выглядит совершенно аналогично алгоритму Витерби с жестким решением, но хэммингово расстояние заменено в нем евклидовым.

Рассмотрим сверточные коды, использующие вещественные или комплексные алфавиты из 2"« символов, где По - некоторое целое число. Типичные сигнальные алфавиты представлены на рис. 15.1. Каждый алфавит-это дискретное множество символов, выбираемых или из поля вещественных чисел, или из поля комплексных чисел. Сигнал представляет собой последовательность этих вещественных или комплексных чисел.

Каждый сигнал из набора сигналов будет использоваться для представления одного из 2"» ребер двоичного сверточного (тпо, то)-кода. Наборы сигналов на рис. 15.1 обеспечивают кодирование байтов, в которые входят от 2 до 6 битов. Информационный байт меньше кодового байта. На протяжении кадра информационные байты поступают в кодер. Один из байтов кодового слова (какой именно - это зависит от текущего состояния кодера) передается по каналу в виде комплексного числа, а кодер переходит в новое состояние.

Пусть W - сверточный (тпр, то)-код над комплексным полем С. Евклидово расстояние между двумя кодовыми словами С;- и Сг (с комплексными компонентами Сп и Сг-с, / = О, ... соответственно) определяется формулой