Алгоритмы анализа и синтеза помехоустойчивых низкоплотностных кодов в системах телерадиовещания Овинников Алексей Анатольевич

Содержание к диссертации

Введение

1 Синтез кодов с малой плотностью проверок на чётность 11

1.1 Низкоплотностные коды. Основные положения 12

1.2 Описание процедуры «Density Evolution» 14

1.3 Алгоритмы синтеза кодов с низкой плотностью проверок на чётность

1.3.1 Алгоритм Маккая . 18

1.3.2 Процедура PEG 20

1.4 Процедуры кодирования и декодирования LDPC кодов 23

1.4.1 Традиционные способы кодирования 23

1.4.2 Вычислительно эффективные алгоритмы кодирования 24

1.4.3 Алгоритм декодирования с инверсией бита 28

1.4.4 Алгоритм декодирования с итеративным распространением доверия 29

1.5 Алгоритм синтеза псевдослучайных кодов с многокритериальным отбором проверочных матриц 32

1.5.1 Модифицированный алгоритм Маккая 33

1.5.2 Критерии отбора кодов из ансамбля 34

1.5.3 Имитационное моделирование. Результаты исследования 37

1.6 Заключение по разделу 41

2 Алгоритмы синтеза регулярных квазициклических низкоплотностных кодов на основе комбинаторных структур и модульных алгоритмов 42

2.1 Теоретические постулаты 42

2.1.1 Введение 42

2.1.2 Свойства низкоплотностных квазициклических кодов 45

2.2 Алгоритмы синтеза квазициклических LDPC кодов 50

2.2.1 Анализ свойств низкоплотностных кодов Таннера 51

2.2.2 Синтез LDPC кодов на основе комбинаторных блок-схем 59

2.2.2.1 Концепция синтеза LDPC кодов с использованием комбинаторики 59

2.2.2.2 Математические модели уравновешенных неполных блок схем, применимых для

синтеза квазициклических LDPC кодов 62

2.2.2.3 Процедура синтеза проверочных матриц LDPC кодов на базе циклических

разрешимых систем Штейнера 67

2.2.2.4 Ансамбли регулярных низкоплотностных кодов, полученных на базе УНБС и их

свойства з

2.3 Заключение и выводы по разделу 97

3 Анализ структуры графов таннера квазициклических кодов с низкой плотностью проверок на чётность 98

3.1 Протографы квазициклических LDPC кодов 99

3.1.1 Определения, свойства, взаимосвязь с другими способами представления проверочных матриц 99

3.1.2 Проекция циклов протографа на расширенный граф 102

3.1.3 Анализ пересечений циклов протографа 105

3.2 Алгоритм быстрой идентификации циклов в расширенном графе Таннера по протографу квазициклического кода с низкой плотностью проверок на чётность 126

3.3 Заключение по разделу 130

4 Оценка помехоустойчивости и структурных свойств графов таннера кодов с малой плотностью проверок на чётность в стандартах цифрового телерадиовещания 131

4.1 Метрика связанности циклов в графе Таннера 131

4.2 Оценка распределений метрик связанности циклов в современных стандартах

цифрового телевидения 133

4.3 Оценка предельного энергетического выигрыша от кодирования для LDPC кодов в системах цифрового телевидения 148

4.4 Заключение по разделу 157

Заключение 158

Библиографический список

• Алгоритм Маккая
• Свойства низкоплотностных квазициклических кодов
• Определения, свойства, взаимосвязь с другими способами представления проверочных матриц
• Алгоритм быстрой идентификации циклов в расширенном графе Таннера по протографу квазициклического кода с низкой плотностью проверок на чётность

Введение к работе

Актуальность темы. Стремительное развитие микроэлектроники в конце XX века заложило основу для создания современных стандартов и технологий высокоскоростной передачи данных, которые в настоящее время используются при проектировании огромного количества технических устройств и систем. При этом параллельно с усовершенствованием элементной базы постоянно улучшаются и усложняются методы и алгоритмы обработки сигналов. В частности, ужесточение требований к минимальной скорости передачи данных, пропускной способности и помехоустойчивости заставляет исследователей и разработчиков искать новые пути решения возникающих проблем. Одним из методов, позволяющих в значительной степени снизить сложность рассматриваемых задач, является помехоустойчивое кодирование. Благодаря энергетическому выигрышу от использования кодирования (ЭВК) с исправлением ошибок системы передачи данных получают дополнительные преимущества, которые можно конвертировать в улучшение различных характеристик радиотехнических и телекоммуникационных средств и систем. Среди них стоит выделить: увеличение скорости передачи данных в заданной частотной полосе при увеличении позиционности модуляции, повышение дальности связи, уменьшение требуемой мощности передатчика. При этом внесение задержки и уменьшение скорости передачи информации являются основными недостатками любой схемы кодирования. Поэтому проблема повышения ЭВК является чрезвычайно актуальной для отечественных и зарубежных исследователей.

В области канального кодирования, начиная с середины 90-х годов XX
века, наиболее актуальным и перспективным решением является использование
итеративно-декодируемых кодов, к которым относятся турбо- и

низкоплотностные коды. Значительный вклад в развитие современной теории кодирования внесли такие зарубежные и отечественные учные, как Р. Галлагер, К. Берроу, Д. Маккай, Р. Нил, М. Таннер, Р. Урбанке, Т. Ричардсон, С. Лин, Х. Ксяо, Д. Зигангиров, В. Зяблов, В. Золотарв, Г. Овечкин и другие. В настоящий момент существуют два взаимодополняющих направления исследования и разработки передовых систем помехоустойчивого кодирования. Первое из них заключается в создании методов и алгоритмов синтеза и анализа кодов, позволяющих вплотную приблизиться к пропускной способности для заданного канала передачи информации и метода декодирования. Второе, но не менее важное направление ставит своей задачей получение оптимальных с точки зрения максимизации ЭВК и минимизации требуемых на реализацию вычислительных затрат методов и алгоритмов декодирования.

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

повышения ЭВК в канале с аддитивным белым гауссовским шумом, окончательное решение которой не получено до сих пор.

Современные радиотехнические и телекоммуникационные системы используют в свом составе помехоустойчивые коды с различными характеристиками, некоторые из них вплотную приблизились к пределу Шеннона и отстоят от него всего на 1 дБ. Положение усугубляется тем, что многие алгоритмы их получения запатентованы, что не позволяет их использовать на безвозмездной основе. Кроме того, ряд кодов с длинами в пределах от сотни до нескольких тысяч бит и канальными скоростями от 0,5 до 0,9 ещ далк от максимально возможной эффективности. Все эти факторы являются отправной точкой для исследований и разработок в этом направлении.

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

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

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

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

-выполнить оценку степени влияния различных параметров LDPC кодов на эффективность работы итеративного декодера;

-провести сравнительный анализ известных алгоритмов синтеза кодов в классах регулярных и нерегулярных конструкций по методу статистических испытаний в канале с аддитивным белым гауссовским шумом;

-разработать алгоритмы синтеза кодов с низкой плотностью проверок на чтность, не уступающих по ЭВК мировым аналогам;

-разработать программные средства для анализа и синтеза LDPC кодов;

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

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

экспериментальными исследованиями на основе имитационного моделирования.

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

-оценка коэффициента расширения ансамбля квазициклических LDPC кодов, синтезированных в соответствии с алгоритмом Таннера;

-процедура синтеза регулярных высокоскоростных кодов с низкой плотностью проверок на чтность, скорость кодирования і?>0.85, на базе комбинаторных блок-схем и последовательностей Роса и Сколема;

-правила расширения отдельных циклов и комбинаций их пересечений при переходе от протографа к расширенному графу;

-алгоритм идентификации циклов в графе Таннера по протографу, работающий с переменной матрицей перестановок;

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

Достоверность результатов. Достоверность полученных в диссертационной работе результатов и выводов качественно и количественно верифицирована по известным достижениям, опубликованным как в отечественных, так и в зарубежных изданиях.

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

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

Основные положения, выносимые на защиту:

1. Модификация алгоритма синтеза нерегулярных кодов повторения накопления, отличающаяся наличием ступенчатой составляющей в структуре проверочной матрицы и позволяющая снизить асимптотическую вычислительную сложность кодирования с 0(п²) до 0{п), а также трхкритериальная процедура выбора кода из ансамбля, минимизирующая уровень насыщения вероятности ошибки декодирования.

2. Модификация алгоритма синтеза проверочных матриц Таннера, обеспечивающая расширение ансамбля кодов от 8 до 48 раз для скоростей кодирования в диапазоне от 0,4 до 0,651.

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

псевдослучайных конструкций Маккая от 0,7 до 2,5 дБ при Re [2/3; 0,9] и PEG в пике до 0,4 дБ при Re[0,42; 0,93] с фиксированной вероятностью битовой ошибки в^= 10"⁶.

4 Алгоритм идентификации циклов в графе Таннера по протографу, с ограничением в 10 единиц на длину максимально обнаруживаемого цикла, позволяющий работать с переменной матрицей перестановок.

Апробация работы. Основные результаты диссертационной работы докладывались на следующих конференциях:

-11-й, 12-й, 19-й Международной конференции «Цифровая обработка сигналов и е применение», 2009-2010, 2017 гг., г. Москва;

-17-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», 2012 г., г. Рязань;

8-й Международной молоджной научно-технической конференции «Современные проблемы радиотехники и телекоммуникаций», 2012 г., г. Севастополь;

Международной научно-технической конференции «Фундаментальные проблемы радиоэлектронного приборостроения», 2012, 2014 гг., г. Москва;

-2-й Всероссийской конференции «Радиоэлектронные средства передачи и прима сигналов и визуализации информации», 2012 г., г. Таганрог;

-19-й Всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика», 2012 г., г. Зеленоград;

-70-й Международной конференции «Радиоэлектронные устройства и системы для инфокоммуникационных технологий», 2015, 2016 гг., г. Москва;

-XI Международной (IEEE) Сибирской конференции по управлению и связи, 2015 г., г. Омск;

-6-й Всероссийской конференции «Радиоэлектронные средства получения, обработки и визуализации информации», 2016 г., г. Москва;

-23-й Международной конференции «Радиолокация, навигация, связь», 2017 г., г. Воронеж.

Внедрение результатов работы. Результаты диссертационной работы внедрены в НПФ ООО «САД-КОМ», государственный стандарт ГОСТ 54309-2011 «Аудиовизуальная информационная система реального времени (РАВИС)», что подтверждено соответствующими актами, и в учебный процесс кафедры ТОР в рамках индивидуальных заданий и цикла лабораторных работ по предмету «Основы теории систем связи с подвижными объектами». Разработанные алгоритмы использованы при выполнении ряда хоздоговорных и госбюджетных НИР, проводимых в ФГБОУ ВО «Рязанский государственный радиотехнический университет», а именно НИР № 23-09, № 15-10, № 7-12Г, № 12-12Г, № 24-12Г, № 7-14Г, грант РНФ 14-19-01263 «Исследование путей создания высокопроизводительной системы передачи информации от беспилотных летательных аппаратов».

Публикации. По теме диссертации опубликовано 17 работ. Из них 3 статьи в журналах, рекомендованных ВАК РФ для кандидатских диссертаций, 4

статьи в центральной печати, 13 тезисов докладов на конференциях, в том числе 1 статья цитируемая в системах SCOPUS и Web of Science.

Структура и объм работы. Диссертационная работа состоит из введения, четырх глав, заключения, списка литературы из 99 наименований и 2 приложений. Диссертация содержит 181 страницу, в том числе 144 страницы основного текста, 33 таблицы и 78 рисунков.

Алгоритм Маккая

В работе [67] доктором Маккаем было предложено несколько алгоритмов формирования проверочных матриц, обладающих различной вычислительной сложностью. В случае синтеза регулярной кодовой конструкции входными параметрами являются веса строк и столбцов (ds,dc), а наиболее ресурсоёмкий алгоритм состоит из следующей последовательности действий:

Используя датчик псевдослучайных чисел, синтезировать проверочную матрицу с количеством ненулевых элементов равным ds на столбец при этом вес строк должен стремиться к равномерному и равному dc. Дополнительно на код накладывается ряд ограничений: - циклы длиной 4 должны отсутствовать; - по возможности дополнительно удаляются короткие циклы большие четырёх; - структура матрицы Н должна соответствовать: Н = [нх Н2 ], причём Н2 обратима. Помимо регулярных кодовых конструкций рассмотренный алгоритм может быть использован для синтеза нерегулярных LDPC кодов, для чего необходимо в качестве входных параметров выбрать соответствующие весовые многочлены Х{х) и р(х). Одна из основных проблем кодов, разработанных Маккаем, заключается в сложности реализации вычислительно эффективной процедуры кодирования. При помощи алгоритма Гаусса-Жордана [4] либо за счёт умножения матрицы Я на Щ1 происходит преобразование искомой матрицы к систематической форме [Рт 1\. При этом генераторная матрица G в общем случае не является разреженной, поэтому сложность кодирования оказывается высокой. Также стоит отметить, что высокую трудоёмкость представляет анализ свойств кодов Маккая, в особенности оценка минимального кодового расстояния. Поэтому для определения эффективности синтезированных кодов остаётся лишь метод Монте Карло.

В качестве одного из ключевых ограничений представленного алгоритма выступает отсутствие в графе Таннера LDPC кода циклов определённой длины. При рассмотрении алгоритмов декодирования будет показано, каким образом короткие циклы влияют на решения, принимаемые помехоустойчивым декодером. Вероятностные методы синтеза низкоплотностных кодов пошли по пути оптимизации основных характеристик, в частности в следующем разделе представлена процедура, максимизирующая обхват графа Таннера. 1.3.2 Процедура PEG

Задача синтеза двудольного графа Таннера с наибольшим обхватом относится к числу сложных комбинаторных проблем. Тем не менее, для сравнительно большого параметра g0 она реализуема. В работе [56] была предложена процедура PEG (Progressive-Edge-Growth), позволяющая синтезировать граф Таннера, для которого рост обхвата пропорционален логарифму от числа проверочных вершин. Основной целью алгоритма является максимизация локального цикла минимальной длины (gt) в процессе добавления к графу новых ветвей. Проблема синтеза графа Таннера с большим обхватом заключается в выборе такого множества рёбер Es j для символьной вершины sj, чтобы последующее добавление ветвей не оказывало серьёзного влияния на параметр gt. Поэтому процедура PEG сводится к оптимизации множества Es j таким образом, чтобы после его добавления к вершине sj локальный обхват графа был максимальным. При полном переборе всех возможных значений сложность определения набора Es j оказывается пропорциональной числу сочетаний: М \ М! d \ s (1.11) где ds j - вес sj символьной вершины. В свою очередь вычислительные затраты на процедуру PEG оказываются значительно ниже.

Для более подробного описания алгоритма PEG введём ряд обозначений. Пусть Nsl j - множество проверочных вершин, которые могут быть достигнуты из символьной вершины за l и менее переходов по рёбрам графа, а Nsl j - дополняет Nsl j до множества всех проверочных вершин. Основой алгоритма PEG является процедура построения дерева из вершины Sj на глубину / при выборе каждой следующей ветви графа. Параметр / определяется в соответствии с выражениями:

В этом случае выбор максимально отдалённой от корня дерева вершины гарантирует отсутствие циклов длиной меньше 2(1+2). Рассмотренная процедура PEG обобщённо представлена псевдокодом на рисунке 1.3.

Стоит отметить ряд случаев, когда существует несколько проверочных вершин с,- в множестве Nl . В этом случае наименьший становится критерием выбора подходящего проверочного узла, что позволяет привести распределение проверок к равномерному настолько, насколько это возможно. Таким образом, алгоритмом не учитываются степени весового многочлена проверочных вершин. Если несколько элементов множества Nl обладают одинаковой и наименьшей степенью, то выбор вершины с,- осуществляется либо в произвольном порядке, либо в соответствии с заранее определённым индексом. В рамках рассмотренного алгоритма PEG существует ряд модификаций, направленных на сокращение вычислительных затрат либо увеличение обхвата графа Таннера. Уменьшение алгоритмической сложности достигается с помощью ограничения параметра / значением lmax=gJ2-2, где gx - требуемое значение обхвата. При этом могут преследоваться цели формирования определённого весового распределения проверочных вершин либо уменьшение диаметра - максимального расстояния между парой вершин графа, что может повлечь за собой снижение количества итераций декодирования необходимого для достижения целевого отношения сигнал-шум. Кроме того, существует возможность использования элемента памяти, который позволит проверить результативность выбора ветви на этапе предыдущего принятия решения и поможет в определении следующей ненулевой позиции.

Свойства низкоплотностных квазициклических кодов

Коды с малой плотностью проверок на чётность в отличие от большинства других классов линейных блоковых кодов [85] помимо малого числа ненулевых элементов в проверочной матрице не обременены другими требованиями к структуре кода. Поэтому в настоящее время предложено огромное количество различных кодовых конструкций, отличающихся друг от друга по целому ряду показателей, в том числе энергетической эффективностью алгоритмов декодирования [62, 24], компактностью хранения матриц [9, 17], затратами на аппаратную реализацию [32], вычислительной сложностью кодера и др. Стоит отметить, что первые проверочные матрицы LDPC кодов, сформированные Р. Галлагером [51], имели блоковую квазициклическую структуру, изображённую на рисунке 2.1. Представление традиционных циклических кодов в форме проверочной матрицы (рисунок 2.2), имеет значительные отличия от структуры, предложенной ниже. Характерной чертой таких конструкций является наличие единственного полинома вида h(x) = hg +hjx + --- + h]c, который полностью описывает циклический код. [

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

Низкоплотностные коды, применяемые в современных стандартах [58, 59, 47, 5], отличаются от большинства других LDPC кодов наличием квазицикличности в структуре проверочных матриц. В этом случае матрица может быть представлена в сжатой форме и записана в виде: H

В общем случае квадрант Pt у может содержать от нуля до нескольких единиц на столбец, что необходимо для формирования нерегулярных кодов с малой плотностью проверок на чётность. В качестве примера представим 3 разновидности подматриц Pt у и соответствующих им полиномов pij(x):

Выделим подкласс регулярных двоичных квазициклических кодов, которые можно охарактеризовать выражением вида: kt = 1; Vz m,j /.

Рассматриваемая группа LDPC кодов формируется исключительно из квадрантов і)010(2.3), причём смещение единичной диагонали может быть различным. В таком случае легко упростить описание LDPC кодов, представив проверочную матрицу в сжатой форме: со,о сод CV,dc-\ и _\ ci,o CU ciA-i с\ \ : -. : c ds-l,0 c ds-l,0 c ds-l,dc-lj (2.4) где 0 ct j z - десятичное число, показывающее значение сдвига единичной диагонали в матрице /f из выражения (2.1).

На основании этой формы ниже будут рассмотрены, синтезированы и проанализированы регулярные квазициклические коды вида (2.4). Выбранный подкласс кодов обладает по сравнению с другими квазициклическими конструкциями рядом преимуществ, а именно, наличием наиболее компактной формы хранения, высокой эффективностью декодирования, возможностью реализации простого кодирующего устройства. Немаловажен и тот факт, что существует достаточное количество алгоритмов формирования таких кодов [49, 79, 96]. В силу практической важности подобного класса кодов ниже рассматриваются основные свойства и способы синтеза выделенного для исследований подкласса квазициклических LDPC кодов.

Наличие строгой структуры в помехоустойчивом коде вида (2.4) позволяет в значительной мере упростить процедуру анализа его параметров и свойств. Это в свою очередь может существенно облегчить задачу синтеза проверочной матрицы регулярных квазициклических кодов с заданными характеристиками, к которым относятся: число единиц на столбец ds и строку (dс) матрицы H, минимальное кодовое расстояние d0, а также величина обхвата графа Таннера g0 (п. 1.1). Интересной особенностью регулярных LDPC кодов является зависимость скорости сходимости декодера и вероятности ошибки на его выходе от пары параметров go и do, причём величина обхвата графа go связана с минимальным кодовым расстоянием, а также увеличение go согласно формуле (1.6) приводит к росту числа независимых итераций декодера. В работе [49, 69] было обнаружено, что параметр do для регулярных низко-плотностных кодов ограничен сверху величиной, равной (ds+l)!. Результаты, полученные в исследованиях [93], дают уточнённую оценку верней границы параметра do и показывают, что уменьшение размерности циклов минимальной длины оказывает существенное влияние на верхнюю границу параметра do, что подтверждается следующими выражениями: g0 =4, d0 ((ds + l).-2(ds -1)); g0 =6, d0 ((ds + l)-2(ds - 2));, (2.5) g0 8, d0 (ds+l). Поэтому с точки зрения анализа и синтеза низкоплотностных кодов вида (2.4) важно уметь оценивать величину go, а также при возможности обеспечить её максимальное значение, приблизившись к потенциальной границе (2.5). К примеру, как показано в [73] для регулярного LDPC кода с параметрами ds=3 и dc=6 при g0=4 и g0=6 разница в помехоустойчивости для канала с белым гауссовским шумом оказывается существенной и может быть более 2 дБ при вероятности ошибки на бит 10"6 и определённых параметрах кодовой длины и скорости.

Рассмотрим цикл произвольной длины, имеющийся в проверочной матрице Я. Представим его в векторной форме вида: [СІ І СІ І СІ І СІ І СІ І СІ І СІ І ), где с - некоторые числа, используемые в выражении (2.4). Автором [49] была предложена метрика, дающая возможность эффективно измерять длину циклов в двудольном графе для квазициклических кодов, а именно: Ax,i (j)=k,J-clJ)mod(z)., (2.6) Согласно [49] однозначное обнаружение цикла в графе соответствует выполнению следующего выражения: (g/2-l Л T4tJJjt)Uod(z) = 0, V к=о J 2.7) где i0=ig/2; h h+u Jk Jk+i- Параметр g g0 определяет длину произвольного цикла в графе Таннера LDPC кода. С учётом полученного выражения автору [49] удалось доказать ряд теорем, определяющих характерные особенности класса кодов вида (2.4). Так, в работе [49] было показано, что максимально возможная длина обхвата графа для регулярных квазициклических LDPC кодов равна 12, т.е параметр go l2. Как и в случае go =4,6 повышение минимального кодового расстояния возможно лишь в случае увеличения плотности заполнения ненулевыми элементами проверочной матрицы кода (увеличение значения ds). Выделим следующие необходимые условия для получения кода с заданным обхватом графа Таннера [49]:

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

Дополнительно следует отметить, что для п=\ последовательность Роса не существует.

Таким образом, в рамках первого блока процедуры синтеза (рисунок 2.11) получаем перекрытие всех размерностей v систем Штейнера, используя последовательности Сколема и Роса, а также их модификаций.

Единственной и наиболее существенной проблемой первого этапа рассматриваемой процедуры является отсутствие полноценного алгоритма синтеза представленных математических последовательностей произвольной длины. Кроме того, для одного и того же параметра п может существовать множество различных S наборов, каждый из которых формирует изоморфную систему Штейнера. Соответственно выбор последовательности из ансамбля по критерию максимального энергетического выигрыша декодера получаемого на выходе метода (рисунок 2.11) является отдельной исследовательской задачей. В дальнейшем для синтеза LDPC кодов используются последовательности Сколема и Роса небольшой длины полученные либо эвристическим путём, либо взятые из ряда сторонних источников [41, 42, 87, 40, 45, 50].

Синтез циклических разрешимых троек Штейнера. Известно [55], что для синтеза циклических разрешимых троек Штейнера u = 6t + l, где t=n могут использоваться последовательности Сколема, при этом процедура формирования состоит из следующего набора действий: а) для каждого значения st = s є Ss получается пара чисел \i,jy, б) выполняется преобразование пары в тройку вида (lj + nj + п), где / = Sj = s ,; в) базовый блок системы Штейнера формируется из тройки {і,і + п,] + п), как{0,1,] + п}; г) набор из п базовых блоков с v = 6t + l, t=n циклическими сдвигами образуют циклическую разрешимую систему троек Штейнера. Простой пример формирования системы Штейнера порядка и = 25 рассмотрен далее. Возьмём последовательность Сколема с параметром п=4 вида Ss=(l, 1, 4, 2, 3, 2, 4, 3). В соответствии с описанной выше процедурой формирования на первом шаге получаются четыре пары чисел (1,2), (4,6), (5,8), (3,7). Результатом выполнения следующего шага являются тройки вида: (1,5,6), (2,8,10), (3,9,12), (4,7,11). И, наконец, базовые блоки системы Штейнера оказываются следующими: {0,1,6}, {0,2,10}, {0,3,12}, {0,4,11}. Остальные блоки получаются из базовых путём выполнения и операций циклического сдвига по модулю и для каждого блока.

При использовании модифицированной последовательности Сколема процедура формирования троек остаётся неизменной, но ансамбль возможных систем Штейнера расширяется на все и = 6 +1, \/t є N. Для нескольких из рассмотренных в таблице 2.5 значений параметра и определены базовые блоки В и записаны в таблице 2.7.

Необходимые последовательности Сколема получены эвристическим путём. Очевидно, что с ростом длины n значительно возрастает количество отличающихся друг от друга систем Штейнера. Это связано с тем, что при грамотной перестановке элементов в наборе Ss количество новых последовательностей зависит от числа возможных перестановок. В частности, для п = t = 3, число различных вариантов Ss равно двум, а именно Ssi=(3 1 1 3 2 0 2) и SS2=(l 1 2 3 2 0 3). Таким образом, в соответствии с процедурой синтеза LDPC кодов практически для каждого конкретного показателя п можно получить более одной проверочной матрицы.

На этапе формирования комбинаторных последовательностей было показано, что при u = 6t + 3, для синтеза LDPC кодов необходимо использовать последовательности Роса, процедура получения циклических разрешимых троек Штейнера на базе которых отличается от варианта, предложенного Сколемом [91, 92] фактически 2-мя действиями, а именно: -добавлением недостающего базового блока в форме тройки {0,2п + 1,4л +1}, -получением набора из и циклически сдвинутых блоков на основе имеющегося множества базовых блоков. Согласно формулам (2.25) и (2.26) для некоторых значений параметра п необходимо использовать модификацию.

Для случая, когда п=4 и и = 27 соответственно, процедура формирования системы троек Штейнера из последовательности Роса состоит в следующем:

По аналогии с набором базовых блоков системы Штейнера, полученных из последовательностей Сколема, в таблице 2.9 приведён набор блоков, синтезированных на основе представленного выше алгоритма для небольших значений параметра п 7. При пересчёте переменной Ъ по заданному значению и согласно (2.21) несложно обнаружить, что размерность троек Штейнера в таблице 2.9 не соответствует требуемой, что говорит о необходимости укорочения последнего базового блока. Согласно обобщённому алгоритму синтеза (рисунок 2.11) процедура выполняется на 3-ем этапе по соответствующей матрице инцидентности.

Рассмотренные алгоритмы синтеза систем Штейнера на базе комбинаторных последовательностей вносят ограничение на весовое распределение регулярных LDPC кодов, которое связано с тем, что для k 3 последовательностей Сколема и Роса не существует. Для того, чтобы несколько расширить возможности предлагаемой процедуры синтеза рассмотрим далее подмножества систем Штейнера с большим параметром k (k 3).

Синтез циклических разрешимых систем Штейнера большой плотности. Процедура формирования квазициклических LDPC кодов может быть расширена на случай, когда параметр k оказывается больше, чем три. Для этого вместо первых двух блоков метода (рисунок 2.11) вводится подсистема формирования циклических разрешимых систем Штейнера на основе полей Галуа, таким образом, получается модификация, представленная на рисунке 2.12. Определение размерности системы Штейнера в первом блоке определяется как наиболее близкое к величине N - K целое число, удовлетворяющее соотношениям (2.28). В соответствии с этим числом находятся остальные параметры блок-схемы в соответствии с процедурой, описанной ниже.

Алгоритм быстрой идентификации циклов в расширенном графе Таннера по протографу квазициклического кода с низкой плотностью проверок на чётность

Второй особенностью циклов в протографе является их возможность группирования таким образом, что при расширении в искомом графе образуются циклы относительно большой длины, которых до этого преобразования просто не было. Для начала необходимо определить какова минимальная длина цикла, который может быть получен путём группирования более коротких экземпляров. Т.к. коэффициент кратности параллельных ветвей рассматриваемых протографов равен единице, то проекция циклов длиной четыре и шесть в расширенном графе может оставаться не изменной, увеличиваться в z раз, либо кратное число раз согласно теореме 1. В тоже время циклы длиной восемь и более в расширенном графе могут быть получены группированием более коротких замкнутых структур протографа. Цель дальнейшего анализа пересечений циклов заключается в определении набора правил, который бы позволил сформулировать алгоритм их быстрой и полной идентификации по протографу. В силу того, что существует верхняя граница обхвата графа Таннера квазициклических LDPC кодов равная 12 [49], которая может быть преодолена только в случае отсутствия в проверочной матрице структур, вид которых представлен на рисунке 3.6, рассмотрению подлежат только пересечения циклов длиной 4 и 6. Это связано с тем, что встречающиеся на практике низкоплотностные коды имеют ограниченную длину и плотность заполнения ненулевыми элементами, что в большинстве случаев не позволяет выйти за пределы обхвата равного 12. Рассматривая пару связанных замкнутых структур в графе, следует обращать внимание на следующие факторы [20, 21]: а) длины циклов, исключительно g1 = 4 и g2 = 6; б) взаимное направление обхода циклов (ncr) – принимает нулевое значение при совпадении, в противном случае единицу; в) количество общих вершин (ncv) и рёбер между ними (nce); г) общее число вершин (nv) и рёбер (ne), образуемое пересечением циклов.

Все перечисленные параметры непосредственным образом оказывают влияние на правила идентификации циклов в графе Таннера по протографу. Общий принцип быстрого обнаружения нового цикла по пересекающейся паре состоит в следующем. Введём краткое обозначение для формулы (3.1) вида: Таким образом, нулевые значения pi или р2 отражают наличие цикла длиной g в протографе, иначе они отсутствуют. Если некоторая линейная комбинация значений pt, і є [l,2] равна нулю, то в зависимости от параметров пересечения представленных выше в расширенном графе кода могут появляться циклы длиной 8 и 10. Фактически, определённые таким образом модульные уравнения и будут составлять перечень правил быстрой идентификации циклов. Рассмотрим последовательно все возможные конфигурации пересечений в соответствии с имеющимися факторами.

Пусть имеется пара наиболее коротких циклов в протографе, объединённых друг с другом одной общей вершиной. На рисунке 3.7 представлен граф (а) для такого пересечения и соответствующая матрица-прототип (б) с параметрами gi = g2 = 4, ncr = 1, nv = 7, ne = 8, псл, = 1, nce = 0.

Представим аналитически модульные уравнения для циклов С4.1: v1, c1, v2, c2 и С4.2: v3, c1, v4, c3 в соответствии с формулой (3.4) в виде, здесь и далее mod(q) по умолчанию: P2=(C23-C03) + (C02-C22).

Граф и матрица-прототип пересечения двух коротких циклов с одной общей вершиной (ncr = 1, nv = 7, ne = 8, ncv = 1, nce = 0) Две наиболее простые линейные комбинации с участием p1 и p2 описываются следующим образом: pl + p2 = (c00 -c10)+(c23 -c03) + (c02 -c22)+(cu -c01\ P\- p2 = (c00 -c10)+(c22 -c02)+(c03 -c23)+(cn -с01У (3.6) Не сложно обнаружить, что модульные уравнения (3.6) образуют два независимых цикла длиной gxi = 8, а именно Сs.i . vi, сі, V4, сз, У з, сі, V2, C2 и С8.2. Vi, a, vj, cj, v4, СІ, v2, C2. Если обход циклов станет по какой-либо причине равнонаправленным (псг = 0) это не повлияет на конечный результат, т.к. выражения (3.6) просто поменяются местами. Таким образом, правило идентификации цикла длиной gxi по рассматриваемому пересечению описывается формулой: Р\=±Р2-- (3.7) Любые линейные комбинации, отличные от (3.7), не образуют циклов длиной 8 или 10 в силу того, что количество разностных компонент становится больше четырёх. Этот факт также подтверждён экспериментально, результаты отражены в таблице 3.1, где абсолютная и относительная доли циклов длиной gxi из всех возможных перестановок z"e.