7.4. СВЕРТОЧНЫЕ (РЕШЕТЧАТЫЕ) КОДЫ

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

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

Однако возможен и другой, непрерывный принцип кодирования и декодирования, когда на вход кодера поступает непрерывная последовательность информационных символов источника, а с выхода кодера также снимается непрерывная последовательность символов, являющихся функцией входных символов и структуры кодера. В декодере такого типа на вход поступает непрерывная последовательность символов из каната связи (возможно, искажённая ошибками), а на выходе восстанавливается (возможно, с ошибками, но, как правило, меньшими чем канальные) последовательность информационных символов. Наиболее распространённым классом непрерывных кодов являются так называемые свёрточные коды, для которых операция формирования выходной последовательности по заданной входной последовательности является линейной. Свёрточные коды были впервые открыты Финком и Элайесом, вскоре Возенкрафт разработал метод последовательного декодирования сверточного кода [13]. В 1967 г. появился алгоритм Витерби для оптимачьного декодирования свёрточных кодов [6].

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

На рис. 7.10 показан частный случай свёрточного кода со скоростью 1/2 и

Рис. 7.9. Структура свёрточного кодера со скоростью

длиной кодового ограничения При нулевой информационной последовательности выходная кодовая последовательность также равна нулю. В табл. 7.5 приведён пример формирования выходной последовательности для кодера, показанного на рис. 7.10. Выходная последовательность кодера может быть представлена как цифровая свёртка входной информационной последовательности и импульсного отклика кодера (отсюда название кодов — свёрточные).

Таблица 7.5 (см. скан)

Свёрточный код характеризуется следующими параметрами: относительной скоростью кода и избыточностью где кип — число информационных и кодовых символов, соответствующих одному такту работы кодера (для кодера рис. 7.10 ), длиной кодового ограничения (длина регистра кодера); порождающим полиномом кода, коэффициенты которых описывают связи сумматоров с ячейками регистра кодера (для верхнего сумматора для нижнего сумматора Полиномы обычно записывают сокращённо, обозначая каждые три отвода (двоичных коэффициента) как одну восьмеричную цифру (код рис. 7.10 обозначается (7,5)).

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

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

Поиск хороших свёрточных кодов (с наибольшим при заданных обычно осуществляется методом перебора всех порождающих полиномов на ЭВМ. Таблицы хороших кодов приведены в [13].

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

Решёткой называется ориентированный граф с периодически повторяющейся структурой "ячеек". Каждая ячейка содержит колонки из одинакового числа вершин (узлов), соединённых ребрами. Между процедурой кодирования свёрточным кодом и решёткой имеется взаимно однозначное соответствие, которое задаётся следующими правилами [6]:

Рис. 7.10. Свёрточный кодер со скоростью

— каждая вершина (узел) соответствует внутреннему состоянию кодера;

— ребро, исходящее из каждой вершины, соответствует одному из возможных символов источника (для двоичного источника из каждой вершины выходит два ребра — верхнее для 0 и нижнее для 1);

— над каждым ребром отмечены значения символов, передаваемых в канал связи, если кодер находился в состоянии, соответствующем данной вершине и источник выдал символ, соответствующий данному ребру;

— последовательность ребер (путь на решётке) — это последовательность символов, выданных источником.

Рис. 7.11. Решёчка кодера, показанного на рис. 7.10

Так, если под состоянием кодера понимать содержимое двух последних ячеек памяти (2, 3) в регистре сдвига на рис. 7.10, то решётка с четырьмя состояниями, соответствующая данному кодеру, будет иметь вид, показанный на рис. 7.11 (решётка может отражать и нелинейный кодер, когда выходные символы не являются линейной функцией входных). Так же как и блоковые коды, свёрточные допускают представление в виде полубесконечных порождающих или проверочных матриц, однако представление в виде решётки оказывается более удобным для описания алгоритмов декодирования.

Свёрточные коды имеют следующие основные преимущества перед блоковыми при их использовании для исправления ошибок.

1. Они не требуют синхронизации по блокам, а лишь синхронизации коммутаторов К (на передаче и приёме).

2. Если кодовое ограничение выбрать равным длине блокового кода, то исправляющая способность свёрточного кода оказывается больше, чем исправляющая способность такого блокового кода (при наилучшем выборе обоих кодов).

3. Алгоритм декодирования свёрточных кодов допускает простое обобщение на случай мягкого декодирования, что обеспечивает дополнительный энергетический выигрыш.

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

Для оптимального декодирования свёрточных кодов в каналах без памяти часто используется рекуррентный алгоритм декодирования Витерби Рассмотрим его на примере мягкого декодирования в постоянном канале с аддитивным белым гауссовским шумом.

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

где ожидаемый в месте приёма сигнал, соответствующий символу (для двоичных сигналов сигнал, принятый на тактовом интервале.

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

Проще всего можно пояснить данный алгоритм на простом примере Пусть решётка имеет всего два состояния и структуру, показанную на рис. 7.12, где над ребрами подписаны соответствующие метрики. Полагаем, что первый информационный символ 0. Тогда пути, оставленные ("выжившие") на различных шагах, показаны на рис. 7.13. Видно, что на шаге получаем выживший путь, который в условиях наших обозначений (ориентация ребра вниз — 1, вверх — 0) соответствует информационной последовательности

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

Рис. 7.12. Решетка с метриками

Рис. 7.13. Построение "выжившего" пути по

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

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

где произвольные функции векторных аргументов вида

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

Шаг 1. Найти (Поскольку то для каждого значения аргумента это потребует не более чем вычислений.)

Шаг 2 Найти где было найдено на шаге и т.д.

Шаг 5. Найти где были найдены на предыдущих шагах и т. д.

Шаг Найти где были найдены на всех предыдущих шагах.

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

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

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

В § 5.6 было отмечено, что в каналах с МСИ алгоритм Кловского-Николаева (АКН) с обратной связью по решению при фиксированной задержке принятия решения память канала) практически не уступает по помехоустойчивости с той же задержкой решения, но реализуется проще. АКН, полученный первоначально для субоптимального поэлементного приёма дискретных сообщений в каналах с рассеянием (МСИ), можно использовать и для совместной демодуляции-декодирования при свёрточном кодировании, так как свёрточный кодер является аналогом некоторого канала с рассеянием. Естественно, что в этом

случае задержка в принятии решения должна учитывать не только память канала но и длину кодового ограничения.

Свёрточные коды могут декодироваться и другими алгоритмами (например, последовательного декодирования и синдромного декодирования не являющимися, вообще говоря, оптимальными

Последовательное декодирование было впервые введено Возенкрафтом, однако наиболее широко используемый в настоящее время алгоритм принадлежит Фано [13]

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

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

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

Тогда для вероятности ошибки в первом символе в детерминированном канале без памяти с БГШ при декодировании по будет справедлива следующая граница

где число путей с евклидовым расстоянием начинающихся и заканчивающихся на правильном пути; спектральная плотность БГШ.

Используя более полно структуру решётки свёрточного кода, можно оценить также и среднюю вероятность ошибки на бит причём эта величина будет также экспоненциально зависеть от

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

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

Рис. 7.14. Система с кодированной модуляцией

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

Пример такого разбиения для -ричной ФМ показан на рис. 7.15. Созвездия находятся в нижнем ряду рисунка. На рис. 7.16 представлена схема кодирования Унгербоека, использующая представление сигналов в виде созвездий.

Здесь двоичная последовательность символов источника разбивается на блоки по к бит, и первые к бит этих блоков подаются на вход свёрточного кодера, а оставшиеся поступают на модулятор в некодированном виде. Общий принцип состоит в том, что некодированные биты выбирают сигнал в созвездии, а кодированные биты определяют выбор созвездия. (Так, например, для схемы разбиения, показанной на рис. 7 15, кодер Унгербоека, изображённый на рис. 7.16, будет иметь параметры:

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

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

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

Рис. 7.15. Разбиение 8 ричных ФМ сигналов на созвездия

Рис. 7.16. Кодер Унгербоека

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