3. Рекуррентное кодирование Финка — Хагельбаргера

Идея рекуррентного кодирования принадлежит Л. М. Финку (1955 г). Существенный вклад в развитие такого рода кодирования внесен Хагельбаргером [169, 170], Возенкрафтом [10], Килмером [102], Элспасом [184] и рядом других авторов. Эти коды в основном предназначены для коррекции пачек ошибок, хотя и могут с успехом применяться для коррекции независимых ошибок.

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

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

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

(XI.3.1)

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

(XI.3.2)

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

Рис. XI.2. Устройство для получения рекуррентной последовательности Финка с шагом

Кодирующее устройство для случая представлено на рис. XI.2. Оно содержит два сдвигающих регистра и . Первый из них имеет две , а второй — одну ячейку памяти. Ячейка памяти, помеченная на рис. XI.2 буквой , играет вспомогательную роль. Она подключается к через сумматор по модулю два.

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

Одновременно в ячейку записывается сумма по модулю два входного символа и символа, хранившегося в последней ячейке CP-II (в данный момент запишется символ ).

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

Таблица XI.5

Начиная с седьмого такта работы кодера (табл. XI.5) образуется рекуррентная последовательность, формальная запись которой совпадает с (XI.3.1) при . Вопрос о декодировании рекуррентной последовательности может быть решен многими способами.

На рис. XI.3 представлена блок-схема декодера, принцип работы которого сводится к следующему. В сдвигающий регистр, содержащий ячеек памяти (в нашем случае 12) вводятся символы так, что в крайней справа ячейке располагается информационный символ (в данной ситуации ).

При указанном на рис. XI.3 расположении символов будет осуществляться декодирование символа .

Рис. XI.3. Блок-схема декодера рекуррентной последовательности Финка, основанного на проверке на четность.

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

и

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

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

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

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

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

Легко заметить, что символ декодируется правильно, если «длина» пакета не превосходит 3 (в общем случае ), а следующие за ним 9 символов приняты правильно [в общем случае ), а иногда ].

Рис.XI.4 . Блок-схема декодера рекуррентной последовательности с мажоритарным селектором.

Применительно к случаю бинарного симметричного канала без памяти вероятность ошибочного декодирования данного конкретного символа в последовательности (XI.3.1)

(XI.3.3)

На рис. XI.4 представлена другая схема декодера, которая отличается от предыдущей тем, что здесь решение о символе (в частности ) принимается по «большинству голосов» (мажоритарный селектор выдает на выходе символ 1, если на какие-либо два или все три его входа поданы единицы, а символ 0 — во всех остальных случаях). В этой схеме декодера, так же как и ранее, имеется один «холостой» такт, на котором ключ К размыкается. Схема может служить хорошей иллюстрацией к декодированию по методу независимых решений.

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

Рис. XI.5. Декодирование рекуррентной последовательности Финка методом последовательного исключения независимых переменных.

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

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

Талица XI.6

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

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

Детальное изложение затронутых вопросов с несколько иных позиций можно найти в [29]. Там же обсуждается ряд интересных идей по синтезу кодирующих и декодирующих устройств, а также рекуррентных последовательностей, обеспечивающих скорость передачи, как равную, так и отличную от .