Выколотые (перфорированные) сверточные коды

Когда необходим сверточный код со скоростью R₁=l/n₁ (1<l<n₁), а не 1/n, этого, конечно, можно добиться, способом описанным ранее. Более практичной альтернативой, однако, оказывается применениевыколотых(перфорированных) кодов. Под выкалыванием или перфорацией понимается удаление из кодовых слов некоторых символов согласно определенному правилу, известному, разумеется, приемной стороне. Возьмем сверточный код со скоростью 1/n<R₁ и разобьем его на блоки из l n-групп каждый. Затем в каждом из блоков удалим по одному кодовому символу в каких-либо g n-группах (в иллюстрации ниже n=2, l=3, g=2, а удаляемые символы показаны черным цветом).

Код, трансформированный таким способом, передает l битов в каждом блоке, длина которого после выкалывания g символов составит ln–g. В итоге скорость выколотого кода

Подбором l и g при заданном n можно варьировать скорость в широком диапазоне, добиваясь ее желаемого значения. В примере выше R₁=3/4.

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

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

Турбо коды

Турбо коды, открытые в 1993 г., входят в число кодов, позволяющих работать на скоростях, близких к пропускной способности или, эквивалентно, к границе Шеннона. Базируются они на достаточно эвристической идее, состоящей в кодировании одного и того же потока данных двумя сверточными кодами, называемыми компонентными. Оба сверточных кода идентичны и должны быть систематическими, т.е. воспроизводить напрямую входной бит данных на фиксированной (обычно первой) позиции текущей кодовой n-группы. Как уже отмечалось, при формировании стандартным (на базе КИХ-фильтра) кодером систематический сверточный код, как правило, имеет худшие дистанционные свойства, чем несистематический. Поскольку при построении турбо кода систематичность критически важна, компонентный кодер приходится модифицировать, применяя рекурсивный фильтр с бесконечной импульсной характеристикой (БИХ-фильтр) на базе регистра сдвига с линейной обратной связью. Последовательность первых символов n-групп на выходе стандартного КИХ-кодера, возбуждаемого битовым потоком a(z), можно найти как u₁(z)=a(z)g₁(z). Чтобы преобразовать код в систематический, необходимо разделить этот результат на первый порождающий полином g₁(z), придя к новой последовательности первых символов:

Как видно, стандартный кодер будет генерировать те же кодовые слова (т.е. с теми же дистанционными свойствами), как и ранее, но находящиеся в систематическом соответствии со входным битовым потоком, если входной полином a(z) перед подачей на вход кодера разделить на первый порождающий полином. Это и реализовано в компонентном кодере с линейной обратной связью, показанном на следующем слайде.

Типичный турбо кодер (см. рисунок) включает два компонентных кодера, причем перед подачей на второй входной битовый поток подвергается псевдослучайной перестановке. Последнюю операцию осуществляет перемежитель. Систематические символы данных второго компонентного кодера отбрасываются и лишь проверочные символы мультиплексируются с кодовым потоком первого компонентного кодера. Поэтому, если компонентный код имеет, к примеру, скорость 1/2, скорость полученного турбо кода равна 1/3. Последнюю легко увеличить до скорости компонентного кода, применяя выкалывание.

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