УДК 519.725

   В [1] предложена новая конструкция линейных двоичных кодов, исправляющих ошибки. Новый код получается из двух семейств кодов с помощью суммы соответствующих тензорных произведений. Получена также формула для размерности нового кода и верхняя граница для расстояния. Эти результаты будут кратко сформулированы ниже. Установление общих условий достижимости границы расстояния, по всей видимости, является трудной задачей. В настоящей статье рассмотрен случай, когда одно из семейств кодов является вложенным. В этом случае граница расстояния достигается. Указаны также некоторые примеры экстремальных фрактальных кодов на коротких составных длинах, полученные из вложенных семейств.
   В данной статье под (n,k,d)-кодами понимаются линейные двоичные коды на длине n, размерности k, с минимальным расстоянием d, т.е. k-мерные подпространства арифметического линейного пространства F₂ⁿ над полем F₂={0;1}. Используется также терминология, принятая в алгебраической теории кодирования (мы следуем [2], см. также русский перевод [3]) и стандартные понятия линейной и тензорной алгебры. Пусть C =   и D =   - два семейства линейных двоичных кодов на длине n и nў соответственно. В [1] были введены фрактальные коды, получающиеся с помощью семейств C, D по формуле

C Ä D = C1 Ä D1 + ¼ + Cs Ä Ds,

(1)

т.е. являющиеся суммой тензорных произведений соответствующих кодов из семейств C и D. Формула (1) задает код на длине nn¢.
   Пусть S = {1;¼;s} - множество первых s натуральных чисел и a = {i₁;¼;i_r} Ì S произвольное подмножество в S. Обозначим |a| = r. Для произвольного семейства кодов   введем в рассмотрение следующие коды:

(2)

   Таким образом, C^a и C_a - суть сумма и пересечение линейных подпространств, соответствующих мультииндексу a. Мы также пишем C₁₂ для C₁ Ç C₂ и т. п. Параметры этих кодов мы будем обозначать (n^a, k^a, d^a) и (n_a, k_a, d_a) соответственно. Обозначим также (n^¢a, k^¢a, d^¢a) и (n^¢_a, k^¢_a, d^¢_a) параметры соответствующих кодов для семейства D.
   Семейство векторов е = {е_i} Ì ÈC назовем базисом семейства подпространств С, если C_a Ç e - порождает C_a и, кроме того, является минимальным (в смысле частичного порядка, порождаемого отношением включения) семейством, обладающим указанным свойством. Легко видеть, что любое семейство подпространств обладает базисом, но базис семейства не всегда будет линейно независимым. Более детальное исследование свойств базисов семейств выходит за рамки настоящей статьи.
   Семейство подпространств, для которого существует линейно независимый базис, назовем ацикличным.
   Обозначим через a_а максимальный по мощности мультииндекс, для которого a Î . Очевидно, что этот мультииндекс определен однозначно. Для произвольного семейства векторов а = {а_i} обозначим Y(а) = {| а_i Î а}. Пусть теперь Y - произвольное подмножество мультииндексов. Выбирая по одному элементу из каждого мультииндекса в Y мы получим некоторый мультииндекс. Множество всех таких мультииндексов обозначим Y^*.
   В [1] показано, что в случае ацикличных семейств C и D размерность кода (1) вычисляется по формуле

(3)

   Верхняя граница расстояния кода (1) имеет вид:

(4)

где минимум берется по всем тем a и b, для которых подпространства , ненулевые.
   Нижняя граница расстояния кода (1) имеет вид:

(5)

где Y₀ произвольное непустое подмножество Y(е) (или Y(g)).
   Семейство С назовем вложенным, если C_i Ì C_i+1 для всех тех i, для которых оба кода определены. Вложенное семейство, очевидно, ациклично.
   Основным результатом настоящей статьи является следующая
   Теорема 1. Если одно из семейств C, D вложено, а другое ациклично, то граница (4) достигается. Более того, верхняя граница (4) и нижняя граница (5) в этой ситуации совпадают.
   Для доказательства теоремы нам понадобится следующая
   Лемма 1. Если семейство C ациклично, то для произвольного вектора x Î C Ä D существует единственное представление:

x = e1 Ä b1 + ¼ + er Ä br ,

(6)

где е = {е_i} - базис в C и b_i Î .
   Доказательство (см. также лемму 1 в [1]). Т. к.    x Î C Ä D,  то x представляется в виде x = x₁ + ¼ + x_s, где x_i Î C_i Ä D_i, а каждый x_i согласно лемме 1 в [1] представляется в виде :

где  Î eÇ C_i, а Î D_i для всех i, j. Группируя подобные члены (т.е. вынося за скобки одинаковые векторы ), получим представление вида (6), где, очевидно, b_i Î . Единственность следует из того, что для любого вектора y = å_i a_i Ä b_i из линейной независимости векторов a_i, следует, что равенство нулю y равносильно равенству нулю всех b_i.
   Пусть теперь, скажем, семейство C ациклично, а семейство D вложено. Для произвольного вектора x Î C Ä D проверим выполнение обратного неравенства в (4). Во-первых, отметим, что из леммы 1 следует существование для вектора х представления вида:

x = e1 Ä b1 + ¼ + er Ä br ,

где е_i - базис в C, а b_i Î D_pi, где р_i - максимальный индекс, для которого e_i Î C_pi.   Введем в рассмотрение мультииндекс p = {р_i}. Пусть также p = min p. Тогда вес вектора b = È_ib_i не меньше, чем d¢p (расстояние кода D_р). Напомним, что вектор e_i Ä b_i можно представить как матрицу, у которой строки, соответствующие ненулевым позициям вектора b_i, совпадают с вектором е_i, а остальные строки нулевые. Соответственно вектор х представляется как сумма матриц такого вида и, следовательно, строки вектора х, соответствующие ненулевым позициям вектора b, являются линейными комбинациями векторов е_i и имеют вес не меньший, чем d^p. Таким образом, вес вектора х не меньше, чем d^pd¢_p.
   Покажем теперь совпадение нижней границы (5) и верхней границы (4).
    В данном случае, Y(g) = {{123¼s}, {23¼s},¼,{s}}. Пусть достигается на некотором и, скажем, a₀ = {i₀;¼;s}. Заметим, что в этом случае можно считать и, следовательно,   для любого Из сказанного можно заключить, что а, значит, откуда окончательно получаем

что завершает доказательство теоремы.
   Следствие 1. Если C и D - два вложенных семейства кодов, то для размерности и расстояния кода:

E = C1 Ä Ds + C2 Ä Ds-1 + ¼ + Cs Ä D1

(7)

верны формулы

k = k1k¢s + (k2 - k1)k¢s-1 + ¼ + (ks - ks-1)k¢1

   Пример 1. (32, 16, 8)-код.
    Рассмотрим два вложенных семейства кодов: C₁ Ì C₂ Ì C₃ и D₁ Ì D₂ Ì D₃ со следующими параметрами:

код	(n, k, d)	код	(n, k, d)
C1	(4,1,4)	D1	(8,1,8)
C2	(4,3,2)	D2	(8,4,4)
C3	(4,4,1)	D3	8,7,2)

   Все коды определены однозначно, кроме кода D₂, который может быть выбран произвольно. Согласно следствию 1, код, определенный формулой (7) является (32, 16, 8)-кодом. Этот код эквивалентен коду Рида-Маллера и являтся экстремальным.
  Пример 2. (28, 22, 4)-код.
    Рассмотрим два вложенных семейства кодов (см. пример 4 в [1]): C₁ Ì C₂ Ì C₃ и D₁ Ì D₂ Ì D₃ со следующими параметрами

код	(n, k, d)	код	(n, k, d)
C1	(7,3,4)	D1	(4,1,4)
C2	(7,6,2)	D2	(4,3,2)
C3	(7,7,1)	D3	4,4,1)

   Согласно следствию 1, код, определенный формулой (7), является (28, 22, 4)-кодом. Этот код также является экстремальным.

   Российско-Армянский (Славянский) государственный университет