Свёрточные коды. Техника кодирования.

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

Тем не менее ради удобства свёрточный код также характеризуют двумя положительными числами n и k. Отношение этих чисел k / n называется степенью кодирования . Это значит, что в бесконечно длинной последовательности на выходе кодера на каждые n передаваемых символов приходится k информационных и r = n-k проверочных символов. Избыточность кода при этом, как обычно, определяется отношением R = r / n.

Кодер свёрточного кода содержит N = kК -разрядный регистр сдвига, n многовходовых сумматоров mod2 и n -входовый мультиплексор (рис. 3.6). Целое число К называется длиной кодового ограничения.

В течение k тактов в регистр сдвига быстро вводятся очередные k информационных символов, а затем мультиплексор совершает цикл опроса сумматоров, выдавая очередные n символов на выход кодера. Далее указанный цикл многократно повторяется в той же последовательности.

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

Таким образом, для полного описания способа кодирования нужно задать n векторов связи (генераторных полиномов). Если k первых генераторных полиномов равны единице, получается систематический свёрточный код, у которого из каждых n позиций первые k позиций занимают информационные символы.

В качестве примера рассмотрим очень простой систематический свёрточный код, у которого довольно низкая степень кодирования k / n =1/3, высокая избыточность R=2/3 и небольшая длина кодового ограничения К =3. Зададим для этого кода три генераторных полинома

, , ,

(3.61)

из которых генерирует (точнее, тождественно передаёт) информационную последовательность (И), а и генерируют первую (П1) и вторую (П2) проверочные последовательности соответственно. Схема кодера дана на рис. 3.7.

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

Существуют разные способы декодирования свёрточных кодов. Один из самых простых – это метод порогового декодирования.

Таблица 3.4 - Последовательности символов
в кодере свёрточного кода k/n =1/3

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

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

Кстати, этот же метод декодирования можно представить в другой интерпретации: рассматриваются два возможных варианта значений текущего информационного символа (0 или 1) и для каждого варианта вычисляются ожидаемые значения всех пяти символов. Выбирается тот вариант, для которого ожидаемые значения символов в этой пятёрке ближе к тому, что наблюдается в действительности (по количеству совпадений).

Именно эта идея реализуется в более сложных алгоритмах декодирования, причём рассматриваются различные варианты не для одного, а для целой серии, состоящей из m предыдущих информационных символов. Чем длиннее серия, тем больше число вариантов , тем выше объём вычислений, но зато при этом повышается корректирующая способность кода.

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

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

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