7. ДРУГИЕ МЕТОДЫ ДЕКОДИРОВАНИЯ СВЕРТОЧНЫХ КОДОВ

Методы сверточного кодирования исследовались в течение многих лет. Сверточные коды были впервые введены Элайсом [63] в 1955 г. Вскоре после этого Возенкрафт [64] разработал метод, который он назвал последовательным декодированием. Этот метод активно изучался в течение более чем 20 лет. Он представляет собой декодирование путем проб и ошибок, и его характеристики иногда достигают или даже превосходят характеристики декодеров Витерби. Поэтому в некоторых практических случаях такой метод оказывается более предпочтительным. Одно из основных свойств последовательного декодирования состоит в том, что время, требуемое для декодирования данного информационного символа, является случайной величиной. В этом отношении алгоритм

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

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

Одним из широко используемых методов синдромного декодирования является декодирование путем табличного поиска с обратной связью. Как следует из названия, формирование поправочных символов по символам синдрома осуществляется путем поиска в таблице (которая может храниться в постоянной памяти). Этот метод очень похож на детектирование Меггитта для блоковых кодов, рассмотренное в гл. 3. Другим широко используемым методом синдромного декодирования является пороговое декодирование. Алгоритмы порогового декодирования, используемые для жесткого или мягкого решения, по существу, совпадают с соответствующими алгоритмами декодирования блоковых кодов, обсуждавшимися соответственно в гл. 3 и 4. Был найден широкий класс сверточных кодов, допускающих пороговое декодирование.

7.1. Методы синдромного декодирования

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

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

7.1.1 Основные понятия

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

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

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

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

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

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

Данный алгоритм, по существу, совпадает с алгоритмом, применяемым при декодировании путем табличного поиска с обратной связью. Рассмотрим, например, принятую последовательность содержащую ошибки в первом и третьем ребрах, как показано на рис. 7.1 (в предположении, что передавалась нулевая последовательность). Начиная с состояния 0 и рассматривая два следующих ребра, видим, что соответствующий участок принятой последовательности нужно сравнить с каждой из четырех возможных кодовых последовательностей и Ясно, что ближайшей (в метрике Хемминга) кодовой последовательностью будет 00 00, так что решением

Рис. 7.1. Кодовое дерево для систематического кода с и с порождающим многочленом

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

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

Используя формулы (7.2) — (7.4), можно выразить синдром как функцию последовательности ошибок в канале, т. е. как функцию от

Оценка информационной последовательности, производимая декодером, имеет вид

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

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

В рассмотренном примере кода с синдром равен

Символ синдрома, соответствующий ребру, имеет поэтому вид

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

при наличии одиночной ошибки в информационном символе соответствующий синдром

в то время как при появлении одиночной ошибки в проверочном символе

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

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

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

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

Рис. 7.2. Кодер и декодер с обратной связью для кода с

реализации требуется существенно более сложное решающее устройство. Такие коды будут вскоре рассмотрены.

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

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

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

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

Заметим, что кодовое расстояние определяется как функция Характеристики фиксированного кода можно улучшить, увеличивая Кроме того, при L величина превращается в свободное расстояние

Определение. Кодовое расстояние при детерминированном декодировании, обозначаемое определяется как наименьшее

число позиций на длине кодового ограничения (при детерминированном декодировании), в которых различаются две кодовые последовательности с разными значениями

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

Соответствующие корректирующие способности при этих двух подходах выражаются формулами

7.1.1.2. Анализ характеристик. Характеристики рассчитываются путем суммирования вероятностей всех событий, приводящих к ошибкам. Это легко проиллюстрировать на примере кода с Вероятность ошибки символа при детерминированном декодировании равна вероятности несовпадения корректирующего символа с ошибкой, т. е.

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

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

наличии такого помощника получаем следующий корректирующий символ:

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

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

Важность понятия декодирования с помощником состоит в том, что вероятность первой ошибки декодирования в точности совпадает с Если ранее ошибок при декодировании не возникало, то и оценка для декодера с обратной связью имеет вид (7.16). Это условие остается выполненным до тех пор, пока не возникнет первая ошибка декодирования. Таким образом, вероятность первой ошибки декодирования задается равенством

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

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

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

Вообще говоря, может превышать Единственный класс кодов, для которых известно, что при состоит из кодов, для которых [заметим, что согласно (7.11) — (7.13) всегда [65]. Это утверждение станет очевидным, если учесть, что при

Если обратная связь не приводит к бесконечному распространению ошибок и если то при

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

Неограниченное распространение ошибок первого типа вызывается плохим выбором кода. Плохие — это так называемые коды с катастрофическим распространением ошибок (см. гл. 6). Месси и Сайн [60] определили свойства порождающего многочлена кода, которые вызывают такой эффект. Заметим, что такие коды обладают плохими свойствами независимо от метода их декодирования. При использовании систематических кодов такой эффект никогда не возникает (все информационные последовательности бесконечного веса приводят к кодовым последовательностям бесконечного веса). Однако даже при хорошем выборе кода декодирование с помощью плохого декодера может вызвать неограниченное распространение ошибок второго типа (в результате появления конечного числа ошибок в канале декодер может внести бесконечное число ошибок в информационные символы). Было пока зано, что при декодировании путем табличного поиска с обратной

связью такой эффект возникает в случаях, когда глубина декодирования слишком мала [66].

Для кода с используют глубину декодирования Оказывается, что уменьшение глубины декодирования до приводит к катастрофическому влиянию на характеристики кода. Месси и предложили исследовать распространение ошибок, наблюдая автономное поведение (т. е. ситуацию, когда на вход поступает нулевая последовательность) регистра синдрома [67]. Регистр является конечным автоматом, и исследование его автономной диаграммы состояний оказывается очень полезным.

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

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

Автономные схемы состояний для этих двух случаев и для случая показаны на рис. 7.3. В случае, изображенном на рис. 7.3, о, ошибка в информационном символе приводит к переходу в состояние 3, в результате которого возникнет правильная коррекция и декодер переходит в состояние 0. Таким образом, распространения ошибок не происходит. Однако при появлении ошибки в проверочном символе возникают трудности. Такая ошибка вызывает переход в состояние 2, а затем в состояние 1, где производится неправильная коррекция. При каждой коррекции

Рис. 7.3. Автономные схемы переходов между состояниями регистра синдрома для нескольких декодеров кода с

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

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

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

Другим часто используемым является несистематический код с для которого Было показано, что при декодирование такого кода путем табличного поиска при наличии обратной связи приводит к неограниченному распространению ошибок второго типа [66]. При расстояние, на которое распространяются ошибки после исчезновения ошибок в канале, не ограничено, однако его среднее значение относительно невелико. Наконец, при расстояние, на которое распространяются ошибки, ограничено.

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