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

Циклические коды – подкласс класса линейных кодов, которые удовлетворяют следующим циклическим свойствам: если - кодовое слово циклического кода, тогда , полученное циклическим сдвигом элементов кода , также являются кодовым словом. Все циклические сдвиги образуют кодовые слова. Как следствие циклического свойства, эти коды обладают значительным количеством структурных удобств, которые можно использовать при реализации операций кодирования и декодирования. Большое количество алгоритмов эффективных кодеров и декодеров жёстких решений были сделаны посредством циклических кодов, что сделало возможным в практических системах связи строить блоковые коды большой длины с большим количеством кодовых слов. Описание специфических алгоритмов находится вне кругозора этой книги. Наша основная цель - вкратце описать некоторые характеристик циклических кодов.

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

. (8.1.22)

Для двоичного кода каждый из коэффициентов полинома является или нулем, или единицей. Рассмотрим алгебру циклических кодов. Допустим, необходимо перемножить три многочлена (x³+x²+1)·(x³+x+1)·(x+1). Действия производятся также как в обычной алгебре, только сложение проводится по модулю 2.

При делении операция вычитания заменяется операцией сложения по модулю 2. Например, необходимо разделить многочлен седьмой степени на многочлен третей степени (x⁷+x⁵+x⁴+x+1) / (x³+x²+1)

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

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

Теперь предположим, мы формируем полином

.

Этот полином не может представить кодовое слово, так как его степень может быть равна (если ). Однако если мы разделим на , мы получим

, (8.1.23)

где

.

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

. (8.1.24)

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

, (8.1.25)

где остаточный полином представляет кодовое слово циклического кода, a -частное.

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

. (8.1.26)

Мы также определяем полином информационного сообщения

, (8.1.27)

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

Допустим, что мы обозначим эти кодовые слова так

(8.1.28)

Чтобы показать, что кодовые слова в (8.1.28) удовлетворяют циклическому сдвигу, рассмотрим какое-либо кодовое слово в (8.1.28), Циклический сдвиг дает

(8.1.29)

и, поскольку и и делятся на без остатка, то и делится на без остатка, т.е. можно представить как

.

Следовательно, циклический сдвиг в кодовом слове , генерируемый согласно (8.1.28), порождает другое кодовое слово.

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

Пример 8.1.3. Рассмотрим код с длиной блока . Полином можно разложить на следующие сомножители

. (8.1.30)

Чтобы синтезировать циклический код (7,4), мы можем взять один из двух порождающих полиномов:

или (8.1.31)

.

Коды, генерируемые порождающими полиномами и , квивалентны. Кодовые слова кода (7,4), генерируемые полиномом даны в табл. 8.1.2.

В общем полином можно факторизовать так:

,

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

Таблица 8.1.2. Циклический код (7,4). Порождающий полином

Информационные биты	Кодовые слова
							]

С этой целью можно использовать полином, обратный , определяемый так:

(8.1.32)

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

Пример 8.1.4. Рассмотрим циклический код, дуальный коду (7,4), генерированному в примере 8.1.3. Этот дуальный циклический код (7,3) связан с проверочным полиномом

. (8.1.33)

Обратный полином равен

.

Этот полином генерирует дуальный код (7, 3), данный в таблице 8.1.3. Читатель может убедиться в том, что кодовые слова дуального кода (7, 3) ортогональны кодовым словам циклического кода (7,4) из примера 8.1.3. Заметим, что ни код (7,4), ни код (7,3) не являются систематическими.

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

Таблица 8.1.3. Дуальный код (7, 3). Порождающий полином

Информационные биты	Кодовые слова

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

Пример 8.1.5. Четыре строки порождающей матрицы для циклического кода (7,4) с порождающим полиномом можно получить из полиномов

Легко видеть, что порождающая матрица равна

. (8.1.34)

Аналогично, порождающая матрица для циклического кода (7,4), образуемая порождающим полиномом , равна

. (8.1.35)

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

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

или, что эквивалентно

, (8.1.36)

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

Пример 8.1.6. Для циклического кода (7,4) с порождающим полиномом , ранее рассмотренного в примере 8.1.5, имеем

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

(8.1.37)

и соответствующая проверочная матрица

(8.1.38)

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

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

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

или

, (8.1.39)

где имеет степень меньшую, чем . Ясно, что - это кодовое слово циклического кода. Следовательно, суммируя (по ) с обеими частями (8.1.39), мы получаем желаемый систематический код.

Подытоживая, скажем, что систематический код можно генерировать так:

1. Умножаем полином сообщения на ;

2. Делим на , чтобы получить остаток ; и

3. Добавляем к .

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

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

Пример 8.1.7. Дуальный код для циклического кода (7, 4), порождаемого полиномом - это код (7,3), который порождается обратным полиномом . Однако, мы можем также использовать для получения порождающей матрицы для дуального кода. Матрица, соответствующая полиному равна

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

Таким образом,

Читатель может убедиться, что .

Заметив, что вектор , состоит из всех семи двоичных вектор-столбцов длины 3, исключая вектор из одних нулей. Но это как раз описание проверочной матрицы для кода Хемминга (7, 4). Следовательно, циклический код (7, 4) эквивалентен коду Хемминга (7, 4), рассмотренному ранее в примерах 8.1.1 и 8.1.2.

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

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

Деление полинома степени на полином

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

Рис. 8.1.2. Регистр сдвига с обратной связью для деления полинома на

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

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

Рис. 8.1.3. Циклический кодер с использованием порождающего полинома

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

Пример 8.1.8. Регистр сдвига для кодирования циклическим кодом (7,4) с порождающим полиномом показан на рис. 8.1.4.

Рис. 8.1.4. Циклический кодер (7,4) с использованием порождающего полинома

Предположим, что сообщением является цепочка 0110. Содержание сдвигового регистра дано таблицей:

Таким, образом, три проверочных символа: 100. Они соответствуют кодовым символам

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

.

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

Рис. 8.1.5. Циклический кодер с использованием проверочного полинома

Пример 8.1.9. Проверочный полином для циклического кода (7,4), генерируемый порождающим полиномом , равен . Кодер для этого кода, основанный на проверочном полиноме, иллюстрируется на рис. 8.1.6. Если на входе кодера действует сообщение 0110, то проверочными символами являются , как легко проверить.

Рис. 8.1.6. Циклический кодер (7,4) с использованием проверочного полинома

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

Циклические коды Хемминга. Класс циклических кодов включает коды Хемминга, которые имеют длину блока и проверочных символов, где - любое положительное целое число. Циклические коды Хемминга эквивалентны кодам Хемминга, описанным в разделе 8.1.2.