7.1.3. Декодеры циклических кодов

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

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

Фиг. 7.10. Декодер, обнаруживающий ошибки.

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

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

б) Декодер БЧХ-кода. Как уже указывалось выше, БЧХ-коды могут иметь достаточно большое кодовое расстояние.

Однако их техническая реализация оказывается сравнительно сложной.

Алгоритм декодирования БЧХ-кода включает следующие пять операций:

I. Вычисление синдрома.

II. Вычисление многочлена, имеющего своими корнями локаторы ошибок.

III. Нахождение корней этого многочлена.

IV. Вычисление значений ошибок (в двоичном случае эта операция не нужна).

V. Исправление ошибок.

В двоичном случае операции III и V могут выполняться одновременно с помощью описанного ниже алгоритма Ченя.

Фиг. 7.11. Схема для вычисления

При декодировании БЧХ-кодов сначала находится синдром; эта операция может быть реализована с помощью схемы, осуществляющей вычисления в поле Галуа. Чтобы найти синдром, необходимо для принятого слова

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

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

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

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

GF(2^4)]. Так как, согласно таблице умножения в поле

то

Фиг. 7.12. Схема для вычисления .

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

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

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

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

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

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

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

Если многочлен

корнями которого являются локаторы ошибок, найден, то непосредственное исправление ошибок можно осуществить, например, воспользовавшись следующим алгоритмом Ченя. Предположим, что при передаче кодового слова БЧХ-кода произошло ошибок. Тогда, если компонента принятого слова является ошибочной, то

Пусть

Тогда, как легко видеть, имеют место следующие равенства:

и

С помощью схемы, показанной на фиг. 7.13, для каждого можно вычислить сумму Если эта сумма равно 0, то, как следует из формулы (7.11), компонента принятого кодового слова содержит ошибку.

Фиг. 7.13. Схема, реализующая алгоритм Ченя.

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

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

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

Шаг 1. Вычисляется синдром.

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

Шаг 3. Первый символ принятой последовательности считывается из буфера и складывается по модулю 2 с выходным символом последнего мажоритарного элемента; этим завершается исправление ошибки в первом символе.

Шаг 4. Осуществляется сдвиг синдрома и буферного регистра. На этом шаге необходимо устранить воздействие на синдром. Если обозначить шумовую последовательность через сумму членов степени и менее через то синдром можно представить в виде

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

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

Шаг 5. Новый синдром, полученный на шаге 4, используется для декодирования 2-го символа принятой последовательности. Вновь выполняя операции 2, 3 и 4, можно декодировать 2-й символ принятой последовательности точно так же, как и 1-й символ.

(кликните для просмотра скана)

Шаг 6. Точно так же декодер осуществляет декодирование остальных символов принятой последовательности.

Блок-схема декодера, осуществляющего декодирование принятой последовательности описанным выше образом, приведена на фиг. 7.14. Изображенный на фиг. 7.14 декодер называют декодером типа На фиг. 7.15 показан декодер типа I циклического кода с порождающим многочленом получающегося из совершенного разностного множества.

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

элементы пространства строк проверочной матрицы а черео

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

Так как , то

или, что то же самое,

Как видно, отыскание составных проверок, ортогональных относительно эквивалентно отысканию векторов в пространстве строк матрицы элементы строк равны 1, и строки таковы, что ни при каком среди элементов нет двух единиц. Согласно формуле (7.15), в качестве составных проверок, ортогональных относительно можно взять следующие проверки:

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

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

Шаг 1. Вентиль 1 открыт, вентиль 2 закрыт, и принятая последовательность вводится в буферный регистр. После ввода принятой последовательности вентиль 1 закрывается, а вентиль 2 открывается.

Фиг. 7.16. Мажоритарный декодер типа II в общем случае

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

Шаг составных проверок подаются на входы мажоритарных элементов 1-й ступени. Символы с выходов мажоритарных элементов 1-й ступени подаются на входы мажоритарных элементов 2-й ступени и т.д. Символ с выхода мажоритарного элемента ступени складывается по модулю 2 с первым принятым символом считываемым из буферного регистра, и таким образом исправление ошибки в завершается,

Шаг 4. После выполнения шага 3 содержимое буферного регистра сдвигается на один символ вправо. При этом 2-й принятый символ переходит на место 1-го принятого символа и декодируется точно так же, как и 1-й принятый символ.

Шаг 5. Повторяя указанные выше операции 2, 3 и 4, декодер точно так же декодирует остальные принятые символы.

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

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

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

Среди подпространств существуют три подпространства содержащие элемент соответствующий Гц. Следовательно, строками

матрицы ортогональными относительно являются 10, 13 и 14-я строки. Кроме того, 5, 11 и 13-я строки матрицы ортогональны относительно и 11-я строки ортогональны относительно Вычисляя следующие три суммы по модулю 2, в каждую из которых входит по 7 символов:

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

получаем составную проверку, ортогональную относительно Аналогично, вычисляя суммы

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

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

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

информационным и проверочным символам кодового слова. Выше предполагалось, что

Разделив на синдром можно представить в следующем виде:

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

Фиг. 7.17. Мажоритарный декодер типа II проективно-геометрического кода.

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

Теорема 7.1. Синдром последовательности, получающейся -кратным циклическим сдвигом принятого кодового слова

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

Доказательство. Пусть синдром последовательности длины Тогда

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

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

Фиг. 7.18. Декодер кода, исправляющего пачки ошибок.

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

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

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

Для примера рассмотрим код длины информационными символами, исправляющий пачки ошибок длины 3 и менее. Согласно табл. 7.1, этот код имеет следующий порождающий многочлен:

Для исправления пачек ошибок длины 9 и менее этот код следует «проредить» с шагом 3. В этом случае код будет задаваться порождающим многочленом

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

а синдром

Далее предположим, что при передаче возникла пачка ошибок длины 3 в символах. В этом случае

а синдром

Если этот синдром сдвигать влево, в сторону младших разрядов, то содержимое регистра будет изменяться следующим

образом:

После -кратного сдвига старшие разряда синдрома оказываются равными нулю, а в младших разрядах формируется вектор ошибок.

Фиг. 7.19. Декодер кода с порождающим многочленом

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