9. Циклические AN-коды

9.1. Структура циклических AN-кодов

9.1.1. Определение циклического AN-кода

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

Например, рассмотрим AN-код с Кодовыми числами этого кода являются 0, 9, 18, 27, 36, 45, 54, которым соответствуют кодовые слова 000000, 001001,010010,011011, 100100, 101101, 110110. Это множество кодовых слов является замкнутым относительно циклических сдвигов, и, следовательно, рассматриваемый AN-код является циклическим.

Циклические -коды впервые исследовал Мандельбаум [1]. После этого они были предметом большого числа публикаций других авторов. В этом разделе рассматриваются основные свойства этих кодов.

9.1.2. Кольцо целых чисел по модулю 2^e-1 и его идеалы

Если целые числа 2 и В взаимно просты, т. е. и показатель 2 по модулю В равен то, как следует из изложенного в разд. 8.1.7,

Следовательно, при подходящем выборе целого числа

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

Используя равенство (9.2), легко показать, что это подмножество, состоящее из В целых чисел и включающее 0, является идеалом. Обозначим этот идеал через а число назовем его порождающим элементом.

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

Теорема 9.1. Циклический сдвиг двоичного представления произвольного целого числа идеала I, т. е. кодового слова, также принадлежит идеалу Другими словами, идеал I замкнут относительно циклических сдвигов.

Доказательство. Так как то двоичное представление произвольного числа входящего в имеет не более разрядов. Пусть

Вновь пользуясь тем, что получаем

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

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

9.1.3. Задание циклических кодов

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

докажем следующие сравнения:

а кроме того, укажем простой способ определения коэффициентов двоичного представления числа Обращаясь к разд. 8.1.11 и равенству (9.2), имеем

Так как то длина двоичного представления не превосходит Полагая

из формулы (9.3) получаем

Следовательно, при любом целом имеет место следующее равенство:

где являются соответственно целой и дробной частями числа Отсюда в свою очередь следует, что

и

Переходя к сравнению по модулю 2, получаем

или (поскольку

Так как то следовательно, Так как при этом то Кроме того, Таким образом,

т.е. если В — нечетное число, и если — четное число.

Например, при получаем двоичное представление А, приведенное в табл. 9.1.

Таблица 9.1 (см. скан) Двоичное представление А при

Действительно, -разрядным двоичным представлением является 000100111011. Путем деления двоичных чисел можно проверить, что

Произвольное ненулевое кодовое слово этого -кода может быть получено путем циклического сдвига

9.1.4. Разложение и структура циклических AN-кодов

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

В результате циклических сдвигов кодового числа получаются кодовые слова

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

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

Далее представим кодовые слова, получающиеся в результате циклических сдвигов А а, в виде

Следовательно, если а выбрать так, что всем ненулевым кодовым словам будут соответствовать ненулевые вычеты по модулю В.

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

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

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

который к тому же совпадает с Таким образом, если В— простое число и 2— примитивный корень В, то может быть построен строго циклический -код.

Однако если В не является простым, то существует вычет а по модулю В, не являющийся взаимно простым с В. Предположим, что Тогда, поскольку то В этом случае множество кодовых слов, соответствующих вычетам по модулю В, получающимся умножением на вычетов по модулю взаимно простых с образует подкод. Обозначим этот подкод через входит кодовых слов. Если показатель 2 по модулю равен к, а именно если то каждый простой код в содержит кодовых слов. Само собой разумеется, что является делителем Следовательно, состоит из простых кодов. Здесь следует заметить, что равно -кратному повторению подкода соответствующего вычетам из

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

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

Если разложению подкода на простые коды соответствует разложение мультипликативной группы на смежные классы по ее подгруппе, то разложение циклического AN-кода на подкоды является одним из применений равенства (8.12):

Это равенство дает суммарное число кодовых слов В (включая кодовое слово 0, соответствующее случаю Разложение на подкоды соответствует разложению целого числа, на слагаемые. Остановимся на этом несколько более подробно.

(кликните для просмотра скана)

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

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

Подкоды можно классифицировать следующим образом: подкод порядка, — подкоды 1-го порядка, подкоды 2-го порядка, подкод 1-го порядка. Подкоды порядка, представляют собой коды где произведение тсомножителей из разложения всего существует подкодов порядка. В частности, подкод 1-го порядка состоит только из одного нулевого кодового слова. Такая структура называется «пучковой» конструкцией. Пучковая конструкция подкодов в случае показана на фиг. 9.2.

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

Пример 9.1. Рассмотрим случай При этом Как следует из изложенного в рассматриваемый код имеет длину и содержит 105 кодовых чисел. Поскольку В является составным числом, у кода существует несколько подкодов. Подкод порядка приведен в табл. 9.2. Кодовые слова, приведенные в этой таблице, были вычислены с помощью формулы (9.7) или (9.9). Каждый простой код является строго циклическим, и все его кодовые слова могут быть получены путем циклических сдвигов кодового слова, помещенного в соответствующей графе формулы. Каждый простой код содержит 12 кодовых слов; всего в содержится кодовых слов.

Существуют три подкода 1-го порядка: эти подкоды приведены в табл. 9.3.

Существуют три подкода 2-го порядка: эти подкоды приведены в табл. 9.4.

В подкоды порядка входят кодовые слова, соответствующие ненулевым вычетам по модулю В, которые не являются взаимно простыми с всего имеется таких кодовых слов. Эти подкоды эквивалентны подкодам, соответствующим вычетам, которые

(кликните для просмотра скана)

(см. скан)

Таблица 9.4 (см. скан) Подходы 2-го порядка

принадлежат Например, подкод эквивалентен подкоду кодовые слова которого соответствуют вычетам, принадлежащим Как видно из табл. 9.5, подкод состоит из двух простых подкодов

Таблица 9.5 (см. скан)

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

Таблица 9.6. (см. скан) Построение повторением