Комбинированный метод построения многокомпонентных сетевых кодов

Рассмотрим К_ц — копечш>е поле из q элементов. Построим нал Ку п-мерное векторное пространство Ку и обозначим через Л(п) множество всех его подпространств. Подпространство У из Л(п), имеющее размерность к 6 п, будет представлять собой совокупность q^k векторов длины п из Ку.

Подпространство У можно рассматривать как линейную оболочку над к векторами из Ку или, что эквивалентно, над матрицей размера к х п с элементами из Ку. Таким образом, каждая матрица V размерности к х п над полем К_у однозначно задает некоторое к-мерное поппрострапство У из Д(п). Однако каждое п<улпрострапство из Л(п) может иметь несколько порождающих его матриц: умножение матрицы V на невырожденную матрицу Т размерности к хк даст матрицу V = TV размера к х п, задающую то же подпространство, что п матрица. V.

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

• •    Первый справа, ненулевой элемент каждой строки равен 1. Он называется ведущим элементом.

е Каждый ведущий элемент является единственным ненулевым элементом в своем столбце.

• •    Ведущий элемент следующей строки всегда расположен правее ведущего элемента предыдущей строки.

• •    На остальные элементы матрицы ограничений не накладывается. Они называются свободными элементами.

Ниже приводится пример матрицы размером 4 х 8 в приведенной ступенчатой форме (сим волами «*» обозначены свободные элементы):

/ 0 1 * 0

0 0 0 1

0 0 0 0

0 0 0 0

0 * 0 * 0*0* 1*0* 001*

Между к-мерными подпространствами из Л(п) и матрицами размера к х п над К_ц в приведенной ступенчатой форме можно установить взаимно однозначное соответствие.

Расположение ведущих элементов матрицы размером к х п в приведенной ступенчатой форме можно описать с помощью мультииндекса Т = {^1,^2,..., ik }, определяемого как набор целых чисел, соответствующих номерам столбцов, в которых находятся ведущие элементы всех к строк, начиная с первой. Еще один способ описания расположения ведущих элементов — с помощью двоичного индекс-вектора г длины п, который содержит 1 в тех своих компонентах, номера которых соответствуют номерам столбцов матрицы с ведущими элементами, и 0 в остальных элементах.

К примеру, матрица размером 4 х 8 из приведенного выше примера содержит ведущие элементы во втором, четвертом, пятом и седьмом столбцах. Она будет описываться мультииндексом Т = {2,4, 5, 7} и индекс-вектором г = (0,1, 0,1,1, 0,1, 0).

Число свободных элементов зависит от мультииндекса, соответствующего матрице в приведенной ступенчатой форме. Для матрицы размером к х п с мультииндексом Т = {іі,І2,..., ik} число свободных элементов будет равно

/ = /k,n^(Т) = ^кп --^ ” ^{— (І}1 + ^і2 + • • • + ⁱk ).                    (2)

При этом количество различных матриц с одним и тем же мультииндексом Т (а значит, и количество соответствующих им подпространств) будет равно q^y.

2.    Коды над подпространствами

Пусть Ы и У — два произвольных подпространства Л(п). Между ними можно ввести расстояние, называемое расстоянием Грассмана [1]:

d_Sub(U, У) = dim(W U У) - dim(W П У).

Пусть U имеет расмерность т и задается порождающей матрицей V размером тхп. ;а У имеет размерность к и задается порождающей матрицей V размером кхп. Тогда расстояние Грассмана между этими подпространствами можно вычислить следующим образом:

([ VD

— т - к.

В случае подпространств равной размерности (т = к) расстояние d_sub будет четным для любых U п У.

С использованием расстояния Грассмана вводится понятие кодов над подпространствами. Подпространственным [п, М, d_sub, к]-кодом называется множество к-мерных подпространств Л(п), содержащее М элементов, причем расстояние Грассмана между любой парой подпространств не меньше d_sub.

Подпространственные коды находят широкое применение в теории случайного сетевого кодирования [2-4]. Важной задачей при построении подпространственных кодов является максимизация их мощности М при фиксированной исправляющей способности, определяемой расстоянием d_sub.

Расстояние Грассмана тесно связано с ранговым расстоянием, используемым при построении ранговых кодов [1,5]. Пусть подпространства Ы и У размерности к, заданные матрицами V ii V. имеют мультшшдексы Ту 1і Ту. а также вектор-иидексы гу 11 гу.

Для иллюстрации связи с ранговыми кодами введем понятие подматрицы ведущих элементов. Для матрицы V в приведенной ступенчатой форме совокупность ее столбцов, содержащих ведущие элементы, называется подматрицей ведущих элементов и обозначается U[. Совокупность оставшихся столбцов называется подматрицей свободных элементов п обозначается Uy. Заметим, что Uy содержит все свободные элементы матрицы V. Далее возможны два случая.

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

d_sub(U, У) = 2rank

(I UI)

2* 2.....*(Щ])

—

2k =

= 2k + 2rank([Uy — Ру ]) — 2k = 2nmk([Uy — Ру ]).

В промежуточных выкладках использован тот факт, что для подпространств размерности k ранг матрицы ведущих элементов в точности равен k. Отметим, что итоговое вы ражение в точности соответствует удвоенному ранговому расстоянию между матрицами свободных элементов Uy и Vy.

Таким образом, для подпространств внутри одного мультииндекса задача построения кода максимальной мощности при заданном подпространственном расстоянии dsub сво дится к построению рангового кода максимальной мощности с ранговым расстоянием drank   dsub/2'

Рассмотрим теперь случай различных мультииндексов Тц и Ту. В этом случае количе

[ UI

ство линейно независимых столбцов в матрице элементов в векторе гц V гу . Следовательно, не меньше, чем количество ненулевых

d_Sub(W , У) = 2rank

([ и])

— 2k >  2(гц V гу ) — 2k =

= 2(2k — гц Л гу) — 2k = 2k — 2гц Л гу = гц ф гу = dham(гц; гу), где dham обозначает расстояние в хэмминговой метрике между двоичными вектор-индексами матриц.

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

Теперь задачу построения подпространственных кодов можно декомпозировать на две составляющие: сначала нужно построить в хэмминоговой метрике код постоянного веса из вектор-индексов с минимальным расстоянием dh_am = d_sub, а затем для каждого вектор-индекса построить в соответствующем подпространстве вложенный ранговый код на подматрице свободных элементов с минимальным расстоянием d_ran^ = d_sub/2.

Кодовые слова подпространственного кода, соответствующие одному вектор-индексу, называют принадлежащими одной кодовой компоненте. Код, содержащий кодовые слова из нескольких кодовых компонент, называется многокомпонентным кодом.

Для мощности многокомпонентых подпространственных кодов с параметрами n, k, d_rank = d_sub/2 существует верхняя граница [6]:

М 6

n k — drank + 1

k k  drank + 1

,

где

Г n 1 = (qⁿ — 1)(qⁿ — q) ... (qⁿ — q^s 1)

^s (q^s — i)(q^s — q)...(q^s — q^s-1)"

Рассмотрим некоторые примеры алгоритмов построения подпространственных кодов и конкретные примеры известных конструкций.

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

Исторически первой конструкцией подпространственных кодов, использующей ранго вые коды в качестве подкодов внутри одной компоненты, является код Сильвы-Кеттера-

Кшишанга (СКК-код) [7]. Для подпространств Д(п) размерности к используется только одна кодовая компонента с мультииндексом Т = {1, 2,..., к}. Подматрица свободных элементов при этом имеет размеры к х (п — к) и состоит только из свободных элементов. Для параметров п = 8, к = 4 матрица этого кода имеет вид

⎜0010

*  *  *  *\

*  *  **

*  *  **

*  *  *  *у

Мощность СКК-кода может быть найдена следующим образом [1]:

М = |

q(n—k")(k—d_rank +1), дЦп-к—1_га„_к+1'),

если п > 2к;

если п < 2к.

(Ю)

СКК-код используется в качестве первой компоненты во всех конструкциях многокомпонентных кодов и дает компоненту с наибольшей мощностью. Однако суммарная мощность у любой многокомпонентной конструкции превосходит мощность СКК-кода.

В конструкции Габидулина-Боссерта [8] используется подпространственное расстояние dsub = 2к — максимально возможное для подпространств размерности к. В такой конструкции матрицы кодовых компонент в приведенной ступенчатой форме получаются из матри цы СКК-кода путем добавления нулевых префиксных матриц. Код Габидулина-Боссерта с параметрами п = 8, к = 4 будет состоять из двух компонент:

⎜0100

⎜0010

⎛0000

⎜0000

****

* * * *

****

****

1 0 0 0⎞

0 0 1 0 ⎟ 0001

(И)

Эти коды для значений п, кратных к, достигают верхней границы мощности [8]. Однако ограничение на d_sub = 2к существенно уменьшает свободу разработчика при выборе параметров проектируемого кода.

Более гибкой с точки зрения допустимых параметров кода является конструкция Габидулина-Пилипчук [1], использующая для поиска мультииндексов, соответствующих кодовым компонентам, комбинаторные блок-схемы. В качестве подкодов внутри кодовых компонент в этой конструкции используются ранговые коды с ограничениями на кодовые символы. Такие подкоды достигают границы Синглтона и позволяют использовать те же алгоритмы кодирования и декодирования, что и для классических кодов с максимальным ранговым расстоянием [1].

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

В работах Этзиона и Зильберштейна [10,11] для поиска кодовых компонент используется полный перебор по всем двоичным векторам длины п с хэмминговым весом к. Двоичные векторы при этом предварительно сортируются в лексикографическом порядке. Это позволяет отказаться от блок-схем и дает полную свободу в выборе параметров многокомпонентного кода. Однако этот алгоритм также не предлагает универсальный способ определения мощности ранговых подкодов.

В данной работе описан подход, совмещающий преимущества методов Габидулина-Пилипчук и Этзиона-Зильберштейна. Для поиска кодовых компонент используется перебор по всем двоичным векторам, а в качестве подкодов используются ранговые коды с ограничениями на информационные символы. При этом для ранговых подкодов используется универсальный алгоритм определения мощности, позволяющий автоматизированно строить коды с большим числом компонент. Дополнительной особенностью метода является то, что поиск по двоичным векторам осуществляется с помощью «жадного» перебора: компоненты выбираются не в лексикографическом порядке, а в порядке уменьшения своей мощности. Новый метод позволяет построить коды, совокупная мощность компонент которых в ряде случаев превосходит ранее известные конструкции с теми же параметрами.

4.    Новый метод построения многокомпонентных подпространственных кодов

На первой стадии предлагаемого метода для кода с параметрами п, к, d_sub формируется список из всех двоичных векторов с длиной п и хэмминговым весом к. Количество таких векторов равно С-. Для программной реализации построения этого списка удобно использовать алгоритм Нараяны.

На второй стадии каждый вектор г из полученного списка рассматривается в качестве индекс-вектора матрицы размером к х п в приведенной ступенчатой форме. По восстановленной из вектора матрице V определяется ее матрица свободных элементов Vy. Расположение свободных элементов в этой матрице используется для определения мощности рангового подкода, который можно разместить в соответствующей V кодовой компоненте.

Алгоритм определения мощности подкода с ранговым расстоянием d_rank = d_subp2 следующий. Вычисляется d_rank — 1 — число проверочных символов рангового подкода. Фиксируется горизонтальное расположение символов рангового подкода (в строках матрицы Vy). Определяется количество свободных элементов в строке матрицы Vy с номером d_rank — 1 оно равно размерности рангового подкола N. Определяется гь — общее количество свободных элементов в строках матрицы Vy с номерами от d_rank до min{N, к}.

Мощность рангового подкода при горизонтальном расположении символов равна Сң = q'" ■ Аналогичная процедура повторяется для вертикального расположения символов рангового подкода (в столбцах матрицы Vy) и определяется мощность рангового подкода для этого случая: С_у = q^ty . Итоговая мощность рангового подкода определяется как тах{Сь,С_у }.

На третьей стадии используются полученные ранее списки вектор-индексов и мощностей соответствующих им подкодов длиной С-. На этой стадии осуществляется «жадный» перебор компонент с максимальной мощностью и добавление их к строящемуся многокомпонентному коду. Первым добавляется СКК-код, имеющий максимальную мощность среди всех компонент. Далее из оставшихся ищется вектор-индекс с максимальной мощностью. Если он находится на хэмминговом расстоянии не менее d^_am = d_sub от каждого из уже добавленных к коду вектор-индексов, то он также добавляется к коду и изымается из списка. В противном случае ищется вектор-индекс со следующей по убыванию мощностью рангового подкода и также проверяется на минимальное расстояние до уже сформированного подпространственного кода.

Поиск прекращается и код объявляется построенным в тот момент, когда любой из оставшихся вектор-индексов находится на расстоянии, меньшем dh_am от какого-либо вектор-индекса из добавленных к коду.

5.    Примеры новых кодовых конструкций

Рассмотрим пример использования нового метода для кода с параметрами п = 7, к = 3, d_sub = 4. Список всех двоичных векторов длины п с хэмминговым весом к (их количество равно С7 = 35) имеет вид

{1110000, 1101000, 1100100, 1100010, 1100001, 1011000, 1010100, 1010010, 1010001, 1001100, 1001010, 1001001, 1000110, 1000101, 1000011, 0111000, 0110100, 0110010, 0110001, 0101100, 0101010,      (13) 0101001, 0100110, 0100101, 0100011, 0011100, 0011010, 0011001, 0010110, 0010101, 0010011, 0001110, 0001101, 0001011, 0000111}. Рассмотрим алгоритм определения мощности ранговых подкодов на примере вектор- индекса г = {0011010}. Соответсвующая ему матрица в приведенной ступенчатой форме:

0 0 10 * 0 * \

V =   0 0 0 1 * 0 *   .

000001*

Количество кодовых символов рангового подкода равно d_rank — 1 = d_sub(2 — 1 = 1. Для горизонтального расположения символов рангового подкода количество свободных элементов в строке с номером d_rank — 1 равно 2, то есть размерность рангового подкода N = 2. Общее количество свободных элементов в строках с номерами от d_ran^ = 2 до min{N, к} = 2 равняется 2. С'ледователыю. Л = 2 и С = q} = q².

Рассматривая аналогично вертикальное расположение, получаем N = 3 и г_у = 2, что дает С_у = qy = q². Окончательно мощность рангового подкода равна max{C}, С_у } = max{q², q²} = q².

Повторяя аналогичные действия для остальных индекс-векторов, получаем список из С7 = 35 мощностей кодовых компонент: {q⁸, q⁷, q⁶, q⁵, q⁴, q⁶, q⁵, q⁴, q³, q⁴, q³, q², q², q, q⁰, q⁶, q⁵, q⁴, q³, q⁴, q³, q², q², q, q⁰, q³, q², q², q, q, q⁰, q⁰, q⁰, q⁰, q⁰}-

В качестве первой компоненты выбираем СКК-код с мощностью q⁸ (его вектор-индекс первый в списке). Следующим по мощности подкодом обладает второй вектор-индекс — его мощность равна q⁷. Однако он находится на хэмминговом расстоянии 2 от вектор-индекса СКК-кода, что меньше требуемого d}_am = d_sub = 4. Первым в списке по убыванию мощностей подкодов, удовлетворяющим требованию на минимальное расстояние, является 10-й вектор-индекс (мощность равна q⁴). Его мы и добавляем к коду.

Продолжая поиск вектор-индексов по описанной процедуре, получаем многокомпонентный код из 7 компонент со следующими мультииндексами: 11 = {1, 2, 3}, 12 = {1,4, 5}, 13 = {2,4, 6}, 14 = {3,4, 7}, 15 = {2, 5, 7}, 16 = {3, 5, 6}, І7 = {1, 6, 7}. Его мощность равна М = q⁸ + q⁴ + q³ + q² + q + q + 1. Верхняя граница для мощности при тех же параметрах равна M_max = q⁸ + q⁶ + q⁵ + q⁴ + q³ + q² + 1. Этот код совпадает с кодом, построенным в работе [1] для тех же параметров, отличаясь лишь порядком мультииндексов.

Рассмотрим теперь код с параметрами п = 13, к = 4, d_sub = 6. Описанный метод позволяет построить для этих параметров многокомпонентный код со следующими мультииндексами:

11 = {1, 2, 3,4}. І2 = {1, 5, 6, 7}. 13  = {2, 5, 8, 9}- 2  = {3, 6, 8,10}. Z5  = {4, 7, 8,11}.

26 = {3, 7, 9,12}. I7 = {4, 5,10,12}. 18 = {4, 6, 9,13}. Z9 = {1, 9,10,11}. Z_w = {2, 6,11,12}.

211 = {2, 7,10,13}. 112 = {3, 5,11,13}. 113 = {1, 8,12,13}.

Мощность такого кода равна М = q18 + q12 + q8 + q7 + q6 + q4 + 2q3 + 3q2 + q + 1. В работе [1] для тех  же  параметров был построен код  с  мощностью q18 + q12 + 2q6 + 2q5 + 3q4 + 2q3 + q2 + 1. Таким образом, новый метод позволяет улучшить ранее известную конструкцию. Верхняя граница для мощности такого кода равна Mmax = q18 + q15 + q14 + q12 + q11 + q10 + q9 + q8 + q7 + q6 + q4 + q3 +1

В завершение рассмотрим код с параметрами п = 31, к = 3,dsub = 4 для размерности базового поля q = 2. Этот код состоит из 155 компонент, его мощность при построении по описанному методу равняется М = 81955583110556320 кодовых слов. Верхняя граница составляет Mmax = 109802047904403264 кодовых слова. Отношение фактической мощности к верхней границе составляет примерно 0,746.

Отметим также, что предложенный метод построения для d_sub = 2k совпадает в методом Габидулина-Боссерта.

6.    Вывод

В работе предложен новый метод построения многокомпонентных сетевых кодов, сочетающий в себе «жадный» перебор мультииндексов в лексикографическом порядке, а также использование ранговых подкодов с ограничениями на информационные символы в качестве подкодов внутри компонент. Предложен универсальный метод построения подкодов с известной мощностью для любых конфигураций матриц свободных элементов.

Приведены примеры новых кодов, которые в некоторых случаях превосходят по характеристикам ранее известные конструкции. Для них определена фактическая мощность и осуществлено сравнение с верхней границей, которой при определенных параметрах эти коды достигают.