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

4.2.4. Приближение Гринбергера к алгоритму Хартмана-Рудольфа

Гринбергер [24] предложил другой метод уменьшения числа проверочных уравнений, используемых в алгоритме ХР. Его метод основан на том, что информативность символов, принятых с малой достоверностью, мала, так что содержащие их проверочные уравнения можно не рассматривать. Соответствующий алгоритм выглядит следующим образом.

1. Упорядочим принятые символы в соответствии с их достоверностью, помещая наиболее достоверные символы в начало списка.

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

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

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

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

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

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

8. Переупорядочим символы и доставим полученное слово пользователю.

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

выходе около 1%) и что вероятность ошибки при использовании шести итераций (64 кодовых слова дуального кода) почти совпадает с вероятностью ошибки при использовании полного алгоритма (1024 кодовых слова дуального кода). Он обнаружил также, что хотя этот алгоритм не всегда дает правильную оценку всех требуемых символов, но ошибочные символы, имея низкую достоверность, не входят в множество из наиболее достоверных символов и не влияют, таким образом, на выбор декодированного слова. Этот алгоритм, очевидно, хорош для микропроцессорной реализации. К его недостаткам относится то, что требуемую форму матрицы Н нельзя рассчитать заранее и что при декодировании никак нельзя использовать цикличность применяемого кода.

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