раз) величину т до поучения первого положительного значения или нуля, которые и принимаются за результат. Например, 193 = 1; 1ЭЗ = 6.

В частном случае двоичных кодов операция вычитания коэффициентов исключается, так как операции сложения и вычитания по модулю 2 эквиваленты: 1Ф1 =0; 101 =0; 001 = 1. Это позволяет при использовании двоичных кодов при всех операциях над полиномами (включая и деление) пользоваться только суммированием коэффициентов по модулю 2 (двучлен У - 1 при этом заменяется соответственно двучленом jc + 1).

Циклические коды являются блочными, равномерными и линейными. Линейность циклических кодов вытекает из того, что любая линейная композиция двух циклических кодов, делящихся на порождающий полином F (jc), будет обязательно делиться на тот же порождающий полином, т.е. будет принадлежать к числу разрешенных слов данного циклического кода. На разрешенный набор кодовых слов в этом случае накладывается дополнительное ограничение по сравнению с обычными линейными кодами: делимость на порождающий полином, и этот признак существенно упрощает аппаратурную реализацию кодирующих и декодирующих устройств.

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

L(jc) =

F(x) xF(x)

x*lF(x)m

(9.30)

Матрицу (9.30), представленную в форме полиномов, можно переписать в форме матрицы коэффициентов (символов), записывая в одном столбце коэффициенты при одинаковой степени jc. Наивысшая степень, отвечающая полиному в последней строке матрицы (9.30), равна k -1 + г, где г - степень порождающего полинома F (jc). Поскольку строки этой матрицы, представляющие полиномы по модулю хп - 1, не могут иметь степень выше п - 1, то должно удовлетворяться условие А:- 1 + г = л - 1 или к = п- г. Нетрудно убедиться, что все полиномы в (9.30) соответствуют разрешенному набору слов данного циклического кода [делятся на F (х)] и являются линейно-независимыми, т.е. матрица (9.30), действительно, является базисной матрицей линейного кода (л, к).

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

g(jc) = (jc -l)/F(jc), (9.31)

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

Н(х) =

xg(x) У18(х),

(9.32)

В ортогональности полиномов, составляющих строки матриц Ь(х)иН (jc), легко убедиться, так как в силу (9.31)

jcF (x)®xjg (jc) = хн®(хГ - 1) = 0 .

Можно показать, что если кодовое слово & = (ро, Рь Рл-i) принадлежит к разрешенному набору данного циклического кода, то к нему же принадлежит и кодовое слово &(1) = (рл-ь Ро. Рь Рл-г), полученное из первого циклической перестановкой символов. Легко убедиться, что кодовому слову b(l) отвечает полином Ь{Х)(х\ представляющий произведение xb (jc) по модулю У1 - 1. Поэтому, если b (jc) делится на порождающий полином F (jc), то на него же делится и полином (jc), и кодовое слово принадлежит тому же циклическому коду, что и исходное слово Ь. Это свойство и определило название циклический для данного кода.

Формирование разрешенных слов циклического кода по заданному информационному слову, содержащему к символов, можно осуществить следующим образом. Образуем полином G(jc) степени fe- 1, соответствующий передаваемому -разрядному информационному слову, и умножим его на /, где г - степень порождающего полинома F (jc), к + г^л. Полученный полином степени к + г - 1 разделим на порождающий полином F (jc). Вычтем из полинома jcrG (jc), младший член которого имеет степень г, остаток q (х) от его деления на F (х) [порядок полинома q (jc), по крайней мере на единицу, ниже порядка полинома F(jc), т.е. не выше г - 1]. Получим полином Q (jc) = xrG (jc) - q (jc), делящийся на F (jc) без остатка, определяющий разрешенное кодовое слово. Младшие г разрядов этого кодового слова (проверочные) соответствуют коэффициентам остатка q (jc), а старшие разряды, начиная с (г+ 1)-го соответствуют информационному слову, смещенному на г разрядов в результате операции умножения полинома информационного слова G (х) на хг.

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

общее число разрядов п - степенью двучлена хп - 1. Максимальное число информационных символов k-n-r.

В качестве примера определим разрешенное слово семизначного двоичного циклического кода, определяемое информационным словом 1011 и порождающим полиномом F (х) = х3 + х2 + 1, соответствующим двучлену х1 + 1. Разделим полином xrG (х) = х6 + х4 + х3 на полином F (х) (напомним, что для двоичных кодов вычитание коэффициентов заменяется их суммированием по модулю 2):

х6 +х4 +Х3 lac3* х2* 1 Фх6+х5 -нх3 I J+x2

Фх*+х* + *

Остаток (jc)=jc2. Следовательно, j2(jc)=/G(x) + (jc)=x6 + / + x3 + x2, а искомый циклический код, описываемый полиномом Q (х), имеет вид 1011100 [отсутствующим в полиноме Q (х) степеням отвечают коэффициенты, равные нулю].

Для обнаружения ошибок в циклическом коде вместо операции деления на порождающий полином F (х) удобно использовать операцию умножения по модулю л: - 1 на генераторный полином g (х) (для двоичных кодов, когда используется только суммирование коэффициентов по модулю 2, умножение полиномов осуществляется соответственно по модулю хп + 1).

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

Q(x) = Q(x)®n(x), (9.33)

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

Умножая Q (х) на генераторный полином g (jc) по модулю хп - 1 (для двоичных кодов - по модулю х* + 1), получаем:

Q (x)®g (х) = - 1) + п (x)®g (х) = п (jc)®g (jc) , (9.34)

так как g (х) = (xя - \)IF (jc), а q (х) делится без остатка на F (jc) по определению циклического кода. Произведение п (jc)®g (х) не равно нулю, если только код ошибки не совпадает ни с одним из разрешенных слов цик-

лического кода данного типа. Таким образом, признаком наличия ошибки является отличие от нуля произведения Q (x)®g (х); при этом обнаруживается ошибка любой кратности, если только она не совпадает с одним из разрешенных слов данного циклического кода.

Умножение по модулю У1 + 1 для двоичных кодов легко реализуется с использованием кольцевого регистра из п ячеек с сумматором по модулю 2 на входе (рис. 9.1). Пусть на вход кольцевого регистра последовательно поступают, начиная с младших разрядов, коэффициенты обычного произведения полиномов Q (x)g (jc). Представим это произведение в виде

Q (x)g {х) = р (хКх* + 1) + п (x)®g (х), разбивая его на часть, кратную х* + 1, и остаток п (jt)®g (х).

(9.35)

Рис. 9.1

Первое произведение в правой части (9.35) разбивается на пары членов вида х**1 + J, которые взаимно гасятся при прохождении через кольцевой регистр. Действительно, в тот момент, когда на входной сумматор (рис. 9.1) поступает коэффициент 1 при члене дЛ , по цепи обратной связи из л-й ячейки регистра в него поступает коэффициент 1 при х*. Суммируясь по модулю 2, они гасятся. В результате в момент поступления в регистр последнего (старшего) члена полинома произведения (9.35) в кольцевом регистре будут зафиксированы коэффициенты полинома, равного

n(x)®g(x).

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

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

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

п(х)=х*Апо(х),

(9.36)

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

Остаток в кольцевом регистре, отвечающий ошибке (9.36), равен

W*)f* ]. (9-37)

т.е. отличается от ло(х)®£ (jc) сдвигом вправо (в сторону старших разрядов) нац. - 1 разрядов регистра. Положение ошибки определяется, таким образом, числом разрядов, на которое нужно продвинуть остаток в кольцевом регистре, чтобы он совпал с эталонным полиномом ndxy&g (jc), хранящимся в памяти. В частности, для одиночных ошибок эталоном для сравнения служит генераторный полином g (jc).

К циклическим кодам принадлежит и m-последовательность, рассматривавшаяся в § 4.6. Введем вместо символов + 1 и - 1, использовавшихся в § 4.6 при изучении корреляционных свойств ФМПС, символы 1 и 0. При переходе к новым символам (обозначим их dd закон (4.61) формирования т-последовательности трансформируется к виду

di = ddbdUU~&*i*, (9.38)

где по-прежнему полагается, что среди символов db .... < .г хотя бы один равен 1. Легко убедиться в эквивалентности закона формирования символов (9.42) использовавшемуся в § 4.6 закону di = - ф.г du ... du при замене символа - 1 на 0.

Используя представление кодов в виде полиномов, закон (9.38) можно записать в виде:

<Г,хм =di.rxi-rAxr + dNxil-lxl+ ... +di.kxi-klxk. (9.39)

Из (9.39) следует, что формирование полинома, отвечающего т-последовательности, можно рассматривать как процесс наращивания*1 старших членов этого полинома путем умножения предшествующих его членов на полином

F(x) = xr + x!+...+xk. (9.40)

Покажем, что символы, составляющие период m-последовательности, формируемой по закону (9.38), могут рассматриваться как разрядный двоичный циклический код с порождающим полиномом (9.40). Рассмотрим полином степени N+ г - 1:

Qn+r(x)=Jda ixil. (9-41)

коэффициенты которого составляют период т-последовательности.

Учитывая, что tfu+j = cfj (в силу периодичности m-последовательности) н что

cVod (jc + 1)1 = d *ptx = dpi1. (9.42)

получаем:

Qn+Ax) [mod (x* + 1)] = <Г*У +... + dNx*1 +

+ dl + d2x+...+ drxrl = fivOO. (9-43) где Qn(x) - полином, отображающий N-разрядную кодовую последовательность

b = (dud2.....dd 1.....dN). (9.44)

Используя (9.39) и (9.42), полином (9.41) представим в виде:

r+n r+n

+X1 дум* *1=/£ aetx +у£</у-+... +

e*r+l r=l p=l

tx/l=F(t)p/1. (9.45)

Таким образом, полином Qn+M, а значит, и полином бл/Ос) = Qn+M (mod jc + 1) кратны порождающему полиному (9.40) и последовательность (9.44) представляет циклический код. Любой другой участок m-последовательности длительностью в один период di ... drffs+i dN+t.i -d\... dud\ ... d11, который может быть получен циклической перестановкой последовательности (9.44), принадлежит тому же циклическому коду.

Теперь можно уточнить критерий выбора значений индексов г,/,...Дв законах (4.61) и (9.38) формирования символов m-последовательности: эти индексы определяются порождающим полиномом F (jc). При этом, для получения последовательности максимальной длительности порождающий полином должен обладать дополнительным свойством примитивности : двучлен jc - 1 должен делиться на порождающий полином степени г лишь при n = N-2r - 1 и не должен делиться ни при каком значении n<N.

Циклические коды типа m-последовательности, формируемые по закону (9.38), составляют лишь небольшое подмножество всех кодовых слов, принадлежащих данному циклическому коду: из общего числа 2Nr разрешенных кодовых слов лишь N кодовых слов представляют m-последовательности. Из каждых 2Nrl2r = 2N2r кодовых слов с данным сочетанием проверочных символов лишь одно представляет m-последовательность. Из свойств т-последовательности, рассмотренных в § 4.6 [см. (4.62)], следует, что разрешенные кодовые слова, принадлежащие m-последовательности, отличаются друг от друга ровно на (N+ 1)/2 = 2м символов, что отвечает максимально возможному кодовому расстоянию для разрешенного набора, содержащего N /-разрядных слов.

9.4. Критерии эффективности блочных корректирующих кодов

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

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

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

Если оцениваемый код (л, к) в рассматриваемом канале характеризовать вероятностью ошибочного приема Р*, то вероятность Рэ ошибочного приема символа,при которой обеспечивается та же достоверность передачи информации для примитивного кода (к, к), определятся из равенства (1-Рэ)*=1-Р*или

Рэ=1-(1-Р*)ш. (9.46)

Рэ = /У*. (9.47)

Если корректирующий код (л, к) имеет кодовое расстояние dmin, т.е. способен достоверно исправить t = {dn - 1)/2 ошибок, то при случайных независимых искажениях его символов, характеризуемых вероятностью Ре получим:

Pk=f,CinPie(l-Per\ (9.48)

Г п 11/*

p,=i-(i-p*) *=i- ScUi-p.)-1 (9-49)

l ы+\ j

В случае, когда

Рэ1 и Рк = XcnPl ~ РУ1<Х

*=f+l

сохраняя в (9.49) лишь первый член суммы, имеющий наименьший (t+ 1)-й порядок относительно малой величины Ре, получаем:

Р - Репр/Ржор - кРепр/Cn Рекор (9.53)

где Р 0р - вероятность ошибочного приема символа корректирующего кода; Рещ> - вероятность ошибочного приема символа соответствующего примитивного кода при тех же помехах и тех же значениях скорости передачи информации и средней мощности канала.

В частности, для помехи типа аддитивного белого шума

Для сравнения двух кодов (л k) и (лу, &,), имеющих разрешенные наборы кодовых слов Вр и Вр®9 можно воспользоваться отношением

а Рэ/ *f n\ r*i (95l)

Pv= к^Јà 9 (

где Рул - коэффициент, характеризующий выигрыш j-ro кода по отношению к i-му; /, и tj - число достоверно исправляемых ошибок, соответствующие кодовым расстояниям сравниваемых кодов dи dmn f, Pet и Pej - вероятности искажений элементарных символов сравниваемых кодов при одинаковых значениях скорости передачи информации, средней мощности канала и характеристиках помех.

Рассмотрим частный случай, когда помеха - аддитивный белый шум со спектральной плотностью N0. Скорость передачи информации зафиксируем числом т информационных символов, передаваемых в 1 с ( исходный информационный код считаем безызбыточным). Энергию обоих символов двоичного кода принимаем одинаковой. Тогда, используя формулу (3.38), получаем:

<-(-(9-52)

где 9*с - фиксируемая средняя мощность канала; тлД,- - общее число символов, передаваемых за 1 с при применении кода (л/, kt), отвечающее условию передачи m информационных символов в 1 с; А, - коэффициент различимости символов (3.34).

В качестве характеристик эффективности корректирующего кода удобно использовать значение коэффициента выигрыша Р по отношению к примитивному коду. Для примитивного кода и = tnp= О, Рэ/ = Р^. Поэтому выигрыш Р по эквивалентной вероятности ошибки корректирующего кода (л, к), достоверно исправляющего t ошибок, по отношению к примитивному ifc-символьному коду в соответствии с (9.51) равен

(9.54)

где Ес - энергия символа корректирующего кода (я, к); Ес /к энергия символа примитивного кода при тех же значениях скорости передачи информации и средней мощности сигнала; X - коэффициент различимости символов (см. (3.34)).

В качестве примера на рис. 9.2 приведен график зависимости коэффициента выигрыша Р от отношения Ec/Nq для 15-разрядного кода Хэмминга, исправляющего одиночные ошибки (л = 15, к = 11, t = 1). График построен для Х-2 в области достаточно больших значений EJNq, когда применима приближенная формула (9.54). Эффективность корректирующих кодов растет с увеличением достоверности приема отдельных символов. При низкой же достоверности приема символов (малых значениях Ec/N0) повышение корректирующей способности кода может приводить даже к отрицательным результатам, так как при этом превалирующим может оказаться увеличение вероятности ошибочного приема символов из-за снижения их энергии при увеличении избыточности.

EJNq

Глава 10

СВЕРТОЧНЫЕ КОРРЕКТИРУЮЩИЕ КОДЫ

10.1. Особенности кодирования и декодирования сверточных кодов

Ограничимся рассмотрением двоичных сверточных кодов. Для них рекуррентная формула (8.4) для определения символов кодовой последовательности принимает вид

I V=-<7

(mod 2); j = 0,1, ...,/- 1, cv; = 0, 1, (10.1)

где bi - символы входной информационной последовательности.

\ Выход Коммутатор ▼Выход Коммутатор

Рис. ЮЛ

Функциональная схема кодирующего устройства, обеспечивающего формирование символов по закону (10.1), представлена на рис. 10.1,а. Символы входной информационной последовательности поступают на регистр сдвига, содержащий к = s + q ячеек [в соответствии с обозначениями в (10.1) ячейкам присвоены номера от - q до s - 1]. Символы ру формируются с помощью сумматоров по модулю 2, на которые с ячеек регистра сдвига, отвечающих ненулевым значениям cvy в (10.1), поступают информационные символы. В тот такт работы регистра сдвига, когда в нулевой его ячейке находится символ bi (соответственно во входной ячейке символ

bi+s.u а в выходной - Ь,. на сумматорах формируются символы р,о, Рл,Р/,м. Коммутатор в i-м такте работы регистра сдвига, в течение которого остаются неизменными заполняющие его символы Ь„ поочередно подает символы р,у в канал. В следующем такте все символы в регистре сдвинутся вправо на одну ячейку; в нулевой ячейке будет символ Ьм, во входную ячейку поступит символ bi+5, а в выходную - Ь^+\. Соответственно на сумматорах формируются символы кодовой последовательности Рй.1,0, Р +1, ь .... P/+u-i и т.д. Таким образом, с поступлением на вход кодирующего устройства каждого нового символа информационной последовательности в канал поступают / символов кодовой последовательности.

На рис. 10.1,6 представлена модификация кодирующего устройства для случая систематического сверточного кода. Отличие в этом случае состоит в том, что на один из входов коммутатора (например, на первый) непосредственно из нулевой ячейки регистра поступает информационный символ bi9 т.е. Рю = Ъх. Основное отличие от кодирования блочных систематических кодов здесь состоит в непрерывном обновлении группы информационных символов, участвующих в формировании очередных I символов кодовой последовательности (при блочном кодировании формирование всех символов данного кодового слова происходит с использованием одного кодового слова происходит с использованием одного и того же блока информационных символов, который целиком обновляется при переходе к кодированию следующего слова). Максимальное число информационных символов, участвующих в формировании каждого выходного символа сверточного кода, определяемое числом ячеек регистра сдвига К, носит название длины кодовых ограничений. Эта характеристика близка по смыслу к длине блока информационных символов для блочных кодов. Иногда длину кодовых ограничений определяют в числе канальных (выходных) символов. В этом случае она выражается величиной N = 1К. Каждый символ входной информационной последовательности может участвовать в формировании до 1К-\ символов выходной последовательности сверточного кода. Нетрудно видеть, что усложнение кодирующего устройства с увеличением длины кодовых ограничений характеризуется линейным законом. Поэтому кодирующие устройств не накладывают существенных ограничений на реализуемость сверточных кодов.

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

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

5,у = Р^е|>ууУ/+у, У=1,2,...,/-1, (10.2)

v=-<?

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

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

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

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

Рис. 10.2

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

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

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

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

Эти идеи и лежат в основе метода последовательного декодирования, впервые предложенного Возенкрафтом [29]. Появление метода последовательного декодирования привело к резкому увеличению интереса к свер-точным кодам в теории и практике кодирования: предлагаются новые более экономные алгоритмы последовательного декодирования, исследуется их эффективность. Общие идеи некоторых из этих алгоритмов рассматриваются в § 10.3.

10.2. Сверточные коды с синдромной коррекцией

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

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

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

... bi.h%.h ... ЬмРмЭД, - *wwP*w (ЮЗ)

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

Р| = * к®Ь^1 (10.4)

и является частным случаем формулы (10.1), когда коэффициенты cvj отличны от нуля только при v = -h и v = A+ 1. Составляющие синдрома ошибки для этого кода в соответствии с (10.2) равны

Si - Р',®£/ /,®£/+/,+1

(10.5)

Из (10.3) и (10.4) видно, что проверочные символы Р/ получаются суммированием симметрично расположенных относительно них информационных символов кодовой последовательности, отстоящих на 2h + 1 позиций в каждою сторону.

0i-2h-l ... Pi-k-I bi; ... bi+h ... bi+2h+l v

1II1III1III1HI

TllllMMIHIlT

i/L

Mllllllllllllf

miiimiiiiN

Пачка ошибок

щппшшшз

JiL.

Рис. 10.3

Выберем параметр h так, чтобы выполнялись следующие условия: если информационный символ bt подвергся воздействию пачки ошибок, то ни данная, ни соседние пачки ошибок не должны захватывать ни проверочные символы Рм-/, и Р;-А-ь в формировании которых участвует символ Ь, ни информационные символы 4>/+2a+i и Ь^-и участвующие в формировании тех же проверочных символов. Как видно из рис. 10.3, для того чтобы одна и та же пачка ошибок одновременно с символом b{ не могда захватить и символ Р'+л или PY/,-1, ее максимальная длина /тах должна удовлетворять условию:

/max 2/1. (10.6)

Для того чтобы конец предыдущей и начало следующей пачки ошибок не могли захватывать символы £/.2a-i и bt или bi и fci+2*+i минимальный интервал между началами соседних пачек Lmm должен удовлетворять условию

16*+1. (Ю.7)

При выполнении условий (10.6) и (10.7) искажение информационного символа bi будет сопровождаться одновременным обращением в единицу пары составляющих синдрома ошибок:

Si-H-i&i.h.mi.u.mi, (ю.8)

51+л=р'1+леу,е^.+2Л+1, (ю.9)

индексы которых отличаются на 2й + 1 [остальные символы в правых частях (10.8) и (10.9) не будут подвержены действию пачек ошибок]. Нетрудно убедиться, что при соблюдении условий (10.6) и (10.7) искажение проверочного символа вызовет обращение в единицу лишь составляющей синдрома с тем же индексом, составляющие же синдрома с индексом, отличающимися в ту или иную сторону на 2А + 1, сохраняют нулевое значение.

Таким образом,правила коррекции кода Финка-Хагельбергера сводятся к следующему: если отлична от нуля составляющая синдрома 5у, а составляющая S;.2a-i равна нулю, то исправление ранее принятых информационных символов не производится; если наряду с составляющей 5; не равна нулю и составляющая 5;.2А-ь то исправляется информационный символ bj-h.

Код Финка-Хагельбергера позволяет исправить пачки ошибок, если только минимальный интервал между ними более чем в три раза превышает их максимальную длину [в противном случае невозможно выбрать параметр h кода, удовлетворяющий одновременно условиям (10.6) и (10.7)].

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

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

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

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

Существуют различные подходы к сужению области перебора реализаций при последовательном декодировании. Мы ограничимся рассмотрением основных идей двух характерных с этой точки зрения алгоритмов: Возенкрафта [29] и Зигангирова-Джеминика [28].

Ключевой позицией принятой Возенкрафгом стратегии последовательного декодирования является замена задачи поиска наиболее вероятной из всех разрешенных кодовых последовательностей задачей исключения всех маловероятных кодовых последовательностей, которые могут отвечать принятой последовательности лишь при большом числе искажений [29]. Каждый шаг предложенной Возенкрафгом процедуры последовательного декодирования заключается в переборе отрезков траекторий, которые могут служить продолжением выбранного на предшествующих шагах начального ее участка и закреплении первой ветви отобранного продолжения. Устанавливаются максимальная длина п отрезков траектории, рассматриваемых на каждом шаге декодирования (глубина перебора), и порог d\, определяющий

Рис. 10.4

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

новом значении порога d2>d{. Вычислительная сложность данного алгоритма последовательного декодирования определяется выбором глубины перебора л, значений пороговых уровней du d2,... и числом градаций пороговых уровней (обычно ограничиваются двумя градациями).

В алгоритме Зигангирова-Джеменика [28] все внимание сосредоточено именно на определении оптимальной траектории. Рассмотрим основную идею алгоритма Зигангирова-Джеменика. Для простоты опустим рассмотрение процедуры определения расстояния по Хэммингу между кодовой последовательностью, отвечающей рассматриваемой информационной последовательности, и фактически принятой последовательностью, а каждому варианту траектории перемещения по дереву информационных последовательностей будем условно приписывать некоторое значение dt. В каждой узловой точке, начиная от основания дерева информационных последовательной из двух возможных вариантов продолжения траектории выбирается тот, который обеспечивает меньшее удаление dx соответствующей кодовой последовательности (включая и ранее определенный начальный ее участок) от принятой последовательности. На каждом шаге процедуры значение dt и номер * наилучшего варианта начального участка траектории заносятся в верхнюю строку таблицы, хранящейся в памяти; остальные строки этой таблицы заполняются в порядке возрастания а\ начальными участками траекторий, соответствующими всем рассмотренным вариантам. Для нумерации участков траекторий удобно использовать соответствующие информационные последовательности (эти же номера относятся и к конечным узловым точкам участков). Бели после очередного шага процедуры значение di для лучшего из двух продолжений траектории превысит хотя бы одно из хранящихся в памяти значений dj для рассмотренных ранее вариантов, дальнейший поиск оптимального продолжения траектории переносится в /-й узел (при этом производится перестановка строк в таблице по возрастающим значениям dt). При равенстве значений d{ для двух вариантов траектории предпочтение отдается варианту с большей длиной. После t шагов процедуры (каждый шаг заключается в рассмотрении двух продолжений траектории из данного узла на одну ветвь) таблица будет содержать t + 1 строку, максимальное же продвижение по траектории может быть существенно меньшим, чем на t ветвей, из-за возможных возвратов по дереву информационных последовательностей в процессе поиска оптимальных продолжений.

Таблица 10.1

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

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

При осуществлении последовательного декодирования иа основе посимвольного приема кодовой последовательности принятие решения о соответствующей ей информационной последовательности производится при неполном использовании получаемой информации. Приписывая каждому принимаемому символу значение 0 или 1 ( жесткое решение), при дальнейшей обработке мы учитываем лишь две градации значений отношения правдоподобия (меньше или больше порогового уровня). При некотором усложнении процедуры можно осуществить последовательное декодирование на основе приема кодовой последовательности в целом, обеспечивающее более достоверную оценку передаваемой информации. Усложнение процедуры сводится при этом к введению при приеме символов нескольких пороговых уровней отношения правдоподобия и последовательному сравнению с ними отношения правдоподобия, полученного для символа ( мягкое решение). Если полученное отношение правдоподобия превышает верхний пороговый уровень, то символу приписывается значение 1, если нет, - то производится сравнение со следующим пороговым уровнем, при превышении которого приписывается следующая градация значения символа, и т.д. Бели значения отношения правдоподобия меньше самого нижнего порогового уровня, символу приписывается значение 0. Например, при восьми пороговых уровнях каждому из принимаемых символов приписывается одно из следующих значений: 0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1. Отличие процедуры последовательного декодирования в случае использования мягкого решения при приеме символов состоит в обобщении понятия расстояния d, между двоичными кодовыми последовательностями, отвечающими рассматриваемым траекториям, и принятой (уже не двоичной) последовательностью. Расстояние d{ должно определяться уже не простым счетом числа различающихся символов в сравниваемых последовательностях, а суммированием разностей значений этих символов (в общем случае величины di будут уже дробными). Усложнение процедуры последовательного декодирования сводится в основном к увеличению числа двоичных разрядов, требуемых для представления отдельных символов принятой последовательности и расстояний diy и к соответствующему увеличению объема памяти.

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

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

Совершенствование алгоритмов последовательного декодирования шло и ведется в направлении снижения среднего уровня вычислительной нагрузки и обеспечения большей ее равномерности. Существенное улучшение обоих этих показателей было достигнуто, в частности, с появлением алгоритма Зигангирова-Джеминика. В дальнейшем этот алгоритм был модифицирован Р. Фано с целью уменьшения требований к памяти за счет некоторого увеличения объема вычислений [31].

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

В последнее время все большее пыышмятлг привлекают так ге*8- * * * каскадные коды, основанные на последовательном кодировании двумя разными пдими (Код, используемый при первом кодировании, называется внешним, а код используемый при втором кодировании, формирующий поступающие в mnmny дтютшд - внутренним). В частности, весьма эффективными оказываются каскадные коды, использующие в качестве внешнего соответствующие классы блочного кода, а в качестве внутреннего-сверточные коды [30].