14. ЦИКЛИЧЕСКИЕ КОДЫ
Среди линейных кодов особо важную роль играют так называемые циклические коды. По ряду причин они являются наиболее ценным достоянием теории кодирования. Во-первых, они допускают еще более компактное описание, чем произвольные линейные коды. Во-вторых, имеющиеся для линейных кодов алгоритмы кодирования и декодирования могут быть в применении к циклическим:;одйм значительно упрощены; более того, для циклических кодов существуют свои особые методы декодирования, не- приложимые к другим линейным кодам. Наконец, по своей структуре эти коды идеально приспособлены к реализации в современных технических устройствах.
Простые в реализации, они, однако, не столь просты в теории. Для полного разъяснения большинства вопросов, связанных с построением и методами декодирования циклических кодов, требуется довольно сложный алгебраический аппарат. Поэтому наше предстоящее знакомство с циклическими кодами будет далеко не полным.
Начнем с понятия циклического сдвига вектора. Пусть
задан произвольный гс-мерный вектор а—(а0, а±, а2 ап
с координатами из любого поля I (нумерацию координат в случае циклических кодов удобно начинать с нуля). Циклическим сдвигом этого вектора назовем вектор а' = — (ап-1> «о, а», «г, . . . , оп_2). Например, для вектора (01101) последовательными циклическими сдвигами являются такие вектора:
Циклическим кодом называется линейный код, который вместе с любым своим вектором содержит также и его циклический сдвиг. Иными словами, циклический код обладает следующим свойством: циклический сдвиг любого кодового вектора снова является кодовым вектором.
При рассмотрении циклических кодов кроме обычных действий над векторами мы имеем дело фактически еще с одной операцией, сопоставляющей каждому вектору его циклический сдвиг. Удобным алгебраическим средством для ее описания являются многочлены. С каждым вектором а= «=(ао, аи .. . , ап-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) и их обобщение — каскадные коды. Строящиеся, как правило, на базе кодов БЧХ, они в значительной степени сохраняют их достоинства, но одновременно избавлены от упомянутого выше дефекта.