Специальные конструкции кодов с малой плотностью проверок тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Иванов, Федор Ильич

• Иванов, Федор Ильич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Иванов, Федор Ильич

Содержание

Введение

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

Глава 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 году, удовлетворяют приведенным выше требованиям. Однако "случайность" рассматриваемого Галлагером кода затрудняет использовать его в большинстве практических приложений ввиду достаточно большой сложности реализации. В связи с этим рядом исследователей, таких как Т. Ричардсон, Д. Маккей, М. Фоссориер, Э. Габидулин, М. Эсмаэли было предложено использовать матрицы перестановок для генерации проверочных матриц МПП-кодов. Данный подход позволяет оптимизировать как процедуры хранения матриц, так и алгоритмы кодирования и декодирования. Кроме того К. Ш. Зигангировым было доказано, что для почти всех кодов, проверочная матрица которых состоит из случайных матриц перестановок, минимальное расстояние растет линейно с длиной кода. Как результат - в настоящее время МПП-коды, основанные на матрицах перестановок, вошли в ряд стандартов: стандарт подвижной беспроводной связи LTE, стандарт спутникового телевидения DVB-S2, стандарт беспроводных локальных сетей WiFi 802.Нас.

Помимо МПП-кодов, основанных на матрицах перестановок, существенный интерес представляют низкоплотностные коды, построенные с использованием других алгебраических конструкций, таких как проективные геометрии, системы Штейнера и др. Данный подход приводит к кодам с еще более предсказуемыми характеристиками. Тем не менее количество работ, посвященных кодам на проективных геометриях и на системах Штейнера, сравнительно невелико. Более того, автору неизвестно ни одной работы, где имело бы место совмещение двух подходов к построению проверочных матриц МПП-кодов: при помощи алгебраических конструкций и матриц перестановок.

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

Цель диссертационной работы: построение, теоретическое и практическое (методами имитационного моделирования) исследование кодов с малой плотностью проверок, основанных на матрицах перестановок и других алгебраических конструкциях, а также разработка специальных алгоритмов декодирования полученных кодовых конструкций.

Для достижения поставленных целей необходимо решить следующие задачи:

• Разработать и исследовать специальные конструкции кодов с малой плотностью проверок, основанных на матрицах перестановок.

• Разработать и исследовать специальные конструкции кодов с малой плотностью проверок, основанных на системах троек и четверок Штейнера и матрицах перестановок.

• Разработать специальный векторный алгоритм декодирования кодов с малой плотностью проверок, основанных на матрицах перестановок, который бы позволял распараллелить вычисления при декодировании.

Научная новизна. В настоящей диссертационной работе впервые:

• Разбаботан ряд алгоритмов генерации проверочных матриц МПП-кодов, основанных на матрицах перестановок. Исследованы некоторые свойства полученных кодовых конструкций.

• Представлен метод, позволяющий строить проверочные матрицы МПП-кодов, основанных на системах троек и четверок Штейнера и матрицах перестанок.

• Представлен векторный алгоритм декодирования кодов с малой плотностью проверок, основанных на матрицах перестановок.

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

Представлены алгоритмы генерации проверочных матриц МПП-кодов, основанных на матрицах перестановок специального вида. Получена нижняя оценка минимального кодового расстояния, нижняя оценка минимальной длины цикла, верхняя и нижняя оценки скорости МПП-кодов, основанных на системах троек и четверок Штейнера и матрицах перестановок. Сформулировано и доказано достаточное условие строгого увеличения кодового расстояния при расширении систем троек (четверок) Штейнера матрицами циркулянтов.

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

достигла 100Гбит/с на одной длине волны, а в случае иерспетивных систем речь идет о скоростях порядка 1Тбит/с,. К сожалению, в настоящий момент не существует вычислительных устройств, позволяющих обрабатывать данные на указанных скоростях, таким образом возникает необходимость распараллеливать вычисления.

На защиту выносятся следующие основные результаты и положения:

• Конструкции МПП-кодов, основанных на матрицах перестановок специального вида.

• Конструкции МПП-кодов, основанные на системах троек и четверок Штейнера и матрицах перестановок.

• Векторный алгоритм декодирования МПП-кодов, основанных на матрицах перестановок.

Апробация работы Основные результаты диссертации докладывались на следующих конференциях: XIII International Symposium on Problems of Redundancy in Information and Control Systems (2012); XIII International Workshop on Algebraic and Combinatorial Coding Theory (2012); конференциях молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (2012 2013). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН.

Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 5 статей [34]-[3G], [43], [5G] в рецензируемых журналах (3 статьи опубликованы в изданиях, индексируемых в Web of Science (WoS)) и 4 статьи [37],[38],[63],[64] в сборниках трудов конференций.

Личный вклад автора Все основные научные положения и выводы, составляющие содержание диссертации, разработаны автором самостоятель-

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

Структура и объем диссертации Диссертация состоит из введения, обзора литературы, 3 глав, заключения и библиографии. Общий объем диссертации 149 страниц, из них 111 страниц текста, включая 73 рисунка и 7 таблиц. Библиография включает 66 наименований на 9 страницах.

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

Случайные коды с малой плотностью проверок (МПП-коды) были впервые предложены Р. Галлагером в 1960 году в работе [1]. В этой же работе автором была получена нижняя оценка минимального кодового расстояния, а также предложены практически применимые алгоритмы декодирования МПП-кодов: мажоритарный алгоритм и алгоритм "распространения доверия". Галлагер также впервые указал на взаимосвязь между циклами и количеством независимых итераций декодирования.

В 1981 году Таннер [7] предложил метод построения длинных кодов из коротких кодов-компонентов. Конструкция МПП-кодов Галлагера является частным случаем конструкции Таннера и получается из нее, если использовать код с двоичной проверкой на четность в качестве компонентного кода. Таким обра- зом, коды построенные Таннером можно назвать обобщенными МПП-кодами. Также М. Таннер предложил использовать фактор-графы для описания обобщенных МПП-кодов, что впоследствие дало альтернативный подход к исследованию как свойств МПП-кодов, так и алгоритмов их кодирования и декодирования. Тем не менее, ввиду недостаточного уровня развития вычислительной техники, МПП-коды непосредственно после их открытия не нашли широкого применения и были забыты до конца 1990-х.

Активное исследование МПП-кодов возобновилось в конце 1990-х, когда они были "переоткрыты"Д. Маккеем в статье [65]. С тех пор МПП-коды стали одним из самых популярных направлений для исследований в области помехоустойчивого кодирования. Можно выделить некоторые области исследования МПП-кодов, напрямую связанные с темой диссертационной работы:

• Исследование нерегулярных МПП-кодов [2], [22], [25], [46];

• Конструктивное построение проверочных матриц МПП-кодов, основан-

ных на матрицах перестановок, с заданными свойствами [8], [9], [12], [14]-[16], [23], [29], [33], [39], [47];

• Исследование алгоритмов кодирования МПП-кодов [21], [20];

• Исследование алгоритмов декодирования МПП-кодов [5], [24], [30], [48];

• Комбинирование различных алгебраических конструкций для построения МПП-кодов [3], [4], [0], [12], [13], [18], [20], [28], [34], [40]-[42], [50]-[55];

• Поиск циклов и исследование их влияния на декодирование МПП-кодов [19], [27], [31], [32];

В работе [66] было показано, что минимальное расстояние почти всех МПП-кодов, основанных на случайных матрицах перестановок, возрастает линейно с увеличением длины кода за счет размера матрицы перестановок. МПП-кодам, основанным на системах Штейнера, посвящена работа [42]. Использовать МПП-коды в качестве компонент сверточного кода предложено в работах [49], [18].

Глава 1

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

перестановок

1.1. Введение

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

Для кодов, нья проверочная проверочная матрица состоит из циркулярных перестановочных матриц (квазициклические коды), получено условие отсутствия цикла длины 4. Также приведено обобщение полученного условия на более широкий класс кодов. В соответствии с полученным условием, построены некоторые классы квазициклических кодов, минимальная длица цикла в проверочных матрицах которых равна 6, также построена проверочная матрица кода с минимальной длиной цикла 8.

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

Для представленных кодовых конструкций с фиксированной скоростью Я = 0.5 и итеративного алгоритма декодирования "распространения доверия "приведены результаты моделирования при передаче кодового слова с помощью двоичной фазовой манипуляции по каналу с аддитивным белым гауссовским шумом.

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

1.2.1. Структура проверочной матрицы случайного кода Галлагера

В работе [1] Р. Галлагер впервые описал конструкцию кодов с малой плотностью проверок (МПП-кодов Галлагера) и предложил алгоритм генерации проверочной матрицы Н таких кодов. Проверочную матрицу Н0 МПП-кода длины По можно записать как Но = ,111^.. Запишем диагональную блоч-

пи

ную матрицу Нте с т. проверочными матрицами Но на главной диагонали:

/тт п л \

Н т =

\

Н0 0 ...

О Но ...

О 0 ...

О О О

Н0

/

т

где т достаточно велико. Так как размер матрицы Но равен 1 х щ, то размер матрицы Нт т х тщ. Пусть 7г(Нт) случайная перестановка столблов матрицы Тогда матрица Н, составленная из I > 2 таких перестановок в качестве слоев,

Н =

ТГ2(Нт)

у7Г/(Нт) у

является разреженной проверочной матрицей размера 1т х тщ, которая определяет ансамбль МПП-кодов Галлагера длины п = щт, п щ. Обозначим этот ансамбль £(I, щ, т). Элементы ансамбля Е(1, щ, т) получаются

путем независимого выбора перестановок щ, г = 1,2,...,/. Все перестановки щ выбираются равновероятно, таким образом на ансамбле £(1,щ,т) задано равномерное распределение.

Нижняя оценка на скорость Я кода из 8(1,щ, т) определяется формулой Я > 1 —/(1 —Яо), где Яо = ^^^ = 1 —^ _ скорость кода проверки на четность. Таким образом, получим оценку на скорость МПП-кодов Галлагера:

Я > 1 ——, (1.1)

п0

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

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

В данной работе мы будем использовать несколько иной подход, нежели предложенный Галлагером: в качестве основы для построения проверочной матрицы МПП-кода будут использоваться матрицы перестановок. Опишем способ построения такого ансамбля в общем виде: Пусть т, /, по £ М, причем щ > I, т\ > 1щ. Рассмотрим группу Т'т матриц перестановок размера т х т.

Выберем 1щ случайных матриц {Р/?} С Т>т1 г = 1, 3 = 1, по- Потребуем так же, что если Р^ = Рь, то г = з, к = й. Ясно, что такие условия выбора матриц Ру соответствуют урновой модели без возвращений. Построим проверочную матрицу Н размера I х

(

Н =

■о

(1.2)

^Р/1 Р12 Р/3 ••• Р /гг0 у

Указанный выше способ построения матрицы Н гарантирует, что все матрицы в каждой строке и в каждом столбце будут различны. Так как Р^ -квадратная матрица размера т х т, то размер Н - т1 х тщ. Н определяет ансамбль (7,7?о)-регулярных (с постояннным весом столбца I, и с постоянным весом строки щ) МПП-кодов длины п = щт, который мы обозначим Элементы ансамбля £д(/,по,т) получаются путем выбора без возвращений матриц перестановок Рг7- € Т>т, г = 1, 2,..., j = 1, 2,..., щ.

Легко показать, что

1^/7 м (га!)!

Определение 1.2.1. Произвольный код С Е £п(1,По,т) мы назовем МПП-кодом. основанным на матрицах перестановок.

Для кодов из ансамбля щ, т) выполняется та же оценка для скорости, что и для кодов из ансамбля £(£, по, т), в то же время любая проверочная матрица, составленная из / > 1 слоев, состоящих из матриц перестановок, имеет ранг не более чем га/ — I + 1, то есть равенство в оценке (1.1) не достигается.

Пример 1.2.1. Пусть I = 3, тогда для скоростей Я = 0.25, 0.4, 0.5, 0.625, 0.7, 0.8, 0.9 пом,учим следующие значения щ:

Я 0.25 0.4 0.5 0.625 0.7 0.8 0.9

"0 4 5 6 8 10 15 30

Таблица 1.1. Зависимость между Я, щ при 1 = 3

Фиксируем I — 5. тогда для скоростей Я — 0.1, 0.2, ...,0.9 получим следующие значения щ:

Аналогично, для 1 = 7 получим:

Я 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

щ 6 6 8 9 10 13 17 25 50

Таблица 1.2. Зависимость между Я, щ при 1 = = 5

Я 0.1 0/2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

п0 8 9 10 12 14 18 24 35 70

Таблица 1.3. Зависимость между Я, щ при I — 7

Докажем теорему, дающую верхнюю оценку на кодовое (минимальное) расстояние кода С € £ц(1,по,т).

Теорема 1.2.1. с1с < 2т УС Е £ц(1,по,т), где (1с - кодовое расстояние кода С.

Доказательство. Для доказательства достаточно показать, что что вектор с = (1,1,1..., 1,0, 0,..., 0) является кодовым словом, то есть сНт = О. Дан-

2т п—2т

ное равенство эквивалентно сложению первых 2т строк проверочной матрицы Н по модулю 2. Первые 2т строк соответствуют первым 2 слоям проверочной матрицы Н. Каждый столбец данной двуслойной матрицы содержит ровно 2 единицы. Таким образом с действительно является кодовым словом. Так как т(с) = 2т, то <1с < 2т. □

В то же время в работе [66] было доказано, что минимальное расстояние почти всех кодов из ансамбля £д(/, по, т) возрастает линейно с их длиной п, в то же время из этого не напрямую не следует, что данный класс кодов при любых значениях I и г?о достигает границы Варшамова-Гилберта.

Согласно теореме Варшамова-Гилберта при достаточно большом п существуют двоичные коды со скоростью имеющие кодовое расстояние, кото-

рое находится из уравнения Я = 1 — где И{5) = —5к^2(<5) — (1 —

\ ТЪ /

6) 1о§2 (1 — 5) - энтропийная функция Шеннона двоичного информационного

гтл , " ¿с 2ш 2 т

источника. Так как ас < 2т, поэтому — < - = —. Таким образом, для

п щт по

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

п0<! (1.3)

Построим таблицу зависимости между Я, по и 6 в соответствии с (1.3)

II 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

0.32 0.24 0.19 0.15 0.11 0.08 0.05 0.03 0.01

Щ 7 9 11 14 19 25 40 67 200

Таблица 1.4. Зависимость между Я, пп и 5

Данная таблица показывает, каким должно быть значение По, чтобы код имел возможность достигать границы Варшамова-Гилберта. С другой стороны, скорость Я так же связана с щ и I. Легко заметить, что Я > —, Упо, I-

щ

1 2

Таким образом — < по < Таким образом, при малых значениях щ и, Я д

соответсвтвенно, при малых скоростях (согласно таблице 1.4), не существует кодов с параметрами, которые близки к оптимальным ( в смысле достижения границы Варшамова-Гилберта).

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

1.3.1. Алгоритм декодирования "распространения доверия"

В данном разделе мы напомним классический алгоритм декодирования, предложенный Галлагером в [1]. Рассматриваемый декодер МПП-кодов работает с представлением кода в виде фактор-графа, так же известного как граф Таннера [7]. Граф Таннера - это двудольный граф, состоящий из двух подмножеств вершин: вершин-символов (вершин-переменных) и вершин-проверок. Ребро соединяет вершину-переменную и вершину проверку в том случае, если соответствующая переменная (символ) входит в проверку.

Вершины-проверки

Вершины-неременныс

Рис. 1.1. Граф Таннера регулярного (/,п0) МПП-кода длины п.

Классический алгоритм декодирования Sum-Product, известный так же под названиями "Belief Propagation (алгоритм с распространением доверия) - алгоритм декодирования, являющийся алгоритмом обмена сообщениями на рассмотренном выше фактор-графе. Алгоритм получает на вход вероятности приёма символов, которые для двоичного случая передаются как отношения правдоподобия. Далее алгоритм итеративно выполняет вычисления на вершинах-символах и вершинах-проверках, передавая между ними сообщения,

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

1 Вычисление сообщений от проверок к символам В логарифмах отношения правдоподобия формулы выглядят следующим образом:

Ъг= П Е М'))

1'ем 0)\г l'€N(^)\l

где 7?г - сообщение от ^'-й проверки г-му символу, ап - знак сообщения от г-го символа для ]-й проверки, - модуль (абсолютное значение) сообщения от г-го символа для ^'-й проверки, N{3) - множество символов в ^'-й проверке, Л^'Дг множество символов в проверке кроме г и функция /(х):

ех + 1

2 Вычисление сообщений от символов проверкам В логарифмах отношения правдоподобия формулы выглядят следующим образом:

агфг> = аг/Зг + ^

УёМ(г)

азгР]г = агРг + Е

где ау и ¡Зг> - оценка знака и модуля г-го символа, М(г) - множество проверок, в которые входит г-й символ, М(г)\] - множество проверок, в которые входит г-й символ кроме ]-& проверки

3 Вычисление синдрома: По вычисленным ау и ¡Зг>, 1 < г < По, строится «жесткое решение» х и вычисляется синдром в = Нхт, если Я = 0, то

18

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

Шаги 1-3 выполняются ограниченное число раз. Если достигнуто некоторое максимальное число итераций, то алгоритм прерывается и блок считается принятым с ошибкой.

1.3.2. Циклы в графе Таннера

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

Более важной характеристикой при итеративном декодировании МПП-кода служит минимальная длина циклов в его фактор-графе. Следует отметить, что в пределе, когда Belief Propagation выполняется на фактор-графе без циклов (т.е. на дереве), он сходится к оценке максимального правдоподобия. В то же время при разумных длинах кода (от сотен до сотен тысяч символов) это условие может быть выполнено только для небольшого числа итераций порядка 2-4, а далее сообщения становятся зависимыми и несут смысл не вероятностей, а оценок надёжности символов. В то же время на практике необходимо выполнение существенно большего числа итераций, порядка десятков.

Еще в работе Галлагера была отмечена взаимосвязь между минимальной длиной цикла в фактор-графе и количеством независимых итераций декодирования. Во многих более поздних работах, например [42], [32] также было отмечено негативное влияние коротких циклов на результаты итерационного

декодирования.

Из структуры графа Таннера очевидно следует, что минимально возможная длина цикла в нем равна 4. Ясно, что циклу длины 4 в графе Таннера соответствует прямоугольник с единичными вершинами в проверочной матрице

H. Таким образом, если каждое попарное произведение строк (или столбцов) проверочной матрицы Н не более 1 (равно либо нулю, либо единице), то Н не содержит циклов длины 4. Циклы больших длин определяются минимальной длиной цикла в графе Таннера.

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

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

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

Вначале мы построим некоторые ансамбли кодов с малой плотностью проверок, которые являются подансамблями п0, ш), не задаваясь вопросом о минимальной длине циклов в их проверочных матрицах. Далее же мы рассмотрим специальный ансамбль т. н. "квазициклических"МПП-кодов (и некоторое его обобщение), для которых сформулируем критерий отсутствия циклов длины 4 и построим некоторые примеры ансамблей с минимальной длиной цикла 6 и 8. Затем мы представим способ построения МПП-кодов,

основанных на полях Галуа.

1.4.1. МПП-коды, основанные на смежных классах

Рассмотрим перестановку специального вида.

Л 2 3 ... т\

Пусть а е 5т, о = I , где *5>ш - группа перестановок

а-2 а3 ... ат ]

(симметрическая группа), щ = ст(г), Ь 6 N : (6, га) = 1, (• ,■) - наибольший общий делитель. Определим перестановку аь следующим образом:

где Cj = (аф mod т) + 1.

Определение 1.4.1. Перестановку &ъ назовем перестановкой-умножением.

Лемма 1.4.1. аъ является перестановкой тогда и только тогда, когда (Ь,т) = 1.

Доказательство. Необходимость: Для того, чтобы о~ь было биекцией. необходимо, чтобы ai(i) ф сгъ(з), i Ф j< или Ci ф Cj,i Ф j. Покажем, что данное условие нарушается как только (b,m) = t > 1. Обозначили через Л = {а? — dj} = {1,2,... , га — 1}. Рассмотрим условие, когда q = су, т. е.

(аф mod га) + 1 = (ajb mod га) + 1, (аф mod га) = (ajb mod га), (oj — aj)b mod га = 0.

Так как (6, га) = t > 1, mo j G Л. Таким образом, найдутся а* ф а*- : а* — а*- = у , поэтому (а* — а^)6 mod га = уй mod га = m~t mod га Так

как (b,m) = t > 1, то ^ = г 6 N, поэтому m^ mod m = zm mod m = 0. Таким образом С{ = Cj при г j. Поэтому не является биещией.

Достаточность: Предположим, что (Ь,т) = 1, по &ъ не является би-екцией. Тогда найдутся такие 1 < г < j < т, что С; = Cj, а это значит, что

(аф mod т) = (ajb mod m),

а поскольку (b,m) — 1, это означает, что а,- mod т = aj mod m, а поэтому а не является перестановкой вопреки предположению. □

Легко показать, что bi : (bj,m) = 1 при фиксированном т образуют мультипликативную группу G*т. = ф(т), где ф(-) - функция Эйлера.

Если т - простое, то \G*m\ = т — 1.

Теперь рассмотрим алгоритм построения проверочной матрицы МПП-кода, на основе построенных перестановок-умножений.

Пусть a Е S,m, возьмем случайное &i £ N, (bi,m) = 1, bf = 1 mod m, x > l. Тогда существует перестановки-умножения a^, cr62, ..., <тьг причем условия bf = 1 mod т и х > I гарантируют, что сгЬг = ст^ тогда и только тогда, когда г = j (i,j < I).

Каждой перестановке аь, поставим в соответствие матрицу перестановок . . Построим столбец Pi, состоящий из таких матриц, получим

/р \

Pl =

fb.

а. 2

Выберем Ь2 G N, (Ьг,т) = 1, 62 mod m, г = 1,1. Построим переста-

новки-умножения аь2ьх^ Оъ2ъ%1 ■ ■ ■ •> аь2ъ\■ ^3 алгоритма построения следует, что

22

аь\ Ф аь2ь\ — ^ Вновь отобразим каждую перестановку (?ъ2ъ\ на матрицу перестановок Р^ ;. Построим столбец Р2, состоящий из таких матриц,

2 1

ПОЛУЧИМ

2 =

ОЪзЪ!

\

р р

OV v.2 b2bi

\р%4/

Для 63 G N потребуем выполнения всех условий, описанных выше, и, кроме того,

Ь3 ф &2&1 mod га. Вообще, для bj необходимо выполнение j — 1 соотношения

bj Ф Ъ\ mod т bj ф b')b\ mod т bj ф Ьф\ mod т

bj ф bj-\b\ mod га

(1.4)

/г I \п°

тогда способом, описанным выше, построим множества ( {аь }|=1 ) . Каж-

\ 3 1 /

дому поставим в соответствие

Pj =

\

Tbjbi

bjbl

"bjbf

/

Нщ — (Рх, Р2, . . . , Рц0)

р р 0-ЬпоЬ1

Р р р аЪп0ъ1

Р р р СТЬп0ьЗ

(1.5)

аЬп0ъ\/

\ Ь1 ЬгЬ1!

определяет ансамбль регулярных МПП-кодов Галлагера длины п = щт, который мы обозначим £м{1:щ,тп). Элементы ансамбля получаются путем случайного выбора числа Ь\ : (61, га) = 1, случайного выбора перестановки ст Е ¿>т, а так же случайных чисел Ь2,..., ЬПо, для которых выполяется (1.4). Указанный выше способ построения матрицы Нт гарантирует, что все матрицы в каждой строке и в каждом столбце будут различны (они все будут являться классами смежности).

Определение 1.4.2. Произвольный код С Е £м(1,Щ,т) мы назовем МПП-кодом, основанным на смежных классах.

Список литературы диссертационного исследования кандидат наук Иванов, Федор Ильич, 2014 год

Литература

1. Gallager R. G. Low-Density Parity-Check Codes. Massachusetts: MIT Press, 1963.

2. Richardson T. J., Shokrollahi M. A., Urbanke R. L. Design of capacity-approaching irregular low-density parity check codes // IEEE Trans, on Inform. Theory. 2001. Vol. 47, no. 2. P. 619-637.

3. Lentmaier M., Zigangirov K. S. On generalized low-density parity-check codes based on Hamming component codes // IEEE Communication Letters. 1999. Vol. 3, no. 8. P. 248-250.

4. Djurdjevic I., Xu J., Abdel-Ghaffar K., Lin S. A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols // IEEE Commun. Lett. 2003. Vol. 7, P. 317-319.

5. Groshev F.V., Zyablov V.V., Potapov V. G. Low-complexity decoded LDPC Codes with Reed-Solomon constituent codes // Proc. of the 11-th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2008), Pomporovo, Bulgaria. 2008.

6. Yi Y., Shaobo L., Dawei H. Construction of LDPC codes based on narrowsense primitive BCH codes // Vehicular Technology Conference, Stockholm, Sweden. 2005. P. 1571-1574.

7. Tanner M. A Recursive Approach to Low Complexity Codes // IEEE Trans. Inform. Theory. 1981. Vol. 27, no. 5. P. 533-547.

8. Fossorier P. C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices // IEEE Trans. Inform. Theory. 2004. Vol. 50, no. 8. P. 1788-1793.

9. Okamura T. Designing LDPC codes using cyclic shifts // Proc. IEEE Int. Symp. Information Theory. Yokohama, Japan. 2003. P. 151.

10. Davydov A. A., Giulietti M., Marcugini S., Pambianco F. On the spectrum of possible parameters of symmetric configurations // XII International Symposium on problems of redundancy in information and control systems. Saint-Petersburg, Russia. 2009. P. 69-54.

11. Levy Y., Costello D. J. An algebraic approach to constructing convolutional codes from quasi-cyclic codes // DIMACS Ser. Discr. Math. Theor. Comput. Sci. 1993. Vol. 14, P. 188-198.

12. Fan J. L. Array codes as low-density parity check codes // Proc. 2nd Int. Symp. Turbo Codes and Related Topics. 2000. Brest, France. P. 543-546.

13. Ling Alan С. H. Difference Triangle Sets From Affine Planes // IEEE Trans. Inform. Theory. 2002. Vol. 48, no. 8. P. 2399-2401.

14. Hagiwara M., Nuida K., Kitagawa T. On the minimal length of quasi-cyclic ldpc, codes with girth greater than or equal to 6 // Proc. International Symposium on Information Theory and its Applications. San Diego, USA. 2006.-Feb.

15. Wang Y., Yedidia J., Draper S. Construction of high-girth QC-LDPC codes // Proc. 5th Int. Symp. on Turbo Codes and Related Topics. Lausanne, Switzerland. 2008.-Sep. P. 180-185.

16. Milenkovic, O., Kashyap N., Leyba D. Shortened array codes of large girth /7 IEEE Trans. Inf. Theory. 2006. Vol. 52, no. 8. P. 3707-3722.

17. Яцкин H. И. Алгебра. Теоремы и алгоритмы. Иваново: издательство Ивановского государственного университета, 2006.

18. Bocharova I. E., Kudriashov B. D., Satuikov R. V., Stiglmayr S. Short quasi-cyclic LDPC codes from convolutional codes // Proc. IEEE Int. Symp. Information Theory. Austin, USA. 2010. P. 551-555.

19. Liva G., Rayan W.E., Chiani M. Quasi-Cyclic Generalized LDPC Codes with Low Error Floors // IEEE Transaction on Communications. 2008. Vol. 56, no. 1. P. 49-57.

20. Huang С. M., Huang J. F., Yang С. C. Cyclic LDPC Codes from Quadratic Congruences // IEEE Commun. Lett. 2008. Vol. 12, no. 4. P. 313-315.

21. Myung S., Yang K., Kim J. Quasi-cyclic LDPC codes for fast encoding // IEEE Trans. Inform. Theory. 2008. Vol. 51, no. 8. P. 2894-2901.

22. Milenkovic O., Prakash K., Vasic B. Regular and irregular low density parity check codes for iterative decoding based on cycle-invariant difference sets // Proc. 41st Allerton Conf. Communication, Control and Computing. Monticello, USA. 2003.

23. Gabidulin E., Moinian A., Honary B. Generalized construction of quasi-cyclic regular LDPC codes based on permutation matrices // Proc. IEEE Int. Symp. Inf. Theory. San Diego, USA. 2006. P. 679-683.

24. Жилин И.В., Рыбин П.С., Зяблов В.В. Сравнение алгоритмов декодирования двоичных МПП-кодов с жёстким входом // 34 международная конференция молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы". Тезисы докладов. Геленджик, Россия. 2011. С. 221-227.

25. MacKay D. J. С., Neal R. М. Near Shannon limit performance of low density parity check codes // IEEE Electronics Letters. 1996. Vol. 32, no. 18. P. 1645-1646.

26. Richardson T., Urbanke R. Efficient encoding of low density parity check codes // IEEE Trans. Inform. Theory. 2001. Vol. 47. P. 638-656.

27. Djidjev Hristo N. A faster algorithm for computing the girth of planar and bounded genus graphs // ACM Transactions on Algorithms (TALG). 2010. Vol. 7. no 1.

28. Lu J., Moura M. F., Niesen U. Grouping-and-shifting designs for structured LDPC codes with large girth // Proc. of IEEE International Symposium on Information Theory (ISIT '04). Chicago, USA. 2004. P. 236.

29. Zhang H., Moura M. F. The design of structured regular LDPC codes with large girth // Proc. of IEEE Global Telecommunications Conference (GLOBECOM '03). San-Francisco, USA. 2003. P. 4022-4027.

30. Kschischang F. R., Frey B. J., Loeliger H.A. Factor graphs and the sum-product algorithm // IEEE Trans. Inform. Theory. 2001. Vol. 47, no. 2. P. 498-519.

31. Kim S., Chung H., Shin D.-J. Girth analysis of Tanner's (3,5) QC LDPC codes // Proc. of IEEE International Symposium on Information Theory (ISIT '05). Adelaide, South Australia, Australia. 2005. P. 1632-1636.

32. Xiaofu W., Xiaohu Y., Chunming Z. An Efficient Girth-Locating Algorithm for Quasi-Cyclic LDPC Codes // Proc. of IEEE International Symposium on Information Theory (ISIT '06). San Diego, USA. 2006. P. 817-820.

33. Kim S., No J.-S., Chung H., Shin D.-J. Quasi-cyclic low-density parity-check codes with girth larger than 12 // IEEE Int. Symp. Inf. Theory. 2007. Vol. 53, no. 8. P. 2885-2891.

34. Ivanov F. I., Zyablov V. V., Potapov V. G. Low-Density Parity-Check Codes Based on Galous Field // Information Processes. 2012. Vol. 12, no. 1. P. 68-83.

35. Иванов Ф. И., Зяблов В. В., Потапов В. Г. Оценка длины циклов квазициклических регулярных кодов с малой плотностью проверок на четность // Информационно-управляющие системы. 2012. Т. 42, № 3. С. 42-45.

36. Иванов Ф. И., Зяблов В. В., Потапов В. Г. Сравнение различных конструкций двоичных МПП-кодов, построенных на основе матриц перестановок // Информационные процессы. 2012. Т. 12, № 1. С. 31-52.

37. Ivanov F. I., Zyablov V. V., Potapov V. G. Low-Density Parity-Check Codes Based on the Independent Subgroups // Proc. of XIII International Symposium "Problems of Redundancy in Information and Control Systems''. Russia, Saint-Petersburg. 2012. P 31-34.

38. Ivanov F. I., Zyablov V. V., Potapov V. G. The Score of the Minimum Length of Cycles in Generalized Quasi-Cyclic LDPC Codes // Proc. of Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2012. Pomorie, Bulgaria. 2012. P. 162-167.

39. Esmaeili M., Gholami M. Structured quasi-cyclic LDPC codes with girth 18 and column-weight J>3 // Int. Journal of Electron, and Commun. 2010. Vol. 64, no. 3. P. 202-217.

40. Kou Y., Lin S., Fossorier M. Low-density parity check codes based on finite geometries: A rediscovery and new results // IEEE Trans. Inform. Theory. 2001. Vol. 47, P. 2711-2736.

41. Vasic. В., Pedagani K., Ivkovic M. High-rate girth-eight low-density parity-check codes on rectangular integer lattices // IEEE Transactions on Communications. 2004. Vol. 52, no. 8. P. 1248-1252.

42. Johnson S. Low-density parity-check codes from combinatorial designs. The University of Newcastle Press: Newcastle. 2004.

43. Иванов Ф. И., Жилин И. В., Зяблов В. В. Алгоритм декодирования кодов с малой плотностью проверок на четность с большим распараллеливанием // Информационно-управляющие системы. 2012. № G. С. 49-55.

44. Холл М. Комбинаторный анализ. Издательство иностранной литературы: М. 1963.

45. Мак-Вильямс Ф. Дж., Слоэн И. Дж. А. Теория кодов, исправляющих ошибки. Связь: М. 1979.

46. MacKay D. J. С., Wilson S. Т., Davey М. С. Comparison of constructions of irregular Gallager codes // Proc. 36th Allerton Conf. Communication, Control, and Computing. 1998.

47. Zhang G., Sun R., Wang X. Construction of Girth-Eight QC-LDPC Codes from Greatest Common Divisor // IEEE Communications Letters. 2013. Vol. 17, no. 2. P. 369-372.

48. Зигангиров Д. К., Зигангиров К. Ш. Декодирование низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц, при передаче по каналу со стираниями // Пробл. передачи инф. 2006. Т. 42, № 2. С. 44 52.

49. Bocharova I. Е., Hug F., Johannesson R., Kudryashov В. D., Satyukov R. V. Some voltage graph-based LDPC tailbiting codes with large girth // Proc. IEEE International Symposium on Information Theory (ISIT'll). St. Petersburg, Russia. 2011.

50. Johnson S. J., Weiler S. R. Regular low-density parity-check codes from combinatorial designs /'/' Proc. IEEE Inform. Theory Workshop (ITW'Ol). Cairns, Australia. 2001. P. 90-92.

51. Tanner R. M., Sridhara D., Fuja T. A Class of Group-Structured LDPC Codes // Proc. ISTA. Ambleside, England. 2001.

52. Smarandache R., Vontobel P. O. On Regular Quasi-Cyclic LDPC Codes from Binomials // Proc. IEEE International Symposium on Information Theory (ISIT'04). Chicago, USA. 2004. P. 274.

53. Kou Y., Lin S., Fossorier M. Construction of low-density parity-check codes: A geometric approach // Proc. 2nd Int. Symp. Turbo Codes. Brest, France. 2000.

54. Vasic B., Kurtas E., Kuznetsov A. LDPC codes based on mutually orthogonal Latin rectangles and their application in perpendicular magnetic recording // IEEE Trans. Magn. 2002. Vol. 38, no. 1. P. 2346-2348,

55. Ling A. C., Colbourn C. J., Grannell M. J., Griggs T. S. Construction techniques for anti-Pasch Steiner triple systems // J. London Math. Soc. 2000. Vol. 61, no. 3, P. 641-657.

56. Ivanov F. I., Zyablov V. V. Low-Density Parity-Check Codes Based on Steiner Systems and Permutation Matrices // Problems of Information Transmission. 2013. Vol. 49, no. 4. P. 41-56.

57. Lee L. Short unit-memory byte-oriented binary convolutional codes having maximal free distance // Information Theory, IEEE Transactions on. 1976. Vol. 22, no. 3. P. 349-352.

58. Zyablov V. V., Sidorenko V. On periodic (partial) unit, memory codes with maximum free distance, Selected papers from the Workshop on Information Protection, Error Control, Cryptology, and Speech Compression // London, UK: Springer-Verlag. 1994. P. 74-79.

59. Justesen J. Bounded distance decoding of unit memory codes // Information Theory, IEEE Transactions on. 1993. Vol. 39, no. 5. P. 1616-1627.

60. Dettmar U., Sorger U. New optimal partial unit memory codes based on extended bch codes // Electronics Letters. 1993. Vol. 29, no. 23. P. 2024-2025.

61. Dettmar U., Shavgulidze S. New optimal partial unit memory codes // Electronics Letters. 1992. Vol. 28, no. 18. P. 1748-1749.

62. Ma H. H., Wolf J. K. On tail biting convolutional codes // IEEE Transactions on Communications. 1986. Vol. 34, no. 2. P. 104-111.

63. Ivanov F. I., Zyablov V. V., Potapov V. G. The score of the Minimum Length of Cycles in Quasi-Cyclic LDPC codes based on permutation matrices j j Proc. of 35-th conference "Information technologies and systems (ITAS)". Petrozavodsk, Russia. 2012. P. 133-136.

64. Ivanov F. I., Zyablov V. V. Low-Density Parity-Check Codes Based on Steiner Triple Systems and Permutation Matrices // Proc. of 36-th conference "Information technologies and systems (ITAS)". Kaliningrad, Russia. 2013.

65. MacKav D. J. C. Good error correcting codes based on very sparse matrices // IEEE Trans. Info. Theory. 1999. Vol. 45, no. 2. P. 399-431.

66. Шридхаран А., Лентмайер M., Трухачев Д. В., Костелло Д. Дж., Зи-ганги- ров К. Ш. О минимальном расстоянии низкоплотностных кодов с

проверочны- ми матрицами, составленными из перестановочных матриц // Пробл. передачи информ. 2005. Т. 41, № 1. С. 39-52.