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

На правах рукописи

Лихобабин Евгений Александрович

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

Специальность: 05.12.04 - «Радиотехника, в том числе системы и

устройства телевидения»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата наук

Рязань 2014

15 ЯНЗ 2015

005557116

005557116

Работа выполнена в ФГБОУ ВПО «Рязанский государственный радиотехнический университет»

Научный руководитель: Витязев Владимир Викторович,

доктор технических наук, профессор,

ФГБОУ ВПО «Рязанский государственный радиотехнический университет», заведующий кафедрой телекоммуникаций и основ радиотехники

Официальные Полушин Пётр Алексеевич,

оппоненты: доктор технических наук, профессор,

ФГБОУ ВПО «Владимирский государственный университет им. А.Г. и Н.Г. Столетовых»

Стсшенко Владимир Борисович,

кандидат технических наук, доцент, ОАО «Российские космические системы», заместитель главного конструктора

Ведущая организация:

ЗАО «Московский научно-исследовательский телевизионный институт»

Защита диссертации состоится «13» февраля 2015 г. в 12.00 на заседании диссертационного совета Д212.211.04 в ФГБОУ ВПО «Рязанский государственный радиотехнический университет» по адресу: 390005, г. Рязань, ул. Гагарина, 59/1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Рязанский государственный радиотехнический университет».

Автореферат разослан 201^г.

Ученый секретарь диссертационного совета

Овечкин Г.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Начало XXI века стало вехой широкого внедрения цифровых систем аудио и телевизионного вещания: DRM, DAB, DMB, DVB, ATSC, ISDB. Стандарты этих систем разработаны практически для всех диапазонов телевизионного и радиовещания, за исключением частотного диапазона II (87,5-108 МГЦ) и диапазона I (сегменты 47-72 МГц).

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

При использовании системы в столь сложных условиях ключевым требованием, предъявляемым к системе, становится получение существенно более высокой надежности сервиса по сравнению с аналоговым ЧМ-вещанием. Как показывает практика развития цифровых стандартов вещания (например, DVB-T, DVB-T2), эта задача решается за счет использования передовых схем помехоустойчивого кодирования.

Одно из первых предложений по реализации подобной системы было изложено в патенте Российской Федерации №2219676 (08.11.2000 г.), в котором предусматривалась возможность трансляции информационного телевидения. На прошедшей в марте 2006 года в Женеве объединенной конференции МСЭ-Р от России был представлен доклад «Повышение эффективности использования VHF-диапазона частот», в котором была описана система мобильного узкополосного мультимедийного вещания AVIS (Audiovisual information system).

В качестве системы помехоустойчивого кодирования в предложенной реализации предлагалось использовать достаточно эффективную и проверенную временем (DVB-T, DVB-S и проч.) каскадную схему, состоящую из сверточного кода и кода Рида-Соломона.

Однако время не стоит на месте и сейчас одним из наиболее эффективных методов помехоустойчивого кодирования является использование итеративно-декодируемых кодов, в том числе и низкоплотностных (low density parity check, LDPC). Значительный вклад в развитие этой теории внесли многие отечественные и зарубежные ученые: Р.Галлагер, К.Берроу, Л.Бал, Дж.Кок, Ф.Джалинек, Дж.Равив, Р.Урбанке, Т.Ричардсон, Д. МакКай, Д. Зигангиров, В.Зяблов, В.Золотарёв, Г.Овечкин и другие. Основными проблемами при разработке систем помехоустойчивого кодирования являются получение кодов, позволяющих приблизиться к пропускной способности канала связи, а также поиск оптимальных с точки зрения качества и требуемых на реализацию вычислительных затрат алгоритмов декодирования этих кодов.

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

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

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

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

Таким образом, тема диссертационной работы, направленная на исследование и разработку эффективного с точки зрения вычислительных затрат и качества работы алгоритма декодирования 1ЮРС кодов стандарта РАВИС, является в настоящее время актуальной в рамках обозначенной проблематики и требует дальнейшей детальной проработки.

Цель и задачи работы. Целью диссертационной работы является анализ существующих алгоритмов декодирования ЬОРС кодов и разработка эффективного, с точки зрения вычислительных затрат декодера кодов стандарта РАВИС с заданными показателями качества.

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

• разработка моделирующей среды, позволяющей выполнить экспериментальные исследования и сравнение существующих алгоритмов декодирования ШРС кодов;

• сравнительный анализ сложности реализации и качества существующих алгоритмов декодирования 1Л)РС кодов для кодов стандарта РАВИС;

• разработка и исследование эффективных методов сочетания нескольких алгоритмов декодирования 1ЛЭРС кодов в рамках одного декодера;

• оценка выигрыша в экономии вычислительных затрат при использовании составного декодера ЬОРС кода;

• разработка методики оптимального проектирования эффективных с точки зрения вычислительных затрат декодеров ЬОРС кодов с заданными показателями качества.

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

Научная новизна. Научная новизна работы состоит в следующем.

1. Проведены классификация и сравнительный анализ эффективности использования различных алгоритмов декодирования ЬРОС кодов применительно к кодам стандарта РАВИС.

2. Исследована эффективность и показан выигрыш в средних вычислительных затратах при применении составного декодера ЬОРС кода для кодов стандарта РАВИС.

3. Получена новая модификация алгоритма декодирования ЬОРС кодов ОАМС*.

4. Получена новая модификация алгоритма декодирования ЬОРС кодов МОАМС*.

5. Разработана методика оптимального проектирования составных декодеров ЬОРС кодов для различных аппаратных платформ.

6. Спроектирована и разработана среда моделирования для проведения исследований алгоритмов декодирования ЬОРС кодов.

Достоверность полученных результатов. Достоверность полученных результатов подтверждается сопоставлением теоретических данных с результатами компьютерного моделирования, полученными с помощью разработанной среды моделирования ТБЬ

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

Практическая значимость работы. Результаты проведенных исследований могут быть использованы при проектировании любых приемников (систем, использующих ЬОРС коды), применяемых в мобильных устройствах, запас энергии у которых ограничивается емкостью аккумуляторной батареи, а также в энергоэффективных стационарных приемниках. Разработанные методы, алгоритмы и программное обеспечение использованы при выполнении ряда госбюджетных научно-исследовательских работ, проводимых в ФГБОУ «Рязанский государственный радиотехнический университет» по заказу Федерального агентства по образованию и науке РФ (НИР №5-08Г,

НИР №23-09), а также в учебном процессе. Основные результаты работы внедрены в ЗАО НИИР-КОМ, г.Москва.

Апробация результатов работы. Основные положения диссертационной работы доложены и обсуждены на научных семинарах кафедры телекоммуникаций и основ радиотехники РГРТУ и на следующих международных научно-технических конференциях:

• Цифровая обработка сигналов и ее применение, г. Москва DSPA'2009, DSPA'2010, DSPA'2014.

• Современные проблемы радиотехники и телекоммуникаций, г. Севастополь. СевНТУ, 2009, 2010.

• Современные информационные и электронные технологии, г. Одесса. ОНПУ, 2009.

• Проблемы передачи и обработки информации в сетях и системах телекоммуникаций. г. Рязань. РГРТУ, 2010.

• Перспективные технологии в средствах передачи информации, г. Владимир. IX научно-техническая конференция. 2011.

• Международный симпозиум Digital Radio Broadcasting. Москва, 2009.

• Конференции преподавателей и научных сотрудников, г. Рязань. РГРТУ, 2014.

• 3rd Mediterranean Conference on Embedded Computing. Montenegro, Budva. 2014.

Публикации. По материалам диссертационной работы опубликовано 15 научных работ. Из них 2 статьи в ведущих рецензируемых научных журналах из перечня ВАК РФ, 1 статья в рейтинге Scopus и Web of Science.

Внедрение результатов работы. Результаты диссертации внедрены при проведении НИР в ЗАО НИИР-КОМ, при разработке устройств по стандарту РАВИС. А также в учебный процесс кафедры ТОР РГРТУ в курсе лабораторных работ по предмету «Основы теории средств связи с подвижными объектами».

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объем диссертационной работы вместе с приложениями составляет 177 страниц, в том числе 146 страниц основного текста, 34 рисунка, 18 таблиц, список используемой литературы из 104 наименований и 3 приложения.

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

1. Метод построения составного декодера LDPC кода и выигрыш в средних вычислительных затратах при его применении от 2 до 8 раз по сравнению с алгоритмом распространения доверия.

2. Модификация алгоритма декодирования О AMC*, структура которого позволяет подстраивать алгоритм декодирования под конкретный код, и достижимый выигрыш 0,1-0,2 дБ.

3. Модификация алгоритма декодирования МОАМС*, и выигрыш в вычислительных затратах по сравнению с алгоритмом О AMC* в 2 раза.

4. Методика оптимального проектирования составных декодеров 1ЛЭРС кодов для различных аппаратных платформ.

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

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

Дана классификация каналов связи, относительно которых рассматриваются современные системы помехоустойчивого кодирования. Рассматривается класс помехоустойчивых 1ЛЗРС кодов, варианты представления этих кодов и их основные характеристики. Также рассматриваются принципы декодирования, лежащие в основе итеративно декодируемых кодов, и 1ЛЗРС кодов, в частности. Проводится анализ известных работ по декодированию ЬОРС кодов, приводятся классические алгоритмы декодирования Ы)РС кодов для различных каналов связи.

С целью последующего анализа эффективности и дальнейшей модификации, направленной на уменьшение вычислительных затрат, рассмотрены предложенные Галлагером алгоритмы декодирования 1.0РС кодов: алгоритм распространения доверия (АРД) и алгоритм инверсии бита (АИБ).

АРД может быть представлен в виде следующих шагов.

1 шаг. Инициализация. Для всех узлов / инициализировать значения в зависимости от используемой модели канала связи. Затем для всех / и у, для которых /;,;= 1, устанавливается = /..

2 шаг. Обновление проверочных узлов. Для всех проверочных узлов СИ вычислить исходящие сообщения Ь^:

и передать их соответствующим информационным узлам При этом оператор суммирования представляет собой следующую операцию:

СОДЕРЖАНИЕ РАБОТЫ

¿(*) = -1п[Л(*/2)] = 1п[^| (3)

3 шаг. Обновление битовых узлов. Вычислить сообщения исходящие от информационных узлов У1Ч:

^ = X ьг (4)

ГеЩ 1НД

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

4 шаг. Вычисление апостериорных ЛОП. Для всех ]=0,1 ...,N-1 вычислить:

X Ч (5)

¡¿то

5 шаг. Получение жестких решений. Для всех 1=0,1 ...№-1 найти жесткие решения:

й1' (6)

[о, Ц""' > 0.

6 шаг. Проверка условия остановки. Вычислить синдром уНт Если ШТ =0, или число итераций достигло максимума, вычисления прекращаются, а у считается результатом декодирования. В противном случае вычисления продолжаются с шага 2.

Алгоритм ИБ можно представить в виде следующих шагов.

1 шаг. Инициализация. Для всех узлов г инициализировать значения а1 жесткими оценками принятых бит.

2 шаг. Обновление проверочных узлов. Для всех проверочных узлов СЫ вычислить исходящие сообщения и;

(7)

и передать их соответствующим информационным узлам

3 шаг. Обновление битовых узлов. Вычислить сообщения Ц ,;, исходящие от информационных узлов У1Ч:

(8)

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

4 шаг. Получение окончательных решений. Для всех г=0,/...,Л?-/ найти жесткие решения:

Для тпК" ]а. = а. ф 1. (9)

5 шаг. Получение жестких решений.

Не требуется дополнительных действий.

6 шаг. Проверка правильности декодирования. Вычислить синдром уНт . Если ШТ = 0 или число итераций достигло максимума, вычисления прекращаются, а V считается результатом декодирования. В противном случае вычисления продолжаются с шага 2.

Показано, что АРД способен работать без изменений в любом из каналов связи при условии, что на вход декодера будут поступать логарифмы отно-

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

Показано, что несмотря на универсальность АРД остается сложным для реализации алгоритмом, что побудило исследователей к поискам алгоритма декодирования, близкого по эффективности к АРД, но с приемлемыми вычислительными затратами. Определены основные направления построения упрощенных алгоритмов декодирования: 1) упрощение АРД с некоторой потерей в качестве декодирования; 2) модификация алгоритма с инверсией бита (АИБ) с целью повышения качества и ростом вычислительных затрат.

Ставится задача исследования известных модификаций алгоритмов декодирования ЦЗРС кодов по таким параметрам, как качество декодирования и вычислительная сложность реализации.

Во второй главе рассматриваются и модифицируются представители двух основных направлений получения алгоритмов декодирования с уменьшенными вычислительными затратами. Первое — это упрощения АРД с целью уменьшения вычислительных затрат, при этом качество декодирования падает, и второе - усложнение АИБ, направленное на улучшение качества его работы с некоторым увеличением вычислительных затрат, требуемых на выполнение одной итерации.

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

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

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

Известен алгоритм, позволяющий получить приемлемый аппаратный декодер, даже при аппроксимации функции ф(х). Это алгоритм Ричардсона -Новичкова. В этом алгоритме учитывается тот факт, что для больших х справедливо к>£(\±е~х)в>±е~х, тогда:

ФЮ = 1°в т^-г =1О§(1+0-1об(1-0»2£Г*; (10)

V е )

а функция обратная ф{х):

ф-\х)*~ lnjjj. (11)

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

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

Для двух независимых случайных величин a¡ и аг с вероятностями p(a¡ =х) = pf, х б {0,1} и ЛОП L = Z.(«,) = \n(p'¡> / можно показать, что ЛОП их суммы А, = а, + а2 равно

fl+e^M

(12)

При этом обновление проверочных узлов можно свести к многократному применению (12) для двух аргументов, а функция Lím(a,b) может быть реализована в виде таблицы.

Такое представление шага обновления проверочных узлов послужило основой для множества модификаций АРД. Наиболее распространенная из них использует аппроксимацию логарифма Якоби: 1п(е* +е1') = тах( х,, лг2 ) + 1п(1 + ).

Применяя ее дважды для выражения (8), можно получить:

L^CA,^) = A U ^ I).

где

min* (| Z, |,l А I) = minfl L J,| L, |) + g(\ Ц \,\L, |), S(L,, L, ) = ln(l+) - ln(l+ e"^ ).

При этом обычно представляют в виде:

g(Li,L2) = g(^')+g(L¡'),

где

S(L) = ln(l + eH4), Ц'^Ц+L,,

Самая распространенная реализация g(L) — с использованием таблицы. Было показано, что при использовании таблицы из восьми значений функции g(L), погрешность аппроксимации составляет не более 5 %, чего достаточно для приемлемой точности декодирования.

Более точно реализацию функции g(L) можно получить, используя кусочно-линейную аппроксимацию. Можно пойти дальше с точки зрения упрощения алгоритма и воспользоваться аппроксимацией только одной прямой. Известны также варианты аппроксимации функции g(Z,,Z-,).

Дальнейшее упрощение шага обновления проверочных узлов приводит к алгоритму, известному как алгоритм «минимум-сумма» (АМС, min-sum algo-

(13)

(14)

(15)

(16)

(17)

rithm). Алгоритм ограничивается вычислением только первого слагаемого в выражении (16):

L(^) = sign(Z1)sign(^)min(|L,|,|^|). (18)

Эффективность декодирования несколько снижается, однако во многих приложениях это приемлемо.

Дальнейшее упрощение алгоритма касается уже шага обновления битовых узлов. Можно показать, что на шаге обновления битовых узлов можно вычислять только одно исходящее сообщение от битового узла i вместо dc (Ц вместо £.;—/), как это было во всех алгоритмах, основанных на алгоритме АРД. Получившийся алгоритм называют алгоритмом апостериорных вероятностей (ААВ, а posteriori probability АРР).

Тогда выражение (4) примет вид

^ = С = (19)

где Д. - модуль ЛОП бита i.

Модификации АИБ, в первую очередь, сосредоточены на добавлении мягких оценок принятых бит к алгоритму, первоначально разработанному для ДСК, и только затем на модификации выражений для расчета сообщений к проверочным и информационным узлам. В диссертационной работе рассмотрены такие модификации АИБ, как взвешенный алгоритм ИБ (алгоритм ВИБ, АВИБ, weighted bit flip, WBF), модифицированный алгоритм ВИБ (алгоритм МВИБ, АМВИБ, modified weighted bit flip, MWBF), усовершенствованный алгоритм МВИБ (алгоритм УМВИБ, improved modified weighted bit flip, IMWBF). Однако было показано, что выигрыш в вычислительных затратах при использовании модификаций алгоритма ИБ при построении декодера компонентных кодов несущественный и проще сразу использовать переход к алгоритму AB.

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

Рассмотрим алгоритм, называемый аппроксимированный алгоритм «минимум-сумма» (AMC*, approximate min* - a-min*). Алгоритм является комбинацией алгоритмов АРД и AMC, модификация касается подсчета сообщений в проверочном узле. В общем виде для АРД эта операция имеет вид (14), где под оператором min* понимается поиск минимума. В результате для подсчета сообщений из проверочного узла требуется найти всего два сообщения - первое для узла, сообщение от которого минимально, а второе будет одинаковым для оставшихся узлов.

Алгоритм AMC* использует ту же идеологию — в каждом проверочном узле рассчитывается всего два сообщения: одно для информационного узла, приславшего сообщение с минимальным весом, второе — для всех остальных информационных узлов. Отличие заключается лишь в том, что вместо минимума двух аргументов используется оператор ЕВ, в котором реализуется еще и функция корректировки ^(Z,,^).

Подобная модификация позволяет снизить вычислительные затраты на нахождение сообщений из проверочного узла для АРД-подобных алгоритмов с 3(dc-\) до (dc-1) операции ЕЕ.

В главе 2 впервые предложены две модификации алгоритма AMC*, обобщенный алгоритм AMC* (ОАМС*), минимальный ОАМС* (МОАМС*).

Выражение для обновления проверочных узлов, для обобщенного алгоритма MC* примет вид:

для узла с минимальной достоверностью

Щ L^, (20)

i'iMljHUI

для всех остальных

Видно, что частный случай AMC*, при Щ = ЕЕ^ = ЕВ требует меньших затрат на реализацию, чем ОАМС*, поскольку вторая сумма для оставшихся узлов может быть найдена из первой. Это позволяет выполнить обновление проверочных узлов за (dr-1) операции ЕВ. В обобщенном алгоритме на это требуется (dr-2) операции Щ и (dr-1) операций Щ,, что больше чем для AMC*, но меньше чем для классической схемы реализации АРД-подобных алгоритмов декодирования.

Модификация МОАМС* отличается тем, что в качестве EBj используется оператор поиска минимального значения среди весов проверок, что требует всего одной операции обращения к памяти. Таким образом, получаем модификацию ОАМС* алгоритма, требующего (dr-2) операции ЕБ, и 1 операцию обращения к памяти, что меньше чем для алгоритма AMC*.

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

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

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

(21)

В третьей главе рассматриваются вопросы разработки и исследования составного декодера 1ЛЭРС кода для кодов стандарта РАВИС, позволяющего минимизировать средние вычислительные затраты на декодирование.

Идея построения такого декодера базируется на том факте, что вычислительные затраты на реализацию одной итерации каждого алгоритма декодирования 1ЛЗРС кода различны, а также различно число итераций, выполняемых декодером при заданном ОСШ. Очевидно, что для заданной вероятности битовой ошибки при фиксированном ОСШ можно найти декодер, оптимальный с точки зрения вычислительных затрат.

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

Для оценки выигрыша в вычислительных затратах будет использоваться следующий тестовый сценарий. Абонент начинает прием тестового сигнала на мобильное устройство, находясь в наихудших возможных условиях приема - 0 дБ, и постепенно продвигается к базовой станции. При этом увеличение ОСШ происходит с шагом 0,05 дБ, и для каждого значения ОСШ осуществляется передача 10000 кодовых слов. Критерий качества — максимальная верОЯТНОСТЬ биТОВОЙ ОШИбкИ Рь_тах=Ю^-

Исследования проводились для основного кода стандарта РАВИС размерности 20664 и различных скоростей кодирования. Здесь рассмотрим методику построения декодера только для кода (20664, 10332), оставшиеся результата представлены в полной версии рукописи диссертации.

Эксперименты, проведенные для АРД-подобных алгоритмов показали, что средней эффективностью из всех модификаций АРД является модификация, основанная на аппроксимации функции g(L) из (17) прямой линией. Поэтому далее для упрощения анализа, будем применять алгоритмы, использующие в качестве ядра шага обновления проверок именно эту аппроксимацию. Здесь и далее будем обозначать ее как «Якоби линия».

На рисунке 1 приведены зависимости вероятности битовой ошибки и среднего числа итераций от ОСШ для различных алгоритмов декодирования рассмотренных в главах 1 и 2. Результаты приведены для основного кода стандарта РАВИС 20664 бит, скорость 1/2, число итераций 50, для передачи кодовых слов использовалась двоичная фазовая модуляция.

а б

Рисунок 1 - Результаты моделирования для кода (20664,10332), 50 итераций: а - эффективность; б - среднее число итераций

Очевидно, что для различных алгоритмов минимальное ОСШ, при котором выполняется заданный критерий качества, — будет различным, более того - будет различно и число итераций, выполняемых при заданном ОСШ каждым из алгоритмов, таблица 1.

Таблица 1 - Минимальное значение ОСШ для достижения Рь^Ш"6 и среднее число итераций для этого ОСШ_

Алгоритм АРД Линия Линия АМС* Линия МОАМС* АМС ААВ ИБ

Еь/Ыо 1,15 1,20 1,25 1,35 1,8 4,5 8,2

Итерации 25,28 24,701 25,61 30,016 19,25 7,71 6,89

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

Таблица 2 — Вычислительные затраты на реализацию рассмотренных алгоритмов_

Название Синдром Проверочные узлы Информационные узлы Жесткие решения

Якоби М(4-1) 4 М {2(4-1) [*]+[+](4-1)+[тт](4-1)+ +(4-1)[ё(ЬьЬ2)]} Г£(Ь,,Ь2)]=2Г1п1+5М+2Гех1 N (2 4+1) N[^11]

Якоби прямая то же [ё(Ь,,Ь2)]=2{[*]+[+]+ +[сшрП+Г+1 то же то же

АМС* - М {(2 4-1) [*]+[стр]+[тт] (4-1)+ +Геа,,Ь2)1 (4-1)} - -

МОАМС* - М {(2 dr-1) [*]+[cmp]+[min] (dr-l)+ +rg(L,,L2)l (dr-2)+l} - -

AMC - M {(2 drl) [*]+[cmp]+[cmp] (dr +[1о§Х1-2)}

ААВ - - Ndc -

ЛИВ - M{dr-1} N(dc-l) N[cmp]+ 1

В таблице 2 используются следующие обозначения: min — функция получения минимума двух аргументов; стр — операция сравнения; [л] — сложность реализации функции х.

Количественные оценки сложности выполнения одной итерации каждого из рассматриваемых алгоритмов для конкретного кода приведены в таблице 3.

Таблица 3 — Число вычислительных операций для выполнения одной итерации рассматриваемых алгоритмов декодирования для кода 20664,10332

Алгоритм АРД Якоби Линия Линия AMC* Линия МОАМС* AMC ААВ ЛИГ,

Число операций процессора 1974440 1707872 839977 777982 539312 374010 233495

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

а б Рисунок 2 - Средняя сложность рассмотренных алгоритмов декодирования в зависимости от ОСШ для кода (20644,10322): а - все алгоритмы; б - алгоритмы АВ и ИБ

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

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

1,2 дБ

—

АРД

Якоби линия

1.25 дБ 1,55 дБ__________1,8 дБ________ 4,95 дБ________11,5 дБ

ААВ Ы АИБ

............ ~ 1 ;— --------------

АМС* МОАМС* АМС ФФ

Рисунок 3 — Граф переключения алгоритмов декодирования для составного декодера, состоящего из 7 компонентных алгоритмов декодирования (20664,10332)

Для полноты анализа кроме этой структуры рассмотрим также варианты, представленные на рисунках 4 и 5.

1,25 дБ

АРД

1,8 дБ

АМС*

4,95 дБ,

АМС

11,5 дБ

ААВ

АИБ

Рисунок 4 — Граф переключения алгоритмов для декодера, состоящего из 5 компонентных алгоритмов декодирования (20664,10332)

1,8 дБ

АРД

4,95 дБ

АМС

ААВ

Рисунок 5 — Граф переключения алгоритмов для декодера, состоящего из 3 компонентных алгоритмов декодирования для кода (20664,10332)

Результаты, полученные для кода (20664, 10332), приведены в таблице 4, интервал анализа 1,20-14 дБ.

Таблица — 4 Интегральные оценки сложности для различных структур

Структура декодера Интегральная оцепка сложности, выч. оп.*дБ Выигрыш относительно АРД, раз

АРД 94475616 1

7 компонентных алгоритмов 11465760 8,23

5 компонентных алгоритмов 11915574 7,93

3 компонентных алгоритма 19161880 4,93

Итак, выигрыш при переходе от использования только АРД при построении декодера к предложенной структуре из семи алгоритмов дает интегральный выигрыш более чем в 8 раз. Переход к более простым структурам из 5 и 3 алгоритмов приводит к повышению интегральной оценки вычисли-

тельных затрат примерно на 3 % и 50 % соответственно, однако выигрыш относительно АРД в 7,93 и 4,93 раза остается существенным.

Для кода (20664, 13780) при использовании предложенных структур декодера можно получить выигрыш в 1,95 — 2,6 раза в зависимости от предложенной схемы. Уменьшение выигрыша по сравнению с кодом (20664, 10332) обусловлено тем, что в качестве алгоритма для сравнения используется не АРД, а его модификация Линия AMC*.

Для кода (20664, 15500) применение предложенных структур позволяет снизить средние вычислительные затраты от 3,43 до 4,43 раз.

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

Таблица 5 — Интегральные оценки сложности для различных структур

Структура декодера Интегральная оценка сложности, (20664,13780), выч. оп.*дБ Выигрыш относительно АРД, (20664,13780), раз

Линия AMC* 19766553 1

5 компонентных алгоритмов 7579885 2,61

4 компонентных алгоритма 9864414 2

3 компонентных алгоритма 10111077 1,95

Таблица 6 — Интегральные оценки сложности для различных структур

декодеров для кода (20664,15500)

Структура декодера Интегральная Выигрыш от-

оценка слож- носительно

ности, АРД,

(20664,15500), (20664,15500),

выч. оп.*дБ раз

АРД 27315132 1

7 компонентных алгоритмов 6156444 4,43

5 компонентных алгоритмов 6601059 4,13

3 компонентных алгоритма 7970081 3,43

Четвертая глава посвящена разработке моделирующей среды для исследования 1ЛЭРС кодов и алгоритмов их декодирования.

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

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

Основные требования к системе следующие:

• легковесность среды имитирующей систему связи;

• максимальная эффективность реализации самих алгоритмов декодирования;

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

• возможность комбинировать различные элементы алгоритмов декодирования;

• возможность изменять алгоритмы кодирования;

• возможность использовать различные матрицы размерности до 64800 бит, хранящихся в формате AList;

• возможность изменения параметров эксперимента без перекомпилирования приложения;

• лицензионная чистота полученного программного продукта.

Для выполнения всех перечисленных выше требований были использованы языки программирования С, С++, Python, в качестве платформы реализации - операционная система GNU Linux, рисунок 6.

Gnupiot

Рисунок 6 - Архитектура среды моделирования TSI

Разработанная среда получила рабочее название TSI (Telecommunication System Imitator — имитатор телекоммуникационной системы), состоящая из трех крупных блоков: ядра, блока автоматизации экспериментов и блока обработки результатов.

-Ядро приложения реализовано на языке С++ и выполняет основную работу по получению экспериментальных данных об исследуемом алгоритме декодирования. Входные данные для выполнения эксперимента хранятся во внешнем текстовом файле. Для изменения параметров моделирования достаточно текстового редактора. Эта часть приложения автономна и оставшиеся

блоки являются вспомогательными, облегчающими получение и обработку экспериментальных данных.

Блок автоматизации экспериментов представляет собой набор скриптов на языке Python и текстовых файлов, содержащих исходные данные для серии экспериментов.

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

Кроме этого, рассмотрен вопрос построения алгоритмов декодирования моделирующей среды, оптимизированных для многоядерных платформ с использованием прикладных библиотек ОрепМР.

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

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

В заключении приводятся основные выводы и результаты, полученные в ходе проведенных исследований. Указаны направления дальнейших исследований.

В приложениях приведены характеристики рассматриваемых кодов стандарта РАВИС, исходные коды расчета сложности рассматриваемых алгоритмов, программный код алгоритмов декодирования, оптимизированный для работы на многоядерных процессорах, а также акты внедрения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Экспериментальные исследования и моделирование, проведенные в рамках диссертационной работы, показали, что совместное использование нескольких алгоритмов декодирования в рамках одного декодера LDPC кодов способно в 2-8 раз снизить средние вычислительные затраты на декодирование, в зависимости от кода и выбранной схемы декодера. Результаты экспериментов подтвердили преимущества данного подхода по сравнению с использованием одной упрощенной модификации АРД или АИБ для декодирования во всем рабочем диапазоне ОСШ как по вычислительным затратам, так и по используемым показателям качества.

Основные научные и практические результаты проделанной работы следующие.

1. Проведена классификация и сравнительный анализ качества декодирования и сложности реализации различных алгоритмов декодирования LPDC кодов применительно к кодам стандарта РАВИС.

2. Получены новые модификация алгоритма декодирования LDPC кодов О AMC* и МОАМС*.

3. Исследована эффективность и показан выигрыш в средних вычислительных затратах при применении составного декодера LDPC кода для кодов стандарта РАВИС.

4. Разработана методика оптимального проектирования составных декодеров LDPC кодов для различных аппаратных платформ.

5. Спроектирована и разработана среда моделирования для проведения исследований алгоритмов декодирования LDPC кодов.

6. Создана библиотека оптимальных с точки зрения скорости выполнения программных кодов на языке С++ следующих алгоритмов декодирования LDPC кодов: АРД, АРД в модификации Галлагера, АРД в модификации Гал-лагера с использованием логарифмического представления, алгоритм Ричардсона-Новичкова, АРД на основании аппроксимации логарифмом Яко-би, модификации АРД на основании аппроксимации логарифма Якоби (линейная, кусочно-линейная, табличная, поверхностью), AMC, AMC*, ОАМС*, МОАМС*, ААВ, АИБ.

7. Создана библиотека оптимальных программных кодов реализации алгоритмов декодирования LDPC кодов для процессоров с многоядерной архитектурой на основе библиотеки ОрепМР.

ПУБЛИКАЦИИ ПО ОСНОВНЫМ РЕЗУЛЬТАТАМ РАБОТЫ

1. Лихобабин Е.А. Исследование быстрых алгоритмов декодирования кодов с низкой плотностью проверок на четность // Цифровая обработка сигналов и ее применение - DSPA-2009: Труды РНТОРЭС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применения. Выпуск XI-1. — М., 2009.-С. 55-58.

2. Лихобабин Е.А. Квазиоптимальные алгоритмы декодирования кодов с низкой плотностью поверок на четность // Современные проблемы радиотехники и телекоммуникаций, СевНТУ. - Севастополь, 2009. - С. 257.

3. Лихобабин Е.А., Устинова Е.А. Энергетически эффективный алгоритм помехоустойчивого декодирования в беспроводных сенсорных сетях // Современные информационные и электронные технологии, ОНПУ. - Том 1. — Одесса, 2009.-С.175.

4. Лихобабин Е.А. Использование быстрых алгоритмов декодирования LDPC кодов в системе цифрового вещания DVB-T2 // I региональный итоговый конкурс «У.М.Н.И.К.»-2010:Тезисы докладов. - Рязань, 2010. - С. 31-34.

5. Лихобабин Е.А., Дворкович A.B. Использование квазиоптимапьных алгоритмов декодирования LDPC кодов в системе цифрового телевизионного вещания стандарта DVB-T2 И Цифровая обработка сигналов и ее применение - DSPA-2010: Труды РНТОРЭС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применения. - Выпуск XII-1. - М., 2010. - С. 25-27.

6. Лихобабин Е.А., Устинова Е.А. Совместное использование маршрутизации и помехоустойчивых LDPC кодов для повышения энергетической эф-

фективности беспроводных сенсорных сетей // Цифровая обработка сигналов и ее применение - DSPA-2010: Труды РНТОРЭС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применения. — Выпуск XII-1. — М., 2010 г. - С. 262-264.

7. Лихобабин Е.А., Устинова Е.А. Увеличение времени жизни беспроводных сенсорных сетей за счет применения алгоритма равномерной маршрутизации и помехоустойчивых LDPC кодов // Современные проблемы радиотехники и телекоммуникаций. — СевНТУ. — Севастополь, 2010. — С. 178.

8. Лихобабин Е.А. Алгоритмы декодирование LDPC кодов, основанные на методах оптимизации // Материалы конференции. Проблемы передачи и обработки информации в сетях и системах телекоммуникаций. РГРТУ. — Рязань, 2010. - С. 124-126.

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

10. Лихобабин Е.А., Устинова Е.А. Эффективное использование LDPC кодов в беспроводных сенсорных сетях // Перспективные технологии в средствах передачи информации: Материалы IX научно-технической конференции. - Том 3. — Владимир, 2011. — С.33-36.

11. Лихобабин Е.А. Упрощенные алгоритмы декодирования кодов с низкой плотностью проверок на четность // Цифровая обработка сигналов. — №3. -М., 2013.-С. 54-60.

12. Витязев В.В., Лихобабин Е.А. Алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на алгоритме «минимум-сумма» // Труды РНТОРЭС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применение. —Выпуск XVI-1. —М., 2014. —С.117-121.

13. Vityazev V.V., Likhobabin Е.А., Ustinova Е.А. Min-Sum Algorithm-Structure Based Decoding Algorithms for LDPC Codes // 3rd Mediterrian Conference on Embedded Computing, Budva, Montenegro, P.256-259, 15-19 June, 2014.

14. Витязев B.B., Лихобабин Е.А. Алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на структуре алгоритма «минимум-сумма» // Успехи современной радиоэлектроники. - №6. -М., 2014.-С. 26-35.

15. Витязев В.В., Лихобабин Е.А. Упрощенная модификация a-min* алгоритма декодирования кодов с низкой плотностью проверок на четность / Методы и средства обработки и хранения информации, межвузовский сборник научных трудов. — Рязань, 2014. — С.58-65.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 28.11.2014. Формат бумаги 60x84 1/16. Бумага офсетная. Печать трафаретная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ 7978

Отпечатано в ООО «Информационные технологии». 390035, г Рязань, ул. Островского, д.21/1.