15.5. Ортогонализируемые коды, основанные на конечных геометриях

Относительная простота некоторых пороговых декодеров послужила стимулом к поиску кодов, ортогонализируемых в малое число шагов. Этот поиск привел к открытию нескольких важных классов ортогонализируемых кодов, включающих квазициклические коды Таунсенда — Велдона [1967], евклидово-геометрические коды и проективно-геометрические коды.

Впервые некоторые проективно-геометрические коды исследовал в конце 1950 г. Прейндж. Им были получены многие результаты о распределении весов кодовых слов и лидеров смежных классов для некоторых двоичных кодов, основанные на использовании проективных геометрий, а также подстановок, отросительно которых эти коды инвариантны. К сожалению, эти работы Прейнджа не были опубликованы. В 1966 г. Велдон ввел в рассмотрение разностные коды, являющиеся подклассом проективно-геометрических кодов. Более общие классы кодов, основанные на конечных геометриях, были предложены Рудольфом [1964, 1967]. Дальнейшие результаты в этой области были получены Чоу [1967], Гёталсом и Делзартом [1968], Грэхемом и Мак-Вильямс [1966], Мак-Вильямс и Манном [1968], Смитом [1967, 1969] и Велдоном [1968 а, b].

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

15.51. Определения. Евклидово-геометрическим кодом (ЕТ-кодом) над порядка длины называется код, дуальный к подкоду над подполем ОРМ-кода над порядка

15.52. Теорема. Минимальное расстояние ЕГ-кода порядка не меньше Этот код ортогонализируем за шаг.

Доказательство. Согласно теоремам 11.61 и 15.329, характеристическая функция каждого -мерного подпространства из над является кодовым словом ОРМ-кода порядка Так как все координаты таких кодовых слов равны 0 или 1, то эти слова также принадлежат подкоду ОРМ-кода над подполем Следовательно, ЕГ-код порядка удовлетворяет проверочному соотношению на каждом -мерном аффинном подпространстве.

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

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

15.53. Определение. Пусть а — примитивный элемент поля циклический код над корни порождающего многочлена которого имеют вид где сумма цифр в -ичном разложении числа х. Тогда р-ичным проективно-геометрическим кодом (ПГ-кодсш) порядка с блоковой длиной называется код, дуальный к подкоду кода V над подполем

15.54. Теорема. Минимальное расстояние -ичного ИГ-кода порядка равно по меньшей мере где Этот код ортогонализируем в шагов.

Доказательство. Пусть пусть примитивный элемент поля Тогда у — примитивный корень степени из единицы. Каждый ненулевой элемент поля может быть однозначно записан в виде для некоторых Так как у — примитивный элемент поля то каждое -мерное линейное подпространство в над имеет вид где А — некоторое подмножество множества Если то Проекцией множества называется множество элементов поля. Множество называется -мерным проективным подпространством пространства над если оно является проекцией -мерного линейного подпространства в над . В частности, если то есть -мерное проективное подпространство. Множество является -мерным проективным подпространством.

Так как пересечение двух линейных подпространств — линейное подпространство, то пересечение проективных подпространств — также проективное подпространство. Так как любое -мерное линейное подпространство содержится в различных -мерных линейных подпространствах, то и любое -мерное проективное подпространство содержится в различных -мерных проективных подпространствах.

Декодер для ПГ-кода вычисляет проверки для символов, соответствующих любому -мерному проективному подпространству. Если полученное слово содержит не более ошибочных символов, то декодер может определить проверки над любым -мерным проективным подпространством. Они соответствуют различным -мерным проективным подпространствам, пересекающимся только по этому -мерному подпространству. После этого принимается пороговое решение по известным различным проверкам. Полагая и используя индукцию по и лемму 15.541, отсюда получим доказательство теоремы 15.54. а

15.541. Лемма. Любой -ичный ПГ-код порядка с блоковой длиной удовлетворяет проверочному уравнению на каждом -мерном проективном подпространстве из над

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

подпространстве пространства над и пусть есть -мерное линейное подпространство в над проекцией которого является Пусть - характеристическая функция Р:

Аналогично пусть характеристическая функция с исключенной точкой 0):

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

Если то получаем

Мы показали, что для характеристической функции -мерного проективного подпространства из над выполняется равенство если следовательно, кодовое слово кода, дуального к ПГ-коду порядка

15.55. Пример. Рассмотрим двоичный ПГ-код порядка с блоковой длиной 21, для которого Пусть примитивный элемент поля а — корень примитивного кубического многочлена над Минимальный многочлен элемента а над равен -Минимальный многочлен элемента равен минимальный многочлен для равен . Числами вида , для которых являются (по основанию 4) и их циклические сдвиги. Двоичная система записи дает

и их двукратные сдвиги. Таким образом, для двоичного ПГ-кода порядка (1,2) имеем Каждый ненулевой элемент поля может быть записан в виде где Для получаем

Множество элементов вида где образует двумерное линейное подпространство пространства над Проекция этого подпространства является одномерным проективным подпространством характеристическая функция которого задается равенством Так как многочлен кратен то код удовлетворяет проверочному уравнению на одномерном проективном пространстве

Применимость процедуры порогового декодирования к и ПГ-кодам определяется только тем, что эти коды удовлетворяют проверочным уравнениям на всех аффинных или проективных подпространствах данной размерности. Известны и другие коды, также удовлетворяющие проверочным уравнениям на всех аффинных или проективных подпространствах, однако, как показали Делзарт, Гёталс и Мак-Вильямс [1968], любой такой код — подкод либо ЕГ-кода, либо ПГ-кода, определенных согласно 15.51 и 15.53.

Исторически характеристическая функция проективного пространства раньше чаще обозначалась через а не через Этот многочлен обладает рядом интересных свойств, что показывает следующая теорема:

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

сумма различных ненулевых степеней х.

Доказательство.

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

Следствие. В предположениях теоремы 15.56 при

Доказательство. При существует точно различных ненулевых степеней

Сопоставим проективному подпространству пространства над множество целых чисел с помощью следующего правила:

Так как то

Таким образом, согласно следствию 15.561, для одномерного проективного подпространства пространства над разности различно упорядоченных пар элементов из должны пробегать все ненулевые числа по точно один раз. В силу последнего свойства называют простым совершенным разностным множеством по Если степень простого числа, то простое совершенное разностное множество по может быть построено по одномерному проективному подпространству в над в соответствии с определением (15.562). Разностные множества этого типа впервые изучались Зингером [1938] с несколько иной точки зрения. Удивительно, что зингеровские разностные множества включают в себя все известные простые совершенные разностные множества. Эванс и Манн [1951] показали, что при все совершенные разностные множества являются зингеровскими, однако, пока что никому не удалось доказать (или опровергнуть), что для некоторых больших значений не являющихся степенью простого числа, не существует простых совершенных разностных множеств по

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

Многие ЕГ- и ПГ-коды являются собственными подкодами БЧХ-кодов с той же блоковой длиной и тем же конструктивным расстоянием. В общем случае большинство ЕГ- и ПГ-кодов содержит меньшее число информационных символов, чем сравнимые БЧХ-коды. Эта потеря в скорости передачи информации является той ценой, которую приходится платить за преимущества порогового декодирования. К счастью, при малых блоковых длинах эта цена не очень велика. Все двоичные и ПГ-коды с длинами 32 совпадают с БЧХ-кода-ми. Велдон построил следующую таблицу для сравнения -укороченных ЕГ-кодов длины 63 с соответствующими БЧХ-кодами.

ЕГ- и ПГ-коды ухудшаются с ростом блоковой длины гораздо скорее, чем БЧХ-коды. Подсчет числа информационных символов в ЕГ- и ПГ-кодах в общем случае чрезвычайно труден. Мы остановимся только на двух частных случаях, представляющих наибольший практический интерес: на классе ПГ-кодов, содержащем разностные коды, и на классе ортогонализируемых в один шаг ЕГ-кодов. (Еще один класс ЕГ-кодов рассматривается в задаче 15.8.) Для определения числа информационных символов в этих кодах необходимо прежде доказать некоторые свойства весовых функций. В некоторых случаях нам придется различать сумму цифр -ичного представления числа сумму цифр -ичного представления этого числа.

Для доказательства теорем 15.58 и 15.599 необходимы только леммы 15.571-15.573. Остальные леммы включены потому, что их

доказательства оказываются полезными для вычисления числа информационных символов в некоторых и ПГ-кодах высокого порядка.

15.571. Лемма. Если определены условиями то

Доказательство. Пусть Тогда так что

15.572. Лемма. Если и

то

где

Доказательство. Имеем так что

15.573. Лемма.

Доказательство. Так как для всех то

15.574. Лемма. Справедливо неравенство причем равенство достигается тогда и только тогда, когда

Доказательство. Так как а равенство достигается тогда и только тогда, когда то

15.575. Лемм а. Справедливо неравенство причем равенство достигается тогда и только тогда, когда для всех

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

где Умножая (15.5751) на и суммируя по получим значит, Непосредственно суммируя равенства (15.5751), получаем так что

15.576. Лемма. Если произвольные целые числа и причем равенство достигается тогда и только тогда, когда для всех

Доказательство. Лемма 15.576 вытекает непосредственно из леммы 15.575, если применить индукцию по к.

15.577. Лемма. Если то

Доказательство. Пусть Тогда По лемме

15.578. Лемма. Если то

Доказательство. Пусть Ввиду леммы причем равенство

достигается тогда и только тогда, когда Положим Ясно, что для всех достаточно больших .

Согласно лемме так что Так как из следует, что то и, значит, По лемме 15.577 так что Так как

15.58. Теорема (Грэхем, Мак-Вильямс [1966], Мак-Вильямс, Манн [1968], Гёталс, Делзарт [1968] и Смит [1967, 1969]). -ичный ПГ-код порядка с длиной имеет проверочных и информационных символов.

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

Для вычисления числа проверочных символов кода достаточно найтд число целых чисел по удовлетворяющих условию (15.581). Однако легче найти число целых чисел по модулю удовлетворяющих условиям

Если то для всех По лемме тогда и только тогда, когда Поэтому условия (15.582) для всех можно заменить условиями

Если то не удовлетворяет условию так что условие можно заменить неравенством Если для некоторого имеем то

Следовательно, любое ненулевое решение системы (15.583) должно быть также решением системы

Положим теперь где Согласно лемме 15.572,

где

Если для некоторого то в силу что усиливает условия (15.584). Из равенства (15.585) вытекает также, что Так как то заключаем, что для всех К. Следовательно, условие (15.584) эквивалентно условиям

Последовательность длины можно записать в виде последовательности единиц, за которыми следует запятая, за ней единиц, затем снова запятая, Следовательно, число способов выбора неотрицательных чисел в сумме дающих равно числу способов, которыми можно разместить единиц и запятых в позициях. Следовательно, число чисел удовлетворяющих условиям (15.587), или число ненулевых решений системы (15.583), равно

В заключение этого раздела опишем процедуру вычисления числа проверочных символов в ЕГ-кодах порядка

15.59. Вычисление числа проверочных символов в ЕГ-коде порядка Пусть — примитивный элемент поля Согласно определению 15.51, свойству 14.74 и лемме корень порождающего многочлена -укороченного р-ичного ЕГ-кода порядка и длины тогда и только тогда, когда для всех

Число проверочных символов -укороченного ЕГ-кода равно, таким образом, числу целых чисел удовлетворяющих условию (15.591). В неукороченный ЕГ-код входит, кроме того, общая проверка на четность, которую можно связать с числом Так как для всех то число проверочных символов в ЕГ-коде равно числу таких целых что и выполняются условия (15.591). Если положить где то в силу леммы 15.572 условия и (15.591) могут быть записаны в виде

Пусть число последовательностей длины удовлетворяющих уравнениям

Число зависит от Если то Если то, как следует из заключительных рассуждений в доказательстве теоремы При у точное выражение для имеет более сложный вид. Рекурсивные формулы и производящие функции для были получены Риорданом [1958], причем он рассматривал как число разложений величины точно на слагаемых, каждое из которых не превосходит

Для заданной последовательности неотрицательных чисел удовлетворяющих неравенству (15.592), величины удовлетворяющие условию (15.593), можно выбрать способами.

Условие (15.592) на самом деле относится к последовательности и всем ее циклическим сдвигам. Как и в гл. 12, мы будем рассматривать эту последовательность как спепление нескольких базисных последовательностей. Они вводятся следующим образом:

15.594. Определение. Последовательность называется дефектной, если для Если дефектная последовательность, то ее дефектом называется число

Базисной называется недефектная последовательность, все собственные префиксы которой дефектны.

Пусть число выборов чисел для которых последовательность определенная согласно (15.593), имеет дефект Пусть Так как дефект пустой последовательности равен 0, то положим

Если дефект последовательности равен то дефект последовательности равен I тогда и только тогда, когда Отсюда заключаем, что для

Для любых заданных можно определить производящие функции как решения системы линейных уравнений (15.595) и (15.596).

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

Используя определение 15.594 и непосредственную аналогию с доказательством теоремы 12.23, можно доказать следующую лемму:

15.598. Лемма. Любая последовательность неотрицательных чисел удовлетворяющая условию (15.592), однозначно представима в виде сцепления базисных последовательностей (включая окаймляющую последовательность).

Так же, как теорема 12.33 сразу приводит к теореме 12.35 (или, в обозначениях производящих функций, к уравнению (12.61)), так и лемма 15.598 сразу приводит к теореме 15.599.

15.599. Теорема. Если число проверочных символов -ичного ЕТ-кода порядка с длиной то

где определяется уравнением (15.597) и

Примеры.

Если

Если

Если