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

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

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

Начнем с понятия циклического сдвига вектора. Пусть

задан произвольный гс-мерный вектор а—(а0, а±, а2         ап

с координатами из любого поля I (нумерацию коорди­нат в случае циклических кодов удобно начинать с нуля). Циклическим сдвигом этого вектора назовем вектор а' = — (ап-1> «о, а», «г, . . . , оп_2). Например, для вектора (01101) последовательными циклическими сдвигами являют­ся такие вектора:

 

 

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

 

(1)

При рассмотрении циклических кодов кроме обычных действий над векторами мы имеем дело фактически еще с од­ной операцией, сопоставляющей каждому вектору его цик­лический сдвиг. Удобным алгебраическим средством для ее описания являются многочлены. С каждым вектором а= «=(ао, аи .. . , ап-1) свяжем многочлен а (х)=а0 ЬарН-. .

коэффициенты которого совпадают с соответствует

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

 

 

Менее тривиальным примером циклического кода (проверка предоставляется читателю) является код, эквивалентный (7,4)-коду Хемминга, с проверочной матрицействующими координатами вектора. В дальнейшем будем отождествлять вектор а с соответствующим ему многочле­ном а(х), свободно переходя от векторной записи к записи в виде многочлена. Циклическому сдвигу а'=(ап_и «о, 0.1, . . . , ап_2) вектора «соответствует тогда многочлен а'(х)= = о„_1+о0х+о1л:2+. . .+ап_2хп~1. Сравним многочлены а (а) и а'(х). Если сумму первых п—1 слагаемых а(х) умножить на х, мы получим сумму последних п—1 слагаемых много­члена а'(х\. Вопбгпе. нетоупно заметить, что

 

 

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

 

 

а все меньшие степени, 1, х, х2, ... , х"-1, являются различ­ными элементами. При этом правило умножения степеней х следующее:

 

 

 

 

С учетом (3) равенство (2) дает:

 

 

 

 

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

 

Из равенств (3) и (4) вытекает следующее правило умно­жения любых двух многочленов от х степени ^ п — I. Если

 

 

и

 

 

— два таких многочлена, то чтобы найти их произведение, сначала обычным образом раскрываем скобки, умножая степени хк и хт по правилу (4), а коэффициенты ак и Ът — по правилу умножения в поле Р, после чего приводим по­добные члены

 

и

 

 

 

П р и м е п 1. Пусть

двоичные многочлены. Тогда

 

Пример 2. Пусть п=4, а(х)=1+2х+х2. и Ь{х)=* — 2+х+х3 — многочлены над полем 7,3. Имеем:

а (х)Ь (х)=(1+2х+х2)(2+х+х3)^

=2+2-2х+2х2+х+2х?+х3+х3+2хх3+х2х:>=

=2+х+2х*+х+2я*+2х*+2+х= 1 +х*+2х3.

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

Линейный код V является циклическим тогда и только тогда, когда V является идеалом в кольце Рп.

В самом деле, если V — идеал, то для всякого кодового вектора (многочлена) а(х) € V имеем ха(х) ^ V, т.е. цикличес­кий сдвиг снова является кодовым вектором.

Обратно, если V — циклический код, то для всякого кодо­вого вектора а(х) его последовательные циклические сдви­ги ха(х), х2а(х), ..., хп~1а(х) также являются кодовыми век­торами.

 

произведение Ь(х)а(х) является кодовым вектором. Мы имеем:

 

Остается показать, что для всякого многочлена

Согласно сказанному выше, каждое слагаемое в (5) принад­лежит кодовому пространству, но тогда и вся сумма обла­дает этим свойством. Итак, V— идеал.

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

Во всяком идеале V кольца Рп сушрствует фиксирован­ный многочлен ц(х), которому кратен всякий многочлен идеа­ла V.

Иными словами, любой многочлен а(х) 6 V можно пред­ставить в виде произведения фиксированного многочлена

 

 

 

 

и некоторого подходящего многочлена

 

 

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

 

 

Это можно сделать по обычным правилам деления много­члена на многочлен; степень остатка г(х) будет меньше сте­пени делителя §(х). Первое слагаемое в правой части (7) принадлежит V (в силу определения идеала). Поскольку и многочлен а(х) принадлежит V, то остаток г(х), равный раз­ности

 

 

двух элементов из V, также должен принадлежать идеалу. Если предположить, что г(х) — ненулевой многочлен, то приходим к противоречию: многочлен г(х), принадлежа­щий идеалу, имеет степень, меньшую степени ц(х). Следо­вательно, г(х)—0 и выполняется равенство (6).

Многочлен §(х) называется порождающим многочленом идеала V (или соответствующего циклического кода).

Таким образом, если известен порождающий много­член кода, то тем самым известны и все кодовые многочле­ны — их список исчерпывается всевозможными произведе­ниями §(х)$(х), где &(х) — произвольный многочлен степе­ни, меньшей п.

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

 

— многочлен степени т и к=п—т. Рассмотрим следующие многочлены:

 

Все они являются кодовыми, степень их очевидно не пре- посходит п—1. Нетрудно убедиться, что рассматриваемые

По порождающему многочлену легко найти порождаю­щую матрицу циклического кода. Пусть как векторы, они образуют линейно независимую систему, и всякий кодовый вектор является их линейной комбина­цией. Следовательно, матрица С, составленная из векторов (8), является порождающей матрицей циклического кода. Порядок ее равен кХп и она имеет следующий вид:

 

В качестве примера рассмотрим двоичный циклический код длины 7 с порождающим многочленом @(х)=1-\-хг.~\-х3= = (1011000). Так как

 

 

 

 

то порождающей будет следующая матрица:

 

 

 

Нетрудно убедиться, что данный циклический код эквива­лентен коду Хемминга с проверочной матрицей

 

 

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

 

Для любых значений т и

 

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

1. В теории циклических кодов многочлены удобно трактовать не только как элементы кольца Р п, но и как элементы кольца многочленов Р [X] с обычной операцией умножения многочленов. Ус­ловимся в последнем случае вместо обозначения о (ас) пользоваться обо­значением а(Х). Необходимость различать эти обозначения видна хотя бы из такого примера: если в кольце Рп имеет место хп—1=0, то в коль­це ЛX] многочлен X"—I, разумеется, не является нулевым элементом.

Для циклических кодов существенно следующее свойство порожда­ющего многочлена в(х):

Если в качестве @(х) выбран многочлен наименьшей степени, при­надлежащий идеалу V, то многочлен    является делителе,ч многочлена X"—I.

Для доказательства разделим Хп—I на в (X) с остатком. Получаем:

 

 

где степень г (л) меньше степени § (л)..Ь кольце г„ равенство (Ш) при­обретает вид:

 

 

откуда заключаем, что г(х) должен принадлежать идеалу V, в то время как его степень меньше, чем степень §(*)■ Следовательно, г (х)=0, но тогда и г(Х)=0, т. е.

 

 

Многочлен И (X), удовлетворяющий равенству (11), называется проверочным многочленом.

 

Пусть

2. Воспользуемся определением проверочного многочлена для по­строения проверочной матрицы циклического кода.

проверочный многочлен кода. Из (11) сле­

дует, что если т — степень многочлена в(х), то Н (х) имеет степень п—т, т. е. к=п—т. В силу (11) имеем также, что в кольце Рп проверочный и порождающий многочлены связаны равенством

 

 

 

Рассмотрим матрицу Н порядка тХп, имеющую следующий вид:

 

 

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

порожденный проверочным

Докажем, что матрица Н является проверочной.

 

Действительно, пусть произвольный кодовый многочлен. Рассмотрим идеал и согласно (12)

многочленом п (х) и возьмем произвольный многочлен:

 

из этого идеала. Тогда

 

С другой стороны, умножая многочлены а(х) и Ь(х) по правилам умно­жения в Рп (см. равенства (4)), получаем:

 

 

Так как многочлен а(х)Ъ(х) нулевой, то и все его коэффициенты равны нулю, в частности

 

 

Это равенство означает, что всякий кодовый вектор ортогонален вектору (Ьп-1, . . ., Ь0), который получается из произвольного многочлена I (х) ^ V , если его коэффициенты записать в обратном порядке. Таким образом, в силу построения матрицы (13), каждая ее строка ортого­нальна любому кодовому вектору и, стало быть, эта матрица является проверочной.

 

найти порождающие и проверочные матрицы всех двоичных циклических колов длины 9 и длины 15.

произвольный многочлен

Пусть

 

степени к. Многочлен

называют двойственным

3. Вернемся снова к примеру циклического (7,4)-кода с порождаю­щим многочленом §(дс)=1+*2Ч-*3. Как было доказано, многочлен §(Х)=1-|-.Х2+Х3 является делителем многочлена X7—1. Легко прове­сить. что

 

 

 

Следовательно, для псоессочного многочлена к (х) имеем:

 

 

Поэтому проверочной будет следующая матрица:

 

 

 

4. Исходя из равенств

 

 

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

ЙЯПНГЯНЯ Р ВИПР*

 

где Н* (х) — многочлен, двойственный к проверочному многочлену П (х).

Убедиться, что код, дуальный к циклическому (см. § 11, допол­нение 11), также является циклическим. Как связаны между собой порождающие и проверочные многочлены двух дуальных кодов?

Пусть (х) — многочлен, двойственный к многочлену [> (х). Показать, что

а)         коды, порожденные многочленами §(х) и §*(*), эквивалентны;

б)         если для кода с порождающим многочленом 4' (х) выполняется условие §(*)=&* (х), то кодовое подпространство такого кода вместе с каждым вектором *»= (о0, а1, . . ., о„_содержит также и вектор

 

 

8. Среди циклических кодов особую практическую важность имеет один специальный класс кодов, предложенных американскими матема- ижами Боузом, Чоудхури и Хоквингемом. Эти коды так и называются кодами БЧХ — по начальным буквам фамилий этих математиков. Тео­рия кодов БЧХ выходит за рамки настоящей книги, и мы только объяс­ним в нескольких словах, каким образом они определяются. Для этого нам потребуются некоторые дополнительные сведения из теории полей.

Будем говорить, что подмножество Р является подполем поля Р, если Р есть поле относительно операций на Р. Справедлива такая тео­рема:

Для любого конечного поля Р можно указать конечное поле Р, удов­летворяющее следующим условиям:

Р есть подполе поля Р;

Р содержит п корней уравнения X"—1=0;

не существует поля, обладающего свойствами 1 и 2 и имеющего меньше элементов, чем Р.

Пусть теперь для поля Р указано_поле Р со свойствами 1) — 3). Пусть а — примитивный элемент поля Р, а числа 5 и / таковы, что эле­мент о^ имеет порядок п и 5+/<<?, где д — число элементов поля Р. Циклический код называется кодом БЧХ (с параметрами п, I), если он состоит из всех многочленов степени <п—1 с коэффициентами из Р, среди корней которых содержатся все элементы

 

 

Можно доказать, что кодовое расстояние такого кода не меньше 1+2. Следовательно, варьируя параметры п, 5, I, мы имеем возможность получать коды БЧХ с любым расстоянием, а значит, исправляющие лю­бое заданное число ошибок. Это обстоятельство счастливо дополняется тем, что для указанных кодов разработаны удобные алгоритмы декодиро­вания, основанные на вычислениях в конечных полях'и легко реализуе­мые автоматическими электронными устройствами.

9- До сих пор мы говорили о кодовом расстоянии кода и макси­мальном числе I исправляемых ошибок как об основных показателях корректирующей способности кода. Однако ясно, что более весомым показателем является величина а,п, показывающая^ какова доля числа ошибочных символов от общего числа символов принятого слова, при которой возможно еще правильное декодирование (исправление оши­бок). С другой стороны, отношение к/п (к—число информационных символов) характеризует избыточность кода" чем меньше это отношение, тем, очевидно, больше избыточность.И аот здесь коды БЧХ обнаруживают некоторый изъян. Окззк- с ается, при заданной корректирующей способности, т, е. заданной величине коды БЧХ большой длины имеют слишком высокую из­быточность. Более того: если отношение 11п фиксировано, а п-^со, то

к/п-+ 0.

Стремление исправить этот недостаток привело к появлению таких кодовых конструкций, как коды-произведения (см. дополнение 12 к §11) и их обобщение — каскадные коды. Строящиеся, как правило, на базе кодов БЧХ, они в значительной степени сохраняют их досто­инства, но одновременно избавлены от упомянутого выше дефекта.