3. Общие методы обнаружения и исправления ошибок в циклических кодах

Комбинации циклических кодов независимо от того, каким из указанных способов они были получены, обладают двумя замечательными свойствами. Во-первых, соответствующие им полиномы ортогональны генераторному полиному [см. (X.1.18)]:

(X.3.1)

Во-вторых, полином делится без остатка на порождающий полином [см. (X.2.3)]:

(X.3.2)

Соотношения (X.3.1)-(X.3.2) лежат в основе методов обнаружения и исправления ошибок.

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

(X.3.3)

где — шумовая комбинация, записанная в виде полинома; и — полиномы переданной и принятой комбинации.

Умножим на генераторный полином, тогда с учетом (X.3.2) получим

(X.3.4)

Таким образом, полезный сигнал оказался подавленным, и образовался полином

(X.3.5)

Если

(X.3.6)

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

(X.3.7)

Отсюда следует: полиномы

(X.3.8)

не различимы в том смысле, что

(X.3.9)

(полином представляет комбинации -го смежного класса, а — соответствующее ему контрольное число).

Число полиномов (X.3.8) при фиксированном i точно равно — числу возможных полиномов представляющих комбинации исходного кода.

Два шумовых полинома и будут различимы, если

(X.3.10)

или

(X.3.11)

Из неравенства (X.3.11) непосредственно вытекает следующая теорема.

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

Эта теорема по своему существу совпадает с теоремой VII.3 и отличается от последней лишь терминологией (полином—комбинация; идеал — линейный код).

Допустим, что различимыми являются полиномы

(X.3.12)

где [такая ситуация может иметь место лишь тогда, когда «полиномы и не принадлежат (см. теорему (X.1)].

Контрольный полином

(X.3.10)

где определяется (X.3.5).

Из (X.3.13) мы имеем

(X.3.14)

Здесь знак минус в показателе степени означает циклический сдвиг коэффициентов полинома на шагов влево, в результате чего образуется полином . Это обстоятельство позволяет упростить устройство коррекции ошибок.

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

Блок-схема декодирующего устройства для первого случая показана на рис. X.7. Она содержит два регистра памяти по ячеек, сумматоры по модулю два, селектор и ключи и . Первоначально ключ устанавливается в положение , а ключ размыкается. Затем в ячейки регистра памяти РП-1 вводится принятая комбинация, после чего замыкается ключ и осуществляется тактов работы схемы. Регистр памяти при замкнутой цепи обратной связи совместно с блоком сумматоров образует фильтр-пробку для полезного сигнала (здесь осуществляется операция умножения на , см. (X.3.12)).

Рис. X.7. Декодирующее устройство для кода (7, 4, 3), основанное на умножении полинома принятой комбинации на генераторный полином .

После семи тактов работы схемы в регистре памяти образуется комбинация, соответствующая полиному (X.3.5):

(X.3.15)

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

Тогда согласно (X.3.14) селектор вырабатывает 1 в момент, когда символ принятой комбинации окажется на входе исправляющего сумматора по модулю 2.

Таблица X.4

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

(X.3.16)

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

Чтобы приспособить схему рис. X.7 для коррекции парных ошибок, необходимо настроить селектор на комбинацию, соответствующую полиному

(X.3.17)

При совпадении контрольного полинома принятой комбинации с (X.3.17) парная ошибка корректируется двумя подряд идущими исправляющими символами.

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

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

Рассмотрим далее принципы синтеза декодеров, основанных на соотношении (X.3.2). После деления полинома (X.3.3) на образуется целая часть и остаток, такие, что

(X.3.18)

Здесь -полином безызбыточного кода (информационные символы); и —целая часть и остаток от деления на (степень полинома не больше чем m, а не больше чем .

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

При анализируемом методе декодирования теорема X.1 сохраняет свою силу. Поэтому для всех и соответствующих им можно установить взаимно однозначное соответствие с . Кроме того, здесь имеют место соотношения, аналогичные (X.3.12)-(X.3.14): если полиномы и не принадлежат идеалу и

(X.3.19)

то

(X.3.20)

где по-прежнему .

Короче говоря, в результате циклического сдвига на г шагов влево коэффициентов полинома образуется полином .

Пусть

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

Рис. X.8. Схема деления полиномов степени на полином

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

Таблица X.5

Целая часть определяется полиномом , а остаток —полиномом . Легко заметить, что если бы то целая часть и остаток от деления определялись бы полиномами с коэффициентами, записанными в строке (снизу) первой и второй колонок табл.X.5.

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

Эти обстоятельства положены в основу работы декодера, блок-схема которого приведена на рис.X.9. Она отличается от схемы на рис. X.8 наличием селектора, настроенного на комбинацию 101; регистра памяти сумматора по модулю 2 и ключа К.

Рис.X.9. Декодирующее устройство для кода (7, 4, 3), основанное на делении полинома принятой комбинации на порождающий полином .

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

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

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

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

Рис. X.10. Второй тип декодирующего устройства для кода (7, 4, 3), основанного на делении полинома принятой комбинации на порождающий полином .

Другая схема декодера, использующая операцию деления на на рис. X.10. Принимаемая комбинация символ за символом подается на вход схемы. К такту в ячейках регистра памяти РП-1 сформируется остаток от деления полинома помехи на , а в ячейках регистра будет записана принятая комбинация. Затем символы из регистра через сумматор по модулю два начинают поступать на выход декодера. Одновременно символы регистра РП-1 синхронного сдвигаются влево, и в момент срабатывания селектора на исправляющий сумматор подается соответствующий сигнал (1, если желательно исправлять одиночные ошибки , и 11, если коррекции подлежат парные ошибки). Настройка селектора здесь проводится так же, как и в предыдущей схеме.

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

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