§ 6.3. Схемы порогового декодирования для циклических кодов

Коды максимальной длины являются циклическими кодами, т. е. кодами, для которых циклический сдвиг и любого кодового слова является снова кодовым словом. Питерсон [12, стр. 167— 171] показал, что любой циклический -код может быть получен с помощью линейной последовательной схемы, содержащей регистр сдвига из или разрядов. Как мы сейчас покажем, циклическая структура этих кодов делает возможным также упрощение схем порогового декодирования.

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

циклических кодов делает возможным использование схем порогового декодирования, очень похожих на декодеры типов I и II для сверточных кодов. Назовем эти схемы циклическими декодерами типов I и II и проиллюстрируем их конструкцию на примере -кода максимальной длины с проверочной матрицей (181).

Рис. 24. Циклический декодер типа -кода максимальной длины.

На выходе мажоритарного элемента будет: 1, если 1 поступили на три входа; сигнал об ошибке, если 1 поступили на два входа; 0, если на входы поступило не более одной 1. Обозначения на рис. 24 и 26 такие же, как на рис. 11

Циклический декодер типа I для этого кода показан на рис. 24. Принятые символы поступают одновременно в -разрядное буферное запоминающее устройство и в -разрядное кодирующее устройство. После сдвигов -разрядный регистр содержит сумму по принятых проверочных символов и кодированных принятых информационных символов. По теореме 9 эта сумма как раз и есть совокупность результатов проверок. Затем эти результаты комбинируются в соответствии с правилом образования системы проверок, ортогональных относительно после чего результаты ортогональных проверок взвешиваются и сравниваются с порогом. На выходе порогового элемента получаем

-декодированное значение символа Оно складывается с как раз в это время поступающим из буферного запоминающего устройства, в результате чего и получается декодированное значение символа Так как код циклический, то приведенная схема (без отмеченной пунктиром связи) будет продолжать правильно работать в последовательные промежутки времени; после следующего сдвига на выходе окажется

Декодер типа I для циклического кода имеет такой же вид, как предложенный ранее Меггитом [10] для декодирования произвольного циклического кода. Меггит определяет основной решающий элемент схемы только как комбинаторный элемент, на выходе которого появляется единица для всех сочетаний проверок в -разрядном регистре, соответствующих комбинациям ошибок с единицей в первом разряде. Вообще, кажется, что нет способа построить для этой схемы простой комбинаторный элемент. Трудность заключается в следующем. Существует единственная комбинация ошибок веса комбинаций веса комбинаций веса три и т. д., содержащих единицу в первом разряде. Каждой исправимой комбинации ошибок соответствует свой отличный от других синдром. Таким образом, для того чтобы декодер мог исправить любую комбинацию или менее ошибок, комбинаторный элемент должен распознавать приблизительно сочетаний проверок. Если то пытаться строить такой комбинаторный элемент с помощью стандартных приемов минимизации, используемых в логических схемах, практически нецелесообразно. Единственная надежда состоит в том, чтобы отыскать некоторые специальные структурные свойства кода, которые бы подсказали практически приемлемую форму комбинаторного элемента.

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

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

Меггит ввел показанные на рис. 24 пунктиром связи с его основным циклическим декодером.

Рис. 25. Циклический декодер типа И для -кода максимальной длины.

На выходе мажоритарного элемента будет: 1, если 1 поступили на три или четыре входа; сигнал об ошибке, если 1 поступили на два входа; 0, если на входы поступило не более одной 1.

Это приводит к тому, что -разрядный регистр сдвига содержит проверки, соответствующие принятым символам, когда последние изменяются в процессе декодирования. Если на выходе регистра оказывается правильное кодовое слово, то после завершения декодирования регистр будет содержать только нули. Наличие хотя бы одной единицы соответствует обнаружению неисправимой ошибки. Наконец, как должно быть ясно из рис. 24, если декодированные проверочные символы не представляют интереса (что обычно и бывает), то буферное запоминающее устройство можно сократить до разрядов. Если это сделано, то общее число разрядов регистров сдвига в циклическом декодере типа I будет

Циклический декодер типа II для того же самого -кода максимальной длины показан на рис. 25. Эта схема реализует алгоритм порогового декодирования в той его форме, которая определена в . В этом случае система уравнений, используемых

для принятия решения при декодировании, имеет вид

(Сумма принятых символов, кроме шумовые символы которых контролируются проверкой, ортогональной относительно

Взвешенное суммирование этих величин и сравнение с порогом ничем не отличаются от описанных в § 4.16.

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

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

Основные черты циклических декодеров типов I и II можно суммировать в следующей теореме.

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

В теореме 20 предполагается, что мажоритарное декодирование применяется для системы проверок, ортогональных относительно, ей которые можно построить. В условии теоремы мы выделили часть

предложения, чтобы оттенить тот факт, что если хотят, чтобы циклические декодеры типов I и II были эффективными и практичными декодирующими устройствами, то структура кода должна допускать построение проверок относительно Для предположения о том, что такая структура является общим свойством циклических кодов, никаких оснований нет.

Рис. 26. Аналоговая схема для вычисления весовых множителей и порога.

Когда для определения символа из системы проверок, ортогональных относительно применяется АВ-декодирование, то на каждом входе порогового элемента циклических декодеров типов I и II становится необходимым использовать весовые множители. Как показано в § 4.1, в случае двоичного симметричного канала эти весовые множители постоянны. В случае канала, параметры которого изменяются во времени, весовые множители и порог можно вычислять с помощью аналоговой схемы, подобной той, которая показана «а рис. 14. Такая схема для -кода максимальной длины показана на рис. 26. Входами этой схемы являются где Работа этой схемы аналогична работе схемы рис. 14 и дальнейших пояснений не требует.