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

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

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

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

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

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

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

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

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

Слово кода-произведения может быть записано в виде многочлена от двух переменных. А именно если компоненты кодового слова обозначить то имеем следующее представление:

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

или

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

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

Рис. 10.1. Структура кодового слова систематического -кода.

Теорема 10.1.2. Если минимальные расстояния кодов и равны соответственно, то минимальное расстояние кода равно

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

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

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

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

-кода, не содержит одновременно слова веса не Больше при и слова, представляющего собой пакет ошибок длины не больше при

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

Код-произведение можно использовать в соответствии с доказанной теоремой. Декодер для такого кода можно строить в виде составного декодера, содержащего декодер для исправления пакетов ошибок и декодер для исправления случайных ошибок, каждый из которых исправляет требуемое число ошибок и обнаруживает неисправляемые конфигурации ошибок. При этом либо оба декодера укажут одну и ту же конфигурацию ошибок, либо успешно декодирует только один из них; в последнем случае второй декодер укажет неисправляемую конфигурацию ошибок. Иногда декодер для исправления случайных ошибок может указать все пакеты ошибок. В § 10.3 будет описап декодер для произведения двух кодов БЧХ, исправляющий все случайные ошибки в пределах конструктивного расстояния.