close

Вход

Забыли?

вход по аккаунту

?

Оптимальные линейные коды и критическая проблема для матроидов.

код для вставкиСкачать
УДК 510
ОПТИМАЛЬНЫЕ ЛИНЕЙНЫЕ КОДЫ
И КРИТИЧЕСКАЯ ПРОБЛЕМА ДЛЯ МАТРОИДОВ
© 2011 С. А. Гизунов
докт. техн. наук, профессор,
gsa_sci@rambler.ru
Курский НИИ Министерства обороны РФ
Данной статьей завершается определенный этап в исследованиях, посвященных
изучению свойств псевдоматроидов и полуматроидов, порожденных отображениями
матроидов. На основе полученных результатов предлагается решение проблемы
построения всех неизоморфных оптимальных линейных кодов для достаточно широкого
диапазона значений параметров.
Ключевые слова: матроид, линейный код, оптимальный код, критическая
проблема.
Обозначим через Vn пространство всех двоичных векторов длины
n . Нетрудно
показать, что линейная зависимость между векторами порождает на множестве
матроид
M (Vn ) .
Vn
Этот матроид в определенном смысле можно считать аналогом
S , | S | = n . Аналогия
состоит в том, что если в матроиде B( S ) любое подмножество A ⊆ S является
флатой ранга rB ( S ) ( A) = | A | и 1 ≤ | A | ≤ n , то в матроиде M (Vn ) флатами будут
любые векторные подпространства размерности k ,1 ≤ k ≤ n . В частности, коточки в
матроиде M (Vn ) , или гиперплоскости, это векторные подпространства размерности
n − 1. Напомним, что отсюда следует (см. [6]) , что для любого векторного
подпространства X ⊆ Vn размерности k всегда найдется n − k гиперплоскостей
H1, H 2 ,..., H n−k , таких, что X = H1 ∩ H2 ∩ ... ∩ H n−k .
Векторное подпространство X размерности k называется линейным (n, k ) кодом с расстоянием d + 1, если χ (ν ) ≥ d + 1 для всех векторов ν ∈ X , где
χ (ν ) – вес Хемминга двоичного вектора ν ∈Vn . Оптимальным называется такой
линейный код, для которого при заданных значениях параметров n и d значение
параметра k максимальное. Такое значение параметра k для оптимального кода
будем обозначать через ψ (n, d ) . Подчеркнем, что определение параметра ψ (n, d )
свободного матроида
B( S ),
определенного на множестве
является одной из основных проблем алгебраической теории кодирования.
Применительно к данному контексту для подмножества
векторов
V (n, d ) ⊆ Vn вида V (n, d ) = {v ∈Vn χ (v ) ≤ d } критическая проблема (см. [6])
состоит в нахождении минимального количества h(n, d ) гиперплоскостей, имеющих
МАТЕМАТИЧЕСКИЕ НАУКИ
нулевое пересечение с множеством векторов V (n, d ) . Покажем, что критическая
проблема в этом случае тесно связана с вышеупомянутой проблемой кодирования.
Утверждение 1. Величины ψ (n, d ) и h(n, d ) связаны соотношением
ψ (n, d ) + h(n, d ) = n .
(1)
H1 , H 2 ,..., H h ( n ,d ) – минимальное множество
гиперплоскостей в Vn , таких, что H1 ∩ H 2 ∩ ... ∩ H h ( n ,d ) ∩ V ( n, d ) = ∅ . Тогда
множество векторов X = H1 ∩ H 2 ∩ ... ∩ H h ( n ,d ) есть векторное подпространство
размерности n − h(n, d ) , следовательно, по определению n − h(n, d ) ≤ ψ (n, d ) ,
а значит, h(n, d ) ≥ n −ψ (n, d ) .
Обратно. Пусть Y векторное подпространство в Vn размерности ψ (n, d ) ,
такое, что Y ∩ V (n, d ) = ∅ . Тогда найдется n −ψ (n, d ) гиперплоскостей
H1 , H 2 ,..., H n −ψ ( n ,d ) , для которых Y = H1 ∩ H 2 ∩ ... ∩ H n −ψ ( n ,d ) . Отсюда, и
опять же по определению, получаем неравенство h(n, d ) ≤ n −ψ (n, d ) , что, с
учетом вышесказанного, и доказывает равенство (1). W
Рассмотрим матроид M ∈M ( S ) . Для заданного целочисленного параметра
d , d ≥ 1 , подмножество A ⊆ S называется d -независимым в матроиде M , если
1) | A | ≥ d ;
2) из условий B ⊆ A и | B | = d следует, что B ∈F M .
Предположим, что | S | = n , и определим подсемейство подмножеств
S (n, d ) ⊆ 2S вида S (n, d ) = { A ⊆ S | A | ≤ d }. В этих обозначениях
Доказательство. Пусть
справедливо следующее утверждение.
Утверждение 2. Проблема построения оптимальных линейных кодов
тождественна проблеме нахождения бинарных матроидов
M ∈N ( S )
максимального ранга
rM ( S ) = ψ (n, d ),
таких, что множество
независимым в соответствующих дуальных матроидах
S
будет
d-
M * ∈N ( S ) .
Доказательство. Пусть для некоторого бинарного матроида
M ∈N ( S )
S будет d -независимым в соответствующем дуальном матроиде
M ∈N ( S ) . Так как подмножество A∈ F M * , если | A | ≤ d , то
S (n, d ) ∩ R M * = ∅ . Следовательно, для любого цикла D ∈ R M * справедливо
неравенство | D | ≥ d + 1. Пусть циклы D1 , D2 ∈ R * . По аксиоме для циклов
M
множество
*
бинарных матроидов,
D1 ⊕ D2 = ∑ D ,
D ∈ R M * . Поскольку в
| D1 ⊕ D2 | ≥ d + 1. Отсюда следует,
где циклы
последней сумме циклы не пересекаются, то и
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Гизунов С. А. Оптимальные линейные коды и критическая проблема для матроидов
что
выполняется
равенство
{∑ ⊕ D D ∈ R
M*
} ∩ S (n, d ) = ∅ .
Бинарный
M ∈N ( S ) изоморфен векторному матроиду, порождаемому двоичной
матрицей размера rM ( S ) × n , ненулевые элементы строк которой являются циклами
из множества R * . Таким образом, из последнего равенства следует, что
M
построенный по этой матрице линейный код будет (n, rM ( S )) -кодом с расстоянием
d + 1. Если ранг матроида rM ( S ) = ψ (n, d ) максимален, то и построенный код
будет оптимальным. W
матроид
В статье [5] предложен алгоритм построения всех неизоморфных бинарных
матроидов из множества N ( S ) . Отметим, что данный алгоритм позволяет строить
цикловую структуру не только всех неизоморфных бинарных матроидов, но и только
таких неизоморфных бинарных матроидов, для которых заданы ограничения на длину
циклов. Для этого достаточно на этапах 1 и 2 алгоритма ограничиться только
удовлетворяющими соответствующим ограничениям матроидами M k −1 и размерами
подмножеств, порождающих их G -факторы. Понятно, что такой подход за счет
уменьшения общей трудоемкости позволяет строить специальные неизоморфные
бинарные матроиды для множеств S достаточно большой мощности и, учитывая
утверждение 2, решить, таким образом, проблему построения всех неизоморфных
оптимальных линейных кодов для широкого диапазона значений параметров n , k и
d.
Ниже приведены результаты подсчета количества неизоморфных бинарных
матроидов для различных значений n, n ≤ 22, длина циклов дуальных матроидов
которых не меньше
d=3
2
3
4
5
6
7
6
1
7
3
d + 1, где 3 ≤ d ≤ 8.
8
7
4
9
13
12
5
10
21
33
24
4
11
31
74
92
34
2
12
44
150
311
249
43
2
8
13
59
275
902
1429
623
47
14
77
471
2331
6840
7342
1535
1
49
9
d=4
2
3
4
5
6
7
1
8
1
9
4
10
9
2
11
16
11
1
12
26
36
14
13
38
91
92
15
14
53
195
424
282
11
15
71
373
1490
2921
1011
6
8
d=5
2
3
4
5
6
16
92
654
4328
19669
31010
4019
1
9
1
10
3
11
7
1
12
14
7
1
13
23
24
7
14
35
67
47
6
15
50
156
248
98
5
16
68
320
1031
1249
185
17
89
592
3484
11859
8575
МАТЕМАТИЧЕСКИЕ НАУКИ
7
3
8
368
1
d=6
2
3
4
5
6
7
8
11
1
12
4
13
9
1
14
17
7
1
15
28
27
7
1
16
42
80
48
7
17
59
194
307
95
3
18
80
408
1497
1901
113
2
19
104
773
5669
26431
19043
84
1
d=7
2
3
4
5
6
7
8
12
1
13
3
14
7
1
15
14
4
1
16
24
16
5
1
17
37
50
23
5
18
54
133
131
76
2
19
74
301
688
450
30
1
20
98
611
3091
6907
1855
27
1
d=8
2
3
4
5
6
14
1
15
4
16
9
17
17
2
18
29
14
19
44
53
7
20
63
151
91
3
21
86
361
735
183
22
113
749
4070
7907
248
Суммируя результаты, полученные в этой и в предыдущих статьях [1–5], можно
выделить следующие основные моменты.
В категории матроидов и их отображений каждый матроид M ∈M ( S ) можно
рассматривать как результат канонического отображения B( S ) → M . Каноническое
отображение, как и любое строгое отображение, факторизуется на элементарные
отображения. Элементарные отображения, в свою очередь, однозначно определяются
некоторыми модулярными сечениями семейства флат или линейными сечениями
семейства коточек соответствующих факторов свободного матроида B( S ) .
Гипотетически, таким образом, любой матроид из множества M ( S ) определяется как
некоторая последовательность модулярных сечений семейства флат свободного
матроида. Напомним, что построить матроид – это значит описать его, например,
цикловую структуру, семейство баз или коточек. Проблема состоит в том, что системы
аксиом упомянутых выше однозначно описывающих матроид семейств подмножеств
как раз для построения матроидов не пригодны. Другими словами, с их помощью
можно только проверить, является ли заданный набор подмножеств множества S
семейством тех же циклов, баз или коточек некоторого матроида из множества
M ( S ) . То есть в собственно системах аксиом не содержится отличной от реализации
метода перебора процедуры построения таких наборов подмножеств.
Подчеркнем, что именно этот момент и делает трудноразрешимой задачу
перечисления всех, в том числе и неизоморфных, матроидов в множестве M ( S ) даже
для множеств S относительно небольшой мощности. Вместе с тем сам факт
возможности описания матроидов через последовательность модулярных сечений или
модулярных фильтров свободного матроида B( S ) переводит проблему построения
матроидов из множества
M (S )
в область анализа свойств соответствующих
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Гизунов С. А. Оптимальные линейные коды и критическая проблема для матроидов
модулярных сечений или фильтров. При этом, очевидно, необходимо абстрагироваться
от аксиоматизации модулярных сечений, как некоторого подмножества флат матроида,
которое строится на основе общих систем аксиом.
Введенное нами понятие псевдоматроидов, порожденных элементарными
отображениями матроидов [2], и является тем инструментом, который позволяет
изучать свойства модулярных фильтров с иных, отличных от классических, позиций.
Семейство циклов псевдоматроида, порожденного элементарным отображением
Ф ,Y
M ⎯⎯⎯
→H
M , H ∈M ( S ) , совпадает с множеством минимальных
элементов модулярного фильтра ФM , а семейство баз, соответственно, с множеством
коточек из семейства K M , не принадлежащих модулярному сечению Y M . Таким
образом, совокупность всех элементарных факторов любого матроида M ∈M ( S )
матроидов
однозначно описывается соответствующим семейством псевдоматроидов. В то же
время необходимо отметить, что аксиоматически задать это семейство
псевдоматроидов, как некоторую совокупность алгебраических объектов, порожденных
матроидом M , в общем случае не удается. Например, при факторизации Хиггса
семейства циклов и баз псевдоматроида совпадают соответственно с множествами
R H и B H матроида H и не выражаются через аналогичные структуры матроида
M . При верхнем усечении, наоборот, эти семейства совпадают с множествами B M и
K M матроида M и не определяют матроид H . Вместе с тем исследование свойств
псевдоматроидов как самостоятельных элементов категории матроидов и их
отображений позволило получить ряд новых результатов общетеоретического плана.
Например, при канонических отображениях B( S ) → M цикловая структура лифта
Хиггса матроида
M ∈M ( S ) выражена в явном виде через семейство циклов R M .
[3] введено новое для теории матроидов понятие G -отображений –
В работе
элементарных отображений определенного вида между бинарными матроидами из
множества N ( S ) . Рассматривается частный случай псевдоматроидов, а именно
полуматроиды, порожденные G -отображениями бинарных матроидов из множества
N ( S ) . Характерным отличием полуматроидов от общего случая как раз и является
возможность аксиоматически однозначно задавать упомянутое ранее семейство
псевдоматроидов, порожденных любым бинарным матроидом. Нами доказано, что для
любого бинарного матроида
M ∈N ( S ) всегда существует факторизация
канонического отображения B( S ) → M на G -отображения [4]. Иными словами,
все бинарные матроиды могут быть построены, так же как и в общем случае, с
помощью некоторой последовательности полуматроидов. Однако в показано, что в
отличие от псевдоматроидов соответствующая процедура не только не является
реализацией метода перебора, но и позволяет строить в явном виде цикловую
структуру соответствующих G -факторов [5]. Более того, применение аппарата
полуматроидов дало возможность предложить алгоритм построения всех
неизоморфных бинарных матроидов из множества
3
S
N ( S ) трудоемкостью O( S 3 )
операций, что автоматически означает решение проблемы перечисления неизоморфных
бинарных матроидов для множества S достаточно большой мощности.
МАТЕМАТИЧЕСКИЕ НАУКИ
В настоящей статье данный алгоритм видоизменяется для построения только
неизоморфных бинарных матроидов с заданными ограничениями на их цикловую
структуру. Этот факт, с учетом соответствующего уменьшения общей трудоемкости
алгоритма, позволяет реально построить все неизоморфные оптимальные линейные
коды для достаточно широкого диапазона значений параметра | S | = n .
Наконец, доказано [3], что для любого бинарного матроида совокупность всех
его аксиоматически определенных полуматроидов совпадает с множеством всех G факторов, порожденных соответствующими G -отображениями. Это, в свою очередь,
означает, что семейство всех аксиоматически заданных полуматроидов, порожденных
бинарными матроидами из множества N ( S ) , можно рассматривать как некоторую
самостоятельную алгебраическую структуру, функторно связанную с категорией
бинарных матроидов и их отображений.
В качестве итога следует подчеркнуть, что введенный нами аппарат
псевдоматроидов [2] и полуматроидов [3], может служить основой для дальнейшего
изучения свойств категории матроидов и их отображений.
Библиографический список
1. Гизунов С. А., Лямин В. Н. Сечения матроидов // Ученые записки: электронный
журнал Курского государственного университета. 2010. № 2. URL: http://scientificnotes.ru/pdf/014-2.pdf (дата обращения: 13.03.2011).
2. Гизунов С. А., Лямин В. Н. Псевдоматроиды, порожденные отображениями
матроидов.
3. Гизунов С. А., Лямин В. Н. Полуматроиды, порожденные G -отображениями
бинарных матроидов.
4. Гизунов С. А., Гречкин А. О., Лямин В. Н. G-факторизация канонических
отображений.
5. Гизунов С. А. Неизоморфные бинарные матроиды.
6. Welsh D. J. A. Matroid Theory., London, Acad. Press., 1976, 433 p.
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Документ
Категория
Без категории
Просмотров
7
Размер файла
1 883 Кб
Теги
оптимальное, коды, критических, матроидов, линейный, проблемы
1/--страниц
Пожаловаться на содержимое документа