4.5. Полиномиальные коды

4.5.1. Обобщенные коды Рида — Маллера

Как следует из теоремы 4.4 и утверждения 4.10, код можно задать, указав множество многочленов, удовлетворяющих определенным условиям, и сопоставив далее каждому многочлену вектор, компонентами которого являются значения получающиеся при подстановке в многочлен определенных значений переменной. Впервые этот способ использовал Митани [33] для изучения кодов Рида — Маллера [34].

Обозначим через множество всех многочленов степени и меньше от переменных принимающих значения в поле Так как для любой переменной X, принимающей значения в то любой одночлен из с коэффициентом 1 имеет следующий вид:

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

Лемма 4.6. Сумма равна если равна 0 во всех остальных случаях.

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

Отсюда следует справедливость леммы.

Пусть один из примитивных элементов Тогда

где Для простоты значение многочлена будем обозначать через а значение через Положим

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

Лемма 4.7. Пусть

Множество называется -ичным обобщенным кодом Рида — Маллера длины порядка (или сокращенно ОРМ-кодом) [3, 4, 34, 35]. Очевидно, что этот код является линейным. Расширение ОРМ-кода назовем р-ОРМ-кодом. Как следует из леммы это множество В случае называется кодом Рида — Маллера, а ОРМ-код — укороченным циклическим кодом Рида—Маллера. В случае ОРМ-код совпадает с кодом Рида-Соломона (см. утверждение 4.10). Исследуем основные свойства ОРМ-кодов и р-ОРМ-кодов.

Утверждение 4.11. Число информационных символов р-ОРМ-кода порядка и ОРМ-кода порядка равно общему

числу совокупностей целых чисел удовлетворяющих следующим условиям:

В частности, при

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

Утверждение 4.12. .

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

Полагая получим, что это число равно числу совокупностей целых чисел удовлетворяющих условиям

Следовательно, равно общему числу всех совокупностей для которых

Теорема 4.5. Код, двойственный р-ОРМ-коду порядка является р-ОРМ-кодом порядка

Доказательство. Если то по определению

Поскольку степень не превышает то, как следует из леммы 4.7, вышеприведенное выражение равно 0. Это означает, что р-ОРМ-код порядка является подкодом кода, двойственного р-ОРМ-коду порядка Из утверждения 4.12 в свою очередь следует, что этот подкод совпадает с двойственным кодом.

Определим вес целого числа -ичное разложение которого имеет вид

по формуле

Теорема 4.6. ОРМ-код порядка является циклическим кодом, множеством корней порождающего многочлена которого является множество

Доказательство. Пусть произвольное целое число, такое, что и пусть выражение (4.35) — его -ичное разложение. Как следует из утверждения 4.11, имеется чисел удовлетворяющих указанным выше условиям появляется из-за того, что число исключается). Учитывая, что из утверждения 4.12 находим, что количество равно Следовательно, циклический код С длины с порождающим многочленом имеет то же число проверочных символов, что и ОРМ-код порядка Таким образом, для завершения доказательства теоремы достаточно показать, что ОРМ-код порядка является подкодом кода С. Рассмотрим следующий многочлен от переменных

Так как

Степень не превышает следовательно, не больше Из формулы (4.34) имеем

Отсюда следует, что Если произвольный вектор из

Так как степень меньше то, согласно лемме 4.7, сумма в правой части последнего равенства равна 0. Отсюда и из формулы (3.24) следует, что Таким образом, ОРМ-код порядка является подкодом кода С, так что они совпадают.

Теорема 4.7. Пусть Тогда ОРМ-код порядка имеет минимальное расстояние

и является подкодом БЧХ-кода с конструктивным расстоянием БЧХ-кода с

Доказательство. Так как порождающий многочлен ОРМ-кода порядка имеет среди своих корней элементы Это означает, что ОРМ-код порядка является подкодом БЧХ-кода с конструктивным расстоянием Из нижней БЧХ-границы получаем

Пусть один из примитивных элементов Положим

Так как то необходимым условием того, что является выполнение равенств Поскольку число совокупностей значений для которых равно Учитывая, что в число этих совокупностей входит и получаем, что вес равен Таким образом, в формуле (4.36) в действительности имеет место знак равенства.

Пусть подмножество Для каждого определим величину положив если если положим если если Офи. Вектор называется характеристическим вектором подмножества U (вектор получающийся из удалением первой компоненты, называется укороченным характеристическим вектором).

Теорема 4.8. Пусть аффинное подпространство над пространства размерности Укороченный характеристический вектор и характеристический вектор подпространства являются кодовыми векторами соответственно ОРМ-кода и р-ОРМ-кода порядка

Доказательство. Из разд. 2.6.3 следует существование строк длины с компонентами из элементов поля таких, что

где Положим

Тогда выражение равно 0, если и равно 1 во всех остальных случаях, так что Тогда, очевидно,

Утверждение 4.13. Четный подкод укороченного циклического кода Рида — Маллера 1-го порядка является кодом максимальной длины. Укороченный циклический код Рида — Маллера порядка представляет собой код Хэмминга.

Это утверждение непосредственно следует из теоремы 4.6.

Утверждение 4.14. Минимальное расстояние -ичного БЧХ-кода длины с конструктивным расстоянием (где совпадает с конструктивным расстоянием.

Краткое доказательство. Справедливость данного утверждения непосредственно следует из доказательства теоремы 4.7.

Выше были описаны ОРМ-коды длины но могут быть построены и ОРМ-коды длины где произвольный делитель

Утверждение 4.15. Пусть Тогда вектор получается -кратным повторением первых своих компонент.

Краткое доказательство. Так как то Из формулы (4.34) для произвольных и получаем

Так как то Следовательно,

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

Утверждение 4.16. ОРМ-код длины порядка является циклическим кодом, множеством корней порождающего многочлена которого является множество

Краткое доказательство. Утверждения 4.11 и 4.12 можно легко обобщить. Тогда, если заметить, что для любых многочленов

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

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

Утверждение 4.17. Теорема 4.7 остается справедливой, если длину кода заменить на на на

Идея доказательства. Воспользоваться утверждением 4.16, положить и далее воспользоваться нижней БЧХ-границей.

Рассмотрим частный случай, когда При этом Для любого множество

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

Ниже точки будем представлять с помощью соответствующих элементов а. Пусть проективное подпространство размерности проективного пространства Для каждого определим величину следующим образом: если если а Назовем вектор характеристическим вектором

Утверждение 4.18. Пусть проективное подпространство размерности проективного пространства Характеристический вектор подпространства является кодовым вектором ОРМ-кода длины порядка

Краткое доказательство. Согласно определению проективного подпространства размерности существует такое подпространство размерности что . В свою очередь в существуют такие вектор-строк размерности с компонентами из что (см. разд. 2.6.3)

где Положим

Тогда совпадает с характеристическим вектором подпространства