Сверточные коды. Формирование сверточного кода

Основная литература:

Скляр Б. Цифровая связь.  М., Санкт-П, Киев: Изд. дом «Вильямс», 2003.

Передача дискретных сообщений: Учебник для ВУЗов / В. П. Шувалов, Н. В. Захарченко, В. О. Шварцман и др.; Под ред. В. П. Шувалова. – М.: Радио и связь, 1990 - 464 с.

Дополнительная литература:

Макаров А.А., Прибылов В.П. Помехоустойчивое кодирование: Монография/СибГУТИ - Новосибирск, 2005

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976.

Мирманов А.Б. Курс лекций по дисциплине «Технология цифровой связи» - Астана: КазАТУ, 2009. (электронный)

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

Рассматриваемые вопросы:

Определение сверточных кодов

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

Диаграмма состояний кодера

Оценка исправляющей способности сверточного кода

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

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

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

Жесткая и мягкая схемы принятия решения

Тезисы к лекции

Сверточные коды

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

Свёрточный код описывается тремя целыми числами (n, k,K).

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

Выходные элементы СК зависят не только от текущего входного элемента, но и от (K-1) предыдущих, т.е. СК имеет память.

Основными элементами сверточного кода являются: регистр сдвига, сумматор по модулю 2, коммутатор.

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

Сумматор по модулю 2 осуществляет сложение поступающих на него символов 1 и 0. Правило сложения по модулю 2 таково: сумма двоичных символов равна 0, если число единиц среди поступающих на входы символов четно, и равно 1, если это число нечетно.

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

Рисунок 8.1. Простейший сверточный код (2.1.3)

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

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

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

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

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

Число символов на выходе кодера - n, соответствующих k, поступившим на вход символам в течение такта.

Скорость кода определяется отношением R=k/n и характеризует избыточность, вводимую при кодировании. Избыточность кода  = 1 - R

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

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

Диаграмма состояний кодера

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

Рисунок 8.2. Диаграмма состояний кодера сверточного кода (2.1.3)

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

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

Для СК со скоростью 1/n, состояний могут быть представлены содержимым (К-1) младших ячеек регистра. Поступление следующего элемента будет определять как переход в следующее состояние, так и элементы на выходе кодера.

Оценка исправляющей способности сверточного кода

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

Для СК исправляющая способность не может быть задана так однозначно. Данная способность определяется через просвет или свободное расстояние кода по аналогичной формуле (8.1):

(8.1)

где d f - просвет или свободное расстояние кода.

При декодировании по принципу максимального правдоподобия СК способен исправить заданное количество ошибок в пределах нескольких длин кодовых ограничений («несколько» - это от 3 до 5 К). Точное значение зависит от распределения ошибок.

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

Рисунок 8.3. Определение веса пути

Для кода (2.1.3) минимальный просвет d f =5, значит он может исправить две любые ошибки.

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

В GSM используют код (2.1.5) с полиномами: d f = 7

g 1 (x)=1+x 3 +x 4

g 2 (x)=1+x+x 3 +x 4

В системах спутниковой связи (2.1.7) : d f = 10

g 1 (x)=1+x 2 +x 3 +x 5 +x 6

g 2 (x)=1+x+x 2 +x 3 +x 6 .

Декодирование сверточных кодов. Алгоритм декодирования Витерби.

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

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

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

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

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

Систематически сверточный код – это код, содержащий в своей выходной последовательности кодовых символов породившую ее последовательность информационных символов. Иначе код называют несистематическим .

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

Жесткая и мягкая схемы принятия решения

В зависимости от того в какой форме информация поступает с выхода УПС в декодер СК различают жесткую и мягкую схему принятия решения.

Если решение о значащей позиции принимается жестко «1» или «0» – это жесткая схема .

Если УПС выдает декодеру значение квантованное более чем на 2 уровня – мягкое декодирование .

Мягкая схема обеспечивает декодер большим количеством информации для принятия решения. Вместе с решением о значащей позиции передается и мера его достоверности.

Рисунок 8.4. Жесткая и мягкая схемы декодирования

Контрольные вопросы

Рекуррентные (сверточные) коды

6.3. Рекуррентные (сверточные) коды

Рекуррентные коды относятся к непрерывным и не делятся на блоки. Операции кодирования и декодирования символов кода здесь происходят непрерывно. Широко применяется цепной рекуррентный код, который позволяет обнаруживать и исправлять групповые ошибки (пачки).
Рекуррентные коды обозначаются (m/n). Простейшим является код, у которого за каждым информационным следует контрольный (проверочный) символ. Такой код обозначается (1/2). Длина контрольных символов при этом равна длине информационных символов: m=k=n/2, следовательно, избыточность кода
D=(n-m)100/n=(n-0,5n)100/n=50%.
Принцип построения рекуррентного кода иллюстрируется на рис.1.

Рис. 1. Иллюстрация принципа построения рекуррентного кода

Последовательность контрольных символов (нижняя строка на рис. 1) образуется из последовательности информационных символов (верхняя строка на рис. 1) путем сложения по модулю 2 информационных символов, отстоящих друг от друга на постоянное расстояние l 0 .

Схема кодирующего устройства (кодера) с 4-х разрядным регистром сдвига со «связью вперед» приведена на рис. 2.

Рис. 2. Схема кодирующего устройства рекуррентного кода

Если на вход кодера подается та же последовательность символов, что приведена на рис. 1:
1 0 1 1 0 1 1 1 0 0 1, (1)
то на выходе регистра сдвига образуется последовательность символов
0 0 1 0 0 1 1 0 1 0 1. (2)
Образование последовательности (2) иллюстрируется на рис. 1 и в табл. 1. Последовательность информационных символов (1) соответствует состоянию 1-й ячейки регистра в дискретные моменты времени Т i , а последовательность контрольных (проверочных) символов (2) - символам на выходе сумматора по модулю 2.

Последовательность (2) получается путем суммирования сигналов на выходах второй и четвертой ячеек регистра сдвига в предыдущем такте, что соответствует суммированию символов второй и четвертой позиций состояний ячеек регистра в предыдущей строке табл. 1.
Коммутатор Км на передающей стороне выдает на выход последовательность (3), состоящую из первого информационного символа, затем первого проверочного, затем второго информационного т. д.:
1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1. (3)
Последовательность (3) и является выходной последовательностью закодированных символов рекуррентного кода (1/2).
Рассмотрим декодер, который состоит из двух частей:
1) схемы, вырабатывающей исправляющую последовательность;
2) схемы, производящей исправление (коррекцию) кода.
Первая схема приведена на рис. 3. Коммутатор Км декодера работает синхронно и синфазно с коммутатором кодера (рис. 2). Регистр сдвига декодера также состоит из четырех разрядов (ячеек).
На вход декодера подается последовательность символов (3), которая коммутатором Км разделяется на информационную (1) последовательность, подаваемую на вход регистра сдвига, и на последовательность контрольных символов (2), подаваемую на нижний вход выходного сумматора.

Рис. 3. Схема формирования исправляющей последовательности

В данной схеме четырехразрядный регистр сдвига имеет такую же схему, как и регистр сдвига в кодере. Поэтому, если ошибок нет, последовательность символов на выходе верхнего сумматора (рис. 3) совпадает с последовательностью контрольных символов (2), подаваемых на вход нижнего сумматора. В этом случае на Выходе 2 сумматора последовательность символов состоит из одних нулей, а последовательность символов на Выходе 1 - из последовательности неискаженных символов (1).
Если в канале связи между кодером и декодером возникают ошибки, то последовательность символов на Выходе 2 содержит единицы в определенном сочетании, которое позволяет исправлять ошибки. Следовательно, она служит исправляющей последовательностью.
Рассматриваемый код позволяет исправлять пакет ошибок длиной
Рассмотрим пример возникновения ошибок в наихудшем случае - серии длиной 2l 0 =4. Такой пакет ошибок поражает только половину информационных символов длиной l 0 =2 и половину контрольных символов длиной l 0 =2. Допустим, произошла последовательность ошибок
0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0. (4)
Суммируя последовательности символов (3) и (4), получаем принятую последовательность:
1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1, (5)
которая в рассматриваемом примере подается на вход декодера.
Коммутатор Км в схеме на рис. 3 разделяет последовательность (5) на информационные
1 0 1 1 1 1 1 1 0 0 1 (6)
и контрольные символы
0 0 0 1 0 1 1 0 1 0 1. (7)
Последовательности символов (6) и (7) содержат ошибочные символы, которые подчеркнуты. Регистр сдвига (рис. 3) выдаст последовательность символов
0 0 1 0 0 1 0 0 0 0 1, (8)
которая в сумме с последовательностью (7) даст исправляющую последовательность
0 0 1 1 0 0 1 0 1 0 0. (9)
Автоматически операция исправления последовательности (6), возникающей на Выходе 1 декодера с помощью исправляющей последовательности (9) на Выходе 2 (рис. 3), осуществляется с помощью схемы исправления ошибок, приведенной на рис. 4. Эта схема является продолжением схемы, приведенной на рис. 3 (Выход 1 соединяется с Входом 1 , а Выход 2 соединяется с Входом 2 .).

Рис. 4. Схема декодера, исправляющего ошибки

Исправляющая последовательность (9) подается непосредственно на инвертирующий элемент НЕ , который преобразует символы 1 в 0, а 0 в 1 и подает их на левый вход логического элемента И в виде последовательности (10). Схема нижнего регистра сдвига такая же, как на рис. 3. С выхода ячейки 2 исправляющая последовательность (9) подается со сдвигом l 0 =2 шага на нижний вход элемента И в виде последовательности (11), а с выхода ячейки 4 регистра - на правый вход элемента И в виде последовательности (12), сдвинутой на 2l 0 =4 шага. В результате на выходе элемента И получим последовательность (13)
1 1 0 0 1 1 0 1 0 1 1… (10)
. . 0 0 1 1 0 0 1 0 1… (11)
. . . . 0 0 1 1 0 0 1… (12)
. . . . 0 0 0 0 0 0 1… (13)
Точки в последовательностях слева обозначают сдвиг символов. Единица на выходе элемента И возникает только в тех случаях, когда на все его три входа подаются единицы. Она используется в качестве команды на исправление ошибки.
Выдача этой команды должна быть согласована по времени с входной (ошибочной) последовательностью информационных символов, поступающей на Вход 1 декодера. Для этой цели служат ячейки 5 и 6 регистра сдвига на Входе 1, обеспечивающие l 0 =2.
Исправленная последовательность вырабатывается на выходе схемы в виде суммы последовательностей символов (14) и (15), которые являются последовательностями (13) и (6), сдвинутыми соответственно на 2l 0 =4 и 3l 0 =6 шагов в соответствии с числом ячеек регистров сдвига, включенных последовательно:
. . . . 0 0 0 0 0 0 1 0 0 0 0 0 0 (14)
. . . . . . 1 0 1 1 1 1 1 1 0 0 1 (15)
1 0 1 1 0 1 1 1 0 0 1 (16)
После автоматического исправления последовательность (16) совпадает с последовательностью (1). Как следует из (16), на пути информационных символов включено 3l 0 =6 ячеек регистров сдвига.
Сложность аппаратуры для рекуррентного кода оценивается по числу ячеек регистров сдвига. Кодирующее устройство имеет 2l 0 =4 ячейки регистра, а декодирующее - 5l 0 =10 ячеек, из которых исправляющая схема имеет 3l 0 =6 ячеек. Для увеличения защищенности и пакета исправляемых ошибок увеличивают n, т. е. используют коды [(n-1)/n]. Схемы таких кодирующих и декодирующих устройств несколько усложняются.

Систематические коды

Систематическими кодами называются блочные (n , k ) коды, у которых k (обычно первые) разряды представляют собой двоичный неизбыточный код, а последующие r– контрольные разряды сформированы путем линейных комбинаций над информационными.

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

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

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

Образующая матрица М состоит из единичной матрицы размерностью k ×k и приписанной к ней справа матрицы дополнений размерностью k ×r :

Размерность матрицы дополнений выбирается из выражения (12.8) или (12.9). Причем вес w (число ненулевых элементов) каждой строки матрицы дополнений должен быть не меньше, чем d min – 1.

Проверочная матрица N строится из образующей матрицы следующим образом. Строками проверочной матрицы являются столбцы матрицы дополнений образующей матрицы. К полученной матрице дописывается справа единичная матрица размерностью r ×r . Таким образом, проверочная матрица размерностью r ×k имеет вид:

(12.12)

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

Пример 12.1. Получить алгоритм кодирования в систематическом коде всех четырехразрядных кодовых комбинаций, позволяющий исправлять единичную ошибку. Таким образом, задано число информационных символов k = 4 и кратность исправлений S = 1. По выражению (12.9) определим число контрольных символов:

Минимальное кодовое расстояние определим из выражения (12.6):

Строим образующую матрицу:

Проверочная матрица будет иметь вид

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

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

(12.13)

Из второй строки получим алгоритм для формирования контрольного символа a 6:

(12.14)

Аналогично из третьей строки получим алгоритм для формирования контрольного символа :

(12.15)

Нетрудно убедиться, что все результаты проверок на четность по выражениям (12.13)–(12.15) дают нуль, что свидетельствует о правильноcти составления образующей и проверочной матриц.

Пример 12.2. На основании алгоритма, полученного в примере 12.3, закодировать кодовую комбинацию в систематическом коде, позволяющим исправлять одиночную ошибку. По выражениям (12.13), (12.14) и (12.15) найдем значения для контрольных символов и :

(12.16)

Таким образом, кодовая комбинация F (X ) (10.16) в систематическом коде будет иметь вид

F (X ) = 1 1 0 1 0 1 0 . (12.17)

На приемной стороне производятся проверки Si принятой кодовой комбинации, которые составляются на основании выражений (12.13), (12.14) и (12.15):

Если синдром (результат проверок на четность) S 1 S 2 S 3 будет нулевого порядка, то искажений в принятой кодовой комбинации F ’(X) нет. При наличии искажений синдром S 1 S 2 S 3 указывает на искаженный символ.

Рассмотрим всевозможные состояния S 1 S 2 S 3:

S 1 S 2 S 3

0 0 0 – искажений нет,

1 0 0 – искажен символ а 5 ,

0 1 0 – искажен символ а 6 ,

0 0 1 – искажен символ а 7 ,

1 1 0 – искажен символ а 2 ,

0 1 1 – искажен символ а 1 ,

1 1 1 – искажен символ а 4 ,

1 0 1 – искажен символ а 3 . (12.19)

Пример 12.3. Кодовая комбинация F (X ) = 1 1 0 1 0 1 0 (пример 12.2) при передаче была искажена и приняла вид F ′(X ) = 1 1 1 1 0 1 0 = а 1 а 2 а 3 а 4 а 5 а 6 а 7 . Декодировать принятую кодовую комбинацию.

Произведем проверки согласно выражениям (10.18):

Полученный синдром S 1 S 2 S 3 = 101 согласно (10.19) свидетельствует об искажении символа а 3 . Заменяем этот символ на противоположный и получаем исправленную кодовую комбинацию F (X ) = 1 1 0 1 0 1 0, а исходная кодовая комбинация имеет G (X ) = 1 1 0 1, что совпадает с кодовой комбинацией, подлежащей кодированию в примере 12.2.

Рекуррентные коды

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

Рассмотрим процесс кодирования на примере кодовой комбинации, приведенный на рис. 12.4 (верхняя строка), если шаг сложения b = 2. Процесс образования контрольных символов показан на этом же рисунке (нижняя строка).

Кодирование производимое кодером, схема которого приведена на рис. 12.5. Как видно из рисунка 12.6 входные символы задерживаются на 2b тактов, что эквивалентно дописыванию 2b нулей перед входной кодовой комбинацией (рис. 12.4).

Рис. 12.4. Схема построения рекуррентного кода

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

На выходе кодирующего устройства (рис. 12.5) получим последовательность символов

1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 . (12.20)

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

Структурная схема декодера приведена на рис. 12.6.

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

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

Устройство разделения (рис. 12.4) разделяет последовательность (12.21) на информационные последовательности:

и контрольные символы:

Последовательности символов (12.22) и (12.23) содержат ошибочные символы, которые подчеркнуты сверху. Формирователь контрольных символов из (10.22), по тем же правилам, что и при кодировании входной комбинации, выдает последовательность символов

0 0 1 0 0 1 0 0 0 0 1, (12.24)

которая в сумме по модулю два с последовательностью (10.23) дает исправляющую последовательность

0 0 1 1 0 0 1 0 1 0 0. (12.25)

Исправляющая последовательность (12.25) подается на инвертор, который выдает последовательность (12.26) и одновременно поступает на устройство задержки на b и 2b тактов. На выходе устройств задержки появляются последовательности (12.27) и (12.28) соответственно. На выходе схемы совпадения получаем последовательность (10.29)

1 1 0 0 1 1 0 1 0 1 1 …	(12.26)
. . 0 0 1 1 0 0 1 0 1 …	(12.27)
. . . . 0 0 1 1 0 0 1 …	(12.28)
0 0 0 0 0 0 0 0 0 0 1 …	(12.29)

Точки в последовательностях слева обозначают задержку символов на соответствующее число тактов. Единица на выходе схемы совпадения возникает только в тех случаях, когда на все его три входа подаются единицы. Она представляет собой команду исправить ошибку. Исправленная последовательность вырабатывается устройством коррекции в виде суммы по модулю два последовательности (12.29) и (12.22), задержанной на b тактов:

. (12.30)

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

После автоматического исправления последовательность (12.30) совпадает с последовательностью на рис. 12.4 (верхняя строка). Как следует из (12.29), на пути информационных символов включено 3b = 6 ячеек регистра сдвига. При этом для вывода всех ошибочных символов необходим защитный интервал 6b + 1 = 13 символов.

Рассмотренный код позволяет исправлять пакет ошибок длиной l = 2b = 4.

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

Сверточные коды

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

При использовании сверточных кодов поток данных разбивается на гораздо меньшие блоки длиной k символов (в частном случае k 0 = 1 ), которые называются кадрами информационных символов .

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

Основными характеристиками сверточных кодов являются величины:

– k 0 – размер кадра информационных символов;

- n 0 – размер кадра кодовых символов;

- m – длина памяти кода;

- k = (m+1) × k 0 – информационная длина слова;

- n = (m+1) × n 0 – кодовая длина блока.

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

Наконец, сверточный код имеет еще один важный параметр – скорость R = k/n, которая характеризует степень избыточности кода, вводимой для обеспечения исправляющих свойств кода.

Как и блочные, сверточные коды могут быть систематическими и несистематическими и обозначаются как линейные сверточные (n,k)– коды.

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

Примеры схем кодеров для систематического (8,4) и несистематического сверточных (6,3) –кодов приведены на рис. 12.7 и 12.8.

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

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

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

Импульсная переходная характеристика фильтра (ИПХ )(а кодер сверточного кода, по сути дела, является фильтром) есть реакция на единичное воздействие вида = (10000..... Для кодеров, изображенных на рис. 12.7 и 12.8, соответствующие импульсные характеристики будут иметь вид:

H 1 = (11.00.00.01.00.00… , (12.31)

H 2 = (11.10.11.00.00.00… . (12.32)

Еще одна форма задания сверточных кодов – это использование порождающих полиномов, однозначно связанных с ИПХ эквивалентного фильтра:

H 1 (x) = 1 + x + x 7 , (12.33)

H 2 (x) = 1 + x + x 2 + x 4 + x 5 . (12.34)

При этом кодовая последовательность F(x)на выходе сверточного кодера получается в результате свертки входной информационной последовательности G(x) с импульсной переходной характеристикой H .

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

Пусть G(x)=(110 ... , тогда для кодера с ИПХH 1 = (11.00.00.01.00.00....

11.00.00.01.00.00…
11.00.00.01.00…

F(x) = 11.11.00.01.01.00.00… ,

или G(x) = (1011000…

11.00.00.01.00.00.00…
11.00.00.01.00…
11.00.00.01…

F(x) = 11.00.11.10.00.01.01.00… .

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

P 1 (x) = 1 + x + x 2 , (12.35)

P 2 (x) = 1 + x 2 . (12.36)

Пусть, например, кодируется последовательность G(x) = (1010 … .

Тогда на входе 1 ключа DA1 при кодировании будет последовательность F 2 (x) = (11011000…, а на входе 2 – F 2 (x) = (10001000… .

Легко заметить, что при этом справедливы равенства

F 1 (x) = G(x) × P 1 (x), (12.37)

F 2 (x) = G(x)× P 2 (x). (12.38)

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

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

Рис. 1.21. Схема простейшего турбокодера

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

Кодер содержит два параллельно соединенных сверточных кодера. Отличие кодера 1 от кодера 2 заключается в том, что в первом кодере имеется систематический выход, через который в канал связи поступает информационная последовательность. Это обеспечивает систематическое представление кодовой последовательности. Скорость кодеров равна 1/2. Это означает, что общая скорость кодера ТК равна 1/3, поскольку на выходах 1 и 2 формируются только проверочные биты. Выбор битов с выхода перемежителя может подчиняться псевдослучайному закону и соответствовать заданной функции , следовательно, информационный блок должен быть введен в перемежитель до начала процедуры кодирования. С выхода всего турбо-кодера на модулятор сначала поступает бит с систематического выхода верхнего кодера, а затем два проверочных бита: сначала с 1 кодера, затем – со второго. Анализ многочисленных результатов экспериментальных ис­следований ТК, выполненных различными авторами, показал, что структура перемежителя сравнительно слабо влияет на его эффек­тивность такого кодирования. Те же результаты свидетельствуют о пропорциональном увеличении эффективности ТК с ростом как длины кодового ограни­чения сверточного кода, так и длины перемежителя. В любом случае благодаря использованию систематических сверточных кодеров в кодовом блоке можно явно выделить систематическую и проверочную части. Более того, можно считать, что в канал связи передаются два кодовых блока: первый кодовый блок, состоящий из информационной части и проверочной части кодера 1, и второй кодовый блок, состоящий из перемешанной информационной части и проверочной части кодера 2. Ясно, что передавать перемешанную (систематическую) часть второго кодового блока в канал связи нет смысла. Для ее восстановления в декодере можно использовать опе­рацию обратную операции перемежения информационной части кодового блока (деперемежения), соответствующую функции . Традиционно в соответствии со схемой представленной на рис. 1.15 избыточные коды подбираются по кри­терию максимума минимального расстояния . При этом, однако, достижение больших значений связано со значительным усложнением процедуры декодирования. Эффективность же ТК определяется, в основном, не параметром , а средним значением расстояний между кодовыми блоками , поскольку в процессе кодирования присутствует элемент псевдослучайного выбора, задаваемый функцией перемежителя. Благодаря особенностям формирования кодовых блоков из двух практически независимых частей, величина их суммы будет заметно больше, чем исходного сверточного кода. Это достигается за счет применения рекурсивной схем кодера, получившей свое название от рекуррентных регистров сдвига, имеющих обратную связь через схему неравнозначности. Рекурсивная схема кодера показана на рис. 1.22.

Рис. 1.22. Схема рекурсивного кодера сверточного кода

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

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

Рис. 1.23. Диаграмм состояний рекурсивного кодера сверточного кода

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

Рис. 1.24. Схема простейшего турбодекодера

Декодер для каждой итерации представляет собой каскадное соединение двух элементарных декодеров: первого и второго. Каждый из этих декодеров выносит решение о переданном символе на основе критерия максимальной апостериорной вероятности, чем обеспечивается минимум вероятности ошибочного декодирования каждым элементарным декодером. На первой итерации от демодулятора на вход первого декодера поступают оценки (мягкие решения) символов от демодулятора систематической и первой проверочной частей первого кодового блока. На выходе первого декодера формируется оценка (мягкое решение) информационного символа, которая затем используется в качестве априорной информации о нем для второго декодера. Этот декодер производит оценку символа с выхода деперемежителя на основе проверочной части второго кодового слова. На второй и последующих итерациях декодирования эта оценка обновляется и используется как априорная информация о переданном сим­воле для первого декодера. Таким образом, на вход каждого из двух элементарных декодеров поступают мягкие решения, результат декодирования на выходе элементарного декодера – также мягкое решение. По этой причине такие схемы по­лучили название декодеров с мягким входом и мягким выходом (Soft Input Soft Output -SISO). Именно такой декодер обозначен на рис. 1.3. Изложенный алгоритм декодирования оказался чрезвычайно эффективным, и каждая последующая ите­рация увеличивает априорную информацию о переданном символе. При этом, первое и второе итеративные преобразования обеспечивают траектории близкие к траектории и только на 18 итерации декодер приближается к траектории .

Окончание процесса декодирования происходит либо после вы­полнения заданного количества Q итерационных циклов, либо после того, как величина поправки результата декодирования достигнет установленного порога. Вычислительная сложность турбо-декодера в расче­те на один информационный бит не зависит от длины информационного блока . В этом смысле ТК подобен сверточному коду. В то же время, с ростом , для ТК, как для всех блочных кодов, возрастает требуемый объем памяти декодера и, соответственно, время задержки декодирования . Компаниями France Telecom и Telediffusion de France запа­тентован широкий класс ТК. Более того, ТК утверждены для по­мехоустойчивого кодирования несколькими стандартами космичес­кой связи, а также мобильной связи третьего поколения .

Схема кодирования, с кодерами на 16 состояний (К=5), максимальной длиной перемежения 16384 и кодовыми скоростями R = 1/2; 1/3; 1/4; 1/6 утверждена в 1999 г. аме­риканским комитетом CCSDS (Consultative Committee for Space Data Systems) в стандарте передачи телеметрической информации с кос­мических аппаратов. В феврале 2000 г. консорциум DVB утвер­дил ТК в стандарте DVB-RCS для передачи информации по обратному спутниковому каналу (Return Channel for Satellite - RCS), т.е. в направлении от спутника к абоненту. ТК формируются на основе циклического рекурсивного систематического сверточного кодера (Circular Recursive Systematic Convolutional – CRSC). Использование стандарта совместно с вещательным стандартом DVB-S позволяет проектировать полноценную широкополосную систему спутникового интерактивного цифрового телевидения. Компанией Turbo Concept в партнерстве с европейским спутниковым оператором Eutelsat разработан турбо-декодер ТС1000 в соответствии со стандартом DVB-RCS. Использование ТК принято также в новом стандарте спутниковой системы связи Inmarsat. В универсальных мобильных системах (IMT-2000) третьего поколения (3G), предназначенных для передачи и приема мультимедийной информации, ТК также получили широкое применение. В стандарте CDMA-2000 для высокоскоростного режима передачи информации (больше 14.4 кбит/с) как к абоненту (forward link), так и от абонента (reverse link) используется ТК с восемью состояни­ями (К = 4) и кодовыми скоростями = 1/2; 1/3; 1/4. В стандарте UMTS для высокоскоростного режима передачи информации (больше 32 кбит/с) и приема с высоким качеством (BER около 106) используется ТК с восемью состояниями (К = 4) и двумя кодовыми скоростями = 1/2 и = 1/3.