Сверточные коды. 
Теория электросвязи

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

Структурная схема сверточного кодера показана на рис. 7.29. Внутренняя структура кодера образуется сочетанием многоразрядных регистров сдвига и сумматоров по модулю 2. В зависимости от удобства схемотехнической реализации, формирования и сопряжения различных тактовых частот в состав кодера может входить один или несколько регистров. Входная информационная последовательность с тактовой частотой F_T в последовательно-параллельном преобразователе (S/P) разделяется на блоки по^{потоков,} которые непрерывно поступают в соответствующие входы кодера, задавая набор его входных данных. Регистры кодера тактируются с частотой F_T/k_{). На выходе кодера в каждом такте формируются п₀ выходных символов, которые также преобразуются в последовательный поток с повы;

Рис. 7.29. Структурная схема сверточного кодера

шенной тактовой частотой (F_T/k₀)n₀ = F_T/R и поступают в канал связи. Выходная последовательность кодера может быть представлена как цифровая свертка входной информационной последовательности и импульсного отклика кодера (отсюда название кодов — сверточные).

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

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

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

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

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

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

Рис. 730. Структурная схема декодера Витерби.

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

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