5.5.3. Коды, строящиеся с помощью простых совершенных разностных множеств

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

Коды со скоростью или могут быть построены с помощью следующей процедуры.

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

Пример 5.7. Простое совершенное разностное множество позволяет построить самоортогональный код со скоростью Для этого достаточно взять порождающий многочлен

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

и код со скоростью , положив

Таким образом, с помощью простого совершенного разностного множества всегда можно построить самоортогональный код со скоростью Однако при построении необходимо стремиться уменьшить кодовое ограничение при фиксированном поскольку это повышает корректирующие способности кода и позволяет уменьшить объем памяти кодера и декодера. Учитывая это, оптимальным кодом будем называть код, который при заданных скорости передачи числе ортогональных проверок и длине блока имеет минимально возможное кодовое ограничение Робинсон и Бернстейн предложили следующую эффективную процедуру оптимизации построения самоортогональных кодов на основе совершенных разностных множеств [3]:

1) Строится следующее разбиение множества разностей простого совершенного разностного множества порядка на подмножеств. Первое подмножество:

Остальные подмножеств разбиения определяются равенством

где Например, с помощью простого совершенного разностного множества (0, 1, 3, 9) получается следующее разбиение множества разностей:

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

Например, в (5.50)

В силу основного свойства простого совершенного разностного множества каждое из целых чисел от 1 до входит в это разложение ровно один раз.

2) Рассмотрим множество

Из формул (5.51) и (5.52) получаем

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

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

3) Если из построенных таким образом простых совершенных разностных множеств

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

Например, разложение (5.50) позволяет построить следующие четыре порождающих многочлена кодов со скоростью

Из этих многочленов следует выбрать многочлен

имеющий минимальную степень.

5.5.4. Примеры кодов

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

5.5.5. Оптимальность кодов

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

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

Рассмотрим самоортогональные коды со скоростью -Поскольку для каждого из этих кодов могут быть построены

(см. скан)

(см. скан)

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