3.3. Пороговое декодирование

Пороговое декодирование аналогично декодированию Меггитта; однако оно может применяться лишь к кодам определенной структуры. Для таких кодов пороговое декодирование является весьма простым и эффективным алгоритмом. Различные варианты алгоритма порогового декодирования (допускающие мягкое декодирование) будут рассмотрены в гл. 4. Здесь изложим упрощенный вариант алгоритма (называемый мажоритарным декодированием), который применим только при жестком декодировании. Этот метод будет изложен на нескольких примерах. Мы ограничимся двоичными кодами, поскольку они представляют наибольший практический интерес. Применение этого алгоритма к сверточным кодам будет обсуждаться в гл. 7.

Основная идея, лежащая в основе мажоритарного декодирования, может быть проиллюстрирована на следующем примере. Рассмотренный в разд. 3.1 -код. БЧХ является одним из кодов, к которым можно применить пороговое декодирование. Проверочная матрица этого кода получается транспонированием цикла а в табл. 3.1. Беря столбцы получаем следующие проверочные уравнения:

Поскольку эти уравнения являются проверочными, то они зависят только от вектора ошибки, гак что

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

Рис. 3.11. Пороговый декодер для -кода БЧХ

позволяет исправлять не только все одиночные и двойные ошибки, но и некоторые комбинации ошибок большего веса.

Мажоритарный декодер для такого кода показан на рис. 3.11. В качестве дополнительного элемента он содержит цепь обратной связи (с выхода мажоритарного элемента). Наличие этой связи не обязательно для работы декодера, но может улучшить его характеристики (в данном случае существенно) при больших отношениях сигнал-шум. Декодер работает абсолютно аналогично декодеру Меггитта, вычисляя сперва синдром, а затем сдвигая его по крайней мере на один полный цикл для исправления ошибок. Если обратная связь не используется, то достаточно одного цикла — и последовательность может поступать к пользователю после исправления ошибок. Если обратная связь имеется, то для полной реализации предоставляемых ею возможностей должен быть выполнен по крайней мере еще один цикл. Наличие обратной связи позволяет декодеру исправлять некоторые дополнительные комбинации из трех и четырех ошибок. Например, если возникает комбинация из трех ошибок {9, 13, 14), то будет исправлено. Если, однако, сдвинуть эту комбинацию таким образом, чтобы превратилось в ем, то она будет выглядеть как и ошибка в позиции 14 не будет исправлена. Если же использовать обратную связь, то первое исправление устраняет также эффект соответствующей ошибки, так что при следующем сдвиге комбинация будет иметь вид т. е. ее можно исправить.

Пороговое декодирование легче всего применять к циклическим кодам. Заметим, что проверки на четность, ортогональные по формируются как линейные комбинации символов синдрома.

Таблица 3.4. (см. скан) Порождающие многочлены и проверочные уравнения, ортогональные по последнему символу

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

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

Рассмотренный -код является кодом с одношаговой ортогонализацией (он требует одного мажоритарного элемента). Помимо -кода одношаговую ортогонализацию допускают коды максимальной длины [в них всегда можно найти проверочных символов, ортогональных по любой заданной позиции]. Другими кодами с одношаговой ортогонализацией, представляющими практический интерес, являются и -коды. Эти коды были введены Велдоном [19] в 1966 г. и называются разностными, поскольку строятся с помощью совершенных разностных множеств. Для каждого из этих кодов можно найти проверочных уравнений (для четного ортогональных по последнему символу. Порождающие многочлены и множество проверок, ортогональных по последнему символу, приведены в табл. 3.4. Проверочные уравнения даются как линейные комбинации символов синдрома. Приведены также так называемые многочлены разностных множеств Многочлены по модулю лежат в нулевом пространстве кода, порожденного и содержат все ортогональные символы проверок на четность.

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

Поэтому соответствующие проверочные уравнения имеют вид

Рис. 3.12. Вероятность первой ошибки декодирования для разностных циклических кодов с пороговым декодированием

Расчетные кривые характеристик разностных кодов приведены на рис. 3.12. Эти кривые показывают вероятность первой ошибки декодирования, но не отражают улучшения (или ухудшения), которое может возникнуть в результате введения обратной связи. Они были рассчитаны путем перечисления всех наборов ошибок, ведущих к неправильному декодированию первого символа. (См. задачи.)

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

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

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

Рис. 3.13. Двухшаговый мажоритарный декодер для -кода Хемминга

эта сумма может быть определена безошибочно. Аналогично позволяют вычислить сумму Наконец, заметим, что две вычисленные суммы дают пару оценок, ортогональных по Таким образом, двухступенчатый мажоритарный декодер (с двумя уровнями мажоритарных элементов) для -кода имеет структуру, показанную на рис. 3.13. Ясно, что данный код может быть декодирован проще, однако этот пример иллюстрирует способ -шагового декодирования. Для многих кодов -шаговое декодирование является наиболее простым из известных алгоритмов. Два хорошо известных класса кодов допускают -шаговое декодирование: евклидово-геометрическое (некоторые из которых эквивалентны кодам Рида — Маллера с опущенным символом) и проективно-геометрические коды. Оба этих класса кодов подробно обсуждаются в книге Питерсона и Вэлдона [1].

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