Специальные конструкции кодов с малой плотностью проверок

• Автор: Иванов, Федор Ильич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 151 с. : ил.

Содержание
Введение

Обзор литературы

Глава 1. Конструкции кодов с малой плотностью проверок, основанных на матрицах перестановок

1.1. Введение

1.2. Общая структура проверочной матрицы случайного двоичного

МПП-кода, основанного на матрицах перестановок

1.3. Алгоритм декодирования случайного кода Галлагера

1.4. Некоторые специальные конструкции двоичных МПП-кодов,

основанных на матрицах перестановок

1.5. Результаты имитационного моделирования

1.6. Выводы к первой главе
Глава 2. Коды с малой плотностью проверок, основанные на системах Штейнера и матрицах перестановок
2.1. Введение
2.2. Системы троек Штейнера и код Хэмминга
2.3. Ансамбль кодов с малой плотностью проверок, основанных на
системах троек Штейнера и матрицах перестановок
2.4. Ансамбль кодов с малой плотностью проверок, основанных на
системах четверок Штейнера и матрицах перестановок
2.5. Результаты имитационного моделирования
2.6. Выводы ко второй главе
Глава 3. Проблемы реализации специальных конструкций ко-

дов с малой плотностью проверок
3.1. Введение
3.2. Векторный алгоритм декодирования "распространения дове-
рия"для двоичных МПП-кодов, основанных на матрицах перестановок
3.3. Векторный мажоритарный алгоритм декодирования для двоичных МПП-кодов, основанных на матрицах перестановок
3.4. Перспективы практического применения векторных декодеров
3.5. Построение проверочной матрицы МПП-кода из сверточного

3.6. Результаты имитационного моделирования при Я — 0.8 и их
анализ
3.7. Выводы к третьей главе
Заключение
Литература

Введение
Актуальность работы Активное развитие вычислительной техники и информационных технологий, наблюдаемое в настоящий момент, приводит к все более стремительному усилению требований, предъявляемых к скорости и качеству передачи информации. Одним из основных критериев качества передачи является вероятность принять ошибочные данные.
Для исправления ошибок при передаче данных по каналу связи используют помехоустойчивые коды. На практике одним из важнейших критериев при выборе той или иной кодовой конструкции является наличие быстрых и эффективных алгоритмов алгоритмов кодирования и декодирования, а также возможности эффективного (экономного) использования памяти, необходимой для хранения кодовой конструкции. Двоичные коды с малой плотностью проверок (МПП-коды), впервые предложенные Р. Галлагсром в 1960 гощу, удовлетворяют приведенным выше требованиям. Однако "случайность" рассматриваем ого Галлагсром кода затрудняет использовать его в большинстве практических приложений ввиду достаточно большой сложности реализации. В связи с этим рядом исследователей, таких как Т. Ричардсон, Д. Маккей, М. Фоссориер, Э. Габидулин, М. Эсмаэли было предложено использовать матрицы перестановок для генерации проверочных матриц МПП-кодов. Данный подход позволяет оптимизировать как процедуры хранения матриц, так и алгоритмы кодирования и декодирования. Кроме того К. LU. Зигангировым было доказано, что для почти всех кодов, проверочная матрица которых состоит из случайных матриц перестановок, минимальное расстояние растет линейно с длиной кода. Как результат - в настоящее время МПП-коды, основанные на матрицах перестановок, вошли в ряд стандартов: стандарт подвижной беспроводной связи LTE, стандарт спутникового телевидения DVB-S2, стандарт беспроводных локальных сетей WiFi 802.llac.

не будет содержать циклов длины б при любом значении параметра
т > (а;_ 1 - а0)(?го - 1) + 1.
Рассмотрим частный случай последовательности, фигурирующей в теореме 1.4.2: {0,1, по, Пд,..., Пд-2}. Докажем для такой последовательности следующую лемму:
Лемма 1.4.2. Для любой упорядоченной тройки {п^п^щ} при 0 < х < у < с < I — 2 выполняется
щ - Д

(ng - Tig, Tig - ng)
Доказательство.
Д-Д __ nxo(npr- 1) _ пГ-
(no - no>no - "о) ("o("o ж - 1), "oOo * - !)) ("о x - 1:no * ~ !)
Поскольку наибольший общий делитель не превосходит минимального ИЗ СВОИХ операндов, то
пГ'г- 1 . ng-'r-l

Обозначим у — х = к. Так как xк + 1, поэтому
Д~х - 1 n£+
nfx - 1 “ пко-
В свою очередь неравенство
-ф: > т
"о-1 “
справедливо при всех По > 1. □
Основываясь на выводах леммы 1.4.2 и теоремы 1.4.2, можно сформулировать следующий результат: