Содержание к диссертации
Введение
Глава 1. Конструкции кодов с малой плотностью проверок, основанных на матрицах перестановок 11
1.1. Введение 11
1.2. Общая структура проверочной матрицы случайного двоичного МПП-кода, основанного на матрицах перестановок 12
1.3. Алгоритм декодирования случайного кода Галлагера 16
1.4. Некоторые специальные конструкции двоичных МПП-кодов. основанных на матрицах перестановок 20
1.5. Результаты имитационного моделирования 51
1.6. Выводы к первой главе 53
Глава 2. Коды с малой плотностью проверок, основанные на системах Штейнера и матрицах перестановок 62
2.1. Введение 62
2.2. Системы троек Штейнера и код Хэмминга 63
2.3. Ансамбль кодов с малой плотностью проверок, основанных на системах троек Штейнера и матрицах перестановок 66
2.4. Ансамбль кодов с малой плотностью проверок, основанных на системах четверок Штейнера и матрицах перестановок 80
2.5. Результаты имитационного моделирования 84
2.6. Выводы ко второй главе 85
Глава 3. Проблемы реализации специальных конструкций кодов с малой плотностью проверок 95
3.1. Введение 95
3.2. Векторный алгоритм декодирования "распространения доверия "для двоичных МПП-кодов, основанных на матрицах перестановок 96
3.3. Векторный мажоритарный алгоритм декодирования для двоичных МПП-кодов, основанных на матрицах перестановок 102
3.4. Перспективы практического применения векторных декодеров 105
3.5. Построение проверочной матрицы МПП-кода из сверточного кода 106
3.6. Результаты имитационного моделирования при R = 0.8 и их анализ 109
3.7. Выводы к третьей главе 139
Заключение 141
Литература
- Общая структура проверочной матрицы случайного двоичного МПП-кода, основанного на матрицах перестановок
- Некоторые специальные конструкции двоичных МПП-кодов. основанных на матрицах перестановок
- Ансамбль кодов с малой плотностью проверок, основанных на системах четверок Штейнера и матрицах перестановок
- Векторный мажоритарный алгоритм декодирования для двоичных МПП-кодов, основанных на матрицах перестановок
Общая структура проверочной матрицы случайного двоичного МПП-кода, основанного на матрицах перестановок
В первой главе построены некоторые конструкции кодов с малой плотностью проверок, основанные на матрицах перестановок специального вида.
Для кодов, чья проверочная проверочная матрица состоит из циркулянт-ных перестановочных матриц (квазициклические коды), получено условие отсутствия цикла длины 4. Также приведено обобщение полученного условия на более широкий класс кодов. В соответствии с полученным условием, построены некоторые классы квазициклических кодов, минимальная длица цикла в проверочных матрицах которых равна 6, также построена проверочная матрица кода с минимальной длиной цикла 8.
Предложен способ построения проверочных матриц низкоплотностных кодов, основанных на полях Галуа. Основываясь на предложенном методе построения, дано альтернативное описание квазициклических кодов, а также построен новый ансамбль кодов с малой плотностью проверок, основанный на матрицах перестановок специального вида.
Для представленных кодовых конструкций с фиксированной скоростью R = 0.5 и итеративного алгоритма декодирования "распространения доверия "приведены результаты моделирования при передаче кодового слова с помощью двоичной фазовой манипуляции по каналу с аддитивным белым гауссовским шумом. 1.2. Общая структура проверочной матрицы случайного двоичного МПП-кода, основанного на матрицах перестановок
Структура проверочной матрицы случайного кода Галлагера В работе [1] Р. Галлагер впервые описал конструкцию кодов с малой плотностью проверок (МПП-кодов Галлагера) и предложил алгоритм генерации проверочной матрицы Н таких кодов. Проверочную матрицу Но МПП-кода длины щ можно записать как Но = ,111 ... 1,. Запишем диагональную блоч ную матрицу Нто с т проверочными матрицами Но на главной диагонали:
В данной работе мы будем использовать несколько иной подход, нежели предложенный Галлагером: в качестве основы для построения проверочной матрицы МПП-кода будут использоваться матрицы перестановок. Опишем способ построения такого ансамбля в общем виде: Пусть , , Є N, причем , ! . Рассмотрим группу Vm матриц перестановок размера х .
Выберем случайных матриц {Ру} С Vm, = 1, , = 1, . Потребуем так же, что если Р P&S) то = , = . Ясно, что такие условия выбора матриц Ру соответствуют урновой модели без возвращений. Построим проверочную матрицу Н размера х : Указанный выше способ построения матрицы Н гарантирует, что все матрицы в каждой строке и в каждом столбце будут различны. Так какР -квадратная матрица размера т х т, то размер Н - ml х тщ. Н определяет ансамбль (/,По)-регулярных (с постояннным весом столбца /, и с постоянным весом строки По) МПП-кодов длины п = щт, который мы обозначим д(/,По,т). Элементы ансамбля д(/,по,т) получаются путем выбора без возвращений матриц перестановок Р Є Vm, і = 1,2,... ,1, j = 1,2,... ,щ.
Произвольный код С Є д(/,По,т) мы назовем МПП-кодом, основанным на матрицах перестановок. Для кодов из ансамбля R(1, Щ, т) выполняется та же оценка для скорости, что и для кодов из ансамбля 8(1, щ,т), в то же время любая проверочная матрица, составленная из / 1 слоев, состоящих из матриц перестановок, имеет ранг не более чем ml — 1 + 1, то есть равенство в оценке 1.1 не достигается.
В то же время в работе [66] было доказано, что минимальное расстояние почти всех кодов из ансамбля ц(,о,) возрастает линейно с их длиной , в то же время из этого не напрямую не следует, что данный класс кодов при любых значениях и достигает границы Варшамова-Гилберта.
Согласно теореме Варшамова-Гилберта при достаточно большом не существует двоичного кода со скоростью , имеющего кодовое расстояние больше, чем расстояние, которое находится из уравнения
Данная таблица показывает, каким должно быть значение о, чтобы код имел возможность достигать границы Варшамова-Гилберта. С другой стороны, скорость так же связана с и . Легко заметить, что —, Vo, .
В данном разделе мы напомним классический алгоритм декодирования, предложенный Галлагером в [1]. Рассматриваемый декодер МПП-кодов ра ботает с представлением кода в виде фактор-графа, так же известного как граф Таннера [7]. Граф Таннера - это двудольный граф, состоящий из двух подмножеств вершин: вершин-символов (вершин-переменных) и вершин-проверок. Ребро соединяет вершину-переменную и вершину проверку в том случае, если соответствующая переменная (символ) входит в проверку.
Классический алгоритм декодирования Sum-Product, известный так же под названиями "Belief Propagation (алгоритм с распространением доверия) - алгоритм декодирования, являющийся алгоритмом обмена сообщениями на рассмотренном выше фактор-графе. Алгоритм получает на вход вероятности приёма символов, которые для двоичного случая передаются как отношения правдоподобия. Далее алгоритм итеративно выполняет вычисления на вершинах-символах и вершинах-проверках, передавая между ними сообщения, представляющие из себя по сути отношения правдоподобия данного символа (проверки), вычисленные для соответствующей проверки (символа) на основе всех остальных, кроме того, для кого производится вычисление. Таким образом, алгоритм представляет из себя циклическое выполнение итераций, содержащих три шага:
Некоторые специальные конструкции двоичных МПП-кодов. основанных на матрицах перестановок
Вначале мы построим некоторые ансамбли кодов с малой плотностью проверок, которые являются подансамблями д(/,По,?7г), не задаваясь вопросом о минимальной длине циклов в их проверочных матрицах. Далее же мы рассмотрим специальный ансамбль т. н. "квазициклических"МПП-кодов (и некоторое его обобщение), для которых сформулируем критерий отсутствия циклов длины 4 и построим некоторые примеры ансамблей с минимальной длиной цикла 6 и 8. Затем мы представим способ построения МПП-кодов, основанных на полях Галуа.
Каждой перестановке о # поставим в соответствие матрицу перестановок Ра . . Построим столбец Pi, состоящий из таких матриц, получим определяет ансамбль регулярных МПП-кодов Галлагера длины п = щт, который мы обозначим м{1-,п0іт)- Элементы ансамбля получаются путем случайного выбора числа Ъ\ : (&i,m) = 1, случайного выбора перестановки о" Є Sm, а так же случайных чисел &25 ЬПо, для которых выполяется 1.4. Указанный выше способ построения матрицы Нто гарантирует, что все матрицы в каждой строке и в каждом столбце будут различны (они все будут являться классами смежности).
Определение 1.4.2. Произвольный код С Є м(1,по,т) мы назовем МПП-кодом, основанным на смежных классах. определяет ансамбль регулярных МПП-кодов Галлагера длины п = щт, который мы обозначим ц/(/,По,?7г). Указанный выше способ построения матрицы Hw гарантирует, что все матрицы в каждой строке и в каждом столбце будут различны. Элементы ансамбля ц/(/,По,?7г) получаются путем выбора без возвращений матриц перестановок Pj Є Vm, г = 1, 2,..., по, обладающих свойствами (1)-(2).
Определение 1.4.3. Произвольный код С Є ц/(/,По,т) мы назовем МПП-кодом, основанным на матрице Вандермонда. w Р размера т хт. Пусть Pi,P2,... ,РПо Є Vm. Выберем /,по Є N, причем / п0, и набор из (/ — 1)по случайных (возможно с повторениями) чисел 0 Рассмотрим матрицу следующего вида:
Матрица Hs определяет ансамбль регулярных МПП-кодов Галлагера длины п = щт, который мы обозначим s(l,no,m). Элементы ансамбля s(l,no,m) получаются путем выбора без возвращений матриц перестановок
Приведем важный частный случай матриц, фигурирующих в определении 1.4.4. Определение 1.4.6. Под матрицей 1и размера тх т мы будем понимать матрицу h -кратного циклического сдвига строк (столбцов) единичнойт х т матрицы I.
Теперь мы дадим описание одного из наиболее важных и часто употребляющихся на практике ансамблей двоичных МПП-кодов: квазициклических МПП-кодов. Пусть їРі. - т х т матрица -кратного циклического сдвига, Щ- Построим I х щ матрицу Н следующего вида:
Так как размер 1Р - т х т, то размерность Н - ml х тщ. Н определяет ансамбль регулярных квазициклических МПП-кодов длины п = тщ. Обозначим этот ансамбль дс(/,По,ш). Элементы ансамбля получаются путем равновероятного выбора (возможно с возвращениями) матриц pij -кратных циклических сдвигов.
Определение 1.4.7. Произвольный код С Є gc(/,no,m) мы назовем квазициклическим МПП-кодом.
Очевидно, что данный ансамбль кодов является подансамблем (/, По, т): если в случае ансамбля Еа{1 щ т) "начальный"первый ряд матриц перестановок выбираются из всей группы "Рто, а нижние слои - суть случайные (частичные, длины т ) сдвиги верхнего слоя, то все элементы ансамбля gc(/,no,m) выбираются из одной подгруппы % С Vm. Очевидно, что \Н\ = т.
Данное упрощение, без потери корректирующей способности (как будет показано далее), позволяет существенно оптимизировать процедуру хранения проверочной матрицы. В самом деле, если для хранения любой проверочной матрицы вида 1.2 из ансамбля д(/,по,т) нам требуется тіщ _1 + log2 т\ бит, из ансамбля 3(1}щ}т) — щ(т + / — 1)_1 +log2mJ бит, то для описания проверочной матрицы кода из ансамбля дс(/,По,т) требуется всего Іщ _1 + log2 тп\ бит. Это очевидно следует из того, что для полного описания проверочной матрицы Hq необходимо хранить только 1щ элементов матрицы и размер m матрицы I. Таким образом, достигается почти ш-кратная экономия памяти по сравнению с МПП-кодами, основанными на произвольных матрицах перестановок. Циклы в квазициклических МПП-кодах В данном разделе мы сформулируем и докажем условие отсутствия циклов длины 4 в проверочной матрице квазициклических МПП-кодов. Для этого нам потребуется ввести вспомогательное определение. Определение 1.4.8. Произведением Адамара матриц А = (а ) иВ = (bij) назовем матрицу С = А о В = (аф ) Отметим, что для существования произведения Адамара матриц А = (dij) и В = (bij) требуется, чтобы они имели одинаковый размер.
Далее мы сформулируем элементарные утверждения о матрицах циклических сдвигов, которые понадобятся нам для дальнейшего анализа (предполагается, что матрицы циклических сдвигов имеют одинаковый размерт):
Ансамбль кодов с малой плотностью проверок, основанных на системах четверок Штейнера и матрицах перестановок
В разделе 1.4.1 мы использовали специальный класс перестановок (т. и. перестановок-умножений) для генерации проверочной матрицы регулярного (/, По) МПП-кода из ансамбля м(1, Щ-, те)- Вспомним, что числа 6j, учавству-ющие в построении ансамбля выбираются так, чтобы порядок каждого из них был больше /, каждое из чисел было взаимно просто с т и, кроме того, для них выполняется система 1.4. Матрица Идт полностью описывает ансамбль квазициклических МПП-кодов длины п = тщ, имеющих проверочную матрицу, который мы обозначим QCM(1, ПО,ТП). Очевидно, что QM(1, Щ,т) является подансамблем ансамбля дс(/,пО,т). Элементы ансамбля QCM(l-,nQ- m) получаются путем случайного выбора без возвращений чисел Ь\, Ь -, , Ьщ Є N, удовлетворяющих приведенным выше требованиям. Как и для ансамбля Ем{1, 0, т), указанный выше способ построения проверочной матрицы гарантирует, что все матрицы в каждой строке и каждом столбце будут различны (столбцы являются классами смежности).
Определение 1.4.9. Произвольный код С Є дсм( о, ) мы назовем квазициклическим МПП-кодом, основанным на смежных классах.
Теперь покажем, что матрица 1.15 не содержит циклов длины 4. В матрице iiqm зафиксируем любые 2 строки с индексами 1 i\ %2 / и любые 2 столбца с индексами 1 j\ 32 Щ, тогда матрица 1.12 примет вид:
Ансамбль квазициклических МПП-кодов, основанных на матрице Вандермонда Вновь обратимся к матрице 1.6, определяющей ансамбльw{hri0im)- Теперь в качестве т х т матриц Pi, Р2,... , РПо будем выбирать матрицы цик лических сдвигов L, определяет ансамбль регулярных квазициклических МПП-кодов длины п = щт, который мы обозначим Sqcw{h Щ,т). Элементы ансамбля QCW(1, По,т) получаются путем случайного выбора без возвращений матриц перестановок -P1 1 -Р2 1 Рпг, обладающих свойствами, указанными выше. Определение 1.4.10. Произвольный кодС Є gcw(/,no,m) мы назовем квазициклическим МПП-кодом, основанным на матрице Вандермонда. Покажем также, что минимальная длина циклов в проверочной матрице 1.16 не менее 6. Для этого зафиксируем в ней любые 2 строки с индексами 1 i\ %2 I к любые 2 столбца с индексами 1 Ji J2 Щ, тогда матрица 1.12 примет вид:
Матрицу, фигурирующую в теореме 1.4.3, можно использовать как проверочную матрицу низкоплотностного квазициклического МПП-кода, с другой стороны, как будет показано в главе 2, использование квазициклических МПП-кодов без циклов длины б и выше в составе некоторых кодовых конструкций приводит к строгому увеличению кодового расстояния в последних. . МПП-коды, основанные на полях Галуа
В данном разделе мы рассмотрим способы построения отображения элементов мультипликативной группы поля Галуа на группу матриц перестановок. Предложен метод, минимизирующий порядок симметрической группы. На основании полученных результатов построен ансамбль регулярных двоичных кодов с малой плотностью проверок на четность.
Предварительные результаты
Теоремой, позволяющей связать произвольную конечную группу Q порядка т с некоторой подгруппой симметрической группы Sm (а значит и с подгруппой группы матриц перестановок Vm), является теорема Кэли [17].
Теорема 1.4.4. Любая конечная группа (Q} о) изоморфна некоторой подгруппе % группы перестановок множества элементов этой группы. При этом каждый элемент g Є Q сопоставляется с перестановкой ттд, задаваемой тождеством 7rg(h) = g о h, где h - произвольный элемент группы Q.
Данная теорема говорит не только о существовании изоморфизма ф : Q ь-) Ц, С Sm, но и дает представление о его строении. Также хорошо известен следующий алгебраический факт: Теорема 1.4.5. Для любой перестановки ф Є Sm существует единственное (с точностью до порядка следования множителей) представление в виде
Также приведем формулировку китайской теоремы об остатках, которая потребуется нам для доказательства основной теоремы данного раздела. Теорема 1.4.6. Любое неотрицательное целое число п которое не превышает каждого из множителей модуля М = m\m i... nik можно однозначно восстановить если известны его остатки г І по этим модулям.
Построение изоморфизма GF (qm) и % С Sqm_i
Рассмотрим мультипликативную группу GF (qm) = {а, а2,..., aqm 2, aqm 1} поля Галуа GF(qm), где а - примитивный элемент поля. По теореме Кэ-ли, существует изоморфизм 0, ставящий в соответствие каждому элементу [5 Є GF (qm) перестановку тір Є Ті С Sn. Вначале рассмотрим случай, когда п = qm — 1. Поскольку «Sn = (qm — 1)! и GF (gm) = gm — 1, то l S I ""—— = (qm — 2)! Є Z, то такой изоморфизм ф существует. Прежде чем приступать к построению отображения, докажем теорему, которая утверждает, что для построения изоморфизма групп необходимо и достаточно знать, куда перейдет примитивный элемент поля.
Теорема 1.4.7. Пусть а Є GF (qm) - примитивный элемент поляСГ(дт). Тогда для построения ф : GF (qm) ь-» T-L С Sn необходимо и достаточно вычислить ф(а) = тта.
Доказательство. (Необходимость) Пусть известно, что ф(а) = 7га, где а -примитивный элемент поля. Пусть (3 - произвольный элемент мультипликативной группы поля, тогда 3 s Є N, такой, что (3 = as, таким образом ф(/3) = ф(сх8), так как ф - изоморфизм, то ф(/3) = (0(a))s, поэтому ф(/3) = 7Г . (Достаточность) Пусть известно отображение ф : GF (qm) ь-» % С Sn. Это равносильно тому, что V/3 Є GF (qm) известна такая перестановка жр: ф((3) = 7Г/3, в частности известна и перестановка 7га, такая, что ф(а) = 7га.
Векторный мажоритарный алгоритм декодирования для двоичных МПП-кодов, основанных на матрицах перестановок
А согласно теореме 2.3.1 и замечания 2.3.2 это означает, что минимальный вес кодового слова, полученного на данной конфигурации столбцов, не может быть меньше 8. Аналогично можно показать, что соотношения вида 2.3 не выполняются для любого цикла длины б в матрице Пр. Таким образом, кодовые слова веса б могут образовываться только на конфигурации из б столбцов h , ..., hj6 проверочной матрицы. Конкатенацией этих столбцов образуем матрицу Н = [h .. . hj6]. Очевидно, ни одна из строк полученной матрицы не может иметь нечетный вес. Так же очевидно, что вес никакой строки Hj не может быть равен 6. В самом деле, если вес хотя бы одной строки матрицы Hj равен 6, то по свойству системы троек Штейнера вес любой строки матрицы Hj, полученной из Hj удалением строки веса 6, равен 1 (в противном случае это бы означало появление цикла длины 4). Однако на такой конфигурации столбцов не могут образовываться кодовые слова веса 6.
В то же время из свойства, что любые 5 столбцов Hj являются линейно независимыми, а добавление оставшегося столбца приведет к появлению линейной зависимости, следует, что никакая строка Hj не может иметь вес 4. В противном случае, для того, чтобы избежать появления циклов длины 4, появлялось бы 2 строки веса 1.
Поясним последнее утверждение. Предположим что среди 6 выбранных столбцов найдутся 4 столбца, пересекающиеся по одной единице, и значит в Hj образуется строка веса 4. Без ограничения общности можно считать, что данное условие выполняется для столбцов hji; ..., hj4. Данное множество столбцов не может пересекаться больше ни в одной единице, в противном случае это бы означало наличие цикла длины 4. Поскольку вес каждого столбца должен быть равен 3, то столбец h должен пересекаться с hj5 и с hj6, причем пересечение должно быть по разным единицам, в противном случае образуется строка веса 3. Аналогичные условия выполняются и для столбцов hj2 и hj3. Таким образом, выбор единиц в столбцах h , hj2, hj3 полностью определяет столбцы hj5 и hj6. Но из последнего утверждения следует, что столбец hj4 веса 3 не может пересекаться ни с hj5, ни с hj6. В итоге образуются 2 строки веса 1.
Применяя рассуждения, использованные в теореме 2.3.1, и замечание 2.3.2, можно сформулировать следующую теорему:
Теорема 2.3.3. Рассмотрим кодовые слова веса 6 кода с проверочной матрицей Н. Им соответствуют всевозможные комбинации из6 линейно зависимых столбцов проверочной матрицы И. Если при расширении проверочной матрицы Н до матрицы Н описанной в разделе 4 процедурой, в каждой такой комбинации при замене единиц в столбцах матрицами pij -кратных циклических сдвигов хотя бы один цикл длины 8 перейдет в цикл большей длины, то минимальный вес слова, удовлетворяющего всем проверочным соотношениям, образованным такими столбцами, равен12.
Из теорем 2.3.1 и 2.3.3 следуют важные заключения. Следствие 2.3.1. Пусть кодовое расстояние d кода с проверочной матрицей Н равно 4. Расширим матрицу И матрицами pij -кратных циклических сдвигов до матрицы Н согласно процедуре, описанной в разделе 4. Тогда если в каждой комбинации из 4 линейно зависимых столбцов матрицы Н хотя бы один цикл длины 6 перешел в цикл большей длины, а в каждой комбинации из 6 линейно зависимых столбцов матрицы Н хотя бы один цикл длины 8 перешел в цикл большей длины, то минимальное расстояние кода с проверочной матрицей Н будет не менее 8.
Размер матрицы H4 можно сделать кратным А , заменив каждую единицу на произвольную t х /-матрицу перестановки Р , а каждый из нулей -на нулевую {t х )-матрицу Z . Обозначим результат такого преобразования матрицы Н4 матрицей Н4. Тогда матрица Н4 является низкоплотностной t(2m - 1) х А -матрицей с весом столбца равным 4.
Выберем целое число К, такое что 2т - 1 К ЛГ2. Составим матрицу Н4, выбирая произвольное if-элементное, 2т - 1 К N2 упорядоченное подможество множества столбцов матрицы Н4. К полученной матрице применим процедуру расширения, описанную в предыдущем абзаце. Построенная таким образом матрица Н4 имеет размер t(2m - 1) х N2t, вес каждого ее столбца равен 4.
Большинство результатов, справедливых для кодов из ансамбляEsTs(jn-, к естественным образом переносится на коды из ансамбляEsQs(jn-, K,t), поэтому в данном разделе большинство доказательств будет опущено. К сожалению, для кодов из ансамбля SSQS(, ,) достаточно сложно установить верхнюю границу для скорости , ввиду того, что теоретическая оценка по заданному в общем случае является достаточно трудной задачей. Поэтому мы приведем лишь частные случаи максимально достижимых скоростей для кодов из ансамбля SSQS(, ,) (SQS) И сравним их с максимально достижимыми скоростями кодов, чья проверочная матрица состоит из всех (3, 2т — 1) слов веса 3 кода T-L() (STS) И С веРхней границей для кодов из ансамбля SsTs(, ,) (STS)
Теперь определим условие строго увеличения кодового расстояния при замене каждой из единиц в матрице 4 на матрицы -кратного циклического сдвига.
Теорема 2.4.1. Пусть минимальное расстояние кода с проверочной матрицей Н4 равно 5. Используя метод, описанный в 2.3, расширимИ до матрицы Н4 матрицами ij-кратного циклического сдвига. Тогда, если в каждой линейной комбинации из 5 столбцов Н4 хотя бы один цикл длины 6 перейдет в цикл большей длины, то минимальное расстояние кода с проверочной матрицей Н4 будет не меньше 6. Доказательство. Для доказательства теоремы достаточно применить рас суждения, использованные при доказательстве леммы 2.3.4 для столбцов веса 4, а затем воспользоваться следствием 2.3.1.
Результаты имитационного моделирования Моделирование описанных в главе 2 кодов производилось методами имитационного моделирования с использованием среды MatLab. В качестве канала был выбран канал с аддитивным белым гауссовским шумом (АБГШ) и двоичной фазовой манипуляцией (BPSK). В качестве алгоритма декодирования был выбран описанный в разделе 1.3 итеративный алгоритм Sum-Product с "мягким"входом, работающий с представлением кода в виде двудольного графа Таннера. Максимальное число итераций ограничивалось 50.
На рисунках 2.3-2.6 представлены результаты моделирования МПП-кодов, основанных на системах троек Штейнера и матрицах перестановок, длин 2000, скорости = 0.5 из ансамблей STS(4, 2,68), STS(5, 2, 33), STS(6, 2,16), STS(7, 2,8). На рисунках 2.7, 2.8 приведено сравнение вероятностей ошибки на блок и на бит для различных конструкций МПП-кодов, основанных на системах троек Штейнера и матрицах перестановок.
На рисунках 2.9 - 2.11 представлены результаты моделирования МПП-кодов, основанных на системах четверок Штейнера и матрицах перестановок, длин « 2000, скорости = 0.5 из ансамблей SQS(6, 126,16), SQS(7, 254,8), SQS(8, 510,8). На рисунках 2.12, 2.13 приведено сравнение вероятностей ошибки на блок и на бит для различных конструкций МПП-кодов, основанных на системах четверок Штейнера и матрицах перестановок.
Рисунки 2.14, 2.15 представляют из себя общую сводку результатов, представленных на рис. 2.3 - 2.13: на них сравниваются вероятности ошибки на бит и на блок для кодов, основанных на системах троек и четверок Штейнера и матрицах перестановок.
Анализ результатов показывает, что при заданной скорости и длине кода, большинство конструкций МПП-кодов, основанных на системах троек Штейнера и матрицах перестановок (кроме кода, основанного на коде Хэмминга [127,120, 3] и матрицах перестановок) демонстрируют меньшую вероятность ошибки на блок и на бит при фиксированном отношении сигнал-шум на кодовый символ (g/o). Преимущество составляет 1.5 - 2 порядка. В то же время заметно, что кривые для кодов, основанных на системах четверок Штейнера и матрицах перестановок, имеют больший угол наклона, нежели кривые для кодов из ансамблей sTs(,,), что связано с меньшим весом столбца в проверочных матрицах последних.
