ГЛАВА 10

МНОГОМЕРНЫЕ СПЕКТРАЛЬНЫЕ МЕТОДЫ

Подобно тому как было введено одномерное преобразование Фурье над конечным полем, можно определить многомерное преобразование Фурье над конечным полем. Оно представляет собой преобразование, определяемое на многомерных таблицах данных, и полезно во многих отношениях. Многомерные спектральные методы дают возможность построить новые коды, которые допускают более эффективные схемы декодирования или обладают новыми свойствами. Многомерные спектральные методы являются также полезным инструментом исследования структуры циклических кодов, в частности кодов БЧХ. Многомерные коды тесно связаны с современными методами теории обработки дискретных сигналов, основанными на китайских теоремах об остатках. Наилучшими известными многомерными кодами являются коды-произведения, и наше изложение мы начнем с описания этих кодов.

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

10.1. КОДЫ-ПРОИЗВЕДЕНИЯ

Если длина линейного кода п = пп, то компоненты кодового слова можно расположить в виде (п х П2)-таблицы. В некоторых случаях такая таблица, элементы которой мы обозначим через Сц-или Ccf, является более удобной, так как позволяет при описании и обработке рассматривать строки и столбцы по отдельности. В этом случае код называется многомерным кодом. Размерность кода как векторного пространства, конечно, остается равной числу k ин-

326 гл. 10 МНОГОМЕРНЫЕ СПЕКТРАЛЬНЫЕ МЕТОДЫ

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

Начнем с простейшего случая многомерных кодов - с кодов-произведений.

Определение 10.1.1. Кодом-произведением W = Wy X 2 двух кодов 1 и 2 называется код, словами которого являются все двумерные таблицы со строками, являющимися словами кода Wy, и столбцами, являющимися словами кода

Систематическое представление кода W получается из систематических представлений кодов ё и соответственно первые ki и 2 символов которых являются информационными символами. Слово такого кода приведено на рис. 10.1, где виден и способ кодирования: сначала кодом Wy кодируется каждая из первых 2 строк таблицы, а затем кодом 2 кодируются все столбцы таблицы. Легко проверить, что то же слово можно получить, кодируя сначала первые /г1»столбцов, а потом все строки. Для последовательной передачи по каналу кодовое слово разбивается на части, например считывается по строкам или по столбцам.

Слово кода-произведения может быть записано в виде многочлена от двух переменных. А именно если компоненты кодового слова обозначить Сц-, t = О, т - 1, t == О, «2-1, то имеем следующее представление:

«1-1 «2-1

С(Х, у)= I S CilXУ.

i=0 i=0

Группируя слагаемые, это выражение можно переписать любым из двух способов:

«1-1 /«2-1 \

С{Х, у)= I 1 ClCУ 1=0 \i=0

«3-1 /«,-1

С{Х, У) Т, £ Cci.X i=0\ 1=0

Согласно определению кода-произведения, в первом выражении заключенная в скобки сумма (для каждого i) является словом кода 2. а во втором выражении заключенная в скобки сумма (для каждого i) является словом кода ёу.

Коды-сомножители Wy и 2 могут быть циклическими, однако это не означает, что код-произведение W также является циклическим. В § 10.2 будут выписаны достаточные для. цикличности условия.

Рис. 10.1. Структура кодового слова систематического (пп, ккУкот.

Теорема 10.1.2. Если минимальные расстояния кодов и Ш равны dj и d*2 соответственно, то минимальное расстояние кода равно d\d%.

Доказательство. Код является линейным, и кодовое слово минимального веса в каждом ненулевом столбце содержит не менее d\ ненулевых символов, а число ненулевых столбцов в таком слове равно по меньшей мере d\, так что минимальный вес равен по меньшей мере d\d%. Кроме того, существует хотя бы одно такое слово. □

Из этой теоремы следует, что если составляющие коды могут исправлять ti и ошибок соответственно, то код-произведение может исправлять tt + + 2 ошибок.

Если на рис. 10.1 положить - равным нулю и считывать кодовое слово по столбцам, то получим перемежение слов строчного («1, /Ji)-KOfla. Таким образом, код-произведение является обобщением кода-перемежения. Он подобен коду-перемежению, но некоторые его строки содержат только проверки. Отсюда становится ясным, что код-произведение можно использовать как код, исправляющий пакеты ошибок. Он позволяет исправлять пакеты ошибок длины пф-, если строчный код исправляет пакеты длины fcj. При считывании слов того же самого кода-произведения по строкам он исправляет пакеты ошибок длины пф если столбцовый код исправляет пакеты длины Ъ,. При надлежащем выборе правила линейного считывания слов кода-произведения этот код можно использовать для исправления пакетов ошибок длины max («12. «2&i)- Мы видели, что этот же код может исправлять {d\d\ - 1)/2 случайных ошибок. Следующая теорема утверждает, что такой код можно использовать для одновременного исправления и случайных ошибок, и их пакетов.

Теорема 10.1.3. Ни один смежный класс кода, построенного как произведение линейного (пь ki, dVj-кода и линейного {по,.