Рис. 10.4. Спектры некоторых кодов над QF (8). а - произведение циклических кодов; б - произведение кодов Рида-Соломона; в - дуальный код-произведение; г - произведение (7, 4)-кодов БЧХ.

пусть Р И Y - элементы поля GF (q") порядков Пу и п.2 соответственно; тогда

П,-1 Пг-I г=0 /=0

Используя одномерное обратное преобразование, очевидно, снова получаем

Vw = (1/n,) (1/П2) "l S -y-Vir. /=0 /-=0

Для при.мера выберем в качестве проверочных частот двумерного кода все элементы некоторых вертикальных и горизонтальных полос, как показано на рис. 10.4, а. Кодовыми словами являются все временные функции, в спектре которых в этих частотах стоят нули, т. е. для всех проверочных частот (/, /)

п,-I п,-1

S S р/у-/с,,, = о.

«=0 t=0

to.4. МНОГОМЕРНЫЕ СПЕКТРЫ 341

Это позволяет по-иному интерпретировать определение двумерного кода, задавая его как множество многочленов от двух переменных

л,-1 «5 - 1

С=0 i=0

удовлетворяющих равенствам

с (р, уП = О

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

с (р, у) = 0 и с{х, у) = о

для каждой проверочной частоты / и /. Это показывает, что {{сц-)] является кодом-произведением.

Если полосы проверочных частот идут подряд, то получится произведение двух кодов Рида-Соломона. На рис. 10.4, б приведено спектральное задание (49, 25, 9)-кода над GF (8). Каждый из 25 информационных символов принимает одно из восьми возможных значений. Для формирования кодового слова надо перевести результирующую таблицу во временную область при помощи преобразования Фурье.

Аналогичную процедуру можно использовать и для построения кода над GF (2), выбирая только двоичные кодовые слова. Для этого надо в частотной области определить спектр так, чтобы он задавал только двоичное кодовое слово. Двумерные ограничения сопряженности задаются равенствами

Cjj = C(2j mod n) (2/ mod «)•

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

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

Рис. 10.5. Множества сопряженных элементов для двумерного случая.

строке, попадают в различные подмножества сопряженных элементов. Построенный (49, 16, 9)-код мало привлекателен. Как следует из самого построения, в силу ограничений сопряженности коды-произведения часто обладают плохими характеристиками. Для построения хороших кодов-произведений надо выбирать взаимно простые длины. Но тогда основное поле становится боль-ШИ.М, и обычно дело завершается выбором циклического кода, корни порождающего многочлена которого лежат в этом большом поле.

Второй случай, иллюстрируемый 10.4, в, называется дуальным кодом-произведением. Это код, дуальный к коду-произведению. Дуальный код-произведение мало пригоден для исправления независимых ошибок, так как его минимальное расстояние невелико. Как будет показано в § 10.7, он хорош для исправления кратных низкоплотностиых пакетов ошибок. Код задается выбором прямоугольника самых старших проверочных частот высотой а и шириной Ь. Легко видеть, что минимальное расстояние этого кода удовлетворяет неравенству

d I + min {а, Ь). В качестве примера укажем (49, 45, 3)-код над GF (8). Ограничением этого кода на двоичное подполе является (49, 39, d 3)-код.

10.5. БЫСТРЫЕ КОДЫ БЧХ

Как мы видели в гл. 9, кодер и декодер для кодов БЧХ обычно содержат два преобразования Фурье. В следующей главе будет показано, что в случае составного п использование алгоритмов быстрого преобразования Фурье (БПФ) позволяет существенно уменьшить объем вычислений. Но БПФ-алгоритм Кули-Тьюки