СВЕРТОЧНЫЕ КОДЫ. ДЕКОДИРОВАНИЕ СВЕРТОЧНЫХ КОДОВ.

28.1. Основные параметры и характеристики сверточных кодов

28.2 Методы декодирования сверточных кодов

28.3. Схемное построение декодера Витерби

28.1. Основные параметры и характеристики сверточных кодов

При сверточном кодировании преобразование информационных последовательностей в выходные кодовые происходит

непрерывно. Кодер двоичного сверточного кода содержит сдвигающий регистр из

разрядов и сумматоры по модулю 2 для

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

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

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

1. Число информационных символов, поступающих за один такт на вход кодера –

2. Число символов на выходе кодера –

, поступившим на вход символам за такт.

3. Скорость кода определяется соотношением

и характеризует избыточность, вводимую при кодировании. Так, для кодов Финка (рис. 27.1) и кодеров (рис. 27.2) значение

, т. е. на вход кодера одновременно поступает

информационных символа, а на

кодовых символа за один входной такт. Типичными являются скорости

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

количество ошибок на выходе приемника.

число символов в выходной последовательности превышает их число во входной информационной

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

благодаря хорошим корректирующим свойствам.

5. Память кода, называемая также входной длиной кодового ограничения или информационной длиной кодового слова,

определяется максимальной степенью порождающего многочлена в составе порождающей матрицы

– степень (от degree – англ.) порождающего многочлена.

В свою очередь, максимальная степень одного из порождающих многочленов определяет число разрядов

сдвига кодера (рис. 27.3). С учетом младшего члена многочлена

и задает необходимое число разрядов в регистре сдвига. Таким образом, память кода (входная длина кодового ограничения)

задается простым выражением

входном информационном символе, поступающем в кодер для формирования сверточного

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

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

вводится в соответствующую схему суммирования по модулю 2 или непосредственно на контакт

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

разрядов в регистре сдвига на один уменьшается. Число элементов памяти сдвигающего регистра определяет сложность

6. Полная длина кодового ограничения (ДКО), называемая также ДКО по выходу кодера или кодовой длиной блока,

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

информативного символа и выходом в канал соответствующего символа, в формировании которого входной символ принимает

участие. С учетом того, что каждые

записанные в сдвигающем регистре кодера информационные символы представляются

символами, полная ДКО будет определяться выражением

или в соответствии с (28.4) и (28.5)

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

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

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

7. Маркировка сверточного кода отличается разнообразием, но во всех обозначениях кода присутствуют основные параметры –

, определяющие скорость кода

. Так, в некоторых источниках код обозначается

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

. Будем придерживаться этой позиции и маркировать код тремя параметрами

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

и число разрядов в сдвигающем регистре

кодера, причем для наиболее часто применяемых кодов с

двоичных кодовых последовательностей определяется числом “единиц”, входящих в эту последовательность или

для кодовой комбинации 101011, а

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

-й кодовыми комбинациями при условии их одинаковой

длины. Для любых двух двоичных кодовых комбинаций кодовое расстояние равно числу несовпадающих в них символов. В

общем виде кодовое расстояние может быть определено как суммарный результат сложения по модулю 2 одноименных

разрядов кодовых комбинаций –

-е символы кодовых комбинаций

– длина кодовой комбинации.

10. Минимальное кодовое расстояние

– это наименьшее кодовое расстояние для набора кодовых комбинаций постоянной

длины. Перебрав все возможные пары кодовых комбинаций, определяем минимальное из них

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

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

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

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

Это число символов, которое декодер должен хранить в памяти для обработки принимаемой кодовой последовательности,

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

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

характеристик, однако к конце концов происходит насыщение.

Ширина окна декодирования должна быть не меньше полной длины кодового ограничения

(28.7) и зачастую в несколько раз

ее превышает. В соответствии с различной длиной

обрабатываемых в декодере сегментов, минимальное расстояние

Хемминга для любых пар кодовых слов называется

-м минимальным свободным расстоянием сверточного кода и

, то оно называется просто минимальным свободным расстоянием и будем обозначать

его, как и в блочных кодах

Теоретически значение наибольшего минимального свободного расстояния

можно получить, устремляя длину

обрабатываемых в декодере символов к бесконечности

оказывается полезным при поиске структур хороших сверточных кодов, поскольку эта величина указывает

предел, к достижению которого надо стремиться при поиске структуры кода.

Важной характеристикой кода, полностью определяющей его корректирующие свойства, является спектр свободных расстояний

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

Минимальное свободное расстояние

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

решеточной диаграммы для соответствующего кодера.

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

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

нулей. Следовательно, минимальное свободное расстояние сверточного кода будет равно минимальному числу единиц, т. е.

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

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

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

Рассмотрим кодер, представленный на рис. 28.1.

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

На рис. 28.2 показана подобная решеточная диаграмма c метками весов для кодера сверточного кода (рис. 28.1), построенная

на базе решеточной диаграммы (рис. 27.9).

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

имеющий вес 5, отходящий от нулевого пути на 3 ветви [AB(11)–BC(10)–CA(11)], два пути, отходящие от нулевого пути на 4

ветви [AB(11)–BD(01)–DC(01)–CA(11)] и 5 [AB(11)–BC(10)–CB(00)–BC(10)–CA(11)] ветвей и имеющие вес w = 6 и т. д.

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

свободное расстояние этого кода

. Очевидно, этот код может исправить любые две ошибки, произошедшие в канале

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

хеммингово расстояние от переданной последовательности, равное двум, а от всех других последовательностей это расстояние

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

ошибки этим кодом будут исправлены.

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

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

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

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

при декодировании по алгоритму Витерби.

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

определить по последовательности выходных символов

– на полной длине кодового ограничения

В табл. 28.1 приведены последовательности символов на выходах соответствующих кодеров при поступлении на вход

информационной последовательности, содержащей только одну единицу –

= 1000… Это дает возможность определить

на полной длине кодового ограничения, которая подчеркнута в табл. 28.1.

В табл. 28.1 указаны порождающие матрицы для четырех схем сверточных кодеров, определены значения памяти кодов

и минимального свободного расстояния

. Построены выходные последовательности

на вход кодеров информационной последовательности

, которые позволяют непосредственно определить

. Для кодера под №4, обеспечивающего скорость

(рис.27.5), последовательность

подается на верхний вход, а на нижний вход –

В табл. 28.1 на основании построения

в последней колонке приведены значения

соответствующих кодов, которые равны весу

– вес кодовой последовательности на полной длине кодового ограничения

Обратим внимание на то, что для кодера №2 (вторая строка табл. 28.1) выходная последовательность

полностью совпадает со структурой выходного кода при поступлении на вход кодера последовательности A(X) = 1000… для

решеточной диаграммы (рис. 28.2), так как путь по решетке [AB(11)–BC(10)–CA(11)] определяет тождественную

Таким образом, минимальное свободное расстояние

для различных вариантов коротких сверточных кодов можно найти

по (28.14), определив структуру выходной последовательности

11. Корректирующая способность кода определяется кратностью (количеством) исправляемых

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

, тем эффективнее является код. Хемминг определил простую зависимость между значением минимального

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

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

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

означает целую часть числа

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

при обработке кодовых последовательностей с длиной

. Если в последовательности произошло

удовлетворяет неравенству

кодовой последовательности, равной полной длине кодового ограничения

что совпадает с (28.15) и (28.16) для блочных кодов, так как, постоянная длина блочного кода эквивалентна полной длине

кодового ограничения для сверточных кодов.

12. Мощность кода определяет способность кодов исправлять множественные, одиночные и многократные ошибки,

возникающие в канале связи. Мощность кода зависит от входной длины кодового ограничения

полиномов. Вероятность исправления ошибок при декодировании в явном виде связана со свободным кодовым расстоянием

Так, для рассмотренного ранее кодера (рис. 28.1), генерирующего код (2, 1, 3) с образующей матрицей (табл. 28.1 ), величина

Для кода (2, 1, 5) с образующими полиномами

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

В еще более мощном коде (2, 1, 7) с образующими полиномами

применяемом в системах спутниковой связи,

Следовательно, коды с большим кодовым ограничением

13. Энергетический выигрыш кода

определяет выигрыш по помехоустойчивости при применении корректирующего

кодирования. Как правило, в системах предполагают применение символов с двухпозиционной фазовой модуляцией ФМ-2,

использующей противоположные сигналы с начальной фазой 0° при передаче символа “1” и 180° при передаче “0” (или

Для получения заданного значения вероятности ошибочного приема одного символа

последовательности надо обеспечить на выходе демодулятора приемника некоторое необходимое минимально допустимое

При передаче информации с корректирующем кодированием уже вместо

информативных символов за заданное время

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

При этом придется сокращать длительность символов при передаче (при скорости

= 1/3 – в три раза), что потребует

расширения полосы частот в

раз. Исходное заданное значение вероятности

будет обеспечиваться уже при другом

отношении сигнал/шум. Разница отношений сигнал/шум при применении кодирования и без него при ее положительном

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

Быстрая ориентировочная оценка энергетической эффективности для целей оперативного сравнения кодов производится по

асимптотическому энергетическому выигрышу от кодирования (АЭВК)

– относительная скорость кода;

– минимальное кодовое расстояние.

Величина АЭВК характеризует ЭВК при вероятности

и является верхней границей реального ЭВК при

14. Сложность кодеков сверточных кодов определяет возможность практической реализации кодера на стороне передачи и

декодера на стороне приема системы связи.

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

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

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

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

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

Сложность декодеров определяется методом декодирования. В настоящее время используется три основных метода

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

последовательное и декодирование по алгоритму Витерби.

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

Сложность реализации декодеров растет практически пропорционально полной длине кодового ограничения

Декодеры достаточно просты при исправлении ошибок невысокой кратности (

). Однако дальнейшее увеличение

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

оправдывается возрастанием величины ЭВК.

Наибольшую сложность имеют декодеры Витерби, объем вычислений (сложность) которых возрастает экспоненциально с

ростом длины кодового ограничения. При использовании алгоритма Витерби увеличение ДКО на единицу более чем вдвое

увеличивает объем декодера, но дает прирост ЭВК – 0,4 …0,5 дБ. Поэтому практически используемые декодеры выполняются

. Повышение быстродействия таких декодеров возможно при распараллеливании процедур

декодирования, а снижение объема – за счет перехода к микропроцессорной технике.

15. Надежность кодирования – определяется вероятностью правильного декодирования передаваемой информационной

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

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

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

последовательностями, порождаемыми кодером.

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

задающие связи между сумматорами и отводами регистра. Построение ведут исходя из получения максимального ЭВК, или

, или минимальной вероятности сбоя символа. Поиск кодов осуществляют, как

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

параметрами для борьбы с различного рода помехами.

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

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

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

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

потребуется, в частности, снижение технической скорости передачи.

28.2 Методы декодирования сверточных кодов

Развитие теории сверточных кодов происходило в трех направлениях в соответствии с тремя важнейшими методами

декодирования сверточных кодов: метода порогового декодирования, метода последовательного декодирования и метода

декодирования по максимуму правдоподобия (алгоритм Витерби).

Метод порогового декодирования сверточных кодов в принципе аналогичен методу мажоритарного декодирования блоковых

кодов. Достоинством этого метода является простота алгоритма, а, следовательно, и реализующих его устройств. Число

операций, необходимых для декодирования одного информационного символа, для этого алгоритма не превосходит некоторой

Метод последовательного декодирования является методом вероятностного декодирования, при котором число операций,

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

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

максимуму правдоподобия.

Метод декодирования по максимуму правдоподобия теоретически более эффективен, чем метод порогового декодирования,

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

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

При пороговом декодировании сверточных кодов вычисляются синдромы (признаки места ошибочных символов), затем эти

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

порогового элемента, где путем “голосования” (мажоритарный метод) и сравнения его результатов с порогом выносится

решение о значении декодируемого символа. Основное достоинство этого метода декодирования – простота реализации.

Однако он не полностью реализует потенциальные корректирующие способности сверточного кода.

Кроме того, не все сверточные коды могут быть декодированы этим методом. Чтобы сверточный код допускал декодирование

пороговым методом, он должен обладать свойством ортогональности.

В принципе метод порогового декодирования сверточных кодов аналогичен методу мажоритарного декодирования циклических

Общая схема декодера для сверточного кода (

= 1/2) представлена на рис. 28.3.

Рис. 28.3. Общая схема декодера для сверточного кода

Пороговое декодирование, как правило, применяется для систематических кодов. Декодер содержит аналог кодера, в котором

по принимаемым информационным символам в сдвигающем регистре формируется копия проверочной последовательности. С

этой целью синхронизатор декодера с помощью ключей 1 и 2 “расфасовывает” входную последовательность символов на 2

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

В формирователе синдрома (сумматоре по модулю 2) образуется последовательность синдромов

, которая поступает на вход

синдромного регистра. В отсутствие в канале ошибок последовательности на входах формирователя синдрома всегда

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

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

символы. Закон формирования проверочных символов выбирается таким образом, чтобы по структуре синдромной

последовательности можно было определить искаженные символы.

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

символов. Если имеется комбинация ошибок, которая может быть исправлена, то логическая схема исправляет ошибки в этом

блоке путем подачи единичных символов на выходную схему суммирования по модулю 2 в моменты выхода из

информационного регистра искаженных символов.

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

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

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

которая на схеме (рис. 28.3) представлена пунктирной линией.

Обратная связь преобразует синдромный регистр прямого действия в нелинейный регистр сдвига с обратной связью. Это может

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

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

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

поступает нулевая последовательность, а начальное состояние – ненулевое, может быть периодическим.

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

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

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

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

Очевидно, что без обратной связи не будет размножения ошибок.

При пороговом декодировании используют, в основном, систематические коды. При скорости кода, отличной от 1/2, структура

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

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

Методы порогового декодирования основаны на простых идеях, и они находят широкое применение на практике.

Метод последовательного декодирования

Если простота алгоритмов порогового декодирования и, следовательно, простота их реализации стимулировали исследования

сравнительно коротких кодов и повышение их корректирующих способностей, то проводившиеся параллельно исследования

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

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

символ, изменяется в зависимости от уровня шумов в канале. Число операций при последовательном декодировании является

функцией скорости передачи и шумов в канале. При всех скоростях передачи, меньших определенной скорости, число

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

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

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

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

декодировании и других методах декодирования могут возникать ошибки. Однако при последовательном декодировании

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

устройства, т.е. из-за переполнения буфера. Если вероятность ошибки из-за переполнения буфера оказывается значительно

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

определять характеристики алгоритма последовательного декодирования.

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

которое для кодера (рис. 28.1) приведено на рис. 28.4.

Рис.28.4. Кодовое дерево кодера (рис. 28.1)

Кодовое дерево строится следующим образом. Исходному нулевому состоянию сдвигающего регистра кодера соответствует

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

(ребро дерева), идущая, как принято на этом рисунке, вниз, а если информационный символ равен 0, – то вверх. Тем самым

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

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

кодовых символов, получаемых при этом на выходе

кодера. Совокупность нескольких последовательных ребер, соединяющих какие-либо два узла, составляет ветвь дерева. Узлы,

соединенные одним ребром, называются соседними. Для двоичных кодов в общем случае из каждого узла дерева будет

ребер, каждому из которых сопоставлено

Коды, допускающие подобное представление с помощью кодового дерева, называются древовидными. Таким образом,

сверточные коды относятся к древовидным.

Можно заметить, что рассмотренную ранее решеточную диаграмму кода можно получить из кодового дерева, если объединить

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

на рис. 28.4 одинаковыми буквами

и соответствуют состояниям кодера на диаграмме состояний (рис. 27.8).

Каждая последовательность кодируемых информационных символов порождает определенный путь по кодовому дереву.

Например, информационная последовательность 1001…. порождает путь по кодовому дереву, показанный штриховой линией на

рис. 28.4, которому соответствует последовательность кодовых символов 11101111… Очевидно, задача декодера заключается

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

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

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

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

передававшуюся последовательность. Для этого сначала необходимо передвигаться поочередно вдоль каждого пути кодового

дерева, сравнивая принятую последовательность с последовательностью, соответствующей пути, по которому происходит

движение. Если при этом удается обнаружить некоторый путь, которому соответствует последовательность, почти совпадающая

с принятой последовательностью, то естественно считать, что эта последовательность и передавалась. Метод

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

– число разрядов регистра сдвига кодера), соответствующая которому кодовая последовательность

находится на каком-то определенном расстоянии от переданной последовательности, и далее декодирование первого

информационного символа. Первым переданным информационным символом считается первый информационный символ

первого ребра найденного пути. Поскольку далее декодирование второго и последующих информационных символов

осуществляется точно так же, как и первого информационного символа, то этот алгоритм и был назван алгоритмом

последовательного декодирования.

Одним из критериев близости пути на кодовом дереве к принятой последовательности является расстояние Хемминга между

Если расстояние Хемминга между последовательностями с длиной

, равной числу обработанных двоичных символов, не

превышает определенный порог

, то последовательности можно считать совпадающими. В случае двоичного

симметричного канала порог

выбирается таким образом, чтобы вероятность того, что расстояние Хэмминга между

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

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

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

оказывается чрезвычайно малой.

Предположим, что этот метод декодирования используется в двоичном симметричном канале с вероятностью перехода

Напомним, что в двоичном симметричном канале без памяти каждый переданный кодовый символ может быть принят ошибочно

и правильно с вероятностью

, причем в случае ошибки вместо переданного символа 0 на

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

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

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

с ростом числа обработанных символов

. В то же время расстояние Хемминга, вычисляемое вдоль любого

другого пути кодового дерева, будет возрастать со скоростью 1/2, поскольку различные пути кодового дерева отличаются друг

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

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

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

продолжен и в конце концов правильный путь будет найден.

Этот алгоритм последовательного декодирования был обобщен Рейффеном на случай произвольного дискретного канала без

Обобщение было сделано путем замены расстояния Хемминга на другую функцию (“перекошенное” расстояние), являющуюся

обобщением расстояния Хемминга, которая была названа ценой пути.

Другим алгоритмом последовательного декодирования является алгоритм, предложенный Фано, который предусматривает

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

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

одного символа, не зависит от длины кодового ограничения. Это упрощает анализ алгоритма Фано. Кроме того, достоинством

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

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

вероятностях ошибки на декодированный символ.

Еще одним известным алгоритмом последовательного декодирования является алгоритм Зигангирова, предложенный в 1966 г.,

являющийся алгоритмом декодирования по максимуму правдоподобия.

Этот алгоритм иногда называют стэк-алгоритмом (от английского stack – кипа, стопа), так как для его реализации требуется

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

В качестве метрики (расстояний Хемминга) путей по кодовому дереву при этом алгоритме также используется функция

правдоподобия пути (цена пути), но с добавлением элемента смещения, величина которого определяется исходя из скорости

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

операций при декодировании одного информационного символа.

Количество вычислений на один декодированный информационный символ, которые производит декодер при данном алгоритме

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

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

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

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

буферного запоминающего устройства (ЗУ) между собственно последовательным декодером и первой решающей схемой

приемника. Однако в том случае, когда объем производимых вычислений оказывается очень большим (“всплеск вычислений”,

соответствующий “плохому” состоянию канала связи), возможно переполнение буферного ЗУ, что приводит к отказу в

декодировании. Это является недостатком всех методов последовательногодекодирования. Однако сложность этих методов

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

ограничений, а следовательно, достигнуть большой эффективности корректирующего сверточного кода.

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

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

символов, соответствующее с заданной вероятностью времени наступления отказа в декодировании, передавать

последовательность заранее известных символов, например последовательность нулей. Тем самым декодер устанавливается

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

наступлении отказа в декодировании.

Из-за присущей сверточным кодам непрерывности в обработке информации их синхронизация при декодировании

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

без которой правильное декодирование блоковых кодов, как правило, невозможно. Однако для всех методов декодирования

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

синхронизация по группам символов, соответствующих одному циклу опроса коммутатора кодера.

3. Метод декодирования по алгоритму Витерби

Метод представляет собой декодирование по максимуму правдоподобия. Идея алгоритма Витерби состоит в том, что в

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

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

символами определяют оптимальный путь (оптимальной считается та последовательность, расстояние Хемминга которой от

принятой последовательности минимально).

Декодирование по методу Витерби, по существу, представляет собой алгоритм поиска наивыгоднейшего, максимально

правдоподобного пути на графе – решеточной диаграмме кода.

1. Декодирование в случае отсутствия ошибок при приеме

Продемонстрируем работу алгоритма на примере несистематического сверточного кода с маркировкой (2, 1, 3) с

порождающими полиномами, задаваемыми выражением

кодер которого показан на рис. 28.5.

Возьмем следующую последовательность информационных символов 10110. Этой последовательности соответствует выходная

последовательность 1110000101.

Задача декодирования рассматривается как задача нахождения пути на решетчатой диаграмме. Пусть принята кодовая

комбинация 1110000101 без ошибок.

Рассмотрим графическое отображение изменений состояния сигнала (рис. 28.6). Начальным всегда является состояние 00. В

соответствии с диаграммой переходов состояний сигнала в первый тактовый момент возможны два перехода: 00 > 00 и 00 > 10.

Первому переходу соответствует на выходе кодера кодовая комбинация 00, второму – 11.

При приходе на вход декодера первой пары 11 первой ветви 00 >00 будут соответствовать две ошибки в приеме, а второй ветви

00 > 10 нуль ошибок. Ошибка по каждой ветви служит метрикой

в смысле расстояния Хэмминга, т.е. соответствует числу

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

Эти метрики зафиксированы на диаграмме (рис. 28.7).

В момент времени 2 (второй такт) сигнал может принять 4 состояния, которые определяются двумя возможными переходами из

00 и двумя переходами из 10. Сравнение с принятыми символами 10 дает следующие метрики соответствующих ветвей

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

ветвей. Значения суммарных метрик (метрик путей) показаны на диаграмме рис. 28.7 в кружках. Для момента времени 3

следует анализировать уже 8 возможных путей и сравнивать 8 соответствующих им метрик

Алгоритм Витерби выбирает путь с наименьшей суммарной метрикой (“штрафом”) и может отбрасывать по ходу продвижения во

времени те пути, которые имеют штраф, превышающий минимальный “штраф” в данный момент времени на некоторую

Для упрощения рис. 28.7 установлен пороговый уровень

= 3 и не показываются ветви с большим значением

Оптимальным путем является путь с наименьшим “штрафом” ( при отсутствии ошибок в канале передачи символов

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

совпадает с передаваемым информационным сигналом.

2. Декодирование в случае наличия ошибок при приеме

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

передаваемой последовательности, т.е. ошибки в первой и третьей декодируемой паре

Теперь метрики первой и третьей ветвей оптимального пути не равны нулю и суммарная метрика оптимального пути

Однако как следует из рис. 28.8, оптимальный путь с наименьшей суммарной метрикой восстанавливает передачу

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

Рассмотренный метод декодирования, когда в качестве метрики используют расстояние Хэмминга, называют декодированием с

жестким решением. Здесь каждому символу на выходе демодулятора соответствует одно из двух значений: 0 или 1. Лучшие

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

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

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

= 1– 4, а уровню передачи логического нуля

= (–1) – (– 4) (возможно и наоборот). Величина

квантованного уровня определяет доверительную вероятность полученного результата. Более высоким уровням (3; 4)

соответствует более высокая доверительная вероятность.

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

и вычитая несовпадающие.

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

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

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

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

28.3. Схемное построение декодера Витерби

Обобщенная структурная схема декодера, работающего по алгоритму Витерби, показана на рис. 28.9. Для каждого такта

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

метрики ребер (BMP) вычисляет правдоподобие ребер, сливающихся в каждом узле. Например, в случае двоичного

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

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

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

Вычислитель метрики путей (ВМП), для каждого из путей, выживших на предыдущем такте декодирования и хранимых в ЗУ

путей, осуществляет следующие операции: вводит каждый из этих путей в аналог кодера, где генерируются 2

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

хранимые в ЗУ метрики путей, с новыми вычисленными значениями метрик ребер; заносит вновь полученные пути в ЗУ путей, а

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

узлов и сохраняет его в ЗУ путей, а его метрику — в ЗУ метрики путей. Затем эта же последовательность операций повторяется

для следующего такта работы и т. д.

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

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

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

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

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

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

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