27.1 Идея построения непрерывного кода Финка–Хегельбергера

27.2. Двоичные сверточные коды

27.3 Представление сверточных кодов с помощью многочленов

27.4. Графическое представление сверточных кодов

27.1 Идея построения непрерывного кода Финка–Хегельбергера

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

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

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

Первый непрерывный рекуррентный код был предложен в 1955 г. русским ученым Л. М. Финком, который долгие годы

заведовал кафедрой в Ленинградской военной академии связи, а затем работал в электротехническом институте связи им. М. А.

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

лишь спустя 4 года (в 1959 г.) “вновь открытый” рекуррентный код был назван по имени его западного автора – кодом

Итак, рассмотрим идею построения рекуррентного кода Финка в изложении самого Л. М. Финка.

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

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

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

получаем такую последовательность символов:

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

– произвольное целое число, называемое шагом кода (

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

соотношение (27.1) в принятой

последовательности не будет выполнено для

. В случае же ошибочного приема информационного символа

соотношение (27.1) не будет выполняться при двух значениях

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

проверяется соотношение (27.1). Если оно оказалось не выполненным при двух значениях

то информативный элемент

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

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

неудачных сочетаний. Так, если

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

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

информационные, так и корректирующие символы).

Для наглядности в табл. 27.1, 27.2 и 27.3 графически показаны процессы форматирования (кодирования) кодов Финка при

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

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

таблицах жирным шрифтом. Для всех рассматриваемых значений

принята исходная информативная

последовательность из 10 символов 0001101011 (для

– с добавлением до 14). Как видно из рассмотренных примеров

формирования кодов после суммирования по модулю 2, в соответствии с выражением (27.1), последовательность проверочных

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

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

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

процедура получения проверочных символов, что и на стороне передачи (27.1), и производится сравнение их с принятыми

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

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

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

последовательности 1 на соответствующих позициях. В табл.27.1–27.3 непосредственно синдромы только с 1 на позициях,

определяющих конфигурацию ошибок, не указаны. Их заменяют результаты суммирования по модулю 2 по алгоритму (27.1)

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

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

в таблицах жирным шрифтом.

Как видно из табл. 27.1, при

ошибка при приеме одного 5-го информационного символа приводит при декодировании к

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

символ, в соответствии с выражениями (27.1) и (27.2). Декодирование при ошибке в одном проверочном символе при разных

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

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

Декодирование при ошибке в двух информационных символах (табл. 27.1,

) показывает, что для верного декодирования

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

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

перекрытия и, по крайней мере, без пропуска.

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

следующих символов с 3-го по 6-й, которые отмечены жирным шрифтом.

Это условие “стыковки” требует наличия трех (

) верно принимаемых символов между двумя искаженными

информационными символами. Называется этот интервал

В этом случае, когда соотношение (27.1) оказывается не выполненным для группы проверочных символов с 3-го по 6-й, в

соответствии с выражением (27.2) 4-й и 6-й информационные элементы заменяются на противоположные, т. е. происходит

верное исправление ошибочно принятых информационных символов с номерами

=6. Однако в интервал стыковки

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

4-го и правого 6-го) информационных символов также будет выполняться условие (27.2) и он, верно принятый, будет в декодере

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

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

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

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

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

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

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

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

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

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

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

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

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

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

термина “пачка ошибок”, встречаются и другие варианты (“пакет ошибок”, ”вспышка ошибок” и т. п.)”.

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

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

образом (для последовательности длиной

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

достаточно большом значении

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

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

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

В табл. 27.2 для кода Финка с шагом

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

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

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

четность (27.1). В связи с этим они все (2 информативных и один проверочный между ними) будут декодированы правильно.

Возвращаясь к коду с шагом

, из табл. 27.1 видно, что соседний с информационным искаженным символом

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

последовательности. Таким образом, при шаге

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

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

, а число необходимых дополнительных

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

. Это приводит к тому, что правильное

декодирование очередного (даже одиночного) информативного символа или очередной пачки ошибок из трех символов

возможно при защитном (однозначном) интервале с неискаженными помехами символами

В табл. 27.3 рассмотрены процессы формирования кода Финка с шагом

, что дает возможность верного декодирования

пачки ошибок, состоящей из 5 символов. При этом стыковочное расстояние

результирующий защитный интервал

верно принимаемому символу между крайними пораженными помехами

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

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

кода Финка. На основании данных табл. 27.4 устанавливается

связь между шагом кода Финка

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

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

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

Как отмечалось ранее, код Финка остался незамеченным в Западном мире. Первые сверточные (рекуррентные) коды,

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

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

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

27.2. Двоичные сверточные коды

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

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

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

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

информационных символов, и выдающее на выход за тот же такт

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

называют относительной скоростью кода.

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

информационных символов, поступивших на этом и

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

и состоянием, зависящим от

предыдущих информационных символов. Обратим внимание на то, что в коде Финка

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

алгоритмом (27.1), поскольку шаг кода ±

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

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

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

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

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

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

кода. В соответствии с этим число контактов (ячеек регистра сдвига коммутатора) должно быть равно

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

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

у коммутатора должно быть 2

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

Для примера на рис. 27.1 приведены кодеры кода Финка с различными шагами

, работающие со скоростью

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

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

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

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

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

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

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

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

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

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

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

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

В общем случае сдвигающий регистр кодера сверточного кода (рис. 27.3) содержит

ячеек, а коммутатор делает один цикл

очередных информационных символов, где

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

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

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

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

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

сумматоров по модулю 2, счет разрядов ведется слева направо. Связи

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

-й порождающей последовательности

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

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

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

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

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

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

27.3 Представление сверточных кодов с помощью многочленов

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

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

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

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

– символ оператора задержки на

тактов работы сдвигающего регистра;

– информационные двоичные

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

= 0; 1 – двоичные кодовые символы на

-м входе коммутатора кодера.

В силу линейности сверточного кода

-й порождающий многочлен сверточного кода;

= 0; 1 – его двоичные коэффициенты (27.6), равные 1, если

–1) сдвигающего регистра через схему суммирования связана с

-м входом коммутатора кодера, и равные нулю в

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

а для кодера несистематического сверточного кода (рис. 27.4, б)

Порождающие многочлены могут быть объединены в матрицу размера

, называемую порождающей матрицей из

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

Строка в матрице соответствует одному из

символов входной последовательности (в данном случае

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

суммирования по модулю 2. При

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

Так, для схемы кодера (рис. 27.5) при скорости

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

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

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

В данном случае порождающая матрица многочленов (полиномов) имеет вид

Рассмотрим, в качестве примера, для схемы кодера (рис. 27.6), как кодируется последовательность информационных

Этой последовательности соответствует многочлен

Содержимое выхода кодера

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

соответствует многочлен

На выходе второго сумматора по модулю 2 этого кодера последовательность кодовых символов будет 10001, а ей

соответствует многочлен

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

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

входной последовательности 101 в трехразрядном регистре:

27.4. Графическое представление сверточных кодов

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

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

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

ячейках регистра. Состояние 000...0 называется нулевым, остальные – ненулевые. Над каждым из ребер записывают кодовые

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

Так кодер, изображенный на рис. 27.7 может находиться в таких состояниях:

соответствуют вершинам графа (рис. 27.8).

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

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

около состояния 00. Далее при поступлении символа 1 кодер переходит в состояние 10 и на его выходе будут символы 11. Этот

переход из состояния 00 в состояние 10 обозначают стрелкой (ребром). Затем возможно поступление символа 0 или 1. Кодер

переходит в состояние 01 либо 11, а символы на выходе будут 10 или 01 соответственно. Построение диаграммы состояний

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

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

Так, например, решеточная диаграмма для кодера (рис. 27.7) диаграмма состояний которого представлена на рис. 27.8,

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

информационного символа 1, а сплошные линии (ветви) — информационного символа 0. Из решеточной диаграммы видно, что

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

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

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

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

решетке не растет, а остается равным

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

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

при поступлении на вход кодера последовательности 1011… путь по решетке (1 – пунктирная красная, 0 – сплошная синяя

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

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

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

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

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