Методическое пособие 640

А(Х) = а0 + a1 ·X + а2 ·X2 + ... + ak·Xk ,

на фиксированный полином, в частности, порождающий:

G(X) = go + g1 ·X + g2 ·X2 + ... + gr ·Xr.

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

Рис. 7.14 Умножение полиномов на базе ЛПС

7.16. БЧХ-коды

Среди циклических кодов широкое применение нашли коды Боуза—Чоудхури—Хоквингема (БЧХ). Можно показать, что для любых целых положительных чисел т и t < n/2 существует двоичный код БЧХ длины п = 2 m – 1 с кодовым расстоянием d 2t +1 причем число проверочных символов – k mt.

Данные коды строятся на основе расширенного поля GF(2m). Причем обобщение теории БЧХ–кодов на случай p –ичного алфавита осуществляется достаточно легко. Основная идея построения БЧХ–кодов определяется следующей теоремой.

Теорема (БЧХ теорема). Пусть порождающий полином g(z) имеет в расширенном поле GF(2m) корни , 2, , s,

где – примитивный элемент поля GF(2m). Тогда цикличе-

231

ский код с порождающим полиномом g(z) обладает минимальным расстоянием d , не меньшим s 1.

Доказательство данной теоремы основывается на свойстве определителя специфической матрицы, формулируемом

имеет отличный от нуля определитель, если и только если все элементы 1, 2, , s различны.

На основании БЧХ-теоремы опишем общий алгоритм построения БЧХ–кодов. Для значения m , обеспечивающего не-

обходимую длину кода n 2m 1, из таблиц выбирается примитивный полином степени m и строится расширенное поле

GF(2m). Затем в построенном поле выбирается последова-

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

g(z), то корнями будут и все сопряженные с по степени два

элементы 2, 4, , которые вместе с тем являются и корнями соответствующего минимального многочлена, так что g(z) имеет в качестве сомножителя полином вида

g1(z) (z )(z 2) (z 2l 1 1 ),

где l1 – длина 2–сопряженной последовательности (цикла) с элементом , которая вследствие примитивности равна l1 m. Следующим элементом, претендующим на роль корня

232

g(z), является 2, который уже учтен в сомножителе g1(z), поскольку сопряжен с по степени 2.

Если s 2, то следующим корнем порождающего поли-

нома будет 3, а также все 2–сопряженные с ним элементы

2

( 3)2, ( 3)2 , , которые являются корнями минимального

для 3 полинома

g3(z) (z 3)(z ( 3)2) (z ( 3)2l 3 1 ),

где l3 – длина цикла 2–сопряженных с 3 элементов. Данная операция построения порождающего полинома g(z) продол-

жается до полного исчерпывания множества , 2, , s , т.е. до тех пор, пока каждый из них не войдет число корней какогонибудь минимального многочлена. В итоге, порождающий полином g(z) определяется как произведение всех получаемых минимальных многочленов

g(z) g1(z) g3(z) .

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

служит тот факт, что он делит бином zn 1, где n 2m 1. Действительно, полином g(z) представляет собой произведение некоторых биномов вида (z ) с различными ненулевы-

ми элементами GF(2m), тогда как многочлен zn 1 есть произведение подобных биномов со всеми ненулевыми элементами поля.

Следует отметить, что построенный таким образом цик-

лический код может исправлять более t d 1 s ошибок. В 2 2

связи с чем, величина

d* 2t 1 s 1

233

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

Пример. Построим порождающий полином g(z) БЧХ–

кода длины n 23 1 7, исправляющий любую однократную ошибку. Расширенное поле GF(23), необходимое для нахождения g(z). Требование исправления кодом любых однократных ошибок влечет за собой, что s 2t 2, а значит, корнями порождающего многочлена должны быть элементы и 2.

Минимальный многочлен, отвечающий элементу , имеет вид

g1(z) (z )(z 2)(z 4) (z3 ( 2 4)z2

( 2 4 2 4)z 2 4,

где

2 4 7 1,

2 4 2 2 0,

2 4 2 4 3 5 6 1 2 1 2 1 1,

поэтому g1(z) z3 z 1. Элемент 2, являющийся корнем

g(z), уже учтен в g1(z), так что g(z) g1(z) z3 z 1. Поскольку deg(g(z)) 3, то число информационных сим-

волов k , содержащихся в каждом слове, будет k 4, и значит, результатом построения является циклическая версия (7,4) кода Хэмминга, исправляющего любую однократную ошибку.

В настоящее время разработчику нет необходимости осуществлять весь объем работы по отысканию БЧХ–кода, поскольку подобные исследования уже выполнены много лет назад, результатом чего явились детальные таблицы, содержащие готовые к использованию порождающие полиномы БЧХ– кодов. Для кодов БЧХ умеренной длины и ФМ при передаче символов можно добиться значительного выигрыша (4 дБ и бо-

234

лее). Он достигается при скоростях 1/3 k/n 3/4. При очень высоких и очень низких скоростях выигрыш от кодирования существенно уменьшается.

Тогда, общее число последовательностей из сопряженных по степени 2 элементов, которые должны входить в число корней минимальных полиномов, не больше, чем s/2 t , а поскольку длина любой последовательности не превосходит m , то БЧХ–код характеризуется следующими параметрами

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

7.17. Мажоритарное декодирование

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

носятся коды, допускающие мажоритарное декодирование.

Оно основано на возможности для некоторых циклических кодов выразить каждый информационный символ с помощью Q различных линейных соотношений. Решение о значении символа принимается по мажоритарному принципу. Для исправления всех ошибок до кратности t включительно необходимо иметь 2t + 1 независимых соотношений. Их реализация сравнительно проста.

Схема декодера (рис. 7.15) состоит из сдвигающего регистра, сумматоров по mod 2 и мажоритарного элемента М. Простота ее обусловлена тем, что в данном случае каждый символ кодовой комбинации участвует в одном проверочном соотношении. Код, для которого выполняется это условие, называется кодом с разделенными проверками.

235

Рис. 7.15 Структурная схема декодера циклического мажоритарного кода (7,3)

Мажоритарное декодирование возможно и тогда, когда один и тот же символ участвует в нескольких проверочных соотношениях. Однако при этом алгоритм декодирования усложняется.

7.18. Коды Рида–Соломона

Если при построении, согласно БЧХ-теореме, порождающего полинома g(z) игнорировать сопряженные по степени 2

циклы элементов , 2, , s и составлять его как произведе-

ние только биномов вида z i,i 1,2, , s, то получающийся полином окажется недвоичным. Вследствие этого и код, порождаемый им, также окажется недвоичным, поскольку символы кода будут принадлежать расширенному полю

GF(q),q 2m . В то же время использование 2–сопряженных циклов объясняется только необходимостью перевода g(z) во множество двоичных полиномов и не имеет никакого отношения к достижению предсказанного кодового расстояния. Дру-

гими словами, q–ичный (q 2m ) код с порождающим полиномом вида

236

s

g(z) (z i),

i 1

называемый кодом Рида–Соломона, или просто РС–кодом,

полностью удовлетворяет условиям БЧХ-теоремы, и поэтому

ных) символов, а поскольку степень порождающего полинома в точности равна s, то число информационных символов (не двоичных, а q–ичных) k n s , и значит, d n k 1. С другой стороны, согласно границе Синглтона (7.20) d n k 1, откуда следует точное равенство между кодовым расстоянием d и n k 1, следовательно РС–коды характеризуются следующими параметрами

n 2m 1, d n k 1,

причем на величину k накладывается единственное ограничение: увеличение k на единицу приводит к уменьшению d на ту же величину.

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

Очевидно, что любой q–ичный (q 2m ) символ может быть представлен в виде двоичного блока размерности m . Тогда, придерживаясь указанной замены всех символов произвольного РС–кода, получим двоичный код длины

ное преобразование не приводит к увеличению кодового расстояния, поскольку двоичный код, как и ранее, имеет d n k 1 (nb kb)/m 1, и среди двоичных кодов подобный код не считается хорошим с точки зрения исправления

237

случайных ошибок. Вместе с тем он вполне эффективен в борьбе с т.н. «пакетами ошибок»: если подобный пакет изме-

нит t (d 1)/2 последовательных 2m –ичных символа, то он повредит в m раз большее число двоичных. Однако благодаря своей исправляющей способности РС–код может исправить любую ошибку кратности до t включительно, а значит, его двоичный эквивалент способен исправлять любой пакет ошибок длиной до mt двоичных символов.

Пример. Найдем порождающий многочлен РС–кода дли-

ны n q 1 24 1 15, исправляющего все ошибки кратности

до трех включительно. Расширенное поле GF(24), необходимое для нахождения g(z), построено на основе полинома

f (x) x4 x 1. Требование исправления кодом любых трехкратных ошибок влечет за собой, что s 2t 6, а значит, порождающий полином может быть записан в виде

6

g(z) (z i),

i 1

где – примитивный элемент поля GF(24). Тогда

g(z) (z )(z 2)(z 3)(z 4)(z 5)(z 6)

(z2 ( 2)z 3)(z2 ( 3 4)z 7) (z2 ( 5 6)z 11)

(z2 5z 3)(z2 7z 7)(z2 9z 11)

(z4 ( 7 5)z3 ( 7 12 3)z2

( 12 10)z 10)(z2 9z 11)

(z4 13z3 6z2 3z 10)(z2 9z 11)

z6 ( 9 13)z5 ( 11 7 6)z4

( 9 3 15)z3 ( 2 12 10)z2 ( 14 4)z 6

238

z6 10z5 14z4 4z3 6z2 9z 6.

Таким образом, построенный g(z) порождает (15,9) РС–код. Задавая код в не систематическом виде, произвольный

кодовый многочлен может быть записан как u(z) a(z)g(z),

u(z) a(z)g(z) z14 10z13` 14z12 4z11 6z10 9z9 6z8

Данному кодовому многочлену отвечает вектор

U (0,0,0,0,0,0,0,0, 6, 9, 6, 4, 14, 10,1),

компоненты которого представляют собой 4–х разрядные двоичные числа

0 (0000),1 (0001), 10 (0111), 14 (1001), 4 (0011),

6 (1100), 9 (1010).

7.19. Сверточные коды

Наряду с блоковыми кодами, существует большой и эффективный класс древовидных или решетчатых кодов, среди которых особый интерес представляют сверточные коды. Отличительной чертой последних (в сравнении с блоковыми) служит способ отображения потока информационных символов (бит) в кодовые. При блоковом кодировании последовательность не пересекающихся k –символьных информационных блоков заменяется последовательностью не пересекающихся n–символьных кодовых слов, причем каждое кодовое слово «защищает» только свой k –символьный информационный блок и занимает в реальном времени интервал, отводимый для передачи именно этих k –символов.

При сверточном (древовидном, в общем случае) кодировании используется отличный от предыдущего метод отобра-

239

жения информационных данных в кодовые символы. Суть метода может быть наглядно пояснена на примере использования «скользящего окна» шириной m информационных символов. Указанное окно вырезает в потоке данных m –символьный информационный блок, который отображается в n–символьную кодовую группу, передаваемую в течение интервала, равного одному информационному символу, и называемую иногда кадром кодовых символов. Затем окно сдвигается на один информационный символ вправо и обновленный m –символьный информационный блок отображается в следующую n– символьную кодовую группу и т.д. Теперь вместо последовательности индивидуальных кодовых слов, отвечающих не пересекающимся во времени блокам данных, имеет место последовательный поток кодовых символов, в котором каждая группа из n кодовых символов отвечает за защиту не только текущего символа данных, но и m 1 предшествующих. Иллюстрацией описанного выше алгоритма служит рис. 7.16, на котором изображено формирование сверточного кода с m 4 и n 2.

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

m

Информ. символы

Кодовые символы

n n n

Рис.7.16. Формирование сверточного кода

Как правило, эти соединения описываются порождающи-

240