13.3. ЦИКЛИЧЕСКИЕ КОДЫ

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

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

Пример. Двоичный вектор может быть представлен в виде полинома следующим образом:

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

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

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

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

Пример. Найти сумму многочленов

Найти произведение многочленов

Выполнить деление многочленов

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

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

Примеры неприводимых многочленов:

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

где остаток от деления

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

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

Представим вектор в виде полинома

Тогда

В результате деления полинома на полином получаем остаток . Поэтому

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

где — транспонированная единичная йатрица формата — матрица проверочных разрядов, образованная остатком от деления

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

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

Для нахождения строк проверочных разрядов матрицы вычислим и запишем в виде полинома каждый вектор единичной матрицы

Длина вектора циклического кода поэтому

(см. скан)

В результате получаем порождающую матрицу С:

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

Таблица 13.5

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

Код представлен в табл. 13.5.

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

Пример, Циклический код задан своей порождающей матрицей

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

Характеристики (в смысле обнаружения ошибок) полученного кода такие же, как и циклического кода, представленного порождающей матрицей

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

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

Рекомендации для построения кода следующие:

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

2. Оптимальное число проверочных разрядов циклического кода определяется по специальным таблицам [4].

3. По справочникам находятся все неприводимые полиномы степени

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

где — полином информационного вектора порождающей матрицы; — одночлен степени — остаток от деления

5. Построенная порождающая матрица проверяется на выполнение следующих условий:

а) вес в смысле Хэмминга любого вектора порождающей матрицы должен удовлетворять соотношению где — минимальное расстояние, в смысле Хэмминга рассматриваемого циклического кода;

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

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

Построим циклический код мощностью 16 и корректирующей с по собностью

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

Для определяем значение по

3» По справочникам находим все неприводимые полиномы степени Таких полиномов два:

4. Выбираем в качестве образующего полином Заготовка порождающей матрицы циклического кода имеет вид

Каждый информационный вектор из матрицы представляем полиномом

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

Так как длина вектора циклического кода (см. формат порождающей матрицы то

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

Таблица 13.6

В результате получена порождающая матрица С? циклического кода

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

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

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

1. Принятый кодовый вектор разделить на образующий полином.

2. Подсчитать число единиц в полученном остатке.

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

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

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

Код имеет в 3, т. е. корректирует ошибки кратности Пусть вместо вектора 0001101 принят вектор 0011101. Для исправления ошибки осуществляем следующие действия. Принятый вектор записываем в виде полинома: затем делим на

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

Осуществляем деление на

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

Осуществляем деление на

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

Остаток содержит одну единицу, что равно корректирующей способности кода. Осуществляем суммирование вектора 110100) о последним остатком; и сдвигаем циклически полученный вектор на три разряда вправо. Имеем . В результате получен правильный вектор 0001101 циклического кода.

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

и образующим полиномом .

Тогда матрица ошибок М имеет вид

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

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

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

Из общего количества 35 трехкратных ошибок не обнаруживается всего лишь 7 ошибок, Аналогично, четырехкратных необнаруживаемых ошибок будет также Наконец, рассматриваемым циклическим кодом не обнаруживается единственная семикратная ошибка Таким образом, число всех возможных необнаруживаемых ошибок — 15.

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

и уравнениями

очевидно имеет матрицу ошибок

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

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

Рис. 13.2

Рис. 13.3

Рис. 13.4