3.20. Непрерывные коды

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

К ним относятся цепной и сверточные коды [2, 23, 77, 139]. Они могут обнаруживать и исправлять случайные ошибки и пачки ошибок.

Цепной код. Это код, в котором после каждой информационной посылки следует проверочная посылка. Последние формируются путем сложения по модулю два двух информационных посылок, отстоящих одна от другой на шаг сложения [139].

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

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

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

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

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

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

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

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

Корректирующие возможности цепного кода зависят от шага сложения Изменяя его, можно построить кодирующие и декодирующие устройства для обнаружения и исправления пачек ошибок любой длительности I [59]:

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

Для цепного кода существует понятие условной кодовой группы, длина которой равна сумме длительности пачки ошибок и защитного интервала [59]:

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

Таблица 28 (см. скан)

Цепной код сравнительно просто, но ценой большой избыточности позволяет обнаруживать или исправлять пачки ошибок, возникающие в каналах связи. Изменяя величину шага сложения, можно согласовать корректирующие возможности кода с характеристиками канала связи, т. е. увеличить или уменьшить допустимую частость ошибок [139]. Код с исправлением пачки ошибок длиной сылок и интервалом между пачками а посылок может исправлять: любую однократную ошибку в пределах условной кодовой группы из посылок с вероятностью

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

Вероятность ошибки кодовой комбинации при биноминальном распределении ошибок [59]:

Пример. Определить вероятность ошибки кодовой комбинации в цепном коде, рассчитанном на исправление пачки ошибок длиной I в 4 посылки при вероятности искажения в канале связи единичной посылки По табл. 28 определяем Вероятность ошибки находим по формуле (3.62). Вычисляем коэффициенты Подставив значения коэффициентов и получим

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

Рис. 19. Кодирующее устройство сверточного кода для скорости

В общем случае сверточные коды могут иметь произвольную скорость передачи двоичных единиц на передаваемый символ. Кодирующее устройство таких кодов содержит входов и выходов (рис. 19).

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

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

Входные информационные последовательности можно представить в виде полиномов:

Выходные проверочные последовательности можно представить в виде к полиномов:

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Схема, приведенная на рис. 20, имеет следующие недостатки:

1) сложность реализации логической схемы;

2) возникновение «эффекта размножения ошибок» в регистре корректирующей последовательности из-за наличия обратной связи.

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

Для устранения первого недостатка используются сверточные коды, допускающие мажоритарное декодирование. Чтобы исключить «эффект размножения ошибок», можно использовать три метода, предложенные в работе [130].

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

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

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

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

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

где транспонированная контрольная матрица, описываемая коэффициентами порождающего полинома:

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

Разделенными проверками, т. е. контролирующими являются строки матрицы (3.67), начинающиеся с ненулевых членов. Первая строка дает проверку

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

Рассмотрим первый пример. Сверточный код со скоростью передачи 1/2 порождается полиномом Построим в соответствии с (3.67) транспонированную контрольную матрицу:

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

В соответствии с этими данными строится схема декодирующего устройства.

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

Такую систему уравнений можно получить из контрольной матрицы (3.68), которая отличается от (3.67) тем, что в ней учтено отсутствие коррекции содержимого декодирующего устройства:

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

Рассмотрим второй пример. Сверточный код со скоростью передачи 1/2 порождается полиномом

Контрольная матрица (3.68) имеет вид

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

Добавляя к этим уравнениям тривиальное получаем систему из" четырех независимых уравнений. В соответствии с этими уравнениями строим схему декодирующего устройства. Систематического набора правил для построения сверточных кодов не существует. Наиболее подробно сверточные коды и параметры некоторых кодов рассмотрены в работах [2, 23, 77, 130].