4.5. Алгоритмы перестановочного декодирования

Основной метод выбора нескольких информационных множеств, использования каждого из них для порождения кодового слова и выбора кодового слова, ближайшего к принятой последовательности, уже обсуждался в гл. 3. Наибольшее развитие этот метод получил в работах группы Лаборатории реактивных двигателей (ЛРД) [27, 31]. Все предложенные варианты метода перестановочного декодирования требуют предварительного упорядочения принятых символов по их достоверности. Все эти схемы являются более или менее интуитивными, с очень косвенными теоретическими обоснованиями выбора различных параметров. Поэтому для изложения этих методов здесь выбран исторический подход. Обсуждаемые алгоритмы разделены на три группы: с использованием только информационных множеств, типа алгоритма Омуры и частичного синдромного декодирования.

4.5.1. Алгоритмы с использованием только информационных множеств

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

Баумерт и Мак-Элис [27] из ЛРД этим методом декодировали квадратично-вычетные коды с параметрами (48,24) и (80,40). При декодировании -кода принималось два различных значения При выбиралось 130 информационных множеств, покрывающих все комбинации из четырех или менее ошибок на оставшихся 40 позициях. При выбиралось 124 информационных множества, покрывающих все комбинации из трех или менее ошибок на оставшихся 32-х позициях. Во втором случае удалось добиться улучшения примерно на по сравнению с первым, и, по оценкам из [27], характеристики второго декодера очень близки к характеристикам декодера максимального правдоподобия для этого кода. Оказалось, что для -кода выбор двух различных параметров приводит практически к

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

В работах [27, 31] приведены результаты попыток использовать этот метод для декодирования -кода БЧХ; достигнут лишь ограниченный успех. Затем осуществлялась попытка разбить слово на четыре части. Предполагалось, что 16 наиболее достоверных символов не содержат ошибок и включаются поэтому в каждое информационное множество. В 40 следующих по достоверности символах предполагалось наличие не более двух ошибок, а в следующей группе из 32 ошибок — не более четырех. Оставшиеся 40 наименее достоверных символов не включались ни в одно информационное множество. Хотя в этих работах не указано, сколько информационных множеств использовалось, легко предложить следующее решение. Для покрытия всех возможных упомянутых комбинаций ошибок можно использовать 64 проверочных символа. Ни один из них не расположен на позициях поскольку соответствующие символы предполагаются безошибочными. Однако для покрытия всех двойных ошибок между позициями 17 и 56 можно использовать восемь проверочных символов. Все такие ошибки можно исправить с помощью 45 покрывающих наборов (порожденных с помощью метода, описанного в подразд. 3.2.3.2). Все комбинации из четырех ошибок на позициях можно покрыть с помощью 16 проверочных символов. Множество покрывающих наборов для этого случая задается множеством ненулевых кодовых слов -кода (с кодовым расстоянием 16). Наконец, оставшиеся 40 проверочных символов всегда соответствуют позициям в которых может содержаться любое число ошибок. Поскольку имеются в распоряжении 31 покрывающий набор для группы из 32 символов и 45 покрывающих наборов для группы из 40 символов, то общее число требуемых покрывающих наборов равно 1395.

Характеристики, полученные этим методом, существенно лучше предыдущих, однако не достигают уровня характеристик декодера максимального правдоподобия. Развитие описанного метода [27, 31] привело к алгоритму, согласно которому производится еще более тонкое подразделение кодового слова. В результате собраны достаточные статистические данные о распределении ошибок как функции номера символа в списке символов, упорядоченных по надежности. Затем предложено выбирать информационные множества случайно таким образом, чтобы частота нулей приближенно согласовывалась с энтропией (т. е. распределения ошибок. Другими словами, если вероятность ошибки на данной позиции близка к 0,5, то символ должен включаться в большинство проверочных множеств, в то время как при очень

Рис. 4.12. Весовые функции для -кода

малой вероятности ошибки символ должен включаться в проверочное множество очень редко.

Весовые функции, приведенные в работах [27, 31], показаны на рис. 4.12. Энтропия была нормирована так, чтобы первые 30 (приблизительно) символов входили во все информационные множества. Поскольку вероятность возникновения одной или нескольких ошибок весьма мала, такой выбор почти не оказывал влияния на общие характеристики системы. Чтобы каждое информационное множество состояло из 64 элементов, оказалось необходимым несколько отойти от чисто случайного выбора. Баумерт обнаружил, что если порождать информационные множества таким способом, то для достижения характеристик, близких к получаемым при декодировании максимального правдоподобия, требуется примерна 1000 информационных множеств.

В дальнейшем Гринбергер исследовал некоторые другие весовые функции (см. рис. 4.12), обнаружив, что, хотя функция Баумерта — одна из лучших, алгоритм не особенно чувствителен к точному виду весовой функции. Гринбергер исследовал также различные способы порождения информационных множеств и заметил, что, расположив множества так, чтобы каждое отличалось от предыдущего небольшим числом элементов, объем необходимых вычислений можно минимизировать. Однако для порождения 1000 различных проверочных матриц по-прежнему требуется достаточно много вычислений, так что описанный метод применим лишь в случае сравнительно низких скоростей передачи.