О построении кодов типа Рида-Маллера и исследовании их свойств

Обозначим векторное пространство размерности п над полем Галуа GF (2) по отношению к метрике Хэмминга через F^п. Основные определения кода, линейного кода, веса вектора, кодового расстояния могут быть найдены, например, в [1].

Два двоичных кода С и D длины п называются эквивалентными, если найдутся вектор х Е F^п и перестановка тг G S_n, такие что С = r(D) + х, где + обозначает сложение по модулю 2. Код называется антиподальным, если для любого кодового слова х вектор х + 1^п также принадлежит коду, здесь и всюду ниже 1^п - вектор, имеющий длину п, состоящий из единичных символов. Антиподальный код с параметрами и основными свойствами классического кода Рида-Маллера RM(r,m) называется кодом типа Рида-Маллера порядка r и обозначается LRM(r,m).

В данном обзоре рассматриваются несколько методов построения нелинейных, в том числе Х4-линейных кодов типа Рида-Маллера LRM (г, т) и анализируются их структурные свойства. В заключении статьи приводятся нерешенные проблемы, касающиеся рассматриваемого класса кодов. Автор настоящей работы заведомо не претендует на полноту освещения всех полученных в последнее время результатов по кодам типа Рида-Маллера. За пределами этого небольшого обзора остаются вопросы, касающиеся кодирования и декодирования, радиуса покрытия классических кодов Рида-Маллера, связей кода RM(г,т) с максимально нелинейными функциями, частичными булевыми функциями, блок-схемами и криптографией. В [2] приведен достаточно обширный обзор результатов по оригинальным кодам RM(г,т) и смежным вопросам, полученным до 1993 г.

Подсемейство кодов LRM(т-2, т) совпадает с обширным классом расширенных совершенных кодов. Кроме того, по определению все линейные коды Рида-Маллера, среди них и оригинальный, также являются LRM (г,т) кодам и. При г Е {0,т — 1,т} код LRM (г,т) порядка г совпадает с кодом RM(г,т) порядка г. В литературе известно несколько методов построения LRM(г,т) кодов произвольных порядков, см. [3-6]. Класс таких кодов содержит семейство Х4-линейных кодов Рида-Маллера из [7,8]. Отметим, что недавно был предложен новый свитчинговый метод построения дважды экспоненциального по мощности класса кодов LRM(г,т) см. подробное описание в работе [3].

В параграфе 2 данного обзора упомянем кратко свойства оригинального кода RM(г, т). Параграф 3 посвящен рассмотрению конструкции Пулатова нелинейных кодов типа Рида-Маллера, проблеме пересечения кодов LRM(г,т) и результатов, полученных в данном направлении. В параграфе 4 приведем каскадную конструкцию кодов LRM(г,т). В параграфе 5 рассмотрим конструкции Х4-линейных кодов Рида-Маллера и свойство групповых кодов над кольцом Z4 (являющихся прообразами данных Х4-линейных кодов) обладать базами минимального веса, см. также [9,10].

Изучение структурных свойств кодов некоторого класса представляется актуальным с точки зрения обнаружения новых методов построения кодов этого класса, анализа их комбинаторной структуры, связей с теорией блок-схем. Такого рода исследования полезны с целью классификации с точностью до эквивалентности кодов с заданными параметрами, вопросов кодирования и декодирования, а также применения в криптографии, см. [2,11]. Кроме того, используя свитчинговый метод построения кодов или его модификации, можно получить существенные продвижения в процессе построения широких классов кодов с теми же параметрами, что и исходный линейный код, над которым были произведены серии свитчинговых преобразований. При использовании каскадного метода построения кодов часто получаются новые коды с разнообразными структурными свойствами, например, с богатыми группами автоморфизмов, а также коды с большими ядрами и рангами.

2.    Классические коды Рида-Маллера

Прежде всего напомним определение и основные свойства классического двоичного линейного кода Рида-Маллера, порядка г, обозначаемого в литературе через RM(г,т). Данный код определяется для произвольных гит, 1 <  т, 0 <  г <  т, как множество всех векторов длины 2^т, соответствующих булевым функциям степени не более г от т переменных. Код RM(г,т) обладает следующими параметрами: длиной п = 2^т, мощностью 2^к, где к = ^^^ (т), минимальным расстоянием 2^т-Т.

Код RM (г,т) антипода леи и является дуальным к кону RM (т — 1 — г, т). 0 <  г < т. Дуальные друг другу коды RM (1,т) и RM(т — 2,т) являются расширенными кодами Адамара и Хэмминга соответственно. Для любого 1 < г < т имеет место свойство вложимости для кодов Рида-Маллера: RM(г — 1,т) С RM(г,т)

Код RM(г,т) может быть представлен классической конструкцией Плоткина [1]:

{(ж + у|ж) : ж Е RM(г, т — 1),у Е RM(г — 1,т — 1)}.

Структура и порядок группы автоморфизмов кода Рида-Маллера RM(т,т) хорошо изучены. Группа симметрий этого кода эквивалентна общей аффинной группе GA(m, 2). Известно также, что код порождается множеством своих кодовых слов минимального веса, см. [1, §13.5]. Такое множество кодовых слов линейного (Х4-линейного) кода будем называть базисом минимального веса. Из представления кода Рида-Маллера посредством конструкции Плоткина (1) нетрудно индуктивно построить базис минимального веса этого кода. Итеративное представление базиса при исследовании некоторых свойств кода RM(т,т) может оказаться в ряде случаев полезнее использования представления базиса минимального веса кода Рида-Маллера через конечные геометрии [1].

Несмотря на то, что коды Рида-Маллера являются достаточно хорошо изученными, до сих пор для них остаются нерешенные проблемы. Среди них отметим проблему описания весового спектра этих кодов, которая все еще полностью не решена, несмотря на существенные усилия и результаты, полученные в 1970 г. в данном направлении, см. работу [12], а также недавние статьи [13,14].

Проблема применения кодов Рида-Маллера в криптографии, а именно в криптосистеме Мак-Элиса, по-прежнему является интригующей, поскольку коды малых порядков обладают большими кодовыми расстояниями. Это обстоятельство позволяет исправлять существенное количество ошибок и прятать их в криптосистеме, см. работы [11,15, 16] о применении кодов RM(т,т) в криптосистеме Мак-Элиса и ее криптоанализу. Возможными хорошими кандидатами для использования в криптосистеме Мак-Элиса явятся коды типа Рида-Маллера, а именно, класс четверичных кодов Рида-Маллера LRM(т,т) порядка т, поскольку для фиксированных тит сущеетвует [(т +1)/2] неэквивалентных таких кодов.

3.    Конструкция Пулатова, ее свойства и применение

Сначала рассмотрим свитчинговую конструкцию Пулатова [5] для выколотых кодов типа Рида-Маллера, затем приведем конструкцию для кодов LRM(т,т)

Обозначим выколотый код типа Рида-Маллера порядка т через LRM*(т,т). Пусть LRM* (т, т — 1) и LRM*(т — 1, т — 1) - два произвольных выколотых кода с параметрами кодов Рида-Маллера порядков тит — 1 длины 2т-1 — 1, имеющих мощности 2^i=0 ( 1 ) ^г—1 т—1\ и 2^-'-'> ( 1 ), с минимальными расстояниями 2т-Т-1 — 1 и 2т-т — 1 соответственно. Пусть А - произвольная функция. действующая на кодовых словах кода LRM*(т — 1,т — 1) со значениями в множестве {0,1}. Рассмотрим множество векторов вида

{(ж + у, ж, |ж| + А(у)) : ж Е LRM*(т, т — 1), у Е LRM*(т — 1, т — 1)}.         (2)

Теорема 1. [5]. Для любых тит, 0 < т < т, код, полученный конструкцией (2), является выколотым кодом типа Рида-Маллера порядка т длины п = 2^т — 1 с числом кодовых слов 2^к, где к = ^'=0 (т), " ^с кодовым расстоянием 2^т-г — 1.

Метод построения Пулатова кодов типа Рида-Маллера выглядит следующим образом. Обозначим через ei вектор длины 2^т-1 веса о дин с 1 в 1-й координатной позиции. Пусть А : RM (т — 1,т — 1) ^ {0,1} - произвольная функция.

Теорема 2. [5]. Для любых тит, 0 < т <  т, мномсество векторов

{(ж + у + е1А(у)|ж + е1А(у)) : ж Е RM(т, т — 1), у Е RM (т — 1,т — 1)}        (3)

является расширенным кодом Пулатова, имеющим те мсе параметры, что и код Рида-Маллера RM(т,т) пор.ядка, т.

Конструкция Пулатова (2) для выколотых кодов типа Рида-Маллера является обобщением широко известного в литературе свитчингового метода построения Васильева нелинейных совершенных двоичных кодов [17], а для расширенного случая - обобщением конструкции Плоткина. Если LRM(т,т — 1) = RM(т,т — 1) и

LRM(г — 1,т — 1) = RM(г — 1,т — 1) и А - тождественно нулевая функция, то код, полученный описанной выше конструкцией Пулатова (3), является оригинальным кодом Рида-Маллера RM(г,т) порядка г, представленным конструкцией Плоткина (1).

Нетрудно получить следующее следствие Теоремы 2.

Следствие 1. Для числа N_n различных двоичных кодов Пулатова длины n = 2^т порядка г справедливо

> 2І-КМ(г-1,т-1)|

п

Следует заметить, что все коды Пулатова удовлетворяют, как следует из их определения, свойству антиподальности. Зная нижнюю оценку числа различных двоичных кодов длины n, нетрудно вычислить нижнюю оценку числа неэквивалентных таких кодов с теми же параметрами. Для этого достаточно разделить число различных кодов на число различных автоморфизмов пространства F ^п, равное 2^п • n!, где 2^п - число различных сдвигов на векторы из F ^п и n! - число различивix подстановок на n координатных позициях. Кроме того, для усиления нижней оценки числа кодов типа Рида-Маллера можно учесть итеративность свитчинговой конструкции Пулатова.

Таким образом отметим, что данный свитчинговый подход к кодам позволяет получить дважды экспоненциальные по мощности классы неэквивалентных нелинейных кодов с параметрами кодов Рида-Маллера порядка г длины n = 2^т, n > 16. Среди этих кодов могут оказаться коды с полезными для практических применений свойствами, например с транзитивной группой автоморфизмов (код называется транзитивным, если его группа автоморфизмов действует транзитивно на всех его кодовых словах), а также коды, являющиеся Х4-линейными. Последние, как уже было упомянуто выше, могут найти применение в криптографии, например, в криптосистемах типа Мак-Элиса с открытыми ключами.

3.1.    Проблема пересечения кодов типа Рида-Маллера

Проблему пересечения для совершенных кодов впервые предложили изучать Етцион и Варди в 1994 г. в работе [18]. Исследованиям проблемы пересечения совершенных кодов и кодов Адамара посвящено уже достаточно много статей, тем не менее для нелинейных совершенных двоичных кодов эта проблема до конца не решена, см. обзор [19] и список литературы в нем.

Осветим кратко состояние данного вопроса. В [20] было найдено полное решение проблемы пересечения двоичных кодов Хэмминга. В статье [21] приведено решение проблемы пересечения для всех q-ичных линейных кодов, q >  2, включая также двоичные коды Рида-Маллера. Согласно результатам этой работы, для некоторой подстановки тг порядка 2^т для кода Рида-Маллера RM(г,т) справедливо |RM (г, т) П tt(RM (г, т))| > 2, здесь значение 2 достижимо только при г < [(т — 1)/2].

В работе [20] доказано, что для любого т > 3 существует два нелинейных совершенных двоичных кода длины 2^т — 1, пересекающихся по двум кодовым словам. Данный результат получен конструктивно комбинацией каскадного и свитчингового подходов. В работе [22] установлено, что для любых чисел ki и к^, удовлетворяющих 1 <  k_s < 2^(n+1)/2-log2⁽ⁿ⁺¹⁾, s = 1, 2, найдутся совершенные двоичные коды Ci и С2 длины n = 2^т — 1, т > 4, удовлетворяющие |Ci П С21 = 2kik2. В статье [23] показано, что для всякого четного числа к в интервале 0 < к <  2^п+^1-21од2^(п+1) существуют совершенные двоичные коды Ci и С2 длины n = 2^т — 1, т > 4, такие что ^(Ci, С2) = к. Следует отметить, что совокупности чисел пересечений в [22] и [23] получены свитчинговым методом и не покрывают друг друга.

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

Перейдем к рассмотрению вопросов, касающихся пересечения кодов типа Рида-Маллера, которые обобщают результаты, полученные в [21-23].

Используя конструкцию Пулатова для кодов типа Рида-Маллера, специального вида функции А и модифицированные подходы, обобщающие идеи из статей [22,23], в работах [24,25] были получены следующие результаты.

Определим два кода D x (RM (т — 1, т— 1)) и Dx‘(v(RM(т — 1, т — 1))) длины п, используя конструкцию Пулатова для расширенных кодов типа Рида-Маллера.

Пусть А - произвольная функция, действующая из множества кодовых слов кода RM(т — 1,т — 1) в множество {0,1}. Первый код имеет вид

D_X(RM(т — 1,т — 1)) = {(ж+ у + е1А(у),ж+е1А(у)) : ж Е RM(т,т — 1),у Е RM(т — 1,т — 1)}.

Пусть т - циклический сдвиг вектора длины 2^т-1 па. одну позшшю вправо, a. v - транспозиция первых двух координатных позиций векторов из F2^т . Второй код определим, используя подстановки щ v и произвольную функцию А’, действующую из кода v (RM(т —1, т—1)) в множество {0,1} следующим образом:

D_X‘ (v(RM (т — 1,т — 1))) =

= {(ж + у + е1А‘(у), щ(ж + е1 А‘(у)) : ж Е RM(т, т — 1), у Е v(RM(т — 1, т — 1))}.

Теорема 3. [24,25]. Для любого четного к в интервале г—1 т —1\ 0 < к < 22 ^=0 ( i )

существуют два кода типа Рида-Маллера порядка т длины 2^т, т > 4, пересечение которых равно к.

Рассматривая вместо второго кода код вида Dx‘(RM(т — 1,т — 1)), то есть без учета в построении этого кода транспозиции v, оставляя при этом первый код С = D_X(RM (т — 1,т — 1)) без изменения, было доказано следующее утверждение.

Теорема 4. [24,25]. Для любых чисел кі и к2, удовлетворяющих г—1 т—1

1 <к < 2^=о ⁽ i ), s Е {1, 2}, существуют два кода типа Рида-Маллера порядка т длины 2^т, т > 4, пересечение которых равно 2к1к2.

При доказательстве последних двух теорем существенно использовалось свойство ан-типодальности используемых кодов Пулатова. Нетрудно убедиться в том, что множества, чисел пересечений кодов типа Рида-Маллера порядка т длины 2т, полученных в теоремах 3 и 4, так же как и в работах [22,23] для совершенных двоичных кодов, не покрывают ДРУГ ДРУга- Отметим также, что результаты последних двух теорем справедливы для выколотых кодов типа. Рида-Маллера.

4.    Конструкция Соловьевой

В данном разделе рассмотрим каскадную конструкцию из [6]. Используя конструкцию Пулатова, несложно убедиться, что для любых тит, 1 < т, 1 <  т < т, существуют нетривиальные разбиения кодов LRM (т, т — 1) на коды типа Рида-Маллера LRMi(т — 1,т — 1) порядка т — 1 длины п = 2^т-1:

t

LRM (т,т — 1) = ^LRM_i(т — 1,т — 1), г=1

где t = 2

(т)

Теорема 5. [6]. Пусть даны два произвольных разбиения кодов типа Рида-Маллера порядка г длины 2^т-1:

t

LRM1(r,m - 1) = J LRMi,i(r - 1,m - 1), i=1

t

LRM2(r, m - 1) = J LRM2,i(r - 1, m - 1), г=1

где t = 2^г). Пусть тг - произвольная подстановка на t элементах. Тогда множество

{(х,у, |у|) : х Е LRMi,i(r - 1,m - 1),у Е LRM2,T(i)(r - 1,m - 1),г = 1,...,t} является LRM(r,m) кодом порядка г.

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

Используя итеративность представления этой конструкции, можно также строить нетривиальные разбиения кодов LRM(r,m) на коды типа Рида-Маллера порядка г - 1 длины 2^т-1. Заметим, что конструкция, описанная в теореме 5, не дает более мощные классы кодов типа Рида-Маллера по сравнению с нижней оценкой числа кодов, даваемой конструкцией Пулатова.

Следует подчеркнуть, что каскадный подход достаточно часто позволяет эффективно исследовать нетривиальные свойства кодов, а именно в тех случаях, когда использование свитчингового подхода не является успешным. Например, из линейных расширенных совершенных кодов RM(m - 2,m), благодаря свитчинговой конструкции Васильева (напомним, что при г = m - 2 метод построения Пулатова совпадает с конструкцией Васильева), можно построить коды LRM(m - 1,m + 1) только ранга на единицу большего, чем у расширенного кода Хэмминга, то есть ранга 2^m+1 - m + 1. Напомним, что ранг кода определяется как размерность линейной оболочки, натянутой на код. Ядром кода длины п называется максимальный линейный подкод пространства F^п, сдвиги на векторы которого оставляют код неизменным. Применение конструкции теоремы 5 позволяет строить коды LRM(m - 1, m + 1), близкие по свойствам их групп автоморфизмов к линейным, но имеющие различные, даже большой величины, ранги и большого размера ядра. Это семейство кодов содержит координатно-транзитивные коды, которых нет в классе кодов Васильева ранга 2^m+1 - m +1, см. работу [26]. Кроме тог о, блок-схемы, отвечающие LRM (m -1, m + 1) кодам, также обладают богатыми группами автоморфизмов, см. [27].

О сути и применении свитчингового подхода для построения кодов и исследования их нетривиальных свойств, а также каскадных методов, см., например, обзоры [19,28].

5.    Я4-линейные коды Рида Маллера и их свойства

В данном параграфе речь пойдет о построении и свойствах Zi-линейных кодов Рида-Маллера. Из контекста всегда будет ясно, речь идет о сложении над полем GF (2) или над кольцом Z4.

В работах [7, 8] приведены две конструкции Zi-линейных кодов Рида-Маллера. Семейство этих кодов содержит классы Zi-линейных кодов Адамара и совершенных кодов, классифицированных Кротовым в [29,30].

Напомним необходимые определения и понятия, касающиеся кодов над кольцом Z4 целых чисел по модулю 4. Множество Z i является модул ем над кольцом Z₄. Вес Ли, w l (x), четверичного вектора х определяется как сумма весов Ли его координатных позиций:

^L (0) = 0, m_L(1) = wl (3) = 1, m_L(2) = 2.

Расстояние Ли, обозначаемое C l (x,y), для произвольных четверичных векторов x,y G Z 3 определяется как dL(x,y) = u l (x — у). Множество Z^ является метрическим пространством по отношению к метрике Ли, а произвольное подмножество пространства Z^ - четверичным кодом длины N. Четверичный код длины N называется линейным в случае, когда он образует подгруппу аддитивной группы модуля Z^ . По этой причине целесообразно и часто удобно для исследования таких кодов оперировать аналогами порождающих матриц над кольцом Z4.

Далее будем использовать прописные буквы для двоичных кодов и каллиграфические для четверичных. Четверичный линейный код С в Z^ изоморфен абелевой структуре типа Z2 х Z4 для некоторых чисел у. 5. Отсюда легко пайти мощность кона С: |С| = 2⁷4^. Такой код С называется четверичным линейным кодом типа (N;у,д), а его двоичный образ С = р(С) под действием отображения Грея называется 74-линсйным ?стадом типа (N;у,5). Напомним, что отображение Грея р : Z^ ^ Z2^N определяется как

p(x) = (3(x), у(x)) для .любого x G Z^.

Здесь 3 іі у являются стандартны ми отображениями из Z4 в Z2:

Z4	3	у
0	0	0
1	0	1
2	1	1
3	1	0

Известно, что отображение Грея является изометрией метрических пространств Z^ и Z^. Все двоичные Z4-HHHefiHbie коды обладают следующими двумя замечательными свойствами: они являются транзитивными и дистанционно инвариантными.

Под инверсией четверичного вектора понимаются замены в некоторых координатных позициях элементов кольца Z4 на обратные элементы, а именно 0 на 0, 1 на 3, 2 на 2, 3 на 1. Два четверичных кода СиР длины N эквивалентны, если существует вектор x G Z^, подстановка л и инверсия ст. обе на N коордіпіатпвіх позициях, такие что С = k(ct(D~)) + x.

Первая четверичная конструкция Плоткина кодов Рида-Маллера была предложена в 2007 г. в работе [7]. Затем этот метод построения четверичных кодов был развит и дополнительно обогащен в 2009 г. в статье [8] еще одним методом построения четверичных кодов, названным конструкцией BQ-Плоткина. Эти два подхода позволили построить индуктивно [^т+ J бесконечных семейств нстворинііых кодов Рида-Маллера длины 2^т. Для фиксированных тих, используя индекс s, s = 0,..., L^т— J; такие коды обозначаются KM_S(г,т). Неизоморфизм кодов в этих семействах характеризуется посредством их абелевых структур и строением ядер этих кодов, см., подробнее, ниже теорему 9. Отметим, что Z4-HHHefiHbie коды, полученные из этих четверичных кодов под действием отображения Грея, имеют те же параметры и фундаментальные свойства, что и классические двоичные линейные коды Рида-Маллера. А именно, им присущи свойства дуальности, антиподаль-ности, транзитивности, дистанционной инвариантности, а также вложения последовательностей кодов друг в друга. Кроме того, этот класс Z4-nHHefiHbix кодов Рида-Маллера содержит все Z4-nHHefiHbie совершенные коды и коды Адамара из [29,30].

Случай Z2Z4-4HHefiHbix кодов Рида-Маллера исследован в статьях [31,32], где были предложены конструкции кодов с параметрами выколотых кодов Рида-Маллера.

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

5.1.    Конструкция Плоткина для четверичных кодов Рида-Маллера

Рассмотрим общую конструкцию Плоткина для четверичных кодов, см. [7, 8]. Пусть А и В - произвольные два четверіічных линейных кона типов (N; уд, 5д) и (N; уу, 5g) с порождающими матрицами 5д и Qg соответственно. Четверичный код Плоткина определяется аналогично двоичному коду Плоткина (1):

С = {(х|х + у) : х Е А, у Е В}.

Его порождающая матрица имеет вид г ( 9л 9а \

^9с =( 0 9вР

Это код типа (2N; у, 5), г де у = ул + ув и 5 = 5л + 5в; двоичной длины n = 4N, мощности 27+2 _{и с} минимальным расстоянием Ли йь = тіп{2йл,йв}•

Применим данную конструкцию для построения четверичных кодов Рида-Маллера. Конструкция индуктивна, для малых параметров г, т и s легко построить все требуемые коды. Пусть ПМ₈(г,т — 1) и ПМ₈(г — 1,т — 1) - произвольные четверичные коды Рида-Маллера типов ( N ; у®,_т-1,5®,_т-1) и (N; у®—і,_т-1,5®_—1,_т—1), длин N = 2^т-2, мощностей ^^г /т—1\      ^^г —1 /т —1\

22^i=o ⁽ і ) _и 2 2^і=о ⁽ і ), с минимальными расстояниями 2^т-Т-1 и 2^т-т соответственно. В [8] доказана следующая

Теорема 6. [8]. Для любых гит > 2, 0 < г < т, код, полученный четверичной конструкцией Плоткина

НМ₈(г, т) = {(х|х + у) : х Е НМ₈(г, т — 1), у Е НМзД — 1,т — 1)},       (4)

0 <  s < [т^ ¹ J. за исключением случая нечетного т и s = (т — 1)/2. является четверичным линейным кодом Рида-Маллера, имеющим тип ( 2N ; у®_т, 5®_т), где у?,_т = у?,_т-1 +7^-1 ,_т-1^и 5®,_т = 5®_т-1 + 5®_1 1. Длин а кода 2N = 2 ^{т -1}, число кодовых слов равно 2^к, г де к = ^2^=о (™), минимальное расстояние Ли равно 2^т-г.

Отметим, что справедливо ПМ₈(г — 1,т) С ПМ₈(г,т). При г = 0, к од ПМ₈(0,т) является кодом с повторением с одним ненулевым кодовым словом, все координаты которого равны 2.

5.2.    Конструкция BQ-Плоткина

Отметим, что в теореме б остались неописанными ряд случаев в зависимости от значений т и s. Рассмотрим вторую конструкцию четверичных кодов из [8], которая позволяет провести доказательство для четверичного линейного кода Рида-Маллера ПМ₈(г,т) во всех этих случаях.

Пусть 9л- 9в ¹¹ 9с ~ порождающие матрицы ч<лверннпых линейных кодов А. В и С соответственно. Рассмотрим матрицу

9 л 9 а  9 а

0  9В  29В39В

0   0   9в9в

\ 0   0   0   9с/

Здесь 9В - матрица, полученная из 9в после замены элементов, равных двум, на единицы кольца Z4 в их ув строках по рядка два, 9в является матрицей, полученной из 9в вычер киванием ув строк порядка два.

Четверичный линейный код, порожденный этой матрицей, обозначается ВО.(А, В, С) и называется кодом, построенным конструкцией BQ-Плоткина.

Теорема 7. [8]. Линейный код BQ(A, В, С) с поролсдающей матрицей (5) является четверичным кодом типа (4N;у,5), где у = ул + ус 5 5 = 5л + ув + 26в + §с- Двоичная длина кода равна n = 8N, мощностъ 2 ⁷ 4⁵, минимальное расстояние Ли равно йь = тіп{4йл, 2йв, йс }•

Рассмотрим применение этой теоремы к построению четверичного линейного кода Рида-Маллера. Данная конструкция так же, как и четверичная конструкция Плоткина, является индуктивной. Для малых значений г, m и s нетрудно перечислить все четверичные линейные коды Рида-Маллера. Пусть 'R,M_s—1(r,m — 2), ^^_s-1(г — 1,m — 2) и ^^_s-1(г — 2, m — 2), 0 < s < [ ^M¹ J, m > 3 любые три четверичных линейных кода Рида-Маллера ТИПОВ ( N ; 7"--2 А^ш-2) - (^N; ti,m—2, ^dT—1,m—2) ^H(^N; 7T—2,m-2^,dT—2,m—2) с порождающими матрицами 5_s—1(n,m — 2), д‘_—1(г — 1,m — 2) и §_s-1(r — 2,m — 2) соответственно. Коды имеют четверичную длину N = 2^m-3 (длины отвечающих им двоичных ^г /т —2\   ^г—1 т— 2\

Х4-линейных кодов равны соответственно n = 2^m ); мощности 2^^{i=0 (} t ), 2^^=0 ⁽ t ) и ^^г —2 т —2

2 м₁₌° ⁽ t )• минимальные расстояния Ли 2^m-r—2, 2^m-r—1 и 2^m-r соответственно.

Пусть Q_s (г, m) - матрица вида

/ д_а—1(т,т - 2)

\      0

д_в — 1(т,т - 2) S’ —1(г — 1,т - 2)

д_в — 1(т,т - 2) ²S s — 1 ⁽г ^- 1,^{т - 2)} д_в — 1(т - 1,т - 2)

gs-1(r,т - 2)    \ здд1Ф— 1,т — 2) дв — 1(т - 1,т - 2) gs —1(г - 2,т - 2) /

где 0 < г < m — 1. Отметим, что подматрицы Q'‘-i(r — 1,m — 2) и Q_s-i(r — 1,m — 2) в (6) получены из матриц Q_s—1(г — 1, m — 2) и Q_s-1(r — 1, m — 2) аналогично матрицам 9g и 9в, определенным выше в (5).

Теорема 8. [8]. Для любых г и 3 <  m, 0 < г < m — 1 и 0 < s < [^Д J код

UM_S(г,m') = BQ('RMs—1(r,m — 2), КМ₈-і(г — 1,m — 2), КМ₈-і(г — 2,m — 2))   (7)

с порождающей матрицей Qs(г, m) является четверичным линейным кодом Рида-Маллера типа (4N; ^'m, 5'm), где s   s-1    । s-1          s __ Xs-1    I ^s I        I 9Xs-1           s-1

7r,m     lr,m— 2 + 7t— 2,m— 2, °r,m   °r,m— 2 + I t— 1,m—2 + ²⁰r—1,m—2 + °r—2,m— 2•

Двоичная длина соответствующего 24-линейного кода равна n = 2^m; мощностъ 2^к, где к = ^^ ( • )’ минимальное расстояние Ли равно 2^m-r.

г=0 ^г2

Кроме того, P,M_s(г — 1,m) С P-Mg(гщп) то есть классы четверичных линейных кодов, построенных этими двумя конструкциями, обладают теми же параметрами и свойствами, что и классические коды Рида-Маллера.

Позднее Виллануевой с соавторами были исследованы свойства этих классов Х4-линей-ных кодов Рида-Маллера, а именно структура и размерности ядер, см. [33]. Фактически с помощью структур ядер этих кодов можно различать неэквивалентность кодов, то есть получено еще одно классификационное свойство этого класса кодов. В работе [34] изучены ранги некоторого подкласса Х4-линейных кодов Рида-Маллера данного семейства. Вопрос полной характеризации рангов этого класса Х4-линейных кодов все еще остается открытым.

Теорема 9. [29,30,33]. Для всех 4 <  m и 2 <  г < m — 2 имеется по крайней мере [(m + 1)/2] нсжвивалсптпых 74-липсйпых кодов Рида-Маллсра порядка г. за исключением почетного m и четного г. В последнем случае суш,<'ствует по ?ф«йлсй .мере [(m — 1)/2] нсжвивалсптпых 74-липсйпых кодов Рида-Маллсра порядка г. В случае всех m > 4. г = 1 и г = m — 2 существуют в точности [(m —1)/2] и [(m+1)/2] нсжвивалсптпых 74-липсйпых кодов Рида-Маллера порядков 1 и m — 2 соответственно.

Для 2 <  г < m — 2 теорема 9 следует из структуры приведенных в этом параграфе кодов и из исследования строения их ядер, см. подробности в статье [33]. Для г = 1 и г = m — 2, то есть для Х4-линейных кодов Адамара и совершенных, результаты были доказаны в работах [29,30].

Объединение приведенных выше конструкций Плоткина и BQ-Плоткина позволило доказать, см. работы [9,10], еще одно фундаменталвное свойство семейства приведенных выше кодов LM_S (г, т), присущее также оригинальным линейным кодам Рида-Маллера: данные четверичные коды имеют базисы, состоящие из кодовых слов минимального веса. Следует отметить, что эти базисы строятся индуктивно.

Теорема 10. [9,10]. Для любых гит, 2 <  т, 0 < г <  т, а такзюе произвольных s, 0 <  s < [ Д^-1 J четверичный линейный код Рида-Маллера КМ₈(г,т) имеет базис минимального веса.

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

Нерешенные проблемы. В завершение данного небольшого обзора отметим несколько нерешенных проблем, касающихся кодов типа Рида-Маллера. Остается далекой от решения проблема описания весового спектра классического линейного кода Рида-Маллера. Заметим, что рассмотренная выше проблема пересечения кодов типа Рида-Маллера еще не решена полностью, несмотря на значительное продвижение. Неизвестно, является ли класс Х4-линейных кодов из [7, 8] полным в смысле классификации Z4- линейных кодов с параметрами кодов Рида-Маллера, то есть существуют ли неэквивалентные им Z4-nHHehHbie коды Рида-Маллера. Напомним, что в случае Z4-nHHehHbix кодов Адамара и совершенных кодов имеем классификацию, см. [29, 30]. Было бы также интересно и полезно изучить группы автоморфизмов этого класса четверичных кодов, их применение в криптографии, решить проблему рангов кодов типа Рида-Маллера, в частности, решить ее до конца для Z4-nHHefiHbix кодов Рида-Маллера. Кроме того, исследовать такие важные свойства, как весовые спектры, дистанционную инвариантность, существование транзитивных кодов типа Рида-Маллера.

Работа выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0017).