Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

Использование мягкого декодирования дает разработчику системы связи дополнительные возможности. Дополнительная информация, возникающая при мягком решении, в большинстве случаев увеличивает выигрыш от кодирования примерно на и может поэтому существенно увеличить полезность данного кода. Мягкое декодирование особенно эффективно для кодов сравнительно небольшой длины, где оно приводит к существенному улучшению характеристик в широком диапазоне отношений сигнал-шум. Оно эффективно также в каскадных схемах (см. гл. 8) с двумя или большим числом уровней кодирования и декодирования. В этих схемах мягкое декодирование применяется во внутреннем декодере и должно обеспечивать почти оптимальные характеристики при вероятности ошибки в слове примерно Такие требования контрастируют с обычно предъявляемыми к системам требованиями об эффективности схемы декодирования при вероятности ошибки менее

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

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

Наиболее важными среди методов, в которых делается попытка минимизировать вероятность ошибки символа, являются алгоритм декодирования по апостериорной вероятности (АРР-алгоритм), предложенный Месси [13], оптимальный алгоритм посимвольного декодирования Хартмана — Рудольфа [20] и алгоритм Велдона [21]. АРР-алгоритм Месси представляет собой естественное обобщение рассмотренного в гл. 3 порогового декодирования, позволяющее принимать мягкие решения. Для ограниченного класса кодов, к которым этот алгоритм применим, он является почти оптимальным. Хотя математические операции, необходимые для разработки этого алгоритма, сравнительно сложны, имеется два частных случая, в которых они могут быть замечательным образом упрощены. Один из этих частных случаев возникает при использовании трехуровневого или двоичного стирающего канала, а второй — при использовании лишь информации о надежности наименее достоверного символа. В этом последнем случае алгоритм, называемый приближенным АРР-алгоритмом, был предложен Форни [22] и позднее Дэвисом [23]. Было показано, что он асимптотически оптимален и при разумных значениях отношения сигнал-шум лишь на несколько десятых децибела хуже полного АРР-алгоритма.

Оптимальный алгоритм посимвольного декодирования Хартмана-Рудольфа (ХР) применим к любому групповому коду. Этот метод включает в себя вычисление решающей функции, которая определена на каждом кодовом слове дуального кода (т. е. на множестве всех проверочных уравнений). Поэтому сложность алгоритма увеличивается с уменьшением скорости. Этот алгоритм лежит в основе двух приближенных методов. В одном из них используются лишь члены минимального веса в решающей функции. Если применить этот метод к коду, допускающему одношаговую ортого-нализацию, то полученный алгоритм окажется очень похожим на АРР-алгоритм порогового декодирования. Второй метод, описанный Гринбергером [24] включает предварительное упорядочение принятых символов по убыванию их достоверности. Алгоритм Хартмана — Рудольфа применяется последовательно к наиболее достоверным символам, затем к до тех пор, пока решающие функции, соответствующие первым символам, не изменятся существенным образом. При небольших значениях отношения сигнал-шум эта процедура требует небольшого числа итераций и поэтому лишь небольшого числа слов дуального кода.

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

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

При изложении методов, в которых делается попытка минимизировать вероятности ошибки последовательности, существенным образом используется понятие информационного множества, введенное в гл. 3. Во всех этих методах делается попытка породить небольшое число кодовых слов, среди которых с большой вероятностью содержится кодовое слово, находящееся на наименьшем расстоянии от принятой последовательности. Затем декодер вычисляет расстояние до каждого из этих кодовых слов и выбирает среди них ближайшее. Простой декодер такого типа основан на алгоритме обобщенного минимального расстояния, предложенного Форни [25]. Это понятие тесно связано с группой алгоритмов, позднее предложенных Чейзом [26]. Идея Чейза состоит в том, чтобы выделить небольшую группу наименее надежных символов. Для порождения различных пробных последовательностей вначале осуществляется жесткое решение относительно каждого принятого символа, после чего предполагается, что различные комбинации ошибок малого веса произошли на местах наименее достоверных символов. Декодирование каждой пробной последовательности дает кодовое слово, после чего вычисляется расстояние между каждым из этих кодовых слов и принятой последовательностью.

Второй метод, который интенсивно изучался Баумертом и Мак-Элисом [27], состоит в упорядочении символов по убыванию достоверности, а затем порождении некоторого числа информационных множеств таким образом, чтобы наиболее надежные символы входили в большинство этих множеств. Затем каждое множество используется для получения пробного кодового слова, и эти кодовые слова сравниваются с принятой последовательностью. Две описанные здесь идеи можно объединять в одном декодере, предполагая, что для каждого порожденного информационного множества на информационных позициях возникают комбинации ошибок малой кратности. Этот метод, представляющий собой вариант алгоритма Омуры, включающий мягкие решения, также исследовался Баумертом и Мак-Элисом.

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

подробно рассматриваться для двоичных 1 кодов в оставшейся части этой главы.

<< Предыдущий параграф Следующий параграф >>
Оглавление