5.6. ОБОБЩЕННЫЕ ТЕОРЕМЫ МАК-ВИЛЬЯМС ДЛЯ ЛИНЕЙНЫХ КОДОВ

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

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

Определение. Назовем композицией вектора и обозначим через -вектор где равно числу компонент равных Ясно, что

Пусть линейный -код над GF(q) и пусть число кодовых слов , имеющих композицию Тогда полная весовая функция кода определяется как многочлен

Например, пусть — троичный [4, 2, 3]-код из гл. 1. Его полная весовая функция равна

Характеры поля GF(q). Для формулировки теоремы нам необходимо ввести понятие характеров поля GF(q). Вспомним из гл. 4, что любой элемент поля GF(q) может быть представлен в виде или, что эквивалентно, в виде -вектора где примитивный элемент целые числа, причем —1.

Обозначим через комплексное число которое является примитивным корнем степени из единицы, т. е. и в то же время 1 для значений

Определение. Для любого элемента определим как комплексно-значное отображение элементов поля задаваемое формулой

где

Отображение называется характером поля GF(q). Упражнения. (24). Показать, что для всех выполняется равенство

(25). Показать, что равенство

справедливо для всех Таким образом, характер представляет собой гомоморфизм аддитивной группы поля GF(q) в мультипликативную группу комплексных чисел, модуль которых равен 1.

(26). Показать, что Для всех

Таким образом, множество всех характеров образует группу, которая изоморфна аддитивной группе поля GF(q).

Пример. Пусть поля имеется три характера:

Лемма 9. Для любого ненулевого элемента выполняется равенство

Доказательство. Ясно, что

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

Пример. В поле при эта лемма утверждает, что

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

В случае, когда простое число, это отображение выглядит совсем просто где

Теорема Мак-Вильямс для полных весовых функций. Теорема 10. Если — линейный -код над GF(q) с полной весовой функцией то полная весовая функция дуального к нему кода определяется следующей формулой:

Пример. Для кода над эта теорема утверждает, что

где

Другими словами, многочлен получается применением линейного преобразования

к многочлену и делением результата на число Так, например, для кода приведенного выше, имеем:

Упражнение. (27). Показать, что является самодуальным кодом. Проверить это, доказав, что

Доказательство теоремы опирается на следующую лемму.

Лемма И. Для векторов пусть Так же как и в лемме 2, для отображения определенного на зададим его преобразование Адамара

Тогда, если представляет собой произвольный -код над то

Доказательство этой леммы в сущности ничем не отличается от доказательства леммы 2, но надо лишь воспользоваться леммой 9.

Доказательство теоремы 10. Положим Точно так же, как равенство (5.11) было выведено из (5.9), получим, что

Применяя теперь к лемму 11, получаем, что выражение (5.45) дает утверждение теоремы.

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

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

Назовем композицией Ли вектора и обозначим через вектор где для

Например, для значения композиция Ли классифицирует кодовые слова в зависимости от того, сколько компонент слова равно 0, сколько равно ±1 и сколько равно ±2.

Весовая функция Ли кода определяется как многочлен

Так, например, самодуальный код длины 2 над состоящий из кодовых слов имеет весовую функцию Ли

Теорема Мак-Вильямс для весовых функций Ли. Теорема 12. Весовая функция Ли дуального кода получается из весовой функции Ли кода заменой каждой переменной на выражение

и последующим делением результата на 11.

Доказательство. В теореме 10 положим для

Для кода из предыдущего примера получаем, что где и преобразование теоремы 12 заключается в замене

Так как код самодуален, то теорема утверждает, что справедливо тождество

Упражнение. (28). Проверить это тождество непосредственно.

Весовая функция Хэмминга. Пусть теперь степень любого простого числа. Как и в § 1.3, весом Хэмминга (или просто весом) вектора назовем число ненулевых компонент и обозначим это число через Мы будем использовать обозначения § 5.2, пусть число кодовых слов веса и многочлен

является весовой функцией Хэмминга кода

Теорема Мак-Вильямс для весовых функций Хэмминга.

Теорема 13.

Доказательство. В теореме 10 положим и воспользуемся леммой 9.

Пример. Для кода из рассматриваемого нами примера весовая функция Хэмминга и теорема утверждает, что справедливо тождество

Для случая теорема 13 превращается в теорему 1.

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

Таким образом, вектор и однозначно определяется многочленом Для такого способа описания требуется переменных (Это аналогично тому, что мы делали в § 5.3 для двоичных кодов.)

Назовем точной весовой функцией кода многочлен

Теорема Мак-Вильямс для точных весовых функций. Теорема 14. Точная весовая функция дуального кода получается из функции заменой каждой переменной на выражение

и последующим делением результата на

Доказательство. Достаточно применить лемму 11 к отображению определяемому (5.48).

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

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

Для векторов введем следующие обозначения:

Ясно, что

Определим совместную весовую функцию кодов как многочлен

Совместная весовая функция кода с самим собой называется бивесовой функцией кода

Упражнения. Установить следующие свойства совместных весовых функций.

Весовые функции отдельных кодов задаются выражениями:

Кроме того, справедливо равенство

(30). Если -код с повторением длины то

Если , а код произволен, то

Если код произволен, а код состоит из всех вектор длины то

Если код произволен, а представляет собой код из всех слов четного веса, то

(33). Показать, что для симплексного -кода, являющегося дуальным к коду Хэмминга, при справедлива формула

(34). Показать, что для -кода Хэмминга при справедлива формула

где символ а с нижними индексами обозначает различные симметрические функции от

(35). Показать, что для -кода Рида — Маллера первого порядка при справедливо равенство

(36). Чтобы подчеркнуть, что бивесовая функция дает больше информации о коде, чем обычная весовая функция, показать, что

коды, порожденные словами имеют одинаковые весовые, но различные бивесовые функции. Другую такую пару кодов составляют [32, 16, 8]-код Рида-Маллера второго порядка и квадратично-вычетный код с теми же параметрами (см. гл. 19).

Разделенная весовая функция. Во многих кодах векторы естественным образом разделены на левую и правую половину. К таким кодам относятся, например, коды, образованные конструкцией типа (см. § 2.9), коды Рида-Маллера и коды, полученные из них (см. гл. 13 и 15). Для таких кодов полезно следить за весами обеих половин раздельно.

Для вектора назовем величины левым и правым весом соответственно. Введем для -кода разделенную весовую функцию как многочлен

Упражнения. (37). Пусть и коды длины с весовыми функциями и разделенными весовыми функциями Показать, что код, являющийся их прямой суммой,

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

Тогда разделенные весовые функции кодов

равны соответственно и

(38). Доказать, что

(39). Выписать разделенную весовую функцию для кодов Рида-Маллера первого порядка.

(40). Пусть — линейный код длины предположим, что первые символов каждого кодового слова посылаются по двоичному симметричному каналу с вероятностью ошибки , а

последние символов — по такому же каналу с вероятностью Пусть

где минимум берется по всем ненулевым словам и из кода

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

(Если разделенная весовая функция кода известна, то число может быть легко найдено.)