автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Декодирование кодов с малой плотностью проверок на четкость

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

КИРЬЯНОВ Иван Андреевич

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

ЧЕТНОСТЬ

Специальность 05.12.13 - Системы, сети и устройства телекоммуникаций

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

5561236

¿5имН 2015

Москва 2015

005561236

Работа выполнена на кафедре «Инфокоммуникации» ФГБОУ ВПО Московского авиационного института (национального исследовательского университета).

Научный руководитель: кандидат технических наук, доцент кафедры 408

ФГБОУ ВПО Московского авиационного института (национального исследовательского университета) Важенин Николай Афанасьевич

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

«Вычислительная и прикладная математика» Рязанского государственного радиотехнического университета Овечкин Геннадий Владимирович

кандидат физико-математических наук директор Департамента пакетных сетей и услуг ОАО «Интеллект Телеком» Ефимушкин Владимир Александрович

Ведущая организация: ОАО «Московский научно-исследовательский

институт радиосвязи» (ОАО «МНИИРС»)

Защита диссертации состоится «21»_апреля_2015 г. В 11:40 часов на заседании диссертационного совета Д.212.125.02 Московского авиационного института (национального исследовательского университета) по адресу 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, д.4.

С диссертацией можно ознакомиться на сайте mai.ru и в библиотеке Московского авиационного института (национального исследовательского университета). Автореферат разослан «_»_2015 г.

Ученый секретарь

диссертационного совета Д.212.125.02 к.т.н, доцент

Общая характеристика работы

Работа относится к теории и технике помехоустойчивого кодирования. Рассматриваются пути повышения эффективности практической реализации декодеров кодов с малой плотностью проверок на четность (LDPC от англ. Low-density parity-check). Разрабатываются и исследуются варианты реализации LDPC декодеров, обеспечивающих наилучшие показатели по критерию помехоустойчивость-сложность технической реализации. Результаты исследований апробируются на примере спутниковой телекоммуникационной подсистемы передачи эфемеридной и служебной информации наземным потребителям с использованием сигнала L1C.

Актуальность диссертационной работы

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

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

Коды с малой плотностью проверок на четность рекомендованы для коррекции ошибок в современных стандартах связи DVB-S2, DVB-C2, Wi-Fi 802.1 In, WiMAX 802.16е.

Степень разработанности темы диссертации

На данный момент можно выделить два направления исследований в области кодов с малой плотностью проверок на четность. Первое из них относится к синтезу конструкций LDPC кодов. В этом направлении следует отметить труды Афанасьева В.Б., Воробьева К.А., Зигангирова Д.К., Зигангирова К.Ш., Зяблова В.В., Иванова Ф.И., Крука Е.А., Овчинникова А.А., Пацей Н.В., Потапова В.Г., Трухачева Д.В., Costello D., Johnson S.J., Kou Y., Luby M.G., Richardson J., Weller S.R.

Второе направление исследует алгоритмическую составляющую LDPC кодеков. В этом направлении следует отметить труды Башкирова А.В., Белоголового А.В., Витязева В.В., Владимирова С.М., Климова А.И., Козлова А.В., Кравченко А.Н., Лихобабина Е.А., Муратова А.В., Овечкина Г.В., Проскурина А. А., Солтанова А.Г., Chen J., Fossorier M., Kim N.. Urbanke R.L.

Общий вклад в развитие теории внесли труды Акулинина А.С., Золотарева В.В., Зубарева Ю.Б., Колесника В.Д., Eckford A.W., МасКау D„ Tanner М.

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

Цель диссертационной работы и решаемые задачи

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

1. Анализ существующих алгоритмов декодирования LDPC кодов.

2. Оценка вычислительной сложности декодирования LDPC кодов.

3. Оценка статистических характеристик декодирования (BER, число итераций,

сходимость синдрома) LDPC кодов.

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

эффективность декодирования и сэкономить используемые при декодировании

ресурсы памяти.

Методы исследования

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

Для проведения моделирования использовалась среда имитационного моделирования MATLAB с пакетом Simulink и среда разработки программных продуктов Microsoft Visual Studio 2010.

Научная новизна

1. Получены и проанализированы соотношения для расчета сложности итерации декодирования И)РС кодов для различных алгоритмов коррекции ошибок.

2. Получены и исследованы статистические характеристики декодирования (ВЕЯ, число итераций, сходимость синдрома) для различных алгоритмов коррекции ошибок в рамках рассматриваемого 1Л}РС кода.

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

4. Предложена методика компактного представления разряженной проверочной матрицы 1ЛЭРС кода, позволяющая экономить ресурсы памяти для её хранения.

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

6. Предложен способ идентификации инверсии битового потока за счет внутренних ресурсов 1Л5РС декодера и исследована его работа на реальном сигнале.

Практическая ценность диссертационной работы

Предложенная методика выбора алгоритма декодирования 1ЛЗРС может использоваться при проектировании современных цифровых телекоммуникационных систем.

Компактное представление проверочной матрицы позволяет сэкономить в 2 раза ресурсы памяти, выделенные на её хранение.

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

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

Разработанные программные реализации 1ЛЗРС и БЧХ кодеков могут быть внедрены в системы связи, использующие соответствующее помехоустойчивое кодирование информации.

Внедрение

Программные реализации декодера кодов с малой плотностью проверок на четность и БЧХ декодера были внедрены в ООО «Топкон Позишионинг Системе».

На основе полученных результатов разработано учебное пособие «Принципы построения и алгоритмы реализации Ы)РС кодеков» для использования в учебном процессе по специальности 210402 «Средства связи с подвижными объектами» и направлению подготовки 210700 «Инфокоммуникационные технологии и системы связи».

Достоверность

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

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

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

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

3. Разработанные модификации алгоритмов декодирования ЫЗРС кодов позволяют повысить скорость работы декодера в 3 раза при незначительном увеличении требований к памяти для хранения внутренних переменных декодера.

4. Предложенный способ идентификации инверсии битового потока позволяет определять инверсию за счет внутренних ресурсов ЫЭРС декодера.

Апробация работы

Основные результаты доложены на Московской молодежной научно-практической конференции «Инновации в авиации и космонавтике -2012» (МАИ, Москва, 2012); на 1-ой межвузовской студенческой научно-технической конференции «Современные состояния и перспективы развития сложных радиоэлектронных систем» (ОАО «ГСКБ «Алмаз-Антей», Москва, 2012); на Московской молодежной научно-практической конференции «Инновации в авиации и космонавтике -2013» (МАИ, Москва, 2013); на 12-ой Международной конференции «Авиация и космонавтика - 2013» (МАИ, Москва, 2013); на Московской молодежной научно-практической конференции «Инновации в авиации и космонавтике -

2014» (МАИ, Москва, 2014); на 13-ой Международной конференции «Авиация и космонавтика - 2014» (МАИ, Москва, 2014).

Публикации

Основные результаты исследований опубликованы в 17 работах, в числе которых 7 статей в журналах, входящих в перечень ВАК, 1 свидетельство о государственной регистрации программы для ЭВМ и 9 других публикаций, не входящих в перечень ВАК.

Личный вклад автора

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

автора.

Структура и объем работы

Работа состоит из введения, пяти глав, заключения, содержит 77 рисунков, 21 таблицу и 151 формулу. Работа размещена на 129 страницах.

Соответствие работы паспорту специальности

Работа соответствует паспорту специальности 05.12.13 - «Системы, сети и устройства телекоммуникаций» (пункт 8 — «Исследование и разработка новых сигналов, модемов, кодеков, мультиплексоров и селекторов, обеспечивающих высокую надежность обмена информацией в условиях воздействия внешних и внутренних помех»).

Основное содержание работы

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

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

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

кодов матрица проверки на четность будет содержать малое число «1». Пример такой матрицы приведен на рисунке 1.

I и 1 I

I

I I) '

Ш D IH I I 1 И I ( > in I I И HI oooinoooiooooiooooiooooio ooooiooociooooioouoiooooi п О О О I П (( О I О О I) I О П О I II О П I О (1 (J о I g и и о п I ( ■ о 1 9 и I t ] I t I 1 t t 1 1 I I I Ol 0 H I 0 n О M I H H 1 t ritiiaoetovolooneooonincoio

а о it I noo I J 0 0 0 I о I)

) a i о и о i о

Рисунок 1 - Пример проверочной матрицы LDPC кода

/}>уппа<(1)\1

/=16 /=21~

Рисунок 2 - Фрагмент графа Таннера для первой проверки на четность

В данном случае матрица содержит 15 проверочных уравнений и каждый из 25 принятых символов кодового слова участвует в трех проверках на четность. Число «1» пришедшего кодового слова в рамках проверки на четность должно быть четным. Невыполнение проверки на четность свидетельствует о наличии ошибок в принятом кодовом слове.

При описании алгоритмов декодирования кодов с малой плотностью проверок на четность удобно переходить от матрицы к двудольному графу, с одной стороны которого находятся символьные узлы / (variable nodes), а с другой стороны проверочные узлы т (check nodes). Количество символьных узлов соответствует количеству символов принятого кодового слова, а количество проверочных узлов соответствует количеству проверочных уравнений в матрице проверки на четность. Символьные и проверочные узлы соединяются ребрами в соответствии с расположением «1» в матрице. Фрагмент графа для первой проверки на четность приведен на рисунке 2.

В соответствии с первой строкой матрицы на рисунке 1, в первой проверке на четность т= 1 участвуют символы пришедшего кодового слова с номерами 1, 6, 11, 16 и 21. Предположим, что каждому из этих символов кодового слова были приписаны «жесткие» решения, приведенные в окружностях, и первый символ был принят с ошибкой. В этом случае проверка на четность не будет выполняться. Каждому символу в рамках рассматриваемой проверки на четность выносится поправка. Например, для расчета поправки к первому символу необходимо рассчитать количество «1» в проверке на четность т= 1 без учета первого символа. Для этого формируется локализованная группа символьных узлов 4X1) \1 (выделена пунктиром). Число в скобках показывает номер проверки на четность, а число после черты показывает номер символа, которому рассчитывается поправка относительно локализованной группы. В конкретном примере в группе <f(l) \ 1 Две

«1». Следовательно, для удовлетворения проверки на четность первый символ должен быть «О», о чем проверочный узел т=1 «сообщает» первому символу.

В работе большинства алгоритмов декодирования LDPC кодов лежит принцип, описанный выше. Отличие заключается лишь в том, что работа ведется не с «жесткими» решениями «1» и «О», а с «мягкими» решениями (надежности принятых символов). В этом случае поправка к априорному «мягкому» решению демодулятора, рассчитанная относительно локализованной группы, будет представлять собой вещественное число.

Алгоритмы декодирования LDPC кодов представлены на рисунке 3 и отличаются друг от друга способом расчета поправок к априорным «мягким» решениям демодулятора. Базовым алгоритмом декодирования является алгоритм с распространением доверия «Belief propagation». Его недостатком является высокая сложность в силу необходимости использования гиперболических функций тангенса и арктангенса при расчете поправок. На практике используют упрощенные алгоритмы декодирования из семейств «Min-sum» и «UMP ВР» или различные аппроксимации гиперболических функций.

Рисунок 3 - Алгоритмы декодирования LDPC кодов

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

1800

ш Sub2 Sub3

52 1200 548

Рисунок 4 - Структура кадра сигнала L1C на входе декодера

Кадр состоит из 1800 отсчетов и делится на 3 части. Первая часть представляет собой закодированный БЧХ кодом номер кадра LIC. Информация в части Sub2 (Subframe2) закодирована LDPC кодом длиной 1200 символов. Информация в части Sub3 (Subframe3) закодирована LDPC кодом длиной 548 символов. Матрицы проверки на четность, соответствующие кодам из частей Sub2 и Sub3, представлены на рисунке 5. Точки соответствуют расположению «1».

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

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

алгоритмов того, который обеспечивает это требование с минимальной сложностью. Как следствие, необходимо иметь реестр всех существующих алгоритмов декодирования ЬОРС (глава 1), из которых будет осуществляться выбор, а также оценить сложность (глава 2) и эффективность (глава 3) декодирования.

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

Для оценки сложности алгоритмов декодирования в качестве базовой используется методика, учитывающая операции сложения (Л^), умножения {NX), сравнения (Л^,), взятия модуля числа (М |) и сложения по модулю 2 (А®) на одну итерацию декодирования.

Операция вычитания приравнивается к операции сложения. Число операций различного типа будет зависеть от «весов» строк (к) и столбцов (/) проверочной матрицы, а также от длины кодового слова (/), количества уравнений в матрице проверки на четность (т) и алгоритма декодирования. Работу любого алгоритма декодирования ЬОРС можно разделить на несколько этапов, представленных на рисунке 6. Подсчет числа элементарных операций будет вестись для этапов 1-4, выполняемых итеративно.

® © © ® ©

Рисунок 6 - Этапы декодирования ЬОРС кода

В работе получены аналитические соотношения, позволяющие оценить вычислительную сложность для различных алгоритмов декодирования ЬОРС кодов (число операций различного типа на итерацию декодирования) для любой матрицы проверки на четность. По полученным соотношениям проведен расчет суммарной вычислительной сложности алгоритмов декодирования в рамках ЬОРС кода, применяемого в 8иЬ£гате2. Под суммарной сложностью в данной работе понимается сумма операций различного типа, выполняемых декодером за одну итерацию декодирования. Приведенные значения на рисунке 7 получены при суммировании различных типов операций с «весом» 1. В общем

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

Рисунок 7 - Суммарная вычислительная сложность декодирования ЬОРС кода в 8иМгате2

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

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

Сравнение вычислительной сложности классического и модернизированного алгоритмов «Мт-зит» (МБ) приведено в таблице 1. При реализации выигрыш по скорости работы декодера составил в 3 раза.

Таблица 1 - Сравнение вычислительной сложности для Мв

Операция Количество на итерацию декодирования

Классический М8 Модернизированный М8

Сложение 37024 37024

Умножение 33888 10236

Сравнение 64159 13855

Взятие модуля 33888 4818

Сложение по модулю 2 4218 4218

Сравнение вычислительной сложности классического и модернизированного алгоритма «1)МР ВР» приведено в таблице 2.

Таблица 2 - Сравнение вычислительной сложности для «иМР ВР»

Операция Количество на итерацию декодирования

Классический «UMP ВР» Модернизированный «UMP ВР»

Сложение 37024 37024

Сравнение 39907 18673

Взятие модуля 33888 4818

Сложение по модулю 2 44124 24090

Следует подчеркнуть, что платой за снижение вычислительной сложности классических алгоритмов декодирования «Min-sum» и «UMP ВР» является незначительное увеличение памяти для хранения внутренних переменных декодера. Помехоустойчивость алгоритмов в результате модификаций не изменяется.

В третьей главе на имитационной модели получены и проанализированы статистические характеристики декодирования кодов с малой плотностью проверок на четность на примере одного из двух кодов, используемых для кодирования информации, которую несет сигнал LIC. Основные результаты, полученные в рамках данной главы, опубликованы автором в [1-6].

Обратимся к схематично изображенному на рисунке 8 примеру низкоплотностной матрицы проверки на четность размерностью 600 на 1200, содержащей 4818 ненулевых элементов. Здесь поля с цифрами соответствуют ненулевым элементам, а без цифр -нулевым.

■1200-

1 5 • • • 1199

2 4 1199

1 4 1200 м-position--►

• 1 S 1199 2 4 1199 1 4 1200 3 5 1200 Л Л Л

Рисунок 8 - Схематичное изображение матрицы проверки на четность

-weight го'н-

Рисунок 9 - Компактное представление матрицы проверки на четность

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

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

В работе предложено представлять матрицу (рисунок 9) в виде двух целочисленных одномерных массивов: массива position координат ненулевых элементов матрицы по горизонтали и массива weight row «весов» строк матрицы. Под «весом» строки понимается количество единиц в строке. При этом массив position будет иметь размер, равный числу ненулевых элементов матрицы, а массив weight row будет иметь размер, равный количеству строк матрицы. Такой подход позволяет в 2 раза сократить требуемую память для хранения матрицы по сравнению с существующими методами, в которых для представления используются координаты ненулевых элементов матрицы по вертикали и горизонтали.

Целью моделирования являлось получение ряда статистических характеристик низкоплотностного декодера (BER, число итераций, сходимость синдрома). Моделирование проводилось для LDPC кода из части Subfrarae2. Структурная схема имитационной модели односторонней линии цифровой радиосвязи приведена на рисунке 10.

Рисунок 10 - Структурная схема имитационной модели

Для каждого из алгоритмов декодирования был разработан С++ код, внедряемый в сегмент декодера имитационной модели. Для различных алгоритмов декодирования были получены кривые помехоустойчивости BER (рисунок 11), зависимости среднего числа использованных декодером итераций от отношения сигнал/шум (рисунок 12) и характеристики сходимости среднего «веса» синдрома от номера итерации при битовом отношении сигнал/шум 3 дБ (рисунок 13 и рисунок 14).

Алгоритм «Belief propagation» демонстрирует наилучшие характеристики помехоустойчивости, наименьшее среднее число использованных итераций и наибыстрейшее схождение среднего «веса» синдрома к нулю.

Версии алгоритмов с нормировкой (normalized) и сдвигом (offset) из семейств «Min-sum» и «UMP ВР», а также мажоритарные алгоритмы с варьируемым порогом и нормировкой и сдвигом проигрывают алгоритму «Belief propagation» не более -0.1 дБ.

f

Причем во всех случаях алгоритмы со сдвигом демонстрируют лучшие на -0.05 дБ характеристики помехоустойчивости, чем алгоритмы с нормировкой. Более того, в среднем версии алгоритмов со сдвигом требуют меньшее число итераций на декодирование, а их средние «веса» синдромов сходятся быстрее средних «весов» алгоритмов с нормировкой.

Мажоритарные алгоритмы с варьируемым порогом демонстрируют энергетический выигрыш -0.3-0.4 дБ относительно декодирования с нулевым порогом (стандартный «UMP ВР»), но проигрывают кластеру из алгоритма «Belief propagation» и алгоритмов с нормировкой и сдвигом порядка -0.3-0.4 дБ, тем самым занимая промежуточный сегмент. Следует отметить, что в силу своей специфики эти алгоритмы отличаются медленным схождением среднего «веса» синдрома к нулю и большим средним числом итераций для декодирования по отношению к алгоритмам, не использующим варьирование порога.

Рисунок 11 - Зависимость ВЕК от ОСШ Рисунок 12 - Зависимость среднего

для различных алгоритмов числа итераций от ОСШ

I

В четвертой главе приведен пример применения предлагаемой методики выбора алгоритма декодирования 1Х)РС кодов, а также проанализированы характеристики

номер итеозции

Рисунок 13 - Сходимость среднего веса синдрома (начальный участок)

Рисунок 14 -

м 1» та и 22 и г. »

среднего веса синдрома

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

В качестве примера задается требование обеспечения вероятности ошибки на выходе декодера 10"5 при битовом отношении сигнал/шум 2.2 дБ. Согласно предлагаемой методике, вначале происходит локализация алгоритмов, которые могут обеспечить заданную вероятность ошибки при указанном отношении сигнал/шум. В конкретном случае на рисунке 11 таких алгоритмов 7: «Min-sum normalized», «UMP BP normalized», «С варьируемым порогом (20;-20) normalized», «Min-sum offset», «UMP BP offset», «С варьируемым порогом (20;-20) offset», «Belief propagation».

Как отмечалось выше, алгоритм с распространением доверия «Belief propagation» редко реализуется на практике в чистом виде и будет вычеркнут из рассмотрения. Для остальных алгоритмов необходимо рассчитать комплексный показатель сложности, учитывающий суммарную сложность декодирования на итерацию (рисунок 7) и среднее число итераций (рисунок 12), которое используется алгоритмами при фиксированном отношении сигнал/шум для обеспечения заданного BER. При учете суммарной сложности алгоритма на итерацию декодирования, как уже отмечалось выше, следует учитывать «веса» операций различного типа при их суммировании. Здесь, в качестве примера, «веса» приятны равными 1. Разработчики, используя полученные во второй главе значения сложности по каждому типу операции, могут провести суммирование с соответствующими для их аппаратуры «весами».

Согласно представленным на рисунке 15 значениям комплексного показателя сложности, для удовлетворения сформулированного выше требования с наименьшими «затратами» следует отдать предпочтение алгоритмам «UMP BP offset» и «UMP BP normalized».

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

Рисунок 15 - Значения комплексных показателей сложности

(н^овоеот*сил»ивсигма'./11>уи isEj

Рисунок 16-Характеристика помехоустойчивости БЧХ кода (52,9)

Каждый новый кадр сигнала L1C сопровождается 9-ти разрядным номером эпохи, закодированным БЧХ кодом (52,9). В составе имитационной модели был реализован БЧХ кодек (52,9) и получены характеристики BER для «мягких» и «жестких» решений (рисунок 16). Выигрыш от применения «мягких» решений по сравнению с «жесткими» решениями составил 2 дБ по уровню 10"5.

В качестве «мягких» решений на входах LDPC и БЧХ декодеров используются значения синфазной (I) составляющей радиосигнала LIC. Выборка, полученная при низком энергетическом потенциале (битовое отношение сигнал/шум -3-5 дБ) и содержащая 3646800 отсчетов (ровно 2026 кадров), представлена на рисунке 17.

На выборке было декодировано 1012 кадров из 2026 (-50%). Потери обусловлены тем, что при обработке выборки сигнала с низким энергетическим потенциалом в тракте приемника есть вероятность срыва слежения за фазой в схеме Костаса. Это может приводить к инверсии «мягких» решений на входе декодера, что равносильно внесению ошибок в принимаемый кадр сигнала LIC.

На рисунке 18 показано изменение полярности кадров в составе обрабатываемой выборки. Прямую полярность имеют 1012 кадров (декодированы успешно), а обратную -988 (потеряны при декодировании). Еще 26 кадров находятся на «стыках» между сменой полярности. Такие кадры инвертированы частично и чаще всего не поддаются декодированию. В отличие от кадров, находящихся на стыках, полностью инвертированные кадры можно декодировать, умножив «мягкие» решения по этим кадрам на -1. Для этого необходимо идентифицировать факт произошедшей инверсии.

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

обрабатывающего 8иМгате2. Идея идентификации инверсии заключается в подаче синхронизированного кадра сигнала Ь1С на вход декодера и последующем декодировании его составной части 8иМгате2 в течение большого, но ограниченного числа итераций (до 100 итераций в данной работе). Если в течение ¡00 итераций не удалось декодировать 8иЫгате2, то принимается решение о полной или частичной инверсии всего кадра. С первого взгляда может показаться некорректным вынесение решения по всему кадру на основе анализа только одной его части. Однако следует учитывать, что после внесения инверсии, имеющей характер пакета ошибок, и до декодирования происходит блоковое деперемежение содержимого в кадре. Это означает, что в какой бы части принятого кадра не произошла инверсия, после деперемежения она будет распространена по всему кадру. Недостатком данного способа является долгое время для принятия решения об инверсии кадра.

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

Перед декодированием и после каждой новой проделанной итерации декодер рассчитывает уравнения на четность (синдром), в которых участвуют полученные в результате проведения итерации декодирования «жесткие» символы кодового слова. Моделирование показало (рисунок 13 и рисунок 14), что для случая нормального хода декодирования с каждой новой проделанной итерацией «вес» синдрома (число несошедшихся уравнений на четность), в среднем, уменьшается. Пример сходимости синдрома при декодировании одного из 8иМгате2, изначально содержащего 127 ошибок и декодированного за 17 итераций показан на рисунке 19. В случае инверсии этого 8иМгате2 синдром не сойдется к нулю (рисунок 20).

Рисунок 19 - Пример сходимости Рисунок 20 - Пример сходимости при

синдрома при декодировании 8иМгате2 декодировании 8иМгате2 с инверсией

В первом приближении можно сформулировать критерий, позволяющий отличить динамику на рисунке 19 от динамики на рисунке 20: если значение «веса» синдрома после проведения текущей итерации больше, чем после проведения предыдущей - выносится решение о том, что дальнейшее декодирование не имеет смысла и процесс останавливается.

Сформулированный критерий требует уточнения. Дело в том, что проверка на четность не может обнаружить ошибки четной кратности. Это означает, что если проверка содержит сразу две ошибки (или любое четное число), она будет сходиться (элемент синдрома 0). После проведения одной итерации декодирования одна из этих ошибок может быть исправлена. Число ошибок станет нечетным, что будет зафиксировано проверкой на четность (элемент синдрома 1). Таким образом, число ошибок в результате проведения итерации декодирования уменьшится, а число несошедшихся уравнений на четность («вес» синдрома) увеличится.

Описанное явление иллюстрирует пример на рисунке 21. «Вес» синдрома при декодировании сошелся к нулю, что эквивалентно выполнению всех проверок на четность, однако по ходу декодирования трижды был нарушен сформулированный выше критерий остановки декодирования. Выходом из данной ситуации является разрешение превышения значения «веса» синдрома после текущей итерации над значением после предыдущей итерации, но только фиксированное число раз N. Как только число превышений «веса» синдрома по сравнению с предыдущим значением превышает N - выносится решение об инверсии битового потока. Чем меньше выставленное значение N тем быстрее будет приниматься решение об инверсии, однако тем вероятнее потерять кадры, характеризующиеся большим, как на рисунке 21, значением N.

итчрации апоа*ооля**« Число игёрщиЛ для псиияжя сешения ой нхиосон

Рисунок 21 - Пример сходимость Рисунок 22 - Зависимость числа

синдрома при декодировании 8иЫгате2 итераций для идентификации от потерь

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

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

Без идентификации инверсии на обрабатываемой выборке было потеряно ~50% принятых кадров. Применение предложенных способов идентификации позволило сократить потери до -1-2%, в зависимости от параметров алгоритма идентификации.

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

Применяя способ идентификации инверсии посредствам анализа сходимости синдрома при N=3, на обрабатываемой выборке было декодировано 2000 из 2026 кадров (-99%). Еще 26 кадров, как было отмечено выше, было потеряно на «стыках» при смене полярности «мягких» решений на входе декодера. Правильность декодирования подтверждается расшифровкой декодированной информации и расчетом контрольной суммы для каждого кадра. Фрагмент статистики по обработке данной выборки представлен на рисунке 23. Собранная статистика по числу итераций декодирования 8иЬ6-ате2 соответствует полученной на имитационной модели статистике (рисунок 12).

¡01003 10101015 1020 1025 1030 1033 1040 1045 1050 1$СО1002 1С10 1013 1020 10251030 1035 1040 1045 1050 Ноыер декодированного ЗиЫтте2 Ноиердакодироввнного Э^ГгатаЭ

Рисунок 23 - Статистика по декодированию 8иМгате2 и ЗиЬй'ашеЗ

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

На рисунке 24 демонстрируются полученные на имитационной модели зависимости BER от битового отношения сигнал/шум для блокового турбо кодека (32,26)х(32,26) при различном значении длины списка гипотез Т. Увеличение длины списка гипотез приводит к повышению помехоустойчивости.

Помимо этого, на рисунке 24 приводится сравнение помехоустойчивости LDPC кода, декодируемого по алгоритму минимума суммы «Min-sum normalized», и различных реализаций блокового турбо кодека, в том числе реализации фирмы AHA. Реализованный LDPC код демонстрирует лучшую исправляющую способность, чем блоковый турбо код, опережая реализацию турбо кодека фирмы AHA на -0.8 дБ по уровню вероятности битовой ошибки 10"5.

Рисунок 24 - Сравнение ВЕК турбо кодека и Рисунок 25 - Сравнение среднего числа

ЫЭРС кодека итераций при декодировании

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

Сравнение сложности итерации декодирования турбо кода и Ы)РС кода приводится в таблице 3. Моделирование на ПК показало, что проведение итерации ЬОРС декодирования требует в 3 раза меньше времени, чем проведение итерации блокового турбо декодирования.

Анализ соотношений между сложностью сравниваемых кодов на итерацию декодирования и их средним используемым числом итераций показывает, что в конкретном

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

Таблица 3 - Сравнение сложности декодирования

Операция Количество на итерацию декодирования

1Т>РС («Мт-вшп погтаНгес!») Блоковый Турбо код (Алгоритм Чейза (Т=4))

Сложение 37024 72704

Умножение 38706 215040

Сравнение 64159 149825

Взятие модуля 33888 2048

Сложение по модулю 2 4218 201344

Основные результаты и выводы по работе

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

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

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

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

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

1. Разработана методика выбора алгоритма декодирования 1Л5РС кодов.

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

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

4. Предложен способ идентификации инверсии битового потока на входе 1ЛЭРС декодера.

Публикации по теме диссертации

Публикации в изданиях, рекомендованных ВАК

1. Кирьянов И. А., Моделирование работы LDPC-декодера по алгоритму с распространением доверия по надежностям, Информационные технологии в проектировании и производстве, изд. ФГУП ВИМИ, №4, 2012 г., стр. 57-60.

2. Кирьянов И.А., Исследование статистических характеристик декодирования низкоплотностных кодов, Информационно-измерительные и управляющие системы, изд. Радиотехника, №10,2012 г., стр. 20-25.

3. Кирьянов И.А., Важенин H.A., Оценка статистических характеристик функционирования LDPC-декодера на имитационной модели, Электронный журнал «Труды МАИ», изд. МАИ, №59, 2012 г.

4. Кирьянов И.А., Субоптимальное декодирование кодов с малой плотностью проверок на четность, Электромагнитные волны и электронные системы, изд. Радиотехника, №5, 2014 г., стр.47-51.

5. Кирьянов И.А., Важенин H.A., Особенности программной реализации и характеристики декодера низкоплотностных кодов в среде MATLAB/SIMULINK, Вестник Московского авиационного института, изд. МАИ, №2, 2014 г., стр. 104-113.

6. Кирьянов И.А., Мажоритарное декодирование кодов с малой плотностью проверок на четность, Электромагнитные волны и электронные системы, изд. Радиотехника, № 12, 2014 г., стр.9-14.

7. Кирьянов И.А., Сравнение перспективных техник помехоустойчивого кодирования информации, Электромагнитные волны и электронные системы, изд. Радиотехника, №1,2015 г., стр.26-34.

Авторские свидетельства и патенты

8. Кирьянов И.А., Программа оценки вычислительной сложности декодирования кодов с малой плотностью проверок на четность, Свидетельство о государственной регистрации программы для ЭВМ №2014615590 от 29.05.14 г.

Публикации в других изданиях и сборниках докладов конференций

9. Кирьянов И.А., Декодирование кодов с малой плотностью проверок на четность по алгоритму «Belief propagation» с аппроксимацией, Вестник воздушно-космической обороны, изд. ОАО «ГСКБ «Алмаз-Антей», №2, М.: - 2014 г., стр. 40-47.

10. Кирьянов И.А., Применение помехоустойчивого кодирования информации в глобальной навигационной спутниковой системе GPS, Вестник воздушно-космической обороны, изд. ОАО «ГСКБ «Алмаз-Антей», №4, М.: - 2014 г., стр. 113119.

11. Кирьянов И.А., Повышение вычислительной эффективности декодирования кодов с малой плотностью проверок на чётность, Вестник воздушно-космической обороны, изд. ОАО «ГСКБ «Алмаз-Антей», №4, М.: - 2014 г., стр. 120-124.

12. Кирьянов И.А., Исследование статистических характеристик декодирования низкоплотностных кодов с использованием алгоритма с распространением доверия по надёжностям, Сборник тезисов докладов Московской молодежной научно-практической конференции «Инновации в авиации и космонавтике - 2012», изд. ООО «Принт-салон», Санкт-Петербург: -2012 г., стр. 96-97.

13. Кирьянов И.А., Моделирование работы LDPC - декодера по алгоритму с распространением доверия по надёжностям, Сборник докладов 1-ой межвузовской студенческой научно-технической конференции «Современные состояния и перспективы развития сложных радиоэлектронных систем», изд. ОАО «ГСКБ Алмаз-Антей», М.: - 2012 г., стр. 16-22.

14. Кирьянов И.А., Программная реализация алгоритма декодирования «Belief propagation» LDPC кода на языке С++, Сборник тезисов докладов Московской молодежной научно-практической конференции «Инновации в авиации и космонавтике - 2013», изд. ООО «Принт-салон», Санкт-Петербург: -2013 г., стр. 234-

15. Кирьянов И.А., Анализ методов повышения эффективности вычислительной реализации алгоритмов декодирования LDPC — кодов, Сборник тезисов докладов 12-ой Международной конференции «Авиация и космонавтика - 2013», изд. «Известия», М.:-2013 г., стр. 476-477.

16. Кирьянов И.А., Мажоритарное декодирование кодов с малой плотностью проверок на четность, Сборник тезисов докладов Московской молодежной научно-практической конференции «Инновации в авиации и космонавтике - 2014», изд. ООО «Принт-салон», Санкт - Петербург: - 2014 г., стр. 160-161.

17. Кирьянов И.А., Декодирование низкоплотностных кодов с использованием линейной аппроксимации гиперболических функций, Сборник тезисов докладов 13-ой Международной конференции «Авиация и космонавтика - 2014», изд. ООО «Принт-салон», Санкт-Петербург: -2014 г., стр. 395.

235.

'экз.