Подпространственные коды Габидулина - Боссерта

В 2000 году коллектив авторов - Алсведе, Кэй, Ли, Июнг - в работе [1] предложили принципиально новый подход к передаче сообщений по сети. Сеть связи можно рассматривать как конечный направленный граф, в котором узлы соединены одним или несколькими рёбрами - линиями связи. Узел без входных рёбер - это источник информации. Могут быть один или несколько получателей - конечных узлов. Предложено в качестве пакетов-сообщений использовать элементы конечного поля. На промежуточных узлах надо вычислять линейные комбинации пакетов и передавать их следующему узлу или получателю. На примере такого подхода авторы показали, что пропускная способность сети с таким сетевым кодированием увеличивается по сравнению с прежней системой, в которой на промежуточных узлах пакеты-сообщения принимаются, некоторое время хранятся в буфере и без изменений ретранслируюся дальше.

Следующий шаг в этом направлении был сделан Коэттером и Кшишангом в работе 2007 г. [2]. Они предложили использовать метрику подпространств. В работе [3] Силва, Коэттер и Кшишанг построили коды в этой метрике. В последствии с разрешения авторов эти коды были названы SKK-кодами по первым буквам фамилий авторов. В их конструкции, называемые лифтинговыми, были включены ранговые коды Габидулина [4]. Проблемы построения алгоритмов кодирования и декодирования потребовали проведения предварительных преобразований искажённых сообщений по методу исключения Гаусса. Эта задача подробно представлена в работе [5] 2010 года Габидулиным, Пилипчук, Боссертом. Здесь она сведена к нахождению ранговых ошибок и стираний строк и столбцов.

Кроме проблем защиты от ошибок существует важная проблема мощности кодов. Мощность подпространственного кода равна числу элементов кода, в данном случае подпространств. Чем больше мощность, тем больше скорость кода. В работе [6] Габидулина и Боссерта 2008 года было осуществлено некоторое увеличение мощности. Оно достигнуто за счёт объединения нескольких непересекающихся компонентных кодов. В эти коды, названные многокомпонентными, были включены дополнительные компоненты. ^Т1тобы избежать пересечений компонент, были введены так называемые нулевые префиксы. Вскоре эти коды были названы Многокомпонентными кодами с нулевым префиксом (МНП). В английском языке это переведено как Multicomponent zero prefix (MZP) codes.

Для оценки потенциальной мощности подпространственных кодов нужны теоретические оценки границ мощности. Этой важной проблеме уделяется большое внимание в научных исследованиях, в частности в работах [8-10].

Работа построена следующим образом. В разделе 2 приведены известные верхние оценки границ мощности подпространственных кодов постоянной и смешанной размерности. В разделе 3 показаны структуры многокомпонентных кодов Габидулина - Боссерта. В разделе 4 показан многокомпонентный код постоянной размерности. Доказана теорема о том, что при определённых условиях мощность этого кода равна максимальной величине, задаваемой верхней границей. В разделе 5 показан многокомпонентный код смешанной размерности, а также приведён алгоритм построения таких кодов. В разделе б приведены примеры кодов смешанной размерности. В таблицах указаны параметры и мощности каждого из кодов и оценки мощности по отношению к верхней границе. В разделе 7 выполнено сравнение мощностей кодов постоянной и смешанной размерностей. В разделе 8 подведены итоги.

2.    Верхние границы мощности подпространственных кодов

Сначала введём определение подпространственных кодов. Пусть GF(q) - конечное поле из q элементов, W = GF(q)ⁿ - n-метриковое пространство над полем F(q). Пусть W(п,т) - множество всех m-метриковых подпространств пространства W. которое называется т-грассманнианом, где т меняется от 0 до п. Подпространственный код - это множество подпространств из данного пространства. Подпространственное расстояние между двумя подпространствами U,V Е W определено следующим образом: d_sub(U,V ) = dim(U ^V )~dim(U QV ) = dim(U ) + dim(V)~2dim(U QV ), где U ^V минимальное пространство, которое содержит оба подпространства U,V, UQV - пересечение U,V, обозначение dimQ) - размерность (•). Если код состоит из элементов m-грассманниана с кодовыми подпространствами М, минимальным подпространственным расстоянием d = 25 и размерностью m, то он называется кодом постоянной размерности. Если он состоит из компонент с различными размерностями, то он называется кодом смешанной размерности.

Потенциальные возможности мощности кодов задаются границами мощности. Верхняя граница Aq(n,d,m) мощности подпространственных кодов постоянной размерности получена совместно четырьмя авторами - Венгом, Хингом, Сафави и Найни (Wang, Xing, Safavi и Naini [7]). Она имеет следующий вид:

A (n        ^ — W¹ - ¹)... (^qn-m+ — ^1}

^Aq^    ^m) =    (qm -    : '   - 1)... (q* - 1)

где n - длина кодового слова, d = 25 - подпространственное расстояние, m - размер-ноств. При фиксированной размерности m и кодовом расстоянии 5 длина кода n увеличивает мощноств. При заданной длине n и размерности m увеличение кодового расстояния 5 уменвшает максимально возможную мощность.

В работе [8] Хейнлейн (Heinlein), Киермайер (Kiermaier), Курц (Kurz) и Вассерманн (Wassermann) опубликовали таблицы подпространственных кодов постоянной размерности, а также привели некоторые коды смешанной размерности. Работы авторов Хонольда (Honold), Киермайера (Kiermaier) и Курца (Kurz) [9,10] описывают конструкции и границы мощности кодов смешанной размерности.

Верхняя граница кода смешанной размерности длины кодового слова n и подпространственного расстояния d имеет вид m=n-8

Aq(n,d) < 2+ ^ Aq(n,d,m), т=*

где в правой части, кроме числа 2, есть основное выражение Aq(n, d, m) под знаком суммы. Оно соответствует формуле (1). Индекс суммирования m меняется от m = 5 до m = n~5. Формулы (1) и (2) используем далее при оценке мощности многокомпонентных кодов. Далее в качестве верхней границы будем использовать обозначение Amax вместо Aq(n,d). Для каждого конкретного кода найдём отношение верхней границы к мощности нашего кода у^р| = ^ и назовём его показателем качества кода. Он определяет во сколько раз максимально возможная мощность кода может быть больше мощности конкретного кода.

3.    Многокомпонентные коды Габидулина — Боссерта

В работе [6] Габидулин и Боссерт разработали многокомпонентное семейство подпространственных МНП-кодов в виде объединения компонентных лифтинговых кодов и предложили в компонентах использовать различные размерности. В книгах Габидулина [11,12] введено дополнение: как задавать длины кодовых слов: длину кодового слова задавать в виде суммы длин всех порядков единичных матриц: n = mi + m2 + m3 + ... + m_s- 1 + m_s и при этом представлять в виде убывающей последовательности: mi >  m2 > ... >  m_s- 1 >  m_s, где mi - порядок единичной матриц!>i в лифтинговой конструкции Гй компоненты, s - число компонент. Приведём конструкцию МНП-кода из [11], которая имеет вид объединения непересекающихся кодов X = Xi UX2 UX3 U ... UX_S. Попарное пересечение кодов должно быть нулевым. Этот многокомпонентный код таков:

Xi = {X :X = [Imi xi ]|^i GMi}

X2 = {X : X = [0m2 Im2 Ж2]|Ж2 е M2}

)                                                                                                          (3)

X_s-i = {X : X = [omi+m2+-^+ms-2 Im_a-1 x_s-i ]K-i е M_s-i}

X_s = {X : X = [om- ^ma Im_a ]}

Здесь Oj - матрица с нулевыми элементами, у которой i столбцов и j строк, Mi - ранговый код, состоящий из матриц mi х (n-mi) из GF (q), с ранговым расстоянием d_r1 < min (mi, n -mi), M2 - ранговый код, состоящий из матриц m2 х (n — mi — m2) из GF(q) с ранговым расстоянием d_r2 < min(m₂,n - m_i -m2), M_s-i - ранговый код, состоящий из матриц m_s-i х (n - mi - ... - m_s-i) из GF (q), с ранговым расстоянием d_ra_ 1 < min (m_s-i, n - mi - ... - m_s_ 1) = 5. Очевидно, что Xi О Xj = 0.

Код имеет следующие характеристики:

• 1)    мощность X = \С| = =i₌₁ \Ci\-,

• 2)    подпространственное расстояние d(X) = min(minj=j (mi + mj), min1s-1(2d_ri));

• 3)    длина кодового слова n = m1 + m₂ + ... + m_s.

4.    Многокомпонентный код постоянной размерности

Ниже показана схема построения многокомпонентного кода постоянной размерности.

(I_m М_с 1)

(0 I_m М_С2 )

(0 0 I_m М_С3 )

• (0......... 0 I_m Мс—)

• (0 ...............0 Im) •

Здесь I_m - единичная матрица порядка m, M_Ci - ранговая матрица i-й компоненты (i = 1, 2,..., s — 1), s - число компонент. Последовательности нулей обозначают матрицы, в которых элементы только нули. Для оценки мощности кода постоянной размерности используем формулу из [11]:

s-1

\М \ = ^ q^k^ +1,                            (4)

i=1

где полагаем m = 6, ki = m~6 + 1 = 1, ni = n-im, n = sm. Здесь и далее q = 2.

Следствие. Запишем мощность в виде суммы мощности первой компоненты |Mi| и мощности дополнительных компонент \М_а\ и докажем, что мощность первой компоненты больше мощности суммы дополнительных компонент:

|М1| > |Ма|.

Доказательство. Для указанных в формуле (4) параметров мощность первой компоненты равна |М1 \ = 2^(n-m), мощность дополнительных компонент равна

|Ма| = 2(n~2m) + 2(n~3m) + ... + 2m + 1 =

(2 (n-m)_ 1)

2m — 1

Неравенство (5), то есть |М1| > \М_а\, верно пр и условии 2^m >  2, а это условие очевидно, так как в наших кодах m > 2.

Теорема 1. Мощность кода постоянной размерности равна верхней границе мощности (1) при условии, что размерность m равна минимальному ранговому расстоянию 6.

Доказательство. Используя формулу (4), запишем полную мощность МНП-кода, состоящего из s компонент при значениях параметров m = 6 и n = 6s:

О £s_-|      nⁿ

\Мс\ = 2^S(S- 1) + 2²⁾ + ... + 2* + 1 =       =                        (6)

правая часть полученной формулы (6) совпадает с правой частью неравенства (2) при 6 = man = 6s для любого значения числа компонент s. Это означает, что мощность кода постоянной размерности \М_С\ равна верхней границе. В частности, для параметров s = 2 и m = П = 6 верхняя граница есть

, „ , .     ~ Д -      2 — 1

\ ^МС2 \ = ^{2 2 + 1} = Д

• ²                2 2 — 1

5.    Многокомпонентный код смешанной размерности

В 2009 году на конференции ISIT-09 Габидулин и Боссер представили семейство подпро-странственнв1х кодов, где показали, как превратитв постоянной размерности МНП-кодв1 в коды с разивши размерностями [13]. В [11] работа [13] была дополнена заданием соотношений между размерностями компонент. Имеются примеры [14,15] подпространственных кодов постоянной и смешанной размерности. В работе [15] приведен пример подпространственного кода двух разных размерностей, где код получен с помощвю трёхкомпонентного МНП-кода. В работу [16] включён алгоритм построения кодов смешанных размерностей, а также доказана теорема о максимальной границе мощности для МНП-кода постоянной размерности.

Схема построения кода смешанной размерности:

(Imi Мт1)

(0 1т2 Мт₂ )

(0 0 1тз Мт₃ )

• (⁰......... ^{0 I}m_a-i ^Мт_а-1 )

• (⁰ ...............^{0 1}т_а ) •

Здесь 1_т - единичная матрица порядка mt (i = 1, 2, ...,s), М_т - i-я ранговая матрица (г = 1, 2,..., s — 1), 0 - нулевая матрица, у которой все элементы нули.

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

S-1

|М| = ^ q^ +1,                          (7)

t=i где n = 2s-1 S, mt = 2^, kt = 2^ — S + 1 (i = 1, 2,..., s — 1), ms-1 = ms = S. Равенство mt = ni обеспечивает максимальную мощность для каждой из компонент.

Приведём алгоритм построения кода смешанной размерности. Он состоит из б шагов.

Шаг 1. Задаём минимальное ранговое расстояние S. Удвоенное его значение d = 2S задаёт подпространственное расстояние.

Шаг 2. Задаём равными порядки единичных матриц, соответствующих последней и предпоследней компонентам: m_s-i = m_s = S.

Шаг 3. Задаём число компонент s.

Шаг 5. Определяем длину кодового слова как сумму вычисленных параметров: n = m1 + m2 + ... + m_s-1 + m_s.

Шаг 6. Строем МНП-код, используя схему выше.

Теперь подсчитаем характеристики. Найдём мощность построенного кода с помощью формулы (7). Подсчитаем вычислительную сложность: одно деление ^, вычисление логарифма s = log j для нахождения числа компонент, s операций сложения для нахождения значений kj, s умножений для получения к{П{, s вычислений экспоненты и s сложений для вычисления суммы мощностей всех компонент. Такую сложность алгоритма, состоящего из пяти шагов полагаем небольшой. Результат - построенный код с заданными параметрами смешанной размерности. Для оценки качества нашего кода подсчитаем отношение р = ]М|' Построенный код называем Подпространственным Смешанной Размерности Габидулина - Боссерта кодом (ПСР Г-Б), в английском переводе Sabspace Mixed Dimtnsion Gabidulin - Bossert code (SMD G-B).

6.    Примеры кодов смешанной размерности (параметрыи характеристики)

В этом разделе, в таблицах даны примеры конкретных кодов с указанием параметров и оценок мощности. Напомним обозначения: s - число компонент, d - подпространственное расстояние, mi - порядок i-й единичной матрицы (i = 1, 2,..., s), р = ^J|, |М1| - мощность первой компоненты, А - суммарная мощность дополни тельных компонент, звёздочкой «*» обозначены коды наибольшей мощности.

Таблица!

s = 5, m₄ = m5 = 2, р = 4.4, S = 2

п	m1	m2	m3	М1	А	^шах
22	11	4	3	1,298 х 1033	2,097 х 106	5,685 х 1033
24	12	5	3	5,445 х 1039	2, 6844 х 108	2, 386 х 1040
26	13	6	3	9,134 х 1046	3,4360 х 1011	4, 003 х 1047
26	13	5	4	9,134 х 1046	4, 2950 х 1010	4, 003 х 1047
28	14	7	3	6,130 х 1054	4, 3980 х 1012	2, 688 х 1055
28	14	6	4	6,130 х 1054	1, 0995 х 1012	2, 688 х 1055
30	15	7	4	1, 646 х 1063	2,1475 х 1013	7, 213 х 1063
32*	16	8	4	1, 767 х 1072	7, 0576 х 1015	7, 745 х 1072

Т а б л и ц а 2

d = 4, s = 6, m5 = т.6 = 2, ту = 4.4, 5 = 2

п	т-1	m2	m3	т4	И	M1	Лтах
32	16	5	4	3	1, 7592 х 1015	1, 7668 х 1072	7, 7446 х 1072
34	17	6	4	3	3, 6030 х 1016	7, 5886 х 1081	3, 3263 х 1082
36	18	7	4	3	7, 3787 х 1019	1, 3037 х 1092	5,1146 х 1092
38	19	8	4	3	1,1116 х 1022	8, 9590 х 10102	3, 9271 х 10103
40	20	9	4	3	3, 9485 х 1025	2,4626 х 10114	1, 0795 х 10115
42	21	10	4	3	6, 3825 х 1028	2, 7077 х 10126	1,1914 х 10127
44	22	И	4	3	1, 298074 х 1033	1,1909 х 10139	5, 2200 х 10139
38	19	6	5	4	3, 8935 х 1018	8, 9590 х 10102	3, 9271 х 10103
40	20	7	5	4	3, 2231 х 1022	2,4626 х 10114	1, 0795 х 10115
42	21	8	5	4	2, 7588 х 1022	2, 7077 х 10126	1,1869 х 10127
44	22	9	5	4	2, 2824 х 1022	1,1909 х 10139	5, 2200 х 10139
46	23	10	5	4	1, 6615 х 1035	2, 2095 х 10152	9,1831 х 10152
48	24	И	5	4	1, 3611 х 1039	1,4742 х 10166	6,462 х 10166
50	25	12	5	4	1,1150 х 1043	4,1495 х 10180	1, 8189 х 10181
52	26	13	5	4	9,1344 х 1046	4, 6719 х 10195	2, 0479 х 10196
42	21	7	6	4	1, 3428 х 1024	2, 7077 х 10126	1,1869 х 10127
44	22	8	6	4	3, 6913 х 1028	1,1909 х 10139	5, 2200 х 10139
46	23	9	6	4	5,1923 х 1033	2, 2095 х 10152	9,1831 х 10152
48	24	10	6	4	8, 5071 х 1037	1,4742 х 10166	6,462 х 10166
50	25	И	6	4	1, 3938 х 1042	4,1495 х 10180	1, 8189 х 10181
52	26	12	6	4	2, 2836 х 1046	4, 6719 х 10195	2, 0479 х 10196
54	27	13	6	4	3,7414 х 1050	2,1041 х 10211	9, 2229 х 10211
56	28	14	6	4	6,1300 х 1054	3, 7903 х 10227	1, 6661 х 10228
46	23	8	7	4	4, 0565 х 1031	2, 2095 х 10152	9,1831 х 10152
48	24	9	7	4	1, 3292 х 1036	1,4742 х 10166	6,462 х 10166
50	25	10	7	4	4, 3556 х 1040	4,1495 х 10180	1, 8189 х 10181
52	26	И	7	4	1,4272 х 1045	4, 6719 х 10195	2, 0479 х 10196
54	27	12	7	4	4, 6768 х 1049	2,1041 х 10211	9, 2229 х 10211
56	28	13	7	4	1, 5325 х 1054	3, 7903 х 10227	1, 6661 х 10228
58	29	14	7	4	5, 0217 х 1058	2, 7312 х 10244	1,1972 х 10245
60	30	15	7	4	1, 6455 х 1063	7, 8722 х 10261	3,4507 х 10262
50	25	9	8	4	3,4028 х 1038	4,1495 х 10180	1, 8189 х 10181
52	26	10	8	4	2, 2301 х 1043	4, 6719 х 10195	2, 0479 х 10196
54	27	И	8	4	1,4615 х 1048	2,1041 х 10211	9, 2229 х 10211
56	28	12	8	4	9,5781 х 1052	3, 7903 х 10227	1, 6661 х 10228
58	29	13	8	4	6,2771 х 1057	2, 7312 х 10244	1,1972 х 10245
60	30	14	8	4	4,1138 х 1062	7, 8722 х 10261	3,4507 х 10262
62	31	15	8	4	2, 6960 х 1067	9, 0760 х 10279	3, 9784 х 10280
64*	32	16	8	4	1, 7668 х 1072	4,1856 х 10298	1, 8347 х 10299

Т а б л и ц а 3

d = 6, s = 4, 5 = 3, ту = 5.4

п	т1	m2	И	Mi	'^-тах
20	10	4	4, 096 х 103	1, 2089 х 1024	6,676 х 1024
22	11	5	2,6214 х 105	0, 6338 х 1030	3, 502 х 1030
24*	12	6	1,6777 х 107	1, 3292 х 1036	7, 347 х 1036

В таблице 3 представлены коды, у которых подпространственное расстояние увеличено до d = 6. В предыдущих таблицах было d = 4. Зависимость от плппы кодового слова п остаётся такая же, как в предыдущих случаях. Но при одной и той же длине уменьшается мощность. В таблице 1 для п = 22 пр и d = 4 мощность равна 1, 298 х 10³³, а в данном случае при d = 6 мощность равна 0, 6338 х 10³⁰, то есть уменьшилась более чем в тысячу раз. Изменилось отношение между верхней границей и мощностью кода. Оно увеличилось до значения г) = 5.4, то есть мощность в это число раз ниже максимально возможной величины, определяемой верхней границей (2).

Т а б л и ц а 4 d = 8, s = 4, г = 11, тз = т₄ = 5 = 4

п	т1	m2	А	М1	4 _ ^тах
32*	16	8	1, 0995 х 1012	4,1138 х 1062	6, 7334 х 1063
30	15	7	4, 2950 х 109	1, 5325 х 1054	1, 7633 х 1055
28	14	6	1, 6777 х 107	2, 2836 х 1046	2, 6275 х 1047
26	13	5	6, 5536 х 104	1, 3611 х 1039	1, 566 х 1040

В таблице 4 приведены параметры и мощности четырёх построенных кодов, один из которых с длиной п = 32 имеет наибольшую мощность. Сравнивая мощности кодов для той же длины п = 32 в табл. 2, видим, что увеличение подпространственного расстояния сильно уменьшило мощность и увеличило отношение максимальной границы к нашей мощности до значения г = 11- Но при одном и том же подпространственном расстоянии показатель качества кода г не менялся при всех длинах. Этот показатель зависит только от подпространственного расстояния.

Т а б л и ц а 5

d = 4, 6, 8,10,12, s = 3

п	5	d	т1	m2 = тз	г	А	М1	^тах
7	2	4	3	2	6,22	4	256	1591,733
8*	2	4	4	2	3,93	5	4, 096 х 103	1,6123 х 104
12*	3	6	6	3	5,41	9	1, 6777 х 107	9, 0992 х 107
16*	4	8	8	4	11,47	17	1, 0995 х 1012	1, 2609 х 1013
20*	5	10	10	5	36,26	33	1,1529 х 1018	4,1808 х 1019
24*	6	12	12	6	167	65	1, 9343 х 1025	3, 2338 х 1027

В таблице 5 записаны коды, у которых самое малое значение параметра s = 3 и всего две разные размерности. Здесь одновременно с длиной кодового слова меняется подпространственное расстояние. Увеличение длины увеличивает мощность, увеличение подпространственного расстояния уменьшает мощность. Для построения этих кодов при заданных значениях 5 достаточно задать только параметр ту В соответствии с нашим алгоритмом его значение должно быть больше 5, но не больше d = 25. В данной таблице построено 5 кодов для значений d от 4 до 12. Они отмечены звёздочкой, их компоненты вносят наибольший вклад в общую сумму мощности.

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

7.    Сравнение мощностей кодов постоянной и смешанной размерностей

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

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

\М1\ » (s- 1)|Мс|.

Учитывая формулы (4) и (7), вычислим мощности кодов постоянных и смешанных размерностей и подставим в формулу (8). Кроме того, учтём, что значение (s — 1) = log у при вычислении двоичного логарифма округляем до ближайшего сверху целого числа. Этим мы увеличиваем правую часть неравенства (8):

2(2-“)2 » log(^)2(Z-“)Z,                                    (9)

о где а = 5-1.

Утверждение 1. Знак неравенства в формуле (9) усиливается при увеличении значения п. Считаем знак двойного неравенства правильным, если соблюдается знак обычного неравенства для показателей степени.

В наших кодах наименьшее число компонент s = 3, найменьшее п = 8. Зададим 5 = 2 и подставим эти значения в неравенство (9). Получаем: левая часть есть 2¹², правая часть есть 2222 = 24. Левая часть в 28 раз больше правой части. В приведённых примерах для значения п = 8 мы учитывали суммарную мощность дополнительных компонент.

Увеличиваем число компонент, пусть s = 4 и соответственно п = 16. Проверяем неравенство. В левой части 256, в правой части 214. Отношение этих величин равно 242. Увеличение длины п увеличило отношение приведённых величин, что подтвердило приведённое выше утверждение.

Пусть теперь 5 = 3. Наименьшая длина п = 12. Получаем в левой части неравенства значение 224, в правой части - 25. Отношение равно 219. Неравенство (9) подтверждается и при увеличении минимума рангового расстояния. Приведённое рассмотрение позволяет при оценке полной мощности смешанного кода использовать мощность первой компоненты, по крайней мере при п > 8.

Используя мощность первой компоненты в качестве полной мощности кода, найдём отношение мощности кода смешанной размерности к коду постоянной размерности. Это отношение обозначим у(п,5) = |щ.

Следствие 1. При условии, что кодовое расстояние 5 смешанного кода равно размерности т кода постоянной размерности, отношение мощностей у(п, 5) = |щ равно

У (п,5) =

2 2(2-5+1) (25 — 1)

(Ю)

2п — 1

Здесь в качестве мощности кода смешанной размерности используем мощность первой компоненты этого кода, то есть |М1| = 2z⁽z^—5+1), _{а в} качестве мощности кода постоянной размерности используем полную мощность \М_С\ = 2 Z -1 ■

В таблицах 6 и 7 приведены значения у(п, 5), вычисленные по формуле (10), для различных кодовых длин п и подпространственных расстояний d = 25, одинаковых для обоих кодов. ( S_c - число компонент кода постоянной размерности, S_m - число компонент кода смешанной размерности).

Т а б л и ц а б d = 4, (5 = 2), у = 4,4

7 (п,5)	п	\ М с \	|М1|	Sc	Sm
3.299 х 1012	16	2.1845 х 104	7.3058 х 1016	8	4
1.234 х 1063	32	1.4317 х 109	1.767 х 1072	16	5
6.808 х 10219	64	6.489 х 1018	4.189 х 10238	32	6

Т а б л и ц а 7

d = 6. (5 = 3). г] = 5,4

^(п,8)	п	\мс\	^1\	Sc	Sm
2.869 х 104	12	585	1.678 х 107	4	3
5.546 х 1029	24	2.397 х 106	1.3329 х 1036	8	4
2.185 х 10145	48	4.021 х 1013	8.787 х 10158	16	5

Рассматривая приведённые в таблицах отношения мощностей кодов смешанной и постоянной размерности у(п, 5), видим, что при одинаковвш для обоих кодов параметрах п и 5 мощноств кода смешанной размерности много болвше, чем мощноств кода постоянной размерности.

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

Т а б л и ц а 8

Показатель качества ] (з = 3, п = 8, 12, 16, 20, 24; d = 4, 6, 8, 10, 12)

п 5 d г ^1\ max 8 2 4 3.93 4.101 х 103 1.6123 х 104 12 3 6 5.41 1.6777 х 107 9.0992 х 107 16 4 8 11.47 1.0995 х 1012 1.2609 х 1013 20 5 10 36.26 1.1529 х 1018 4.1808 х 1019 24 6 12 167 1.9343 х 1025 3.2348 х 1027 длина и, следовательно, мощность при том же подпространственном значении. Сравнение мощности кодов смешанной и постоянной размерности показало, что мощность кодов смешанной размерности многократно превышает мощность кодов постоянной размерности при одинаковых значениях длин кодовых слов и одинаковом подпространственном расстоянии. Рассмотренные подпространственные коды предназначены для применения в случайном сетевом кодировании.