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

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

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

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

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

кодовых слов образует линейное подпространство пространства -мерных последовательностей над

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

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

Проверочная матрица соответствующая систематическому линейному коду, должна быть некоторой модификацией матрицы, представленной на рис. 6.1.3, поскольку при переходе от (6.1.9) к (6.1.10) получаем

Поэтому, матрица принимает такой вид, как это представлено на рис. 6.5.1, и для всех кодовых слов выполняется соотношение

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

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

Если кодовое слово циклического кода (т. е. его коэффициенты являются буквами кодового слова), то вычет по модулю также является кодовым словом. Чтобы убедиться в этом, рассмотрим

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

Рис. 6 5.1. Проверочная матрица систематического группового кода в

Рис. 6.5 2. Порождающая матрица циклического кода

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

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

Теперь покажем, что должен быть делителем многочлена Так как нормированный многочлен степени то

получаем

Поскольку то многочлен получается циклическим сдвигом кодового слова и имеет в качестве делителя. Тогда из соотношения (6.5.11) следует, что является делителем

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

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

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

Теорема 6.5.1. Любой циклический код над информационными символами и с длиной блока N порождается нормированным многочленом над степени Этот многочлен является делителем Обратно, любой нормированный многочлен над степени который делит порождает циклический код с информационными символами и длиной блока

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

Если умножить любое кодовое слово на то получим

Так как степень не превышает то из рассмотрения

(6.5.14) следует, что должен иметь нулевые слагаемые при Произведя умножение получим

Из (6.5.13) следует, что нормированный многочлен и что Поэтому можно переписать (6.5.15) в виде

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

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

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

Рис. 6.5.3. Проверочная матрица циклического кода.

Первоначально информационные символы хранятся в разрядах регистра сдвига, как это представлено на рис. 6.5.4. Содержимое в каждом разряде подается на выход разряда (т. е. на линию, выходящую из правой части разряда) и умножается на соответствующее эти произведения суммируются и умножаются на —1, что дает в итоге как это следует из (6.5.16). Затем регистр сдвига сдвигается на одну позицию вправо, символ поступает в канал, а символ подается в левый разряд регистра. После этого сдвига на выходе умножителя на -появляется символ После N сдвигов в канал будет передан а кодер будет подготовлен к поступлению в него следующей информационной последовательности.

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

Рис. 6.5.4. L-разрядный кодер циклического кода.

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

Рис. 6.5.5. -разрядный кодер циклического кода.

Информационные символы в кодовом слове могут быть представлены в виде многочлена Согласно алгоритму Евклида,

где степень не превышает

Из (6.5.17) следует, что является кодовым словом, а многочлен, соответствующий проверочным символам. Любое устройство, совершающее деление на позволяет найти такое устройство представлено на рис. 6.5.5.

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

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

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