Двойственные многокомпонентные коды максимальной мощности

Введём основные обозначения и определения. Пусть W = GF(q)n - основное п-мерное пространство над конечным полем GF(q). W(п, т) - множество всех т-мерных подпространств основного пространства W, называемое грассманианом. Мощность грассманиана равна

| W (п, т) | = [”]

(q ⁿ - 1)(q ⁿ - q) ... (q ⁿ - q ^m- 1 )

(q ^m

- i)(q ^m - q)... (q ^m - q ^m- 1 )^.

Грассманово расстояние между двумя подпространствами U,V Е W(п,т) определено в виде

d(U, V) = dim(U W V) - dim(U n V) =

= dim(u) + dim(V) - 2 dim(U n V) =

= 2m - 2 dim(U n V) = 25.

Обозначим [п, M, d = 25, m] некоторый код в грассмановой метрике, у которого длина равна п, M - число кодовых слов, d = 25 - минимальное кодовое расстояние, т -размерность. Важной характеристикой кода является его мощность. Приведём некоторые границы мощности. Верхняя граница мощности для [п, M, d = 25, т] кода получена в 2003 году в работе [1] и имеет вид

M <  M wang

I ^{| W(п,т} - ^{5 + 1) |} I ₌ I L-W

L l ^W (т,т - ⁵ + 1) |J    [[m - m₊J.

Далее мы рассмотрим границы для спредов, то есть кодов размерности т с максимальным подпространственным расстоянием d = 2т. Верхние границы были получены в ряде работ, некоторые из которых опубликованы намного раньше 2003 года (см., например, [2], [3], [4], [5]).

Запишем длину кода в виде п = тт + s, т >  2, 0 <  s <  т — 1, где т и s - целые числа.

Тогда верхняя граница мощности кода с максимальным кодовым расстоянием d = 2т приобретает вид qn

М = М(п,d = 2т, т) <  М w_ang (п, d = 2т, т) = —m

-

-

q ^

.

Если s = 0, то есть длина п = тт, то верхняя граница такова:

q ⁿ

М wang (п, d = 2т, т) = —

-

-

.

Для s = 1 в работе [3] получена верхняя граница в виде qn

М = М(п,d = 2т, т) < —

-

-

q_ 1

-

^(q - 1) -

Для s >  2 в работе [4] приведены результаты, позволяющие модифицировать границу (2) следующим образом:

где

М = М(п,d = 2т, т) <

q ⁿ q m

-

-

-

'; -1,

2Ө = V1 +4q ^m (q ^m — q ^s )

Верхняя граница (4) для s = 2 имеет вид

-

(2q ^m

-

2q ^s

+ 1).

М = М (п,d = 2т, т)

≤

2п -

2 т

-

-

-

2 ,

тогда как нижняя граница (7) равна

М = М (п,d = 2т, т)

≥

2п .

2 т

-

— 1

-

В работе [6] показано, что для параметров п мощность равна

= 2т + 2, т >  4, d = 2т максимальная

М тах = 2 ^т +2 + 1.

Поставим задачу. Используя известные многокомпонентные коды с нулевым префиксом максимальной мощности со следующими параметрами: п = тт + s, т >  2, 0 <  s <  т — 1, d = 2т, построим двойственные многокомпонентные коды максимальной мощности новой размерности т ‘ = п — т, изменив соотношение между размерностью и кодовым расстоянием. Тем самым мы расширим класс подпространственных сетевых кодов максимальной мощности.

В п-мерном пространстве над GF(q) для каждого т-мерного подпространства X существует ортогональное ему дуальное (п — т)-мерное подпространство X ^ . Так как

(X U У)± = X± П У±, то отсюда следует, что если в коде заменить все подпространства на дуальные, то получим код с той же мощностью и подпространственным расстоянием, но с другой размерностью. Изменение размерности при максимальной мощности принципиально меняет постановку задачи. Ранее предполагалось d = 2т.

Если мощность была максимальной для размерности т, то она остаётся максимальной и для дуальной размерности п — т.

2.    Многокомпонентные коды с нулевым префиксом

В 2008 г. в работе [7] для случая 6 = т впервые был предложен класс многокомпонентных кодов с нулевым префиксом (МНП) при любых значениях основных параметров. В дальнейшем эти исследования дополнялись в работах [8], [9]. Заметим, что в работе 2009 г. [10] также имеется алгоритм построения подпространственных кодов максимальной мощности для кода с определёнными параметрами п = гт.

МНП-код состоит из нескольких компонент. (г)-я компонента состоит из т х (п — т — (г — 1)т) матриц вида

С

мнп ,г

= {( О _т

О т І т М )},

где г = 1,..., г, г >  2. Первая компонента совпадает с кодом SKK [11], [12] (Silva-Koetter-Kschischang), без нулевого префикса: С мнпд = C s^^ .

Матрица M j выбирается из матриц т х (п — т — (г — 1)т) кода Габидулина [13] с ранговым расстоянием 6 = т.

Рассматриваем код с параметрами: длина кода п, размерность кодовых подпространств т, кодовое расстояние d = 2т. Обозначим а = тах { т, (п — т — (г — 1)т) } и b j = тіп { т, (п — т — (г — 1)т) } . Мощность г-й компоненты равна

|С мнп j | = ,             .

Общая мощность равна сумме мощностей всех компонент:

г

С_мнп = ^^ q “ » ( ^Ь ! - т+1) j=1

3.    Двойственные мнокомпонентные коды (ДМК)

Пусть подпространство X размерности т задаётся матрицей L размера т х п ранга т. Тогда ортогональное подпространство X ^j размерности п — т задаётся матрицей L ^j размера (п — т) х п такой, что

(Lj)(LT) = 0, где LT означает транспонирование. Построим двойственный многокомпонентный код (ДМК). Для j = 1,...,г компоненты МНП-кода размерности т и длины п = гт + s задаются матрицами ранга т вида

Lj — [0т  . . . 0т Im  Mj] , которые состоят из нулевого матричного префикса размера т х (j — 1)т, единичной подматрицы 1т порядка т и подматрицы Mj размера т х (п — j)т.

Ортогональная матрица Lj- ранга п — т имеет вид лп—дт

^U (j - 1)т

-1- п—дт

Т,   ., П т

^L j

^{1 (} 3 ^-1)т 0 (^ - 1)т оУ^-1^ -м^т п — дт

Здесь 0 ^ означает нулевую матрицу размера I х v.

ДМК-код Lj- имеет размерность п — т и подпространственное расстояние d = 2т. Для п = тг + s, т = 2, 3, s = 0,1, эти коды имеют максимальную мощность.

4.    Максимальная мощность кодов МНП и ДМК

Сначала рассмотрим случаи, при которых мощность МНП-кода максимальна, а затем перейдём к ДМК. Пусть заданы параметры 6 = т и n = гт + s, s = 0. Тогда

М мнп

Г - 1

_ q(r—i+1)m(m-m+1) । 1 _ г=1

q

—

q ^m —

.

Это совпадает с верхней границей (1).

Теперь пусть n = rm + 1, s = 1, тогда

q ⁽ r +^{1) m} _— i

^ММНП — |С мнп |    ^q ~   "       ^{(q 1).}

q ^m — 1

Это значение совпадает с уточнённой верхней границей (3)

_q ^{( r +1) m} _— 1

М = q----------(q — 1).

⁴ qm _— 1           '

Это означает, что при размерности т = 2 коды МНП всегда имеют максимальную мощность при любых значениях параметров n, d, а при т = 3 коды МНП имеют максимальную мощность при 6 = 3 и n = rm + s, s = 0, 1. Соответствующие двойственные коды также имеют максимальную мощность при другой (в общем случае) размерности т' = n — т.

Пример. Построим МНП-код с параметрами n = (2 х 3) +1 = 7, d = 6 и соответствующий двойственный код размерности n — 3 = 4. В данном случае МНП-код состоит из двух компонент. Первая компонента является конкатенацией двух матриц - единичной матрицы I 3 порядка 3 и матрицы рангового кода М размера 3 х 4. Вторая компонента также является конкатенацией двух матриц - матрицы из нулевых элементов 0 ^ размера 3 х 4 и единичной матрицы I 3 порядка 3. Мощность первой компоненты М 1 = 2 ⁴ , мощность второй компоненты М 2 = 1. Суммарная мощность М _тах = 17 соответствует верхней границе (3) для этих параметров.

Соответствующий двойственный код также состоит из двух компонент. Первая компонента является конкатенацией двух матриц – транспонированной матрицы рангового кода — М ^Т размера 4 х 3 и единичной матрицы порядка 4. Вторая компонента также является конкатенацией двух матриц - единичной матрицы I 4 порядка 4 и матрицы из нулевых элементов 0 ³ ₄ размера 4 х 3 . Построенный двойственный код имеет размерность 4, в то время как исходный МНП-код имел размерность 3. В данном случае условие равенства удвоенной размерности (2 х т ' = 8) и расстояния d = 6 не соблюдено. Тем не менее код имеет максимальную мощность. На этом небольшом примере видно, что построение двойственных кодов на основе МНП-кодов максимальной мощности увеличивает число подпространственных кодов максимальной мощности.

5.    ZJSSS-код максимальной мощности

Изменим параметры: пусть n = (гт + 2) = 8, т = 3. В этом случае МНП-код имеет мощность М = 33, в то время как верхняя граница даёт значение М _тах = 34.

В работе [14] путём исчерпывающего перебора построен код максимальной мощности для этих параметров. Соответственно первым буквам фамилий авторов обозначим его ZJSSS-код.

Кодовые подпространства размерности т = 3 ZJSSS-кода заданы порождающими двоичными матрицами размера 3 х 8. Для краткости каждая 8-битная строка записывается как двоичное разложение десятичного числа. Кодовые матрицы имеют вид

А 1 =(169,75, 5)	А 2 = (195,43,6)	А з = (108, 29, 3)	А 4 =(130,72,20)
А 5 =(144, 68, 33)	А б = (65,61,2)	А 7 = (66,19,4)	А 8 =(140,87,1)
А 9 =(35,16,9)	Аю = (147, 99, 7)	Аң = (155,76,38)	А і2 =(69,40,24)
А із =(132,103,12)	А 14 = (152, 88, 56)	А 15 = (153,94,39)	А іб =(196, 34,11)
А 1т =(167,97,15)	А 18 = (159, 84, 32)	А 19 = (154,71,55)	А 20 =(145, 80, 50)
Л 2і =(131,54,13)	А 22 = (134, 74, 53)	А 23 = (166,18,8)	А 24 =(164, 64, 31)
А 25 =(138,90,60)	А 26 = (135, 73, 27)	А 27 = (146,77,37)	А 28 =(171,105,17)
Л 29 =(158,79,52)	А 30 = (128, 89,47)	А 31 = (129,22,10)	А 32 =(143, 83,46)
А 33 =(205,36,21)	А 34 = (137, 91,44)

6.    Двойственный код (DZJSSS)

Кодовые подпространства размерности п — т = 8 — 3 = 5 длины п = 8 DZJSSS-кода заданы порождающими двоичными матрицами размера 5 х 8. Каждая 8-битная строка записывается как двоичное разложение десятичного числа.

А - =(135,66,39,16,13)	А - = (137, 73,40,16, 7)	А - = (128,43,75,12,19)
А - =(130,72,32,20,1)	А - =(144, 68, 33, 8,4)	А - = (128,69,36,20,12)
А - = (128,32,8, 67,17)	А — =(134,66, 32,18,14)	А - =(128,64,34,11,4)
А ^ = (144, 85, 53,8, 3)	А ^ = (129,71,35,17,14)	А - 2 =(128,65,56,5, 2)
А -3 =(141, 65,33,16,3)	А 14 = (232, 24,4, 2,1)	А - 5 = (161, 98,19,11,6)
А - 6 =(132, 68,42,16,9)	А - 7 =(138, 67,41,16, 6)	А - 8 = (129, 69, 20,9, 3)
А ^ 9 = (131, 98, 51,11,5)	А ^ о =(129,83,34, 8,4)	А - 1 =(137,64,43,27,7)
А 2 2 = (129, 71, 33,17,15)	А - = (132,64,36,22,1)	А - 4 =(133,37,17,9, 3)
А - 5 =(150, 84,36,14,1)	А - = (132,67,32,22,13)	А - = (130, 72,41,18,5)
А ^ 8 =(130, 74,40,25,4)	А^=(131,65,38, 21,10)	А - = (67, 34,19, 9, 6)
А ^ 1 = (129, 64, 32,20,14)	А - 2 =(135,70,35, 22,12)	А -3 =(136,72,37,25,2)
А - = (131, 66, 36,18,13)

7.    Семейство МНП и объединённых кодов

Алгоритм построения МНП-кодов позволяет включить ZJSSS-код в качестве конечной компоненты с целью увеличения мощности. Пусть п = 11. МНП-код состоит из 3-х компонент. Первая компонента – SKK-код. Заменим две последние компоненты МНП-кода на одну компоненту - код ZJSSS с нулевым матричным префиксом 0 з порядка 3. Мощность этой компоненты равна 34 и является максимально возможной для длины п = 8 и расстояния d = 2т = 6. Получили двухкомпонентный объединённый МНП-ZJSSS-код [11, 6, 3] максимальной мощности 290. Таким же образом получим семейство подпространственных кодов максимальной мощности с параметрами п = 3(г — 1) + 8 = 3(г + 1) + 2,т = 3, d = 6.

Сначала построим объединённый МНП-ZJSSS-код длины п = 3 х г + 2, где г - некоторое целое число. Пусть размерность т = 3 и подпространственное расстояние максимально, то есть d = 2т = 6. Для примера зададим несколько значений г = 2, 3, 4, 5, соответственно п = 8, 11, 14, 17. Подсчитаем мощности кодов МНП и МНП-ZJSSS, оценим относительную разность в процентах. Эти данные приведём в таблице.

г	п	M max	Л^МНП	м %
2	8	34	33	3
3	11	290	289	0.35
4	14	2338	2337	0.043
5	17	18722	18721	0.005

Используя структуру объединённого MHn-ZJSSS-кода с параметрами п = 11, т = 3, d = 6, построим объединённый двойственный двухкомпонентный код. Первая компонента задана матрицей

[ М ^Т І 8 ] .

Матрица второй компоненты имеет вид

[ І 3    0 8 1

[ 03 z^ р где Z^ - матрица DZJSSS-кода размера 5 х 8. Матрица размера 8 х 11 является конкатенацией двух подматриц, из которых первая подматрица Мт является транспонированной матрицей рангового кода размера 3 х 8, а вторая подматрица !§ является единичной матрицей порядка 8. Вторая компонента представляет двойственный ZJSSS-код в виде общей матрицы размера 8 х 11, состоящей из четырёх подматриц: в левом верхнем углу единичная матрица І3 порядка 3, в правом верхнем углу матрица 08 из нулевых элементов размера 3 х 8; в левом нижнем углу матрица О5 из нулевых элементов размера 5 х 3, в правом нижнем углу матрица размера 5 х 8, ортогональная матрице ZJSSS-кода размера 3 х 8.

Теперь построим объединёный двойственный трёхкомпонентный код длины п = 14, размерности т ‘ = п — т = 14 — 3 = 11 максимальной мощности. Первая компонента МНП-кода имеет вид

[І3 М11 М12 М13 Мы] , где матрица рангового кода М1 записана в виде конкатенации четырёх матриц:

М1 = [Мп М12 М13 М14] , причём первые три матрицы размера 3 х 3, четвёртая матрица размера 3 х 2. Соответствующая первая компонента двойственного кода такова:

" М Ц І з 0 3 0 3 0 2 " М ^ 0 3 І ₃ 0 3 0 2 М ' ,   0 3 0 3 І 3   0 2 .

_ М ^ 0 3 0 3 0 3 І 2_

Вторая компонента МНП-кода имеет вид

[03 Із М21 М22 М23] , где матрица рангового кода М2 записана в виде конкатенации трёх матриц:

М2 = [М21 М22 М23] , причём первые две матрицы размера 3 х 3, третья матрица размера 3 х 2. Соответствующая вторая компонента двойственного кода такова:

І 3	0 3	0 3	0 3	0 2 ⎤
⎢ 0 3	М 21	І 3	0 3	0 2 ⎥
⎢ 0 3	М 22	0 3	І 3	0 2 ⎥
0 3	М 2 Т 3	0 3	0 3	І2_

Третья компонента объединённого трёхкомпонентного кода является конкатенацией двух нулевых матриц размера 3 х 3 и матрицы ZJSSS-кода размера 3 х 8:

[03   03   z], где Z - матрица ZJSSS-кода.

Соответствующая третья компонента двойственного кода такова:

І3 033 083 ⎣033 І3 083⎦ 035 035 Z т где ZТ - транспонированная матрица ZJSSS-кода размера 5 х 8.

8.    МНП-коды размерности т > 4 и двойственные коды

В работе [6] показано, что для параметров п = 2т + 2, т >  4, d = 2т максимальная мощность M max = 2 ^т +2 + 1. Такую мощность при этих параметрах обеспечивает МНП-код, состоящий из двух компонент.

Пусть т = 4, п = 10, d = 8. Первая компонента - SKK-код:

[Д ^М 11 М 12]

мощности М 1 = 2 ^т +2 = 64. Вторая компонента имеет вид

[ 0 6 А ]

• и дает единственное кодовое слово.

Соответствующий двойственный код имеет две компоненты. Первая компонента

Г М^   1₄  02'

[ М2   0 2    2

Вторая компонента

І4

0   0 ²

0 2   І

Новая размерность равна т' = п — т = 10 — 4 = 6. В этом случае удвоенное значение размерности 2т ' = 12 не совпадает с расстоянием d = 8.

Пусть п = 3т + 2 = 14, т = 4, d = 8. Исходный трёхкомпонентный код

[Д М11 М12 М1з] , [04 і4 М21 М22], [04 04 д 04], где каждая строка - соответствующая компонента, матрицы Мц, М12, М21 имеют размер 4 х 4, матрицы М13 и М22 размера 4 х 2.

Первая компонента двойственного кода

"м^ д 04 04" М^ 04 Д 04 , мт 02 02 д вторая компонента двойственного кода

" і 4    0 4     0 4 0 4 "

04 м2ті І4 04 , 02 м2т2 02 і2_ третья компонента двойственного кода

" і 4 0 4 0 4 0 4 " 0 4 І 4   0 4 0 4 .

0 4 0 4 0 4 І 2

Заключение

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

Для всех значений параметров т >  2, n = (г + 1)m+s, где s = 0, 1, 2, d = 2т, построены подпространственные многокомпонентные коды максимальной мощности. На основе этих кодов построены двойственные коды максимальной мощности размерности т ‘ = n — т, в общем случае не равной половине подпространственного кодового расстояния.

Работа выполнена при частичной финансовой поддержке гранта РФФИ, проект № 15-07-08480/16.