4. Циклические коды

4.1 Основные понятия

Циклическим кодом называется линейный блоковый (n,k)-код, который характеризуется свойством цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый многочлен g(x) степени r = n-k, являющийся сомножителем двучлена xⁿ+1.
Многочлен g(x) называется порождающим.
Как следует из определения, в циклическом коде кодовые слова представляются в виде многочленов

где n - длина кода;
- коэффициенты из поля GF(q).
Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным.
Пример. Если кодовое слово циклического кода

то соответствующий ему многочлен
Например, если код построен над полем GF(q)=GF(2³), которое является расширением GF(2) по модулю неприводимого многочлена f(z)=z³+z+1, а элементы этого поля имеют вид, представленный в таблице 3,

Таблица 3

0	000	0	a3	011	Z+1
a0	001	1	a4	110	Z2+Z
a1	010	Z	a5	111	Z2+Z+1
a2	100	Z2	a6	101	Z2+1

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

где m - степень многочлена, по которому получено расширение поля GF(2);
a_i - коэффициенты, принимающие значение элементов GF(2), т.е. 0 и 1.
Такой код называется q-ным.
Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q^m-1 над GF(q).
Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным.
Как следует из определения общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим.
Результатом деления двучлена xⁿ+1 на многочлен g(x) является проверочный многочлен h(x).
При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x).
Многочлен ошибок степени не более (n-1) определяется из выражения

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

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

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

Таблица 4

(x)	S(x)
1	Rg(x)[1]
X	Rg(x)[x]
X2	Rg(x)[x2]
·	·
·	·
·	·
X+1	Rg(x)[x+1]
X2+1	Rg(x)[x2+1]
·	·
·	·
·	·

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

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по mod 2, а затем по mod xⁿ+1, если степень результата превышает степень (n-1).
Примеры.

4.2 Матричное задание кодов

Циклический код может быть задан порождающей и проверочной матрицами. Для их построения достаточно знать порождающий g(x) и проверочный h(x) многочлены.
Для несистематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, т.е. путем их умножения на x
и
При построении матрицы H_(n,k) старший коэффициент многочлена h(x) располагается справа.
Пример. Для циклического (7,4)-кода с порождающим многочленом g(x)=x³+x+1 матрицы G_(n,k) и H_(n,k) имеют вид:


где
Для систематического циклического кода матрица G_(n,k) определяется из выражения

где
I_k - единичная матрица;
R_k,r - прямоугольная матрица.
Строки матрицы R_k,r определяются из выражений
или
где a_i(x) - значение i-той строки матрицы I_k;
i - номер строки матрицы R_k,r.
Пример. Матрица G_(n,k) для (7,4)-кода на основе порождающего многочлена g(x)=x³+x+1, строится в следующей последовательности

или
Определяется R_4,3, используя
так как

Аналогичным способом определяется

В результате получаем
или
Используя выражение получим тот же результат.
Строки матрицы G_(n,k) можно определить непосредственно из выражения
где
Проверочная матрица в систематическом виде строится на основе матрицы G_(n,k), а именно:

где
I_r - единичная матрица;
- матрица из G_(n,k) в транспонированном виде.
Пример. Для (7,4)-кода матрица H_(n,k) будет иметь вид:

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

4.3 Коды БЧХ

Одним из классов циклических кодов, способных исправлять многократные ошибки, являются коды БЧХ.
Примитивным кодом БЧХ, исправляющим t_u ошибок, называется код длиной n=q^m-1 над GF(q), для которого элементы являются корнями порождающего многочлена.
Здесь a - примитивный элемент GF(q^m).
Порождающий многочлен определяется из выражения
где f₁(x),f₂(x)...- минимальные многочлены корней g(x).
Число проверочных элементов кода БЧХ удовлетворяет соотношению
Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, исправляющего двух кратные ошибки (t_u=2).
Исходя из определения кода БЧХ корнями многочлена g(x) являются: , где a - примитивный элемент GF(q^m)=GF(2⁵).
Порождающий многочлен определяется из выражения где f₁(x), f₂(x), f₃(x), f₄(x) - минимальные многочлены корней соответственно .
Примечание.
Минимальный многочлен элемента b поля GF(q^m) определяется из выражения , где - наименьшее целое число, при котором .
Значения минимальных многочленов будут следующими:

Так как f1(x)= f2(x)= f4(x), то

На практике при определении значений порождающего многочлена пользуются специальной таблицей минимальных многочленов (см. таблицу 8 приложения), и выражением для порождающего многочлена При этом работа осуществляется в следующей последовательности.
По заданной длине кода n и кратности исправляемых ошибок t_u определяют:
- из выражения n=2^m-1 значение параметра m, который является максимальной степенью сомножителей g(x);
- из выражения j=2t_u-1 максимальный порядок минимального многочлена, входящего в число сомножителей g(x).
- пользуясь таблицей минимальных многочленов, определяется выражение для g(x) в зависимости от m и j. Для этого из колонки, соответствующей параметру m, выбираются многочлены с порядками от 1 до j, которые в результате перемножения дают значение g(x).
Примечание.
В выражении для g(x) содержаться минимальные многочлены только для нечетных степеней a, так как обычно соответствующие им минимальные многочлены четных степеней a имеют аналогичные выражения.
Например, минимальные многочлены элементов соответствуют минимальному многочлену элемента a¹, минимальные многочлены элементов соответствуют минимальному многочлену a³ и т.п.
Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, обеспечивающего t_u=3.
Определяем значения m и j.

Из таблицы минимальных многочленов в соответствии с m=5 и j=5 получаем

Заданные исходные данные: n и t_u или k и t_u для построения циклического кода часто приводят к выбору завышенного значения m и как следствие этого к неоправданному увеличению длины кода. Такое положение снижает эффективность полученного кода, так как часть информационных разрядов вообще не используется.
Пример. Требуется построить циклический код, исправляющий двух кратные ошибки, если длина информационной части кода k=40.
Согласно выражению для примитивного кода n=2^m-1, ближайшая длина кода равна 63, для которой m=6, а r=mt_u=12. Следовательно, код будет иметь n=63, k=51. Неиспользованных информационных разрядов будет 11(51-40).
Подобное несоответствие в ряде случаев можно устранить, применяя непримитивный код БЧХ.
Непримитивным кодом БЧХ, исправляющим t_u ошибок, называется код длины n над GF(q), для которого элементы являются корнями порождающего многочлена.
Здесь bⁱ-непримитивный элемент GF(q^m), а длина кода n равна порядку элемента bⁱ.
Примечание.
Порядком элемента bⁱ является наименьшее n, для которого .
Пример. Порядок элемента b³ поля GF(2⁶) равен 21, так как .
Порождающий многочлен непримитивного кода БЧХ, по аналогии с примитивным кодом, определяется из выражения - минимальные многочлены элементов поля GF(q^m), которые являются корнями g(x); i - степень непримитивного элемента b.
Пример. Определить значение g(x) для построения непримитивного кода БЧХ над GF(2) длины n=20, исправляющего двух кратные ошибки.
Из таблицы непримитивных элементов GF(2^m) (см. таблицу 7 приложения) выбираем поле, элемент b которого имеет порядок больший, но близкий к заданному n.
Такими являются GF(2⁶) и b³, порядок которого n=21.
Так как j=2t_u-1=2(2-1=3, то выражение для g(x) будет иметь вид
где f₃(x) и f₉(x) - минимальные многочлены элементов b³ и b⁹ поля GF(2⁶).
Значения этих многочленов следующие:


Выражения для f₃(x) и f₉(x) можно определить из таблицы минимальных многочленов, используя для этого параметр m выбранного поля GF(2^m) и порядковые номера сомножителей g(x).
Для рассмотренного примера m=6, а порядковые номера равны 3 и 9. Поэтому
.

4.4 Способы кодирования

Задача кодирования заключается в формировании по информационным словам a(x) кодовых слов u(x) циклического (n,k)-кода, который по своей структуре может быть несистематическим и систематическим.
Формирование кодовых слов несистематического кода заключается в умножении многочлена a(x), отображающего информационную последовательность длины k, на порождающий многочлен, т.е. u(x)=a(x)(g(x). Формирование кодовых слов систематического кода заключается в преобразовании информационной последовательности a(x) в соответствии с выражением u(x)=a(x)·x^r+r(x).
Проверочная последовательность r(x) определяется двумя способами:
при использовании "классического" способа кодирования ;
при использовании способа кодирования, рекомендованного МККТТ ,
где x(1)^r-1 - единичный многочлен степени (r-1).
Указанные выше математические операции выполняют кодеры несистематического и систематического кодов.

4.5 Способы декодирования с обнаружением ошибок

Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования, использует два способа:
- при кодировании "классическим" способом декодирование основано на использовании свойства делимости без остатка кодового многочлена u(x) циклического (n,k)-кода на порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя деление принятого кодового слова, описываемого многочленом на g(x), вычисление и анализ остатка r(x). Если r(x)=0, то принятое кодовое слово считается неискаженным. Если r(x)№0, то принятое кодовое слово стирается и формируется сигнал "ошибка".
- при кодировании способом МККТТ декодирование основано на свойстве получения определенного контрольного остатка R₀(x) при делении принятого кодового многочлена u(x) на порождающий многочлен. Поэтому, если полученный при делении остаток , то принятое кодовое слово считается неискаженным. Если остаток , то принятое кодовое слово стирается и формируется сигнал "ошибка".
Значение контрольного остатка определяется из выражения .

4.6 Способы декодирования с исправлением ошибок и схемная реализация декодирующих устройств

Декодирование циклического кода в режиме исправления ошибок можно осуществлять различными способами. Ниже излагаются два способа, являющиеся наиболее простыми.
В основу первого способа положено использование таблицы синдромов (декодирования), в которой каждому многочлену или образцу ошибок e_i(x), соответствует определенный синдром S_i(x), представляющий остаток от деления принятого кодового слова и соответствующего ему e_i(x) на g(x). Процедура декодирования следующая. Принятое кодовое слово делится на g(x), определяется S_i(x) и соответствующий ему многочлен e_i(x), а затем суммируется с e_i(x). В результате получаем исправленное кодовое слово, т.е. .
В состав декодера входят: вычислитель синдрома (ВС), два регистра сдвига RG1 и RG2, постоянное запоминающее устройство (ПЗУ), котороесодержит слова длины n, соответствующие многочленам ошибок e_i(x).
Принятое кодовое слово поступает на вход вычислителя синдрома, где осуществляется деление его на g(x) и формирование S_i(x), и одновременно - на вход RG2, где накапливается. Синдром S_i(x) используется в качестве адреса, по которому из ПЗУ в регистр RG1 записывается e_i(x), соответствующий синдрому S_i(x). Перечисленные операции завершаются за n тактов. В течение последующих n тактов происходит поэлементное суммирование содержимого RG2 и RG1, т.е. операция , и исправление ошибок.
В основе второго способа исправления ошибок, позволяющего значительно сократить объем используемых табличных синдромов и существенно упростить схему декодера, лежат следующие положения:
1. Синдром S_i(x), соответствующий принятому кодовому слову равен остатку от деления на g(x), а также остатку от деления соответствующего многочлена ошибок ei(x) на g(x), т.е. .
2. Если S_i(x) соответствует и e_i(x), то x( S_i(x) является синдромом, который соответствует и или .
3. При исправлении ошибок используются синдромы образцов ошибок только с ненулевым коэффициентом в старшем разряде.
Поэтому при реализации этого способа множество всех образцов ошибок разбивается на классы эквивалентности. Каждый класс представляет циклический сдвиг одного образца ошибок, а синдром этого класса соответствует образцу ошибок с ненулевым старшим разрядом. Если вычисленный синдром принадлежит одному из классов эквивалентности образцов исправляемых ошибок, то старший символ кодового слова исправляется. Затем принятое слово и синдром циклически сдвигается, а процесс нахождения в предыдущей по старшинству позиции повторяется.
Для исправления ошибок, принадлежащих данному классу эквивалентности, нужно произвести n циклических сдвигов.
Простейшим является декодер Меггитта. В состав декодера входят: вычислитель синдрома, осуществляющий деление кодового слова на g(x) и формирование соответствующего синдрома; блок декодеров (ДК), который настроен на синдромы всех образцов исправляемых ошибок с ненулевыми старшими разрядами; регистр сдвига RG.
При поступлении на вход схемы кодового слова его символы заполняют регистр RG, а в вычислителе формируется соответствующий синдром S_i(x). Вычисленный синдром сравнивается со всеми табличными синдромами, заложенными в схему блока ДК, и в случае совпадения с одним из них на его выходе формируется сигнал, который исправляет ошибочный символ, находящийся в старшем разряде регистра. После этого содержимое вычислителя и RG циклически сдвигается на один шаг. Этот сдвиг реализует операции и . Если новый синдром совпадает с одним из табличных синдромов, то это означает, что произошла ошибка во втором по старшинству символе кодового слова, который, перейдя в старший разряд RG, исправляется. Затем производится новый циклический сдвиг на одну позицию и новая проверка на совпадение синдромов. После повторения этого процесса n раз в RG будет сформировано исправленное кодовое слово. Введение обратной связи для RG не обязательно, так как в процессе исправления ошибок символы кодового слова поступают на выход декодера.
Пример. Рассмотрим схему и работу декодера Меггитта циклического (15,7)-кода, обеспечивающего исправление одиночных и двойных ошибок, с g(x)=x⁸+ x⁷+ x⁶+ x⁴+1 (см. рисунок 8).
Блок декодеров настраивается на 15 синдромов, которые представлены в таблице 5 и соответствуют классам эквивалентности с образцами ошибок в старшем разряде.

Таблица 5

№	е(х)	S(x)	№	е(х)	S(x)
1	x14	x7+ x6+x5+ x3	9	x14+ x6
2	x14+ x13	x7+ x4+x3+ x2	10	x14+ x5	x7+ x6+x3
3	x14+ x12	x7+ x6+x4+ x	11	x14+ x4	x7+ x6+x5+ x4+x3
4	x14+ x11		12	x14+ x3	x7+ x6+x5
5	x14+ x10		13	x14+ x2	x7+ x6+x5+ x3+x2
6	x14+ x9		14	x14+ x1	x7+ x6+x5+ x3+x
7	x14+ x8		15	x14+ x0	x7+ x6+x5+ x3+0
8	x14+ x7

Допустим, что ошибки в 3 и 5 разрядах, т.е. им соответствует многочлен ошибки e(x)=x¹²+x¹⁰.
При поступлении на вход декодера искаженного кодового слова он заполняет регистр и в вычислителе формируется синдром .
Блок декодеров не реагирует на этот синдром.
Затем происходит сдвиг кодового слова в RG, а в BC формируется новый синдром .
Блок декодеров и в этом случае не срабатывает.
При следующем сдвиге кодового слова в RG первый искаженный разряд занимает старшую позицию в RG, а в BC формируется синдром , от которого срабатывает БДК. В результате исправляется первая ошибка.
Следующим сдвиг приводит к формированию синдрома .
Этот синдром соответствует многочлену ошибки e(x)=x¹³+x⁰, т.к. первый искаженный разряд по обратной связи должен занять младшую позицию RG.
На синдром S_(13,0) блок декодеров не реагирует.
При следующем сдвиге кодового слова в RG второй искаженный разряд занимает старшую позицию в RG, а в BC формируется синдром , от которого срабатывает БДК. В результате исправляется вторая ошибка в кодовом слове.

4.7 Коды Рида-Соломона (РС)

Коды РС являются недвоичными циклическими кодами, символы кодовых слов которых берутся из конечного поля GF(q). Здесь q степень некоторого простого числа, например q=2^m.
Допустим, что РС-код построен над GF(8), которое является расширением поля GF(2) по модулю примитивного многочлена f(z)=z³+z+1. В этом случае символы кодовых слов кода будут иметь значения, представленные в таблице 6.

Таблица 6

000	0	0	011	z+1	a3
001	1	a0	110	z2+z	a4
010	z	a1	111	z2+z+1	a5
100	z2	a2	101	z2+1	a6

Кодовые слова РС-кода отображаются в виде многочленов
,
где N - длина кода; V_i - q-ичные коэффициенты (символы кодовых слов), которые могут принимать любое значение из GF(q).
Эти коэффициенты как это следует из таблицы, также отображаются многочленами с двоичными коэффициентами . Коды РС являются максимальными, т.к. при длине кода N и информационной последовательности k они обладают наибольшим кодовым расстоянием d=N-k+1.
Порождающим многочленом g(x) РС-кода является делитель двучлена x^N+1 степени меньшей N с коэффициентами из GF(q) при условии, что элементы этого поля являются корнями g(x). Здесь - примитивный элемент GF(q).
На основе этого определения, а также теоремы Безу, выражение для порождающего многочлена РС-кода будет иметь вид .
Степень g(x) равна d-1=N-k=R.
В РС-кодах принадлежность кодовых слов данному коду определяется выполнением d-1 уравнений в соответствии с выражением (*),
где V_i - символы-коэффициенты из GF(q);
z₀, z₁... z_N-1 - ненулевые элементы GF(q).
Элементы z₀, z₁... z_N-1 называются локаторами, т.е. указывающими на номер позиции символа кодового слова.
Например, указателем i - позиции является локатор zi или элемент aⁱ GF(q).
Так как все локаторы должны быть различны и причем ненулевыми, то их число в GF(q) равно q-1. Следовательно, такое количество символов должно быть в кодовых словах кода.Поэтому обычно длина РС-кода определяется из выражения N=q-1.
Пример. Допустим, что длина РС-кода равна N, кодовое расстояние d=3, то в соответствии с (*) проверочными уравнениями будут

Свойства РС-кодов.
1. Циклический сдвиг кодовых слов, символы которых принимают значение из GF(q), порождает новые кодовые слова этого же кода.
2. Сумма по mod2 двух и более кодовых слов дает кодовое слово, принадлежащее этому же коду.
3. Кодовое расстояние РС-кода определяется не по двоичным элементам, а по q-ичным символам.
4. В РС-коде, исправляющем t_u ошибок порождающий многочлен определяется из выражения . Обычно m₀ принимают равным 1. Однако, с помощью разумного выбора значения m₀, иногда можно упростить схему кодера.
5. Корректирующие способности РС-кода определяются его кодовым расстоянием.

где T₀ и T_u - длина пакетов, в которых обнаруживаются и исправляются ошибки.
Обнаружение ошибок в кодовых словах состоит в проверке условий ((), т.е. определении синдрома , элементы которого определяются из выражения .
Пример. Требуется сформировать кодовое слово РС-кода над GF(2³), соответствующее двоичной информационной последовательности a(1,0)=000000011100101.
Так как m=3, то каждый q-ичный символ кода состоит из трех двоичных элементов. Поэтому с учетом таблицы 6 a(x)=a³x²+ a²x+a⁶.
Определяем параметры кода.
N=q-1=7; k=5; R=2; d=N-k+1=3;
.
Кодовое слово формируется в соответствии с выражением.
,
где .

В результате или в двоичной форме V(1,0)=000.000.011.100.101.101.101.

---

Назад

Содержание

Вперед