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

Систематическими кодами называются блочные (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.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)

Точки в последовательностях слева обозначают задержку символов на соответствующее число тактов. Единица на выходе схемы совпадения возникает только в тех случаях, когда на все его три входа подаются единицы. Она представляет собой команду исправить ошибку. Исправленная последовательность вырабатывается устройством коррекции в виде суммы по модулю два последовательности (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/2, так как на каждый введенный информационный символ выдаются два кодовых символа. Кодер, использующий т элементов памяти, называется в дальнейшем кодер памяти т. В общем случае, сверточный кодер скорости k/п использу­ет к регистров сдвига, один регистр на один вводимый информационный символ. Под скоростью кода в теории кодирования понимается отношение . Более точное наименование параметра – относительная скорость кода , поскольку за единицу времени кодер принимает на вход информационных разрядов и трансформирует их в разрядов избыточного кода. Кодер памяти и скорости двоичного сверточного ко­да можно рассматривать также как дискретную линейную инвариантную во времени систему. Это означает, что отклик кодера на нулевую последовательность, в которой имеется единственная единица, т.е. выход кодера, полученный для входной последова­тельности , полностью определяет код. Стрелка вправо символизирует, что единица от источника информации первой поступит на вход кодера. Рассмотрим сверточный кодер, показанный на рис. 1.12.

Рис. 1.12. Кодер сверточного кода

Имеется импульсных откликов сверточного кодера скорости , по одному на каждый выход , где . По мере того, как импульс проходит через память кодера, он отражает связи между элементами памяти и выходом. Обозначим набор импульсных откликов сверточ­ного кодера скорости , получивших название порождающи­х последовательностей или генераторов кода, которые задают действительные (физические) связи кодера. Кодер на рис. 1 порождает генераторы и , поскольку на каждом их выходов кодера через тактов формируются последовательности с нулевыми хвостами, при этом , а . Обычно, говоря о сверточном коде, генераторы записывают в восьмеричной системе счисления. Для рассматриваемого кодера эта запись имеет вид (7,5).

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

Сверточный кодер памяти и скорости 1/n может быть задан также диаграммой состояний (см. рис. 1.13). В такой диаграмме должно быть состоя­ний.

Рис. 1.13. Диаграмма состояний сверточного кодера памяти 3 и скорости 1/2

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

По-видимому, метка ребер вида 1/00, 1/11, 1/00 или 0/11 нейтральна, когда символы на выходе одинаковы , но следует быть точным в представлении последовательности символов в метках вида 1/01, 1/10 или 0/10, 0/01, когда .

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

Табл. 1.8 Представление выходной последовательности кодера (7,5)

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

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

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

при (1.18)

Выходные последовательности , равны дискретной свертке входной последовательности с генераторами кода . Уравнение (1.2) в ма­тричной форме имеет вид

где G – порождающая матрица сверточного кода.

В частности, для сверточного кода памяти т и скорости 1/2 имеем

.

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

. (1.20)

Пусть информационная последовательность имеет вид: , тогда произведение вектора на матрицу представляется последовательность двоичных символов (1.21)

, (1.21)

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

Рис. 1.14. Путь на треллис-диаграмме сверточного кода при m = 3

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

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

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

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

Принцип работы декодера иллюстрируется на рис. 1.15.

Рис. 1.15. Принцип работы декодера сверточного кода

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

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

Работа декодера начинается с левого верхнего узла решетки (также как и работа кодера). В этой точке треллис-диаграммы декодер анализирует ситуацию, когда кодер мог находиться в состоянии 000 и на его входе появился 0. Таким образом, в канал связи кодер мог отправить значения 00. Сравнивая эти показатели с показателями, которые реально принял приемник (данные из канала связи соответствуют значениям 11), декодер устанавливает вес этого пути. Это осуществляется путем поразрядного сложения по 2 данных из канала связи и данных выработанных декодером для данного ребра, т.е. 1100=11 и вес этого пути равен 2 (в результате сложения оказалось, что оба разряда равны единице).

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

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

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

На практике для декодирования сверточных кодов наи­большее распространение получил алго­ритм Витерби, предложенный в 70-х го­дах прошлого столетия, и несколько модификаций алгорит­ма последовательного декодирования. Подобные коды используются практически во всех стандартах консорциума DVB (Digital Video Broadcasting) и являются стандартом для многих спутниковых цифровых систем (например, Inmarsat и Intelsat).

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

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]. Схемы таких кодирующих и декодирующих устройств несколько усложняются.

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

Скляр Б. Цифровая связь.  М., Санкт-П, Киев: Изд. дом «Вильямс», 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. Жесткая и мягкая схемы декодирования

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

В противоположность классическим алгебраическим блочным кодам, ТК следует отнести к случайным кодам. Один из вариантов построения кодера ТК представлен на рис. 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.