Главная > Помехоустойчивое кодирование > Теория кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5. Сверточные коды

I. Методы порогового декодирования

5.1. Общий обзор сверточных кодов

Сверточные (или рекуррентные) коды были введены Элайсом [1] из Массачусетского технологического института (МТИ). В отличие от блоковых кодов, когда каждый символ на выходе кодера зависит лишь от конечного числа информационных символов на входе кодера, в случае сверточных кодов символы на выходе кодера., вообще говоря, могут зависеть от бесконечного числа информационных символов. В этом смысле сверточные коды можно рассматривать как обобщение блоковых кодов.

Развитие теории сверточных кодов происходило в трех направлениях в соответствии с тремя важнейшими методами декодирования сверточных кодов: метода порогового декодирования [2], метода декодирования по максимуму правдоподобия [25] и метода последовательного декодирования [14]. Метод порогового декодирования сверточных кодов в принципе аналогичен методу мажоритарного декодирования блоковых кодов. Достоинством этого метода является простота алгоритма, а следовательно, и реализующих его устройств. Точно так же, как и для блоковых алгебраических кодов, число операций, необходимых для декодирования одного информационного символа, для этого алгоритма не превосходит некоторой постоянной величины. Метод декодирования по максимуму правдоподобия теоретически бтрр аффективен, чем метод порогового декодирования, однако сложность устройств, необходимых для его реализации, возрастает экспоненциально с ростом длины кода. И наконец, метод последовательного декодирования является методом вероятностного декодирования, при котором число операций, необходимых для декодирования одного символа, является случайной величиной. При практически приемлемой сложности устройств метод последовательного декодирования по своим характеристикам приближается к методу декодирования по максимуму правдоподобия.

5.1.1. Метод порогового декодирования

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

порогового элемента; исправление ошибок осуществляется далее с помощью символов, поступающих с выхода порогового элемента. Коды, которые допускают декодирование этим методом, должны обладать введенным Месси свойством ортогональности. Ряд кодов со скоростью и меньше, обладающих этим свойством, был построен Месси. В дальнейшем Робинсон и Бернстейн [3] на основе совершенных разностных множеств построили самоортогональные коды, для которых проверочные последовательности обладают свойством ортогональности и могут быть непосредственно поданы на входы пороговых элементов. К числу кодов, которые допускают пороговое декодирование, относятся также равномерные коды [36], аналоги кодов Рида — Маллера [2] и др.

Сверточные коды, исправляющие пачки ошибок, впервые были предложены Хегельбергером [4]. В дальнейшем Вайнер и Эш [6], Препарата [7], Берлекэмп [5], Месси [8] и др., основываясь главным образом на теории матриц, построили ряд квазиоптимальных кодов, исправляющих пачки ошибок и требующих для этого защитный интервал, близкий к минимально возможному. Ивадари [10—12], разлагая синдромы на простые конфигурации, построил класс кодов, допускающих очень простое кодирование и декодирование.

Для исправления случайных ошибок и пачек ошибок Коленбург разработал так называемые диффузные коды, допускающие пороговое декодирование [9]. Относительно регулярный метод построения самоортогональных диффузных кодов предложил Тонг [13].

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

<< Предыдущий параграф Следующий параграф >>
Оглавление