Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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). Порождающий полином

Информационные биты

Кодовые слова

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

1

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

1

0

0

1

0

1

1

0

0

1

0

]

1

1

0

0

1

1

1

0

1

0

0

0

1

1

1

0

0

0

1

1

0

1

0

0

0

1

0

0

1

1

1

0

0

1

0

1

1

0

1

0

1

1

1

0

0

1

0

1

0

1

1

1

1

1

1

1

1

1

1

1

0

0

1

0

1

1

1

0

0

1

1

0

1

1

0

1

0

0

0

1

1

1

1

0

1

0

0

0

1

1

0

1

1

1

1

1

0

0

1

0

1

1

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

        (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). Порождающий полином

Информационные биты

Кодовые слова

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

1

1

0

1

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

0

1

0

1

1

0

0

1

0

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

0

1

0

1

1

1

0

1

1

0

1

0

1

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

Пример 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. Содержание сдвигового регистра дано таблицей:

Вход

Шаг сдвига

Содержимое регистра

 

0

0 0 0

0

1

0 0 0

1

2

1 1 0

1

3

1 0 1

0

4

1 0 0

Таким, образом, три проверочных символа: 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. Код сдвигового регистра максимальной длины для

Информационные биты

Кодовые слова

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

0

1

0

0

1

1

1

1

0

0

0

1

1

0

0

1

1

0

Заметим, что, за исключением кодовых слов из одних нулей, все кодовые слова, генерируемые регистром сдвига, представляют собой циклические сдвиги единственного кодового слова. Это легко увидеть из диаграммы состояний регистра сдвига, которая иллюстрируется на рис. 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. Соединения в сдвиговом регистре для генерирования последовательности максимальной длины

№№ отводов к сумматору по модулю 2

№№ отводов к сумматору по модулю 2

№ № отводов к сумматору по модулю 2

№№  отводов к сумматору по модулю 2

2

3

4

5

б

7

8

9

10

1,2

1,3

1,4

1,4

1,6

1,7

1, 5, 6, 7

1,6

1,8

11

12

13

14

15

16

17

18

19

1, 10

1, 7, 9, 10

1, 10, 11, 13

1, 5, 9, 14

1, 15

1,5, 14, 16

1, 15

1, 12

1, 15, 18, 19

20

21

22

23

24

25

26

27

28

1, 18

1, 20

1, 22

1, 19

1, 18, 23, 24

1, 23

1, 21, 25, 26

1, 23, 26, 27

1, 26

29

30

31

32

33

34

1, 28

1, 8, 29, 30

1, 29

1, 11,31,32

1, 21

1, 8,33,34

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

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

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

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

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

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

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

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

7

15

 

 

31

 

 

 

 

63

 

 

 

 

 

 

 

 

 

 

127

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

255

4

11

7

5

26

21

16

11

6

57

51

45

39

36

30

24

18

16

10

7

120

113

106

99

92

85

78

71

64

57

50

43

36

29

22

15

8

247

239

231

223

215

207

199

191

1

1

2

3

1

2

3

5

7

1

2

3

4

5

6

7

10

11

13

15

1

2

3

4

5

6

7

9

10

11

13

14

15

21

23

27

31

1

2

3

4

5

6

7

8

13

23

721

2467

45

3551

107657

5423325

313365047

103

12471

1701317

166623567

1033500423

157464165547

17323260404441

1363026512351725

6331141367235453

472622305527250155

5231045543503271737

211

41567

11554743

3447023271

624730022327

130704476322273

26230002166130115

6255010713253127753

1206534025570773100045

335265252505705053517721

54446512523314012421501421

17721772213651227521220574343

314607466652207504476457472173 5

403114461367670603667530141176155

123376070404722522435445626637647043

220570424456045547705230137622176043 53

70472640527510306514762242715677331330217

435

267543

156720665

75626641375

23157564726421

16176560567636227

7633031270420722341

2663470176115333714567

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

255

187

179

171

163

155

147

139

131

123

115

107

99

91

 

87

 

79

 

71

 

63

 

55

 

47

 

45

 

37

 

29

 

21

 

13

 

9

9

10

11

12

13

14

15

18

19

21

22

23

25

 

26

 

27

 

29

 

30

 

31

 

42

 

43

 

45

 

47

 

55

 

59

 

63

52755313540001322236351

22634710717340432416300455

1541621421234235607706163067

7500415510075602551574724514601

3757513005407665015722506464677633

1642130173537165525304165305441011711

461401732060175561570722730247453567445

215713331471510151261250277442142024165471

120614052242066003717210326516141226272506267

60526665572100247263636404600276352556313472737

22205772322066256312417300235347420176574750154441

106566672534731742227414162015743322524110764323 03431

675026503032744417272363172473251107555076272072434

    4561

110136763414743236435231634307172046206722545273311

    721317

667000356376575000202703442073661746210153267117665

    41342355

240247105206443215155541721123311632054442503625576

    43221706035

107544750551635443253152173577070036661117264552676

    13656702543301

731542520350110013301527530603205432541432675501055

    7044426035473617

253354201706264656303304137740623317512333414544604

    5005066024552543173

152020560552341611311013463764237015636700244707623

    73033202157025051541

513633025506700741417744724543753042073570617432343

    2347644354737403044003

302571553667307146552706401236137711534224232420117

    4114060254757410403565037

125621525706033265600177315360761210322734140565307

    4542521153121614466513473725

464173200505256454442657371425006600433067744547656

    140317467721357026134460500547

157260252174724632010310432553551346141623672120440

    74545112766115547705561677516057

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

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

.

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

 



<< ПредыдущаяОглавлениеСледующая >>