4.5.2. Алгоритмы типа алгоритма Омуры

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

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

Если, однако, вначале упорядочить символы по их достоверности и включить в начальное проверочное множество наименее достоверных из них, то можно ожидать, что фактическое число комбинаций ошибок в информационном множестве существенно уменьшится. Развив эту идею, группа сотрудников Лаборатории реактивных двигателей определила, что если рассмотреть (128, 64)-код и произвести проверку всех одиночных, всех двойных и примерно 25% наиболее вероятных тройных комбинаций ошибок, то получится декодер, который хуже декодера максимального правдоподобия примерно на При этом требуется рассмотреть примерно 10 000 проверочных комбинаций, и хотя это число сравнительно велико, оно может оказаться практически реализуемым при низких скоростях передачи данных. Если, например, для проверки одной комбинации требуется 50 не, то на декодирование одного кодового слова уйдет примерно Поскольку каждое кодовое слово содержит 64 информационных символа, соответствующая скорость данных равна

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

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

Их оценки были основаны на следующем эксперименте. При использовании 1000 определенных ранее информационных множеств было порождено 10 000 векторов ошибки для жесткого решения, которые были упорядочены по достоверности. Каждый из векторов ошибки сравнивался с каждым информационным множеством, и отмечалось, сколько сравнений нужно провести, чтобы покрыть все ошибки, все ошибки, кроме одной, все ошибки, кроме двух, и т. д. Результаты этого эксперимента при отношении сигнал-шум показаны на рис. 4.13. Приведенные значения соответствуют уровню, при котором непокрытым остается ошибок.

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