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

4.3. Алгоритм Велдона

Аналогично алгоритмам АРР и ХР при алгоритме Велдона [21] дается несколько различных оценок для каждого переданного символа, образуется из них взвешенная сумма с весами, соответствующими их достоверности, и вычисляется решающая функция, подобная (4.5) или (4.21). Отличие алгоритма Велдона от предыдущих состоит в том, что первоначальные оценки вычисляются с помощью нескольких декодеров с жестким решением. Характеристики алгоритма Велдона хуже характеристик других методов мягкого декодирования, однако его привлекательная черта состоит в простоте. Здесь приведем лишь краткое описание алгоритма. Подробности читатель может найти в оригинальной статье Велдона. Основной алгоритм Велдона состоит в следующем.

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

В обычном случае, когда хорошим субоптимальным выбором является выбор в качестве целых чисел в интервале от 0 до

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

где должны удовлетворять равенству

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

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

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

4. Объединяем оценок отдельно для каждого символа, используя решающую функцию

и полагаем если если В формуле (4.22) через обозначен и символ декодированной последовательности, а через весовой коэффициент, пропорциональный достоверности оценки.

Коэффициенты в (4.22) вычисляются следующим образом. Пусть

где фиксированное число, отвечающее данному декодеру, зависит от числа ошибок, исправленных этим декодером. Обычно

где индекс соответствует младшему разряду, следующему разряду и т. д. Так, для восьмиуровневой схемы принимает значения 1, 2, 4. Значение определяется по следующей формуле:

где число жестких ошибок, сделанных декодером.

Можно показать, что приведенные здесь значения позволяют исправить с помощью алгоритма Велдона любую комбинацию мягких ошибок, вес которой, вычисленный с помощью упомянутых не превосходит Предположим, например, что используется код длиной 15 с расстоянием 5 и восьми-уровневым демодулятором. Предположим, что передавалась нулевая последовательность, а принятой оказалась последовательность Вес ошибки равен 17, и эта ошибка должна быть исправлена, поскольку Три последовательности, которые нужно декодировать, используя жесткое решение, имеют вид (начиная с младшего разряда)

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

При использовании этих весов в (4.22) коэффициенты всегда будут умножаться на 1, а иногда на —1. Таким образом, в наихудшем случае

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

К сожалению, декодер Велдона оказывается неспособным правильно декодировать многие комбинации мягких ошибок, которые исправляются истинным декодером максимального правдоподобия для последовательностей. Предположим, как и ранее, что передавалась нулевая последовательность, а принятая последовательность имеет вид Вес этой комбинации ошибок равен 19; однако ее расстояние до ближайшего кодового слова веса 5 равно 20. (Этим кодовым словом является Три последовательности, которые нужно декодировать с помощью жестких декодеров, имеют вид

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

Чтобы получить пример характеристик декодера Велдона, был промоделирован алгоритм для -кода, рассмотренного в разд. 4.2. Использовался трехразрядный демодулятор с мягким решением, и значения были выбраны равными В каждом из грех жестких декодеров таблица синдромов позволяла исправлять все комбинации из одной и двух ошибок, 490 из 1330 возможных комбинаций трех ошибок, 301 из 5985 возможных комбинаций четырех ошибок и одну комбинацию из пяти ошибок. Расстояние между порогами выбиралось так, чтобы процедура декодирования гарантировала исправление всех комбинаций ошибок веса 21 или менее и исходя из этого вычислялась верхняя граница вероятности ошибки. Расстояние между порогами затем менялось до тех пор, пока эта граница не оказывалась наименьшей возможной.

При наилучшее расстояние, полученное таким методом, оказалось равным Следует отметить отличие от оптимального расстояния между порогами при алгоритме АРР, равного

Рис. 4.7. Характеристики алгоритма Велдона для -кода

приблизительно Найденное оптимальное значение использовалось при моделировании. В алгоритм было внесено одно небольшое изменение. Было замечено, что большое число ошибок возникает, когда вес для каждого из трех декодеров равен 0 на каждом символе. Эти ситуации обнаруживались, и декодер использовал в этом случае лишь результаты оценки последовательности, соответствующей старшему разряду в представлении В результате почти во всех указанных случаях декодирование производилось правильно. Полученная кривая показана на рис. 4.7. Для сравнения приведены также кривые, характеризующие такой же алгоритм с расстоянием между порогами, равным и алгоритм АРР без квантования при наличии обратной связи. Поскольку структура алгоритма Велдона аналогична структуре алгоритмов АРР и ХР, то можно было бы считать, что введение обратной связи улучшает характеристики декодера Велдона. Оказывается, однако, что это не так. Одно из возможных объеяснений состоит в том, что первое применение алгоритма Велдона почти всегда дает кодовое слово, в то время как первое применение алгоритмов АРР и ХР часто приводит к последовательности, которая не является кодовым словом, но переводится в него при последующем выполнении алгоритма.

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