Оптимальные и субоптимальные подпространственные коды-спреды

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

n

m

|W ( n, m ) I =

( q n - 1)( q n - q ) ... ( q n - q ^{m -} 1 ) ( q m - 1)( q m - q ) ... ( q m - q ^{m -} 1 ) ^.

Подпространственное расстояние между двумя подпространствами U, V Е W определено в виде dsub( U, V) = dim(U W V) - dim(U П V) = = dim(U) + dim(V) - 2dim(U П V), где U W V означает минимальное подпространство, содержащее оба подпространства U и V . Если U и V одной и той же размерности m, то подпространственное расстояние равно dsub(U, V) = 2(m - dim(U П V)) = 25, где 5 = m — dim(U П V). Это расстояние называется грассманниановой метрикой.

Подпространственный код – это некоторое множество подпространств из пространства W . Если код состоит из подпространств m -грассманниана W ( n, m ) с числом кодовых подпространств M , минимальным расстоянием d _sub и размерностью m , то он называется кодом постоянной размерности и обозначается [ n, M, d sub , m ]. При максимальном кодовом расстоянии d sub = 2 m подпространственный код называется спредом.

Далее эта статья структурирована следующим образом. В разделе 2 представлены конструкции подпространственных кодов Силвы–Коеттера–Кшишанга [1, 2] основанные на ранговых кодах Габидулина [4]. В разделе 3 описаны конструкции многокомпонентных кодов с нулевым префиксом (МНП), построенные Габидулиным и Боссертом [5, 6] и основанные на SKK кодах Силвы–Коеттера–Кшишанга. В разделе 4 приведены оценки мощности МНП-спредов для многих параметров и произведено сравнение с верхними границами мощности подпространственных кодов, полученными в работах других авторов [7–11]. В разделе 5 кратко подведены итоги этой работы.

2.    Коды SKK

В работах [1, 2] Силва, Коеттер и Кшишанг подробно описали конструкцию своего подпространственного случайного кода SKK, предназначенного для работы в сети связи. Этот код состоит из множества матриц вида

C skk = {( I m M 1 )} ,                                 (1)

где I m — единичная матрица порядка m , а M i - кодовая матрица размера m х ( n—m ) из матричного рангового кода M i с ранговым расстоянием d rank = 5 [4]. Подпространственное расстояние кода C _skk равно удвоенному ранговому расстоянию матричного кода M : d sub ( C skk ) = 2 d rank ( M ) = 2 5 . Включение в конструкцию единичной матрицы позволило осуществлять передачу по сети с помощью случайных алгебраических комбинаций элементов конечного поля, что повысило скорость передачи [3].

Мощность кода (общее число кодовых слов) |C _skk | кода SKK равно числу кодовых слов рангового кода с ранговым расстоянием d rank = 5 и длиной кодовых слов ( n — m ):

|C skk | = q ⁽ n-m ) k ,                                             (2)

где k = m — 5 + 1, 5 < m .

Пример 1. Зададим параметры: q = 2, n = 5 m = 20, m = 4, n — m = 16, 5 = 3, k = m — 5 + 1=2. Мощность равна

|C skk | = q (n-m)(m^{- 5 +1)} = 2 ³² = 4294967296 .                        (3)

Если 5 = m принимает максимальное значение (в данном случае 4 = m ), то показатель степени принимает минимальное значение k = m — m + 1 = 1. Мощность равна |C skk | = q ^{( n - m} ) = 2 ¹⁶ = 65536 = M i . Увеличение рангового расстояния на 1 (подпространственного расстояния на 2) при той же длине кода n = 20 привело к уменьшению показателя степени на 1, и в результате мощность стала равна двоичному корню от предыдущего значения. Увеличим длину кодовых слов вдвое ( n = 40) при той же максимальной размерности m = 4. В этом случае мощность кода SKK возрастёт до |C skk | = q ^{( n - m} ) = 2 ³⁶ = 68719476736. В данном случае удвоение длины привело к увеличению мощности более чем в 10 6 раз.

3.    Коды МНП

В 2008 году в работе [5] Габидулин и Боссерт представили конструкции новых подпространственных кодов, названных впоследствии многокомпонентными кодами с нулевым префиксом (МНП). С тех пор и до настоящего времени исследования на этутемупродолжа-ются (см., например работы [6–22]). Имеются также работы других авторов, посвящённых близким темам [23–31].

В первом описании кодов МНП были приняты следующие параметры: n = rm , 5 = m , то есть подпространственное расстояние d sub = 2 m максимально. В последующих работах при 5 < m набор параметров расширился.

Рассмотрим конструкцию кода при следующих параметрах: n = m + r5 + s - длина кодовых слов, где m - размерность, r - целое число, r ^ 1 и 0 ^ s ^ 5 — 1. Первая компонента кода МНП – код SKK. Матрица этой компоненты состоит из конкатенации двух матриц – единичной матрицы и матрицы рангового кода.

Другие компоненты при i >  2 состоят из матриц вида

C

mzpi

= {( 0 0 m

0 m I m M i )} .

Начиная со второй компоненты, в качестве префикса стоит матрица из одних нулей размера m x 5 , в каждой последующей компоненте число таких матриц увеличивается на одну, за нулевым префиксом следует единичная матрица порядка m и матрица рангового кода. Нулевые матрицы обеспечивают подпространственное расстояние между компонентами, равное 2 5 . В ранговом коде задано ранговое расстояние 5 .

Мощность i -й компоненты равна

|M i | = q kn i ,

где длина кодовых слов рангового кода i -й компоненты равна n i = ( r — ( i — 1) 5 ) + s При m < n i < m + 5 строим последнюю компоненту в виде

^C mzpl — ( ⁰ _m ⁰ т • • • ⁰ т I m ) •

Последняя компонента содержит одну кодовую матрицу-конкатенацию нулевой матрицы размера mx ( n—m ) и единичной матрицы порядка m . Так как компоненты не пересекаются, то мощность |M _mzp | многокомпонентного кода равна сумме мощностей всех компонент:

|M mzp | = Yq q ⁽⁽ r-i ^{+1) 0 +} s ^{)( т - 0 +1)} + 1 , i =1

где l – общее число компонент.

Пример 2. Зададим n = m + r5 + s = 20, q = 2, m = 4, r = 5, 5 = 3, s = 1. Вычислим мощность каждой компоненты:

M 1 | =      2 ^{k ( n - m} ) = 2 ³² ,

| m ₂ | =     2 ^{k ( n - m - 0} ) = 2 ²⁶ ,

|M ₃ 1 =     2 ^{k ( n - m - 25}) = 2 ²⁰ ,

|M 4 1 =     2 k ( n-m- 3 0 ) = 2 14

| m ₅ 1 =     2 ^{k ( n - m - 45}) = 2 8 ,

|M61 = 1, где k = m — 5 + 1=2, l = r + 1=6. Просуммируем мощности всех компонент:

|M mzp | = ^ү M i + 1 = 4363141377 •

i =1

Основной вклад внесла первая компонента, полученное значение общей мощности всего лишь на 1 • 6 процента больше мощности первой компоненты.

Перейдём к спреду. Пусть 5 = m = 4, n = 5 m = 20, s = 0, q = 2, k = m — m + 1 = 1.

\M 1 \ = \M 2 \ = \M 3 \ = \M 4 \ = \M 5 \ = 1 .

2 k ( n—m )    2 16 2 k ( n— 2 m )    2 12 2 k ( n— 3 m ) = 2 § 2 k ( n— 4 m )    2 4

В этом случае общее число компонент l = 5.

2 n — 1

\M mzp \ = ^^ \M i I ^{+ 1} = ^{2 + 2 + 2 + 2 + 1} = 2 m --1

= 69905 .

Увеличение размерности на 1 и уменьшение длин кодовых слов рангового кода привело к уменьшению мощности в ~ 6 . 2 х 10 ⁴ раз.

4. Верхние границы и реальные мощности МНП спредов

Зададим следующие параметры МНП кодов-спредов: n = mr + s , 5 = m , 0 < s <  ( m — 1). Вычислим мощность для различных параметров и сравним полученные значения с верхней границей подпространственных кодов для тех же параметров. В уравнении (5) положим 5 = m и получим мощность кода для выбранных параметров:

r 1                    „n„т

Мт,р = \Ст,р\ = У q(mr+s-im) + 1 = q---q+ 1

mzp mzp                         qm — 1

При s = 0 и, следовательно, n = rm мощность МНП спреда в уравнении (8) совпадает с верхней границей мощности , полученной в работе [9]:

^{n q} M wang =       ! •

При n = rm + s и s = 1 получим из уравнения (8)

qn—qm+i mzp — \ mzp\ — т і + ‘

В этом случае полученное выражение для мощности совпадает с верхней границей мощности , полученной в работе [7] M beut = ^ т — — ( q — 1)

При n = rm + 2 и, следовательно, s = 2 получим из (8)

q n ^— q ^{m +2}

mzp — \ mzp \ — m i ⁺ ‘

В работе [8] это выражение совпадает с верхней границей для мощности спредов при s >  2. В работе [22] с использованием этой оценки максимально возможное значение мощности представлено в виде суммы двух слагаемых. Первое слагаемое – это мощность МНП спреда, а второе слагаемое - это некоторая величина ү і :

q ⁿ — q ^{m + s}

M dr-fr <  q m _— 1 ^{+ 1 + ү 1} ’

где ү і = ( q ^s — L^J ) — 2, параметр Ө зависит от m и s таким образом:

2 ^{s — 1} — 1 ,

LӨJ =

₂ s- 1

₂ s- 1

— 2 ,

2 2 s—m— 3

^{— 1} ,

если 2 s < m + 2;

если 2 s = m + 2;

если 2 s > m + 2 .

Возьмём q = 2, m = 3 и s = 2, тогда ү і = 1 . Для этих параметров мощность МНП спреда равна M = 33, то есть на ү і = 1 меньше. Используя результаты работы пяти авторов [32], удалось довести мощность до верхней границы при n = 3 r + 2, r - любое, q = 2 в работе [22]. Путём полного перебора в работе [32] был построен подпространственный код для параметров r = 2, m = 3, s = 2, n = 8, который мы использовали в качестве последней компоненты в МНП спреде.

Увеличим размерность на 1, то есть m = 4, а остальные параметры q = 2, r >  2, n = 4 r + 2 и s = 2. В качестве верхней границы используем верхнюю оценку из работы [10]:

M Kurz

2 4 ^r +2 - 49

Теперь возьмём формулу для МНП спреда (8) для тех же параметров и увидим, что мощность МНП спреда совпадает с верхней границей (13).

Перейдём к новым оценкам верхних границ подпространственных кодов, полученным в работе [11]. В этой работе имеется две важные для нас теоремы. Здесь мы приведём их в нашей интерпретации и наших обозначениях.

Теорема 1. При 0 < s < m и m > q s верхняя граница мощности подпространственного

кода равна M hkk і =

q mr + s -q m + s + q m _— 1

q ^m - 1

Выполним условия этой теоремы 0 < s < m и m > q s и сравним мощность M mzp (8) с границей M HKK 1 (1). Увидим,что они совпадают. Коды, у которых мощность совпадает с верхней границей, называем оптимальными кодами.

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

Теорема 2. При m < qs и по-прежнему 0 < s < (m — 1) мощность подпространственного n m+s m кода mhkk2 =---qm-і--+ Y2, где γ2 вычисляется с помощью дополнительных параметров. Сравнение мощности МНП спреда при параметрах 0 < s < (m — 1) и m < qs с оценкой Mhkk2 показало, что при этих условиях МНП спред верхней оценки мощности подпространственного кода не достигает. Это впервые для рассмотренных случаев.

В теореме 2 предлагается вычислять два значения параметра ү 2 : ү 21 >  1 и ү 22 >  1. Далее, при оценке мощности выбирать наименьшее значение:

ү ₂₁ = р 2 m — 2(1 + 2 m +2 (2 m — 2 ^s )) 2 1 — 1 ,

ү 22 = Г ² s ^— 2^{(1 + 2} s ^{+2 (} m ^— s )) ² 1 ^{— 1} •

Мы считаем, что в этих условиях можем также использовать оценку Дрейка–Фримана [8], в которой добавка к мощности МНП спреда представлена параметром ү 1 = ( q s — L^J ) — 2 (12).

Как мы видим, в обеих теоремах не указаны оценки мощности при выполнении равенства m = 2 ^s . Проверим, в какую из теорем можно включить это соотношение. Зададим, например, значения m = 4 , s = 2, m = 8 , s = 3 и m = 16 , s = 4, и вычислим ү 21 , ү 22 и γ 1 по формулам (14), (15) и (12) соответственно. Вычислим мощность M _mz p МНП спреда при этих параметрах, добавим наименьшее из значений γ и получим верхнюю оценку M _up . Отношение п = M mzp оценивает эффективность МНП спреда.

Эффективность η = ^M _M ^m _u ^z _p ^p при m =2 ^s и n =2 m + s

Таблица 1

η	1 . 000	1 . 000	0 . 9999 ...	0 . 9999 ...	0 . 99999 ...
M mzp	65	4049	1048579	137438953473	1180591620717411303425
M up	65	4049	1048578	137438953473	1180591620717411303428
n =2 m + s	10	19	36	69	134
m	4	8	16	32	64
s	2	3	4	5	6
γ 21	5	3	7	15	31
γ 22	0	0	1	1	3
γ 1	1	3	7	15	31

Как видно из приведённых в табл. 1 значений дополнительного слагаемого γ : γ 21 ,γ 22 ,γ 1 , наименьшее значение имеет γ 22 , но оно равно нулю только для параметров m =4 ,s =2и m =8 ,s =4, в остальных случаях γ 22 ≥ 1. Это объясняет условие в приведённых выше теоремах из работы [25], выраженное знаком неравенства больше: m> 2 ^s (первая теорема), меньше: m< 2 ^s (вторая теорема), а не знаком больше-равно: m ≥ 2 ^s или меньше-равно: m ≤ 2 ^s соответственно приведённым здесь теоремам. В этих численных примерах мощности МНП спредов настолько велики по сравнению со вторым слагаемым – минимальным из значений γ 21 ,γ 22 ,γ 1 , что эффективность выражена большим количеством цифр 9 после нуля и точки. Поэтому можно считать, что практически эффективность равна η = 1 . 000 при условии m =2 ^s .

Теперь при выполнении условий m^s и 0 (m- 1) задаём параметры m, s, длину в виде n =2m + s и вычислим значения трёх величин γ1 , γ21 γ22. Выбрав наименьшее из этих значений, просуммируем с мощностью МНП спреда. Полученное значение используем в качестве верхней оценки и обозначим M_up. Эффективность МНП спреда оценим в виде отношения η = ^|M_|M^m_u^z_p^p_|^| . В табл. 2 приведены значения эффективности, мощности для заданных параметров и значения вспомогательных параметров γ .

Таблица2

Эффективность η = ^M _M ^m _u ^z _p ^p при m< 2 ^s и n =2 m + s

η	0 . 971	0 . 970	0 . 992	0 . 985	0 . 996	0 . 993	0 . 992	0 . 997
M mzp	33	129	257	513	513	1025	2049	1025
M up	34	133	259	521	515	1032	2066	1028
n =2 m + s	8	11	13	14	15	16	17	17
m	3	4	5	5	6	6	6	7
s	2	3	3	4	3	4	5	3
γ 21	1	4	3	8	2	9	18	3
γ 22	1	5	2	11	3	7	25	1
γ 1	1	4	3	10	3	8	17	3
M mzp	2049	4097	4097	8193	16385	8193	32769	524289
M up	2055	4112	4103	8207	16414	8208	32824	524296
n =2 m + s	18	19	20	21	22	20	23	34
m	7	7		8	8	7	8	15
s	4	5	4	5	6	6	7	4
γ 21	6	15	6	15	144	15	73	7
γ 22	7	22	6	20	51	54	106	2
γ 1	7	19	7	14	29	35	55	9

В табл. 2 представлены значения эффективности для случаев, когда выполняется условие m< 2s и длина определена в виде n =2m + s. Заметим, что при такой длине мы имеем всего две компоненты МНП-кода, причём первая из них – это SKK-код, а вторая компонента имеет одно кодовое слово в виде конкатенации нулевой и единичной матриц. Добавление такой компоненты незначительно меняет общую мощность. Так что вычисленное отношение мощности МНП-кода к верхней границе фактически в этом случае оценивает эффективность SKK-кода.

Анализируя данные, представленные в табл. 2, отмечаем следующее. При размерностях от m =3до m = 5 эффективность η = ^{| M} _{| M} ^m _u ^z _p ^p _| ^| меняется от 0 . 970 до 0 . 985, при m ≥ 6 эффективность η >  0 . 99. Дополнительное слагаемое γ тем больше, чем больше s . В то же время увеличение s при той же размерности увеличивает длину кодового слова, задаваемого по формуле n =2 m + s . Поэтому при одной и той же размерности m = 7 мощность МНП спреда равна |M _mzp | = 4097 при s =5и почти вдвое больше – |M _mzp | = 8193 при s =6. Эффективность η равна соответственно 0 . 996 и 0 . 998, то есть отличается в третьем знаке десятичной дроби.

Перейдём к случаю использования трёхкомпонентного МНП-кода, когда n =3 m + s . Составим аналогичную таблицу для этого случая.

Таблица3

Эффективность η = ^M _M ^m _u ^z _p ^p при m< 2 ^s и n =3 m + s

η	0 . 9966	0 . 9982	0 . 9998	0 . 9995	0 . 99994	0 . 99988	0 . 99988	0 . 999999
M mzp	289	2177	8449	16897	33281	66561	133121	132097
M up	290	2181	8451	16905	33283	66569	133138	132098
n =3 m + s	11	15	18	19	21	22	23	24
m	3	4	5	5	6	6	6	7
s	2	3	3	4	3	4	5	3
γ 21	1	4	3	8	2	9	18	3
γ 22	1	5	2	11	3	7	25	1
γ 1	1	4	3	10	3	8	17	3

Приведённые расчёты показали, что при условии m< 2 ^s мощность МНП спредов хотя и не достигает внешней границы, но находится близи её: отношение мощности к максимальному значению тем больше, чем больше длина. Например, при n = 11 эффективность η = 0 . 996552, а при n = 21 эффективность η = 0 . 999940.

Такие коды являются высоко эффективными кодами, так как показатель эффективности η >  0 . 99 при всех рассмотренных параметрах. Мощность близка к верхней границе, хотя незначительно от неё отличается. Мы называем эти коды субоптимальными подпространственными кодами.

5.    Заключение

Здесь были представлены подпространственные коды с максимальным кодовым расстоянием – МНП спреды. Мощность этих кодов при больших размерностях ( m >  2 ^s ) совпадает с верхней границей. Для случаев противоположного неравенства m< 2 ^s были проведены расчёты для ряда параметров: найдено отношение мощности кода к верхней границе η = ^{| M} _{| M} ^m _u ^z _p ^p _| ^| , которое определено как эффективность. Для всех рассмотренных случаев двухкомпонентного МНП-кода эффективность η >  0 . 9, а для трёхкомпонентного МНП-кода η >  0 . 99. При условии равенства m =2 ^s есть случаи совпадения мощности с верхней границей и есть также случаи небольшого отличия.

Таким образом, показано, что при m> 2 ^s МНП-коды являются оптимальными подпространственными кодами-спредами, а при m< 2 ^s эти коды названы субоптимальными подпространственными кодами-спредами.

При оценке эффективности были использованы верхние границы мощности подпространственных кодов-спредов, полученные в работах [7, 11].

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (Проект 15-07-08480-2017).