Алгоритмы анализа и синтеза помехоустойчивых низкоплотностных кодов в системах телерадиовещания тема диссертации и автореферата по ВАК РФ 05.12.04, кандидат наук Овинников, Алексей Анатольевич

• Овинников, Алексей Анатольевич
• кандидат наук
• 2017

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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1 СИНТЕЗ КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЁТНОСТЬ

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

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

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

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

1.3.2 Процедура PEG

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

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

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

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

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

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

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

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

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

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

2 АЛГОРИТМЫ СИНТЕЗА РЕГУЛЯРНЫХ КВАЗИЦИКЛИЧЕСКИХ НИЗКОПЛОТНОСТНЫХ КОДОВ НА ОСНОВЕ КОМБИНАТОРНЫХ СТРУКТУР И МОДУЛЬНЫХ АЛГОРИТМОВ

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

2.1.1 Введение

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

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

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

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

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

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

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

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

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

3 АНАЛИЗ СТРУКТУРЫ ГРАФОВ ТАННЕРА КВАЗИЦИКЛИЧЕСКИХ КОДОВ С НИЗКОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЁТНОСТЬ

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

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

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

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

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

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

4 ОЦЕНКА ПОМЕХОУСТОЙЧИВОСТИ И СТРУКТУРНЫХ СВОЙСТВ ГРАФОВ ТАННЕРА КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЁТНОСТЬ В СТАНДАРТАХ ЦИФРОВОГО ТЕЛЕРАДИОВЕЩАНИЯ

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

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

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

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

Заключение

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

Приложение I. Условные обозначения, аббревиатуры, сокращения и термины

Приложение II. Копии актов внедрения

Введение диссертации (часть автореферата) на тему «Алгоритмы анализа и синтеза помехоустойчивых низкоплотностных кодов в системах телерадиовещания»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личный вклад автора. Все основные результаты диссертационной

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

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

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

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

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

3 Процедура получения кодов с низкой плотностью проверок на чётность на базе систем Штейнера, реализующий синтез регулярных высокоскоростных LDPC кодов, превосходящих по помехоустойчивости аналоги в классе псевдослучайных конструкций Маккая от 0,7 до 2,5 дБ при ^е[2/3; 0,9] и PEG в пике до 0,4 дБ при ^е[0,42; 0,93] с фиксированной вероятностью битовой ошибки в pb = 10-6.

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 статьи в центральной печати, 15 тезисов докладов на конференциях, в том числе 1 статья цитируемая в системах Scopus и Web Of Science.

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

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

1 СИНТЕЗ КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК

НА ЧЁТНОСТЬ

Коды с малой плотность проверок на чётность (Low-density parity-check LDPC) относятся к классу линейных блоковых кодов, которые благодаря применению специальных алгоритмов декодирования позволяют вплотную приблизиться к пределу Шеннона [88]. Впервые LDPC коды были предложены Р. Галлагером в его докторской диссертации [51], однако в середине 60-х годов XX века они не смогли найти применения в связи в высокой вычислительной сложностью их реализации. В течение последующих 35 лет появилось незначительное количество работ [95, 6], посвящённых LDPC кодам и лишь в середине 90-х годов интерес исследователей в данной области начал быстро расти, что было вызвано работами Маккая и Нила [67, 68]. В настоящее время коды с малой плотностью проверок на чётность внедрены во многие стандарты беспроводной передачи данных [58, 59, 64], цифрового телевидения [47] и многие другие. Это связано с их высокой корректирующей способностью при сравнительно низких вычислительных затратах с возможностью эффективной реализации алгоритмов кодирования/декодирования LDPC на современной элементной базе.

В рамках первой главы диссертации будут даны основные определения LDPC кодов, понятия регулярных и нерегулярных весовых распределений с описанием оптимизационной процедуры «Density Evolution». Кроме того, будут рассмотрены алгоритмы синтеза псевдослучайных низкоплотностных кодов с использованием различных критериев. В разделе 1.4 описаны процедуры кодирования и декодирования LDPC кодов. Изложению особенностей разработанного быстрого алгоритма синтеза, а также результатам проведённого исследования посвящены разделы 1.5 и 1.6.

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

Код с малой плотностью проверок на чётность обычно задаётся своей проверочной матрицей Н размерностью М*Ы, которая обладает свойством разреженности, т.е. её строки и столбцы содержат мало ненулевых позиций по сравнению с размерностью матрицы. Помимо нулевого пространства проверочной матрицы ЬЭРС код может быть представлен с помощью графа Таннера {У,Е}, который является двудольным неориентированным графом, содержащим У=М+Ы - вершин (Ы - символьных и М - проверочных), и Е -рёбер, соединяющих вершины графа, соответствуют ненулевым позициям в проверочной матрице. Стоит отметить, что ЬЭРС, как и любой другой линейный блоковый код, может быть описан с помощью порождающей матрицы О, которая в общем случае не является разреженной и обычно используется в процедуре кодирования. Различные способы представления низкоплотностного кода приведены на рисунке 1.1.

Рисунок 1.1 — Способы представления низкоплотностных кодов

Все коды с малой плотностью проверок на чётность можно разделить на регулярные и нерегулярные. Код называется (<^Д)-регулярным, если каждый столбец и каждая строка его проверочной матрицы содержит ds и dc ненулевых элементов соответственно. При этом кодовая скорость определяется по формуле [51]:

R > 1 - i (1.1)

dc

В противном случае код является нерегулярным и описывается с помощью весовых многочленов степеней символьных и проверочных вершин A(x) и p(x), аналитические выражения [83] которых имеют вид:

d d

s max * у c max , 7

X(x) = £ Xdxd-1, p(x) = £ pdxd-1 (1.2)

d=1 d=1

где Xdlpd - доля столбцов/строк проверочной матрицы, имеющих вес d, ds max и dc max -максимальный вес столбцов и строк соответственно. Введя обозначения

1

£Ad/d = j A(x)dx, (1.3)

d>2 0

несложно показать [83], что для нерегулярного LDPC кодовая скорость может быть вычислена по следующей формуле:

R > 1-i^i. (1.4)

\Х( x )dx

J0

Было обнаружено [65], что эффективность нерегулярных LDPC конструкций превосходит регулярные в случае оптимизации весовых многочленов с использованием ряда критериев и статических характеристик канала. Существует несколько методов оптимизации, дающих асимптотически хорошие результаты, один из которых рассмотрен в разделе 1.2.

Существующие классы низкоплотностных кодов могут быть разделены на псевдослучайные [68, 56], основанные на оптимизации весовых распределений X(x), p(x) и алгоритмах компьютерного моделирования, и детерминированные [62, 24, 94, 44], использующие свойства тех объектов, на базе которых они построены.

Основными характеристиками LDPC кодов являются - минимальное кодовое расстояние (do) и величина цикла минимальной длины либо обхват

графа Таннера ^0). Для классических линейных блоковых кодов параметр do непосредственно связан с числом гарантированно исправляемых ошибок, однако низкоплотностные коды при использовании итеративного алгоритма декодирования показывают результаты близкие к пределу Шеннона при малом значении d0. В работе Р. Галлагера [51] было показано, что для ансамбля регулярных ЬЭРС кодов величина минимального кодового расстояния зависит от параметра N линейно. Позднее [95] Таннер обнаружил, что для низкоплотностных кодов с весом столбцов ds = 2 существует детерминированная связь между параметрами go и do:

¿о = , (1.5)

при которой зависимость d0(N) становится логарифмической, что негативно сказывается на энергетической эффективности таких кодовых конструкций.

Наличие коротких циклов, в особенности длиной 4 (рисунок 1.1), в графе Таннера приводит к уменьшению статической независимости итераций декодера, что отрицательно сказывается на помехоустойчивости ЬЭРС кода. В работе [51] было показано, что число независимых итераций Т зависит от обхвата графа и ограничено условиями следующего неравенства:

Т < gо/4 < Т +1. (1.6)

Однако для увеличения обхвата графа Таннера необходимо либо увеличивать параметр Ы, либо уменьшать плотность заполнения ненулевыми элементами проверочной матрицы, что значительно уменьшит энергетическую эффективность системы кодирования при минимально возможном ds = 2 [67].

1.2 Описание процедуры «Density Evolution» В работах [82] показано, что анализ энергетической эффективности

LDPC кодов может проводиться асимптотически. Для этого достаточно задать определённые значения коэффициентов весовых многочленов A(x) и р(х) (либо ds и dc для регулярных кодов) для нерегулярных конструкций. Результатом такого анализа является некоторое пороговое значение параметра канала, такого, что сходимость к нулю вероятности ошибочного декодирования достигается лишь при значениях а < а *, где а * - искомый уровень порога. Этот алгоритм получил название Density Evolution (DE) и фактически отражает изменение функции плотности распределения вероятностей принятых из канала сообщений в процессе итеративного декодирования.

Рассмотрим ряд допущений процедуры DE:

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

- теорема о концентрации [82] утверждает, что бесконечно малая доля кодов при N отклоняется от среднего по ансамблю на произвольно малую величину S. Поэтому при достаточно больших кодовых длинах среднее по ансамблю будет хорошим показателем эффективности отдельных кодов;

- декодирование осуществляется по графу, не содержащему циклов (дереву).

Схема, отражающая процесс нахождения порогового значения шума в канале, изображена на рисунке 1.2. Предполагается, что канал не обладает памятью, что в совокупности с отсутствием циклов в графе Таннера LDPC кода гарантирует статистическую независимость обрабатываемых сообщений. Следует отметить, что передача нулей по каналу осуществляется с помощью двоичной фазовой модуляции (ДФМ).

Рисунок 1.2— Идеализированная модель помехоустойчивой системы передачи информации

Рассмотрим подробнее процедуру ЭБ для АБГШ канала и регулярных ЬЭРС кодов. В качестве искомого параметра в этом случае выступает среднеквадратическое отклонение (СКО) шума - а. Логарифмические отношения правдоподобий сообщений, которыми обмениваются символьные и проверочные вершины декодера в процессе его работы, могут быть описаны функциями плотности распределения вероятности (ПРВ). Анализ их изменения от одной итерации к другой следует начать с введения следующих обозначений. Пусть р1 (т5) - функция ПРВ сообщения ш1' при его передаче от кодовых узлов к проверочным на 1-м шаге, а рС (шс) - функция ПРВ

сообщения шс при его передаче от проверочных вершин к символьным на I-

м шаге и, наконец, р0 (ш0) - функция ПРВ логарифмических отношений

правдоподобия вектора на входе итеративного декодера. Предполагая, что все случайные величины в декодере независимы, определим их сумму, как свёртку функций ПРВ на 1-ой итерации следующим образом:

р\ = Р0 *р1 *...*Р1 = Р0 *[рс], (1.7)

где символов * - обозначена операция свёртки, рс - вектор функций ПРВ

сообщений от ds узлов. На практике эта процедура может быть выполнена с использованием быстрого преобразования Фурье:

Р1 = Р"

1 {р р к р Г 1

(1.8)

где операторы прямого и обратного преобразования обозначены, как Р {•} и Р _1{}. Далее вычислим функции рС (тс) по формуле:

-с (0,тс ) =

1

Р(о>*) Р1 [1,т ) =

1

Р1 (°т )= . у( ЛРУ°'2), Р1 (1т )=—ГГС]

ипп(т ) иппхт )

р!* ),

р(°,* ) =

1

БХикХ* )

( г г

Р (ф(*)), Р(1,2)

1

* ) =

зткХг)

Р1 (Ф)),

(1.9)

ф(*) = - 1п

1апк

- 1п

1апк

-т

V V V

2

После чего процедура итеративно повторяется. В компактной форме алгоритм ЭБ может быть представлен в виде:

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

- установить СКО шума в канале - а, значительно меньше ожидаемого предельного результата. Установить счётчик I в нулевое состояние;

- согласно формуле (1.9) определить значения функции рЦ (т5);

- увеличить значение счётчика I на единицу и рассчитать значение функций рС (тс) и р5 (т5);

- если 1< 1тах и

1Р1 (Т^Т< Ре

(1.10)

то необходимо незначительно увеличить параметр а и перейти к пункту б). В противном случае найдено пороговое значение а = а *.

Процедура ЭБ малоприменима для кодов малой длины (#<1000 бит) в силу заложенных в ней ограничений, а также она не позволяет синтезировать граф Таннера в соответствии с найденными весовыми многочленами А(х) и р(х) либо параметрами ds и dc. Эта задача может быть эффективно решена с помощью алгоритмов рассмотренных в следующем разделе.

х>

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

чётность

В настоящее время на практике [58, 59, 64, 47] широкое распространение получили ЬЭРС коды, проверочная матрица которых обладает строго определённой структурой и может быть записана в компактной форме. При этом наиболее эффективный до сегодняшнего дня код является псевдослучайным [39]. Кроме того, в решении задачи синтеза энергетически эффективных кодовых конструкций часто приходится использовать вероятностные алгоритмы синтеза низкоплотностных кодов, поэтому целесообразно представить некоторые них.

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

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

Используя датчик псевдослучайных чисел, синтезировать проверочную матрицу с количеством ненулевых элементов равным ds на столбец при этом вес строк должен стремиться к равномерному и равному dc. Дополнительно на код накладывается ряд ограничений:

- циклы длиной 4 должны отсутствовать;

- по возможности дополнительно удаляются короткие циклы большие

четырёх;

- структура матрицы И должна соответствовать: И = [И1 Н2 ], причём И обратима.

Помимо регулярных кодовых конструкций рассмотренный алгоритм может быть использован для синтеза нерегулярных ЬЭРС кодов, для чего необходимо в качестве входных параметров выбрать соответствующие весовые многочлены Х(х) и р(х).

Одна из основных проблем кодов, разработанных Маккаем, заключается в сложности реализации вычислительно эффективной процедуры кодирования. При помощи алгоритма Гаусса-Жордана [4] либо за счёт умножения матрицы И на И2"1 происходит преобразование искомой матрицы к систематической форме [Рт I]. При этом генераторная матрица О в общем случае не является разреженной, поэтому сложность кодирования оказывается высокой. Также стоит отметить, что высокую трудоёмкость представляет анализ свойств кодов Маккая, в особенности оценка минимального кодового расстояния. Поэтому для определения эффективности синтезированных кодов остаётся лишь метод Монте Карло.

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

1.3.2 Процедура PEG

Задача синтеза двудольного графа Таннера с наибольшим обхватом относится к числу сложных комбинаторных проблем. Тем не менее, для сравнительно большого параметра go она реализуема. В работе [56] была предложена процедура PEG (Progressive-Edge-Growth), позволяющая синтезировать граф Таннера, для которого рост обхвата пропорционален логарифму от числа проверочных вершин. Основной целью алгоритма является максимизация локального цикла минимальной длины (g) в процессе добавления к графу новых ветвей. Проблема синтеза графа Таннера с большим обхватом заключается в выборе такого множества рёбер Es для

Список литературы диссертационного исследования кандидат наук Овинников, Алексей Анатольевич, 2017 год

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

1 Блейхут Р. Теория и практика кодов контролирующих ошибки / Р. Блейхут // М.: Мир - 1986. - 576 с.

2 Варгузин В. Вблизи границы Шеннона / В. Варгузин // ТелеМультиМедия - июнь - 2005 - с. 3-10.

3 Воропаев А. Н. Учёт обхвата при подсчёте коротких циклов в графах Таннера / А. Н. Воропаев // Информационные процессы: Том 11 - №2 - 2011 -с. 225-252.

4 Голуб Дж., Ван Лоун Ч. Матричные вычисления: Пер. с англ. / Дж. Голуб, Ван Лоун Ч. - М.: Мир, 1999 - 548 с.

5 ГОСТ Р 54309-2011 Аудиовизуальная информационная система реального времени (РАВИС). Процессы формирования кадровой структуры, канального кодирования и модуляции для системы цифрового наземного узкополосного радиовещания в ОВЧ диапазоне. Технические условия. - М.: Изд -во стандартов - 43 с

6 Зяблов В. В., Пинскер М.С. Оценка сложности исправления ошибок низкоплотностными кодами Галлагера. Проблемы передачи информации, XI(1) / В. В. Зяблов, М.С. Пинскер: - ИППИ РАН - 1975 - с. 23-36.

7 Лихобабин Е.А., Овинников А.А. Особенности системы помехоустойчивого кодирования DVB-T2 // Радиочастотный спектр. - №4. - М. , 2011, - С. 24 - 31.

8 Морелос-Сарагоса Р. Исскуство помехоустойчивого кодирования. Методы, алгоритмы применение. / Р. Морелос-Сарагоса - М.: Техносфера, 2006 -320с.

9 Овинников А.А., Бакке А.В. Исследование влияния циклов в графах Таннера и распределения единиц в столбцах LDPC кодов на помехоустойчивость

системы // Цифровая обработка сигналов и её применение - DSPA - 2009: Труды РНТОРЭС имени А.С. Попова. Серия: Цифровая обработка сигналов и её применение: )»: Тез. докл. Выпуск XI-1. - М., 2009. - С. 106 - 108.

10 Овинников А.А., Иртюга В.А. Исследование оптимизационных алгоритмов формирования проверочных матриц LDPC кодов // Цифровая обработка сигналов и её применение - DSPA - 2010: Труды РНТОРЭС имени А.С. Попова. Серия: Цифровая обработка сигналов и её применение: )»: Тез. докл. Выпуск XII-1. - М., 2010. - С. 28 - 31.

11 Овинников А.А. О синтезе низкоплотностных кодов // Современные проблемы радиотехники и телекоммуникаций: Тез. докл. - СевНТУ. -Севастополь, 2012 - С. 348.

12 Овинников А.А. Низкоплотностные коды в стандартах беспроводной передачи данных. // Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика»: Тез. докл. - М., 2012. - С.225.

13 Овинников А.А. Анализ характеристик кодов с низкой плотностью проверок на чётность // МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» »: Тез. докл. Рязань, 2012. - С. 26 -28.

14 Овинников А.А. Многокритериальный анализ ансамблей LDPC кодов // МНТК «Фундаментальные проблемы радиоэлектронного приборостроения»: Тез. докл. - М., 2012. С. 95 - 97.

15 Овинников А.А., Витязев В.В. Статистический анализ ансамблей LDPC кодов // Всероссийская мультиконференция «Радиоэлектронные средства передачи и приёма сигналов и визуализации информации» »: Тез. докл. Таганрог 2012. - С.43 - 45.

16 Овинников А. А. Синтез низкоплотностных кодов на основе уравновешенных неполных блок-схем / А. А. Овинников // Цифровая обработка сигналов - №4 - 2014 - с. 22-27.

17 Овинников А.А. Анализ свойств и параметров низкоплотностных кодов, синтезированных по алгоритму Таннера / А. А. Овинников // Международная научно-техническая конференция «Фундаментальные проблемы радиоэлектронного приборостроения»(ШТЕКМЛТ1С-2014) - Москва 2014 - с. 80-83.

18 Овинников А.А. Исследование влияния спектра связанности циклов в графе Таннера на энергетический выигрыш кодирования известных LDPC кодов // Цифровая обработка сигналов. - №4. - М., 2015, С. 24 - 29.

19 Овинников А.А. Косвенная оценка снижения эффективности декодирования низкоплотностных кодов на уровне насыщения ошибок // МНТК «Радиоэлектронные устройства и системы для инфокоммуникационных технологий (REDS-2015)»: Тез. докл. - М., 2015. С. 130 - 134.

20 Овинников А.А. Способ идентификации циклов в графах Таннера LDPC кодов на основе пересечений коротких замкнутых структур в протографах // Цифровая обработка сигналов. - №4. - М., 2016, С. 26 - 30.

21 Овинников А.А. Правила для оценки пересекающихся циклов в графах Таннера квазициклических кодов с низкой плотностью проверок на чётность // Всероссийская конференция «Радиоэлектронные средства получения, обработки и визуализации информации» Тез. докл. - М., 2016. - С.225 - 229.

22 Овинников А.А. Алгоритм быстрой идентификации циклов в графах Таннра квазициклических кодов с низкой плотностью проверок на чётность // Цифровая обработка сигналов и её применение - DSPA - 2017: Труды РНТОРЭС имени А.С. Попова. Серия: Цифровая обработка сигналов и её применение: Тез. докл. - М., 2017. - С. 80 - 85.

23 Овинников А.А. Об алгоритме поиска циклов в графах Таннера кодов с низкой плотностью проверок на чётность // МНТК «Радиолокация, навигация, связь»:Тез. докл. - Воронеж ВГУ, 2017. - С.248 - 252.

24 Овчинников А. А. Некоторые замечания о спектральных свойствах EG-кодов. / А. А. Овчинников - VII Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2004.

25 Холл М. Комбинаторика / М. Холл - М.: Мир, 1970 - 421 с.

26 Alon N., Yuster R., Zwick U. Finding and counting given length cycles / N. Alon, R. Yuster, and U. Zwick // Algorithmica, 17 - 1997 - p. 209-223.

27 Anderson I., Combinatorics of Finite Sets / I. Anderson // Dover Publications inc - 1989 - р. 272.

28 ATSC: ATSC Physical Layer Protocol Standard, document A/322, Adv. Television Syst. Committee, Washington, DC, USA, Sep. 2016.

29 Baldi М. LDPC codes in the McEliece cryptosystem: attacks and countermeasures / M. Baldi // NATO Science for Peace and Security Series - D: Information and Communication Security, vol. 23 - IOS Press, 2009 - p. 160-174.

30 Baker C.A. Extended Skolem sequences / C.A. Baker J. // Gombin. Des., 3 -1995 - р. 363-379.

31 E. Birmel e, R. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto Optimallisting of cycles and st-paths in undirected paths / E. Birmel e, R. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto // InProceedings of the Twenty-FourthAnnual ACM-SIAM Symposium on Discrete Algorithms - 2013 - p. 1884-1896.

32 Blanksby A., Howland C. A 690-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder / A. Blanksby, C. Howland // IEEE Journal of Solid-Sate Circuits - 37(3) - March 2002 - р. 402-412.

33 Bonello N., Chen S., Hanzo L. Design of Low-Density Parity Check Codes / N. Bonello, S. Chen, L. Hanzo // IEEE Vehicular Technology, vol. 6 - no. 4 -December 2011 - p.16-23.

34 Bose R. C. On the construction of balanced incomplete block designs / R. C. Bose // - 1939 - с. 48.

35 Chilappagari Shashi Kiran, Nguyen Dung Viet, Vasic Bane, Marcellin Michael W. On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes / Shashi Kiran Chilappagari, Dung Viet Nguyen, Bane Vasic, Michael W. Marcellin // IEEE Transactions on Information Theory, vol. 56, no. 4 -2010 - p. 1600 - 1611

36 China's state administration of radio and television, "Mobile Multimedia Broadcasting Part 1: Framing Structure, Channel Coding and Modulation For Broadcasting Channel" - 2006

37 Chinese Standard GB20600-2006. Framing structure, channel coding and modulation for digital television terrestrial broadcasting system

38 Chinese Standard GD/J 068-2015. Frame Structure, Channel Coding and Modulation for Digital Television/Terrestrial Multimedia Broadcasting-Advanced (DTMB-A)

39 Chung S.-Y., Forney G. D., Richardson Jr., T., Urbanke R. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit / S.-Y. Chung, G. David Forney, Jr., T. Richardson, R. Urbanke // IEEE Communication Lett., vol. 4 -no. 2 - February 2001 - p. 58-60.

40 Churchill D. Algorithms for constructing generalized Skolem-type sequences / D. Churchill // Master's thesis, Memorial University of Newfoundland:- 2005 -p. 19.

41 Colboum C. J., Rosa A. Triple systems / C. J. Colboum, A. Rosa // Oxford University Press, New York:- 1999 - p. 550.

42 Colbourn Ch. J., Mendelsohn E., Rosa A., Sirfifi J. Anti-Mitre Steiner Triple Systems / Ch. J. Colbourn, E. Mendelsohn, A. Rosa, J. Sirfifi // Graphs and Combinatorics - 10, 1994 - p. 215-224.

43 Demaine Erik D., Reidl Felix, Rossmanith Peter, Villaamil Fernando S anchez, Sikdar Somnath, Sullivan Blair D. Structural sparsity of complex networks: Random graph models and linear algorithms / Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando S anchez Villaamil, Somnath Sikdar, and Blair D. Sullivan // CoRR, abs/1406.2587 - 2014.

44 Divsalar D., Dolinar S., Jones C. Construction of Protograph LDPC Codes with Linear Minimum Distance / D. Divsalar, S. Dolinar, C. Jones // IEEE International Symposium on Information Theory - July 2006 - р 664 - 668.

45 Eldin A. Sh., Shalaby N., Al-Thukair F. Construction of Skolem sequences / A. Sh. Eldin, N. Shalaby, F. Al-Thukair // Int. J. Comput. Math., 70(2) - 1998 - р. 333-345.

46 Encyclopedia of Sparse Graph Codes. Database of Codes [электрон. ресурс].

- Режим доступа: http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html

47 ETSI Standart TR 102 376 V1.1.1: Digital Video Broadcasting (DVB) User Guidelines for the Second Generation System for Broadcasting, Interactive Services, News Gathering and Other Broadband Satellite Applications (DVB-S2).

48 Explicit Formulae [электрон. ресурс]. - Режим доступа: http://flowproblem.ru/cycles/explicit-formulae.

49 Fossorier M. P. C. Quasi-Cyclic Low-Density Parity-Check Codes From Circulant Permutation Matrices / M. P. C. Fossorier // IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50 - NO. 8 - AUGUST 2004 - p. 1788-1793.

50 Franceti'c N., Mendelsohn E. A survey of Skolem-type sequences and Rosa's use of them / N. Franceti'c, E. Mendelsohn // Math. Slovaca, 59(1) - 2009 - р. 39-76.

51 Gallager R. Low-density Parity-Check codes / R. Gallager - Ph. D. thesis/ MIT - 1963 - р. 90.

52 Gholami M., Mostafaieeon F. S. On the girth of Tanner (3,7) Quasi-Cyclic LDPC codes / M. Gholami, F. S. Mostafaieeon // Transactions on Combinatorics, vol. 1,

- no.2 - 2012 - p. 1-16.

53 Jin H., Khandecar A., McEliece R. Irregular repeat-accumulate codes / H. Jin, A. Khandecar, R. McEliece // Proc. 2nd. Int. Sump. On Turbo Codes and Related Topics, Brest, France, p. 1-8 - September 2000 - р. 8.

54 Johnson S. J. Iterative Error Correction. Turbo, Low-Density Parity-Check and Repeat-Accumulate Codes / S. J. Johnson // Cambridge University Press - 2010 -р. 356.

55 Johnson S. J., Weller S. R. Construction of low-density parity-check codes from Kirkman triple systems / S. J. Johnson, S. R. Weller // Global Telecommunications Conference - GLOBECOM '01, vol.2 - 2001 - p. 970 - 974.

56 Hu X. Y., Eleftheriou E., Arnold D. M. Regular and Irregular Progressive Edge-Growth Tanner Graphs / X. Y. Hu, E. Eleftheriou, D. M. Arnold // IBM Reseach: Zurich Reseach Laboratory - 2003 - p. 386 - 398

57 Huang Qin, Diao Qiuju, Lin Shu, Abdel-Ghaffar Khaled Trapping sets of structured LDPC codes / Qin Huang, Qiuju Diao, Shu Lin, Khaled Abdel-Ghaffar // Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on -2011 - p. 1086 - 1090.

58 IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks -Specific Requirements, Part 11: Wireless LAN Medium Access Control (Mac) and Physical Layer (PHY) Specifications. Amendment 5: Enhancements for Higher Throughput, October 2009.

59 IEEE Std. 802.16e - 2005, Amendment to IEEE Standard for Local and Metropolitan Area Networks, "Part 16: Air interface for fixed broadband wireless access systems - Physical and Medium Access Control Layers for Combined Fixed and Mobile Operations in Licensed Bands", Feb. 2006.

60 ITU-T Rec. G.9960, Unified high-speed wire-line based home networking transceivers - System architecture and physical layer specification, ITU-T Std., June 2010

61 Kim S., No J-S., Chung H., Shin D.-J., "Girth of Tanner's (3, 5) Quasi-Cyclic LDPC Codes / S. Kim, J-S. No, H. Chung, D.-J. Shin // Proceedings. International Symposium on Information Theory - 2005 - p. 1632 - 1636.

62 Kou Y., Lin S., Fossorier M. Low-density parity-check codes based on finite geometries: a rediscovery and new results / Y. Kou, S. Lin, M. Fossorier // IEEE Trans. Info. Theory, vol. 47- no. 7- November 2001 - p. 2711-2736.

63 Landner S., Milenkovic O. Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes / S. Landner, O. Milenkovic // Wireless Networks, Communications and Mobile Computing, 2005 International Conference on-2005 - p. 630 - 635.

64 Low Density Parity Check Codes for Use in Near-Earth and Deep Space. Orange Book. Issue 2. September 2007.

65 Luby M. G., Mitzenmacher M., Shokrollahi M. A., Spielman D. A. Improved low-density parity-check codes using irregular graphs / M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman // IEEE Trans. Info - Theory 47(2) - February 2001 - p. 585-598.

66 MacKay D. Encyclopedia of Sparse Graph Codes. Database of Codes. Department of Physics [электрон. ресурс]. - Режим доступа: http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html

67 MacKay D. Good error correcting codes based on very sparse matrixes / D. MacKay // IEEE Trans. Information Theory, vol. 45 - no. 3 - March 1999 - p. 399-431.

68 MacKay D., Neal R. Good codes based on very sparse matrixes / D. MacKay, R. Neal // Cryptography and Coding 5th IMA Conf - October 1995 - р. 100-111.

69 MacKay D. J. C., Wilson S. T., Davey M. C. Comparison of constructions of irregular Gallager codes / D. J. C. MacKay, S. T. Wilson, M. C. Davey // IEEE Transactions on Communications, vol. 47 - no. 10 - Oct. 1999 - p. 1449-1454.

70 Malema G. Constructing Quasi-Cyclic LDPC Codes Using a Search Algorithm / G. Malema // International Symposium on Signal Processing and Information Technology - Cairo Egypt - December 2007 - p.969-973.

71 Mathon, R., Phelps, K.T., Rosa, A. Small Steiner triple systems and their properties / R. Mathon, , K.T. Phelps, A. Rosa // Ars. Comb. 15 - 1983 - p. 3-110.

72 McEliece R. J. A Public-Key Cryptosystem Based On Algebraic Coding Theory / R. J. McEliece // DSN Progress report - 1978 - p. 114-116.

73 McGowan J. A., Williamson R. C. Loop Removal from LDPC Codes / J. A. McGowan, R. C. Williamson // Information Theory Workshop - 2003 - p. 230233.

74 Milenkovic O., Kashyap N., Leyba D. Shortened Array Codes of Large Girth / O. Milenkovic, N. Kashyap, D. Leyba // IEEE Transactions on Information Theory, vol. 52 - no. 8 - 2006 - p. 3707 - 3722.

75 Monico C., Rosenthal J., Shokrollahi A., "Using low density parity check codes in the McEliece cryptosystem / C. Monico, J. Rosenthal, A. Shokrollahi // in Proc. IEEE International Symposium on Information Theory (ISIT 2000), Sorrento, Italy - Jun. 2000 - p. 215.

76 Nguyen D.V., Chilappagari S.K., Marcellin M.W., Vasic B.V. LDPC Codes from Latin Squares Free of Small Trapping Sets / D.V. Nguyen, S.K. Chilappagari, M.W. Marcellin, B.V. Vasic // CoRR - 2010 - p. 21.

77 Ovinnikov A.A., Vityazev V.V. Fast estimation of error floor effect for irregular low-density pariry-check codes // International Siberian Conference on Control and Communications (SIBCON). 2015. - P.1 - 4.

78 O'Keefe E.S. Verification of the conjecture of Th. Skolem / E.S. O'Keefe // Math. Scand. 9 - 1961 - p. 80-82.

79 O'Sullivan M. E. Algebraic Construction of Sparse Matrices With Large Girth / M. E. O'Sullivan // IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52 - NO. 2 - FEBRUARY 2006 - p. 718-727.

80 Richardson T. J., "Error floors of LDPC codes / T. J. Richardson // in 41st Annu. Allerton Conf. Communications, Control and Computing, Urbana-Champaing -IL - Oct. 2003 - p. 1426-1435.

81 Richarson T. J., Shokrollahi M. A., Urbanke R. L. Finite length analysis of varous low-density parity-check ensembles for the binary erasure channel / T. J. Richarson, M. A. Shokrollahi, R. L. Urbanke // in Proc. IEEE Int. Symp. Information Theory, Lausanne, Switzerland, Jun./Jul. - 2002, p. 1.

82 Richardson T., Urbanke R. Modern Coding Theory / T. Richardson, R. Urbanke //, Cambridge, Cambridge University Press:- 2008 - p. 590

83 Richardson T. J., Urbanke R. L., Shokrollani M. A. Design of Capasity-Approaching Irregular low-Density Parity-Check Codes / T. J. Richardson, R. L. Urbanke, M. A. Shokrollani // IEEE Transactions on Information Theory - 47(2) -February 2001 - p. 619 - 637.

84 Rosa A. Algebraic properties of designs and recursive constructions / A. Rosa // Congressus Numer.13 - 1975 - p. 183-200.

85 Ryan W. E., Lin S., Channel Codes Classical and Modern / W. E. Ryan, S. Lin // Cambridge, Cambridge University Press: - 2009 - p. 710 .

86 Schwartz M., Vardy A. On the stopping distance and the stopping redundancy of codes / M. Schwartz, A. Vardy // IEEE Transactions on Information Theory, vol. 52, no. 3 - 2006 - p. 922 - 932

87 Shalaby N. Skolem sequences: Generalizations and applications / N. Shalaby // Doctoral Thesis, McMaster University: - 1991 - p. 132.

88 Shannon C. A. mathematical theory of communication / C. A. Shannon // Bell Systems Tech. J.: Part I - 1948 - p. 379-423,

89 Shannon C. A mathematical theory of communication / C. A. Shannon // Bell Systems Tech. J.: Part II - 1948 - p. 623-656

90 Shin M.-H., Kim J.-S., Song H.-Y. Minimum Distance Dounds for Irregular QC-LDPC Codes and their Applications / M.-H. Shin, J.-S. Kim, H.-Y. Song // ISIT -July 2004 - p. 311.

91 Skolem Th. On certain distributions of integers in pairs with given differences / Th. Skolem // Math. Scand 5 - 1957 - p. 57-68.

92 Skolem Th. Some remarks on the triple systems of Steiner / Th. Skolem // Math. Scand., 6 - 1958 - 273-280.

93 Smarandache R., Vontobel P. O. Pseudo-Codeword Analysis of Tanner Graphs From Projective and Euclidean Planes / R. Smarandache, P. O. Vontobel // IEEE Transactions on Information Theory, vol. 53 - no. 7 - 2007 - p. 2376 - 2393.

94 Tai Y. Y., Lan L., Zeng L.-Q., Lin S., Abdel-Ghaffar K. Algebraic construction of quasi-cyclic LDPC codes for AWGN and erasure channels / Y. Y. Tai, L. Lan, L.-Q. Zeng, S. Lin, K. Abdel-Ghaffar // IEEE Trans. Communication, vol. 54 -no. 10 - October 2006 - p. 1765-1774.

95 Tanner R. M. A recursive approach to low complexity codes / R. M. Tanner // IEEE Trans. Information Theory, vol. 27 - no. 9 - September 1981 - p. 533-547.

96 Tanner R. M., Sridhara D., Fuja T. A class of group-structured LDPC codes / R. M. Tanner, D. Sridhara, T. Fuja // in Proc. ISTA, Ambleside, England - 2001 - p. 5.

97 Tanner R. M., Sridhara D., Sridharan A., Fuja T. E., Costello D. J. LDPC block and convolutional codes based on circulant matrices / R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, D. J. Costello // IEEE Transactions on Information Theory, vol. 50 - no. 12 - 2004 - p. 2966 - 2984.

98 Vasic B. Structured iteratively decodable codes based on Steiner systems and their application in magnetic recording / B. Vasic // proceedings of Globecom: 2001 -p. 2954 - 2960.

99 Zhang Yifei, Ryan W.E., Li Yan, Structured eIRA codes with low floors / Yifei Zhang, W.E. Ryan, Yan Li // Proceedings. International Symposium on Information Theory: 2005 - p. 174 - 178.

Приложение I. Условные обозначения, аббревиатуры, сокращения и

термины Список условных обозначений Знаки

*

— операция свертки;

т

т — знак транспонирования; ' — процедура триангуляции матрицы;

Латинские символы А— 1) матрица вида ННТ;

2) компонента проверочной матрицы;

3) псевдослучайное число;

а — параметр алгоритма Таннера, число в поле Галуа; ау — элементы матрицы инцидентности А; В — 1) базовая или матрица смежности протографа;

2) компонента проверочной матрицы; В1 — блоки матрицы инцидентности; Ь— 1) параметр УНБС;

2) параметр алгоритма Таннера, число в поле Галуа; с — кодовый вектор;

С — 1) компонента проверочной матрицы;

2) псевдослучайное число;

3) множество синтезированных проверочных матриц;

Сй — множество символьных вершин, содержащих минимум один цикл; Ср — полный ансамбль кодов на основе систем Штейнера; Стр — полный ансамбль кодов Таннера;

С^ — ансамбль кодов Таннера, полученный путем укорочения более

высокоскоростных экземпляров; Сти — ансамбль кодов Таннера с уникальными длинами и скоростями; с;—]-я проверочная вершина;

С— информационная часть кодового слова;

Ср— проверочная часть кодового слова;

с^(х) — элементы матрицы инцидентности;

О — компонента проверочной матрицы;

d— вес текущей вершины графа Таннера;

^ — минимальное кодовое расстояние;

d0LB — нижняя граница минимального кодового расстояния;

d0_uв — верхняя граница минимального кодового расстояния;

di — вес /-ой вершины графа Таннера;

ds — количество ненулевых элементов столбца проверочной матрицы регулярного ЬБРС кода;

dc — количество ненулевых элементов строки проверочной матрицы регулярного ЬБРС кода;

ds тах — максимальный вес столбцов проверочной матрицы; dc тах— максимальный вес строк проверочной матрицы; ds — вес Sj символьной вершины

Е — 1) количество рёбер графе Таннера;

2) компонента проверочной матрицы; Еь — энергия бита;

Е^ — множество рёбер для символьной вершины Sj

— оператор прямого преобразования; Е'1 {•}— оператор обратного преобразования; О - порождающая/генераторная матрица; Ог - протограф или базовый граф; О'г - граф Таннера; ОЕф — поле Галуа размерности т g - 1) размер произвольного цикла в графе Таннера;

2) размер подматриц А и С;

g0 - обхват графа Таннера;

gmax- максимальная длина цикла в графе Таннера;

^ - локальный цикл минимальной длины;

gx- требуемое значение обхвата графа Таннера;

J - квадратная (иХи) матрица, состоящая исключительно из единиц;

у — номер символьной вершины;

Н — проверочная матрица, размерностью М*Ы;

Н1 и Нр — псевдослучайная компонента проверочной матрицы Н

Н2 и Н8 — регулярная компонента проверочной матрицы Н

Нс - компактная форма представления квазициклической проверочной

матрицы ЬЭРС кода

Иу — элемент /-ой строки и у-го столбца проверочной матрицы Н

Н(х) — проверочный полином циклического кода

I — квадратная диагональная единичная матрица;

/ — номер проверочной вершины;

К — число бит в информационном слове;

Ку — коэффициент расширения ансамбля ЬБРС кодов;

к — 1) параметр УНБС;

2) коэффициент кратности параллельных ветвей протографа;

3) глубина построения дерева цепей;

максимальная степень полинома р у (х) = ха° + ха1 н-----ь х1,1,

описывающего первую строку подматрицы Р^у ;

Ь (г) — количество символьных вершин, входящих в состав циклов минимальной длины

1) счетчик итерации;

2) уровень построения дерева;

3) длина цикла;

4) число столбцов в компактной форме представления

проверочной матрицы квазициклического ЬЭРС кода;

¡т

тах

максимальное количество итераций декодирования;

1) количество проверочных вершин в графе Таннера;

2) количество проверочных уравнений;

М—

т — число строк в компактной форме представления проверочной матрицы

квазициклического ЬЭРС кода; N— 1) длина кода;

2) количество символьных вершин в графе Таннера; N0— спектральная плотность мощности шума; Na— коэффициент расширения ансамбля ЬБРС кодов по столбцам; N— коэффициент расширения ансамбля ЬБРС кодов по строкам; N1 — множество проверочных вершин, которые могут быть достигнуты из

символьной вершины за ¡ и менее переходов по рёбрам графа;

^— максимальная длина кодового слова;

п — количество элементов в ансамбле;

пСг — взаимное направление обхода пересекающихся циклов;

псу — количество общих вершин между пересекающими циклами;

псе — количество общих рёбер между пересекающими циклами;

пе — количество общих рёбер в подграфе пересечения;

пу — количество общих вершин в подграфе пересечения;

пт/п— число экземпляров подграфов множества «остановки»;

п^п) — абсолютная доля циклов длиной g при переборе всех возможных

перестановок из 2 по п; О(-) — асимптотическая оценка вычислительной сложности алгоритма;

Р — матрица чётности;

Р(и\с) — условная вероятность передачи вектора и при приёме с; рг— кратное обозначение модульного уравнения;

р1 (т5) — функция ПРВ сообщения т при его передаче от символьных узлов к проверочным на ¡-м шаге;

р (т ) — функция ПРВ сообщения т° при его передаче от проверочных вершин к символьным на ¡-м шаге;

р0 (т0) — функция ПРВ логарифмических отношений правдоподобия вектора на входе итеративного декодера; рс — вектор функций ПРВ сообщений от ds узлов; Ре — пороговая вероятность ошибки;

р^(х) — полиномиальное представлении квадранта квазициклической

проверочной матрицы ЬЭРС кода;

ц — отношение сигнал-шум, эквивалентно Е^0;

Цел — предельное значение ОСШ ЬЭРС кода с заданным весовым

распределением по алгоритму ЭБ с учётом аппроксимации Гаусса;

Ццт(Я) — предел двоичной модуляции с учётом мягких оценок

демодулятора в канале с АБГШ;

дх - вероятность того, что все символы кроме х являются независимыми Я — скорость кодирования;

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

ЯР — скорость кодирования с учётом линейно-зависимых строк в проверочной матрице Н; г— параметр УНБС;

5— 1) комбинаторная последовательность; 2) целое число в диапазоне 0...215-!;

Sd— множество остановки;

Smin— размер множества остановки;

Sr— последовательность Роса;

Ss— последовательность Сколема;

S(n)— спектр метрик связанности циклов длиной g;

Sj — j-я символьная вершина;

T — 1) число независимых итераций;

2) компонента проверочной матрицы; U— множество возможных информационных слов; u— информационный вектор; V - количество вершин в графе Таннера; z— 1) размерность поля Галуа;

2) размер квадранта квазициклического кода; zp— размер квадранта, полученный на практике; zt— минимально возможный размер квадранта.

Греческие символы а— 1) нормирующий множитель;

2) коэффициент пропорциональности;

3) примитивный элемент поля Галуа; в— коэффициент пропорциональности;

Ацт — относительный к пределу Шеннона ЭВК LDPC кода; 8 — произвольно малая величина;

8(i) — доля кодовых вершин, не входящих в состав циклов длиной равной обхвату графа;

^(ш) — множество кодовых позиций, участвующих в m-ом проверочном уравнении;

Л— оценка кодового слова с выхода декодера IBP; X— параметр УНБС;

X(x) — весовое распределение символьных вершин графа Таннера;

Xd(x) — доля столбцов проверочной матрицы, имеющих вес d;

/u(l) — множество проверок, в которых участвует l-ый символ принятого

вектора;

[1 и ¡л2 — первое и второе собственное число матрицы H • H ;

П — связанность цикла длиной g c остальными циклами из Cd;

ng(zn) — относительная доля циклов длиной g при переборе всех возможных

перестановок из z по n;

Пг — параметр п для регулярных LDPC кодов;

р(х) — весовое распределение проверочных вершин графа Таннера; pd(x) — доля строк проверочной матрицы, имеющих вес d; а— среднеквадратическое отклонение шума;

а * — искомый уровень порога насыщения вероятности ошибки декодирования;

amin — минимальное СКО шума; и— количество элементов в УНБС; ф — базисная функция алгоритма DE.

Список аббревиатур

BFA - bit flip algorithm (алгоритм с инверсией бит);

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

DE - Density Evolution (алгоритм «эволюция плотности») DVB-T2 - стандарт европейского цифрового наземного вещания DVB-T2; DTMB - китайский стандарт наземного стационарного вещания первого поколения;

DTMB-A - китайский стандарт наземного стационарного вещания второго поколения;

IBP - iterative belief propagation (алгоритм итеративного распростанения доверия);

IRA - irregular repeat accumulate (нерегулярный код повторения-накопления);

QC - quasi-cyclic (кваци-циклический код)

LDPC - Low-density parity-check (коды с малой плотность проверок на чётность);

МАР - maximum a posterior probability (алгоритм максимума апостериорной вероятности);

PEG - Progressive-Edge-Growth (алгоритм последовательного добавления ветвей в граф Таннера);

АБГШ - аддитивный белый гауссовский шум;

ВАК - высшая аттестационная комиссия;

ДСК - двоичный симметричный канал;

ДФМ - двоичная фазовая модуляция;

НИР - научно-исследовательская работа;

ОВЧ - диапазон очень высоких частот;

ОСШ - отношение сигнал-шум;

ПВР - плотность распределения вероятности;

РАВИС - российская аудио-визуальная информационная система;

РФ - Российская Федерация;

СПМ - спектральная плоность мощности;

СКО — среднеквадратическое отклонение;

ТОР - телекоммуникации и основы радиотехники;

УНБС — уравновешенная неполная блок-схема;

ЭВК - энергетический выигрыш от использования кодирования.

Список сокращений дБ - децибелы.

Приложение II. Копии актов внедрения

Ниже приведены копии актов внедрения диссертационных исследований в разработки следующих предприятий и организаций:

1) ООО «НПФ «САД-КОМ» (г. Москва)

2) Рязанский государственный радиотехнический университет

УТВЕРЖДАЮ Генеральный директор

ООО «1ЩФ «САД-КОМ» /Ж; *?Щу].ВОрКОВИЧ

\\o\v

АКТ

Внедрения результатов кандидатской диссертации Овинникова Алексея

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

Комиссия в составе: председатель комиссии - д.т.н, проф., главный научный сотрудник В.П. Дворкович, члены комиссии - к.т.н., начальник отдела В.А. Ирпога, к.т.н., зам. начальника отдела Д.Г. Макаров, рассмотрев диссертационную работу Овинникова A.A., составила настоящий акт о том, что результаты диссертационной работы нашли применение в разработках ООО «НПФ «САД-КОМ». При совершенствовании стандарта РАВИС и разработке модуляторов были использованы следующие методы и алгоритмы, представленные в диссертации:

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

2. Подпрограммы реализации разработанных алгоритмов на языке С++.

Разработанные алгоритмы и программы реализованы в цифровом модуляторе усовершенствованного стандарта РАВИС.

Анатольевича, выполненной

в

Рязанском государственном

Члены комиссии

Председатель комиссии