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

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

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

.                    (8.1.22)

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

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

.

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

,                    (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.

Циклический код Голея (23, 12). Линейный код Голея (23, 12), описанный в разделе (8.1.2), можно генерировать как циклический код посредством порождающего полинома

.                    (8.1.40)

Кодовые слова имеют минимальное расстояние .

Коды сдвигового регистра максимальной длины. Коды сдвигового регистра максимальной длины – это класс циклических кодов

,                    (8.1.41)

где  - положительное целое. Кодовые слова обычно генерируются посредством -каскадного цифрового регистра сдвига с обратной связью, основанного на проверочном полиноме. Для каждого передаваемого кодового слова  информационных бит вводятся в регистр сдвига, а ключ перемещается с позиции 1 на позицию 2. Содержание регистра сдвигается влево в общей сложности  раз. Такая операция генерирует систематический код с требуемой длиной  . Для примера, кодовые слова, генерируемые 3-каскадным регистром сдвига по рис. 8.1.7, сведены в таблицу 8.1.4.

Рис. 8.1.7. Трёхкаскадный регистр сдвига  с обратной связью

Таблица 8.1.4. Код сдвигового регистра максимальной длины для

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

Рис. 8.1.8. Семь шагов последовательности максимальной длины, генерируемой регистром сдвига с

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

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

.

В заключение заметим, что код регистра сдвига максимальной длины (7,3), показанный в табл. 8.1.4, идентичен коду (7,3), данному в табл. 8.1.3 и является дуальным коду Хемминга (7,4), данному в табл. 8.1.2. Это не совпадение. Коды регистра сдвига максимальной длины являются дуальными кодами для циклических кодов Хемминга .

Таблица 8.1.5. Соединения в сдвиговом регистре для генерирования последовательности максимальной длины

Источник: Forney (1970)

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

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

Двоичные БЧХ коды можно построить с параметрами

где  и  - произвольные положительные целые числа. Этот класс двоичных кодов предоставляет разработчику систем связи большой выбор длин блока и скоростей кода. Недвоичные БЧХ коды включают в себя мощные коды Рида-Соломона, которые будут описаны ниже.

Порождающие полиномы для БЧХ кодов можно конструировать из множителей полинома .

В таблице 8.1.6. приведены коэффициенты порождающих полиномов для БЧХ кодов длины , соответствующие . Коэффициенты даны в восьмеричной форме, причём самая левая цифра соответствует слагаемому полинома с наивысшей степенью.

Таблица  8.1.6. Коэффициенты порождающих полиномов (в восьмеричной форме) для кодов БЧХ длиной

Таблица 8.1.6. (продолжение)

Источник: Stenbit (1964), © 1964 IEEE

Так, коэффициентами полинома для кода (15,5) является 2467, что соответствует двоичной форме 10 100 110 111. Следовательно, порождающий полином равен

.

Более общий список порождающих полиномов для БЧХ кодов дан Питерсоном и Уэлдоном (1972), которые дали таблицы множителей полиномов  для .