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

• Лихобабин, Евгений Александрович
• кандидат наук
• 2014

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

СОДЕРЖАНИЕ

Введение

Глава 1. Проблема достоверной передачи информации в системах наземного теле радиовещания - постановка задачи, методы решения

1.1. Постановка задачи

1.2. Системы связи

1.3. Модели каналов связи

13.1 Двоичный симметричный канал

13.2 Двоичный симметричный канал со стираниями

13.3 Канал с аддитивным белым гауссовским шумом

13.4 Канал с аддитивным белым гауссовским шумом и квантованным выходом

1.3.5 Канал с обобщенными Релеевскими замираниями

1.4. Математическая формализация задачи построения декодера

1.5. Коды с низкой плотностью проверок на четность

1.5.1 Представление LDPC кода

1.5.2 Графическое представлении LDPC кода

1.6. Классические алгоритмы декодирования LDPC кодов

1.6.1 Передача сообщений и принципы турбо-декодирования

1.6.2 Декодирование LDPC кодов

1.6.3 Декодирование кода повторения

1.6.4 Декодирование кода проверки на четность

1.6.5 Алгоритм сумма-произведение

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

1.6.6.1 Итеративный алгоритм заполнения стираний

1.6.6.2 Декодер максимального правдоподобия дляДСКС

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

1.6.7.1 Алгоритмы Галлагера А и Б

1.4.7.2 Алгоритм мажоритарного декодирования дляДСК

1.4.7.3 Алгоритм с инверсией бита дляДСК

1.7. Выводы и рекомендации

Глава 2. Разработка и исследование упрощенных алгоритмов декодирования 1Л)РС кодов

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

2.1.1 Алгоритм Ричардсона-Новичкова

2.1.2 Алгебра логарифма отношений правдоподобия

2.1.3 Алгоритм минимум-сумма с корректировкой

2.1.4 Алгоритм минимум-сумма

2.1.5 Алгоритм вычисления апостериорных вероятностей

2.2 Алгоритмы, основанные на алгоритме с инверсией бита

2.2.1 Взвешенный алгоритм с инверсией бита

2.2.2 Модифицированный взвешенный алгоритм с инверсией бита

2.2.3 Усовершенствованный модифицированный взвешенный алгоритм

с инверсией бита

2.3. Комбинации алгоритмов

2.3.1 Алгоритм аппроксимация минимум-сумма

2.3.2 Алгоритмы, основанные на алгоритме МС*

2.3.3 Обобщенный алгоритм МС*

2.3.4 Алгоритм минимальный ОАМС*

2.3.5 Выводы и рекомендации

Глава 3. Разработка и исследование методов построения составного декодера Ы)РС кода, минимизирующего средние вычислительные затраты

3.1 Математическая формализация и решение задачи оптимизации параметров декодера Ы)РС кода

3.2 Исследование сложности реализации различных алгоритмов декодирования LDPC кодов

3.3 Разработка структуры декодера LDPC кодов

3.4 Результаты экспериментов

3.5 Выводы и рекомендации

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

4.1 Разработка среды моделирования в программной среде

GNU Linux

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

4.3 Разработка методики оптимального проектирования декодеров LDPC кодов

4.4 Выводы и рекомендации

Заключение

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

Список используемых сокращений

Приложения

Приложение I. Распределение весов строк и столбцов проверочной матрицы

исследуемых кодов стандарта РАВИС

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

декодирования LDPC кодов и составного декодера в целом

Приложение III. Исходные тексты скриптов расчета интегральных оценок сложности составного декодера

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

ВВЕДЕНИЕ

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

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

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

Одно из первых предложений по реализации подобной системы было изложено в патенте Российской Федерации №2219676 с приоритетом от 08.11.2000 г. [3], в котором предусматривалась возможность трансляции информационного телевидения, содержащего динамические цветные изображения и стереозвуковое сопровождение. Результаты создания модели системы и ее натурных испытаний впервые были изложены в журнале

«Broadcasting. Телевидение и радиовещание», 2005, №5 [4]. На прошедшей в марте 2006 года в Женеве объединенной конференции МСЭ-Р от России был представлен доклад «Повышение эффективности использования VHF-диапазона частот», в котором была описана система мобильного узкополосного мультимедийного вещания AVIS (Audiovisual information system) [5].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первая глава посвящена постановке, математической формализации и методам решения задачи достоверной передачи информации. Рассматриваются каналы связи, относительно которых рассматриваются современные системы помехоустойчивого кодирования. Рассматривается класс LDPC кодов, варианты представления этих кодов и их основные характеристики. Также рассматриваются классические алгоритмы декодирования LDPC кодов и принципы лежащие в основе декодирования итеративно-декодируемых кодов. Рассмотрены алгоритмы декодирования для каналов связи ДСК, ДСКС и АБГШ.

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

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

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

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

Также рассмотрено интересное направление получения алгоритмов декодирования со сниженными вычислительными затратами - комбинация различных алгоритмов декодирования в рамках одной итерации. Рассмотрен АРД, построенный по схеме алгоритма минимум-сумма (AMC*), а также предложены его обобщенная интерпретация (О AMC*) и алгоритм декодирования, использующий для получения второго сообщения к проверочным узлам операцию поиска минимума.

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

исследованию сложности реализации различных алгоритмов декодирования LDPC кодов.

Предлагается метод оценки вычислительных затрат на реализацию алгоритма декодирования LDPC кода. Приводятся результаты экспериментов и оценки сложности полученных схем декодирования LDPC кодов стандарта РАВИС. Так для кода (20664,10332) выигрыш в средних вычислительных затратах составляет от 4,93 до 8,23 раз в зависимости от схемы декодера, для кода (20664,13780) - от 1,95 до 2,61, для кода (20664,15500) от 3,43 до 4,43 раз.

Четвертая глава посвящена разработке моделирующей среды для исследования LDPC кодов и алгоритмов их декодирования. Разработка велась на языках С, С++, Python с использованием пакета Gnuplot для визуализации экспериментальных данных. Также рассмотрен вопрос построения алгоритмов декодирования, оптимизированных для многоядерных платформ. Кроме этого предложена методика оптимального проектирования составных декодеров LDPC кодов.

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

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

ГЛАВА 1. ПРОБЛЕМА ДОСТОВЕРНОЙ ПЕРЕДАЧИ ИНФОРМАЦИИ В СИСТЕМАХ НАЗЕМНОГО ТЕЛЕРАДИОВЕЩАНИЯ - ПОСТАНОВКА ЗАДАЧИ, МЕТОДЫ РЕШЕНИЯ

1.1. Постановка задачи

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

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

• получение кодов, позволяющих приблизится к пропускной способности канала связи;

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

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

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

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

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

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

1.2. Системы связи

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

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

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

Источник информации

Канал связи

Приемник информации

Рисунок 1.1 - Простейшая система связи

В своей основополагающей работе в 1948 году, Шеннон, помимо введения фундаментальных понятий теории информации, таких, как энтропия, формализовал задачу передачи информации в целом и показал, что эта проблема может быть разделена на две - кодирование источника и кодирование канала [11], рисунок 1.2.

Канал связи

Рисунок 1.2 — Система передачи информации с точки зрения теоремы о разделении канала и источника

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

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

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

Теорема Шеннона о канальном кодировании утверждает существование максимальной скорости (бит на используемый канал), с которой информация может быть передана надежно, т.е. со сколь угодно малой вероятностью ошибки в данном канале. Эта максимальная скорость называется пропускной способностью канала связи и обозначается С. Никакой метод кодирования не до-

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

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

13. Модели каналов связи

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

Для дальнейшего рассмотрения введем следующие обозначения. Здесь и далее, если не указано иное, будем полагать, что для передачи по каналу связи кодового слова с=(с/,с2,...,сдг) кода сеС длины N используется модуляция ВРБК. При этом передаваемое кодовое слово с при модуляции отображается в биполярную последовательность:

где 1-ый компонент л: = +1 при с. = О и х, = -1 при с, = 1. Пусть у = (у0,у„...,уп_1) последовательность выборок (или символов) на выходе канального приемника. Эта последовательность обычно называют мягким решением принятого кодового слова. Выборки у - это действительные числа с у = х+п, гдеп=[«„, л,,- шумовой вектор, его элементы л(. - в общем случае, случай-

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

= {0,л>0,

Тогда мы получим двоичную последовательность г = (г0,г„...,г^_1) - это жесткое решение относительно принятого кодового слова, г-ий бит г/ принятого кодового слова г - просто оценка /-ого бита с, переданного кодового слова с. Если г, =с, для 0 < г < /V, то г = с, в противном случае ъ содержит ошибки. Таким образом, г является априорной (декодированию) оценкой переданного кодового слова с.

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

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

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

Любой канал характеризуется входным алфавитом X, выходным алфавитом У и, в общем случае, плотностью распределения вероятностей р(у1!х1) принятой случайной величины при условии передачи символа из алфавита X [18].

В данной работе будут рассматриваться только каналы без памяти с двоичным входным алфавитом Х=В={+1,-1} и выходным алфавитом У, который может быть как дискретным, так и непрерывным. Более того, будем считать все рассматриваемые каналы симметричными, то есть в нашем случае:

р(уШ= р(-у11-х1).

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

Простейшим ДСКП является двоичный симметричный канал (ДСК, binaiy symmetric channel - BSC) - канал, выходом которого являются жесткие решения относительно принятых бит. Помимо ДСК к классу ДСКП относится ряд каналов с мягким выходом, часть из которых будет рассмотрена ниже - это двоичный симметричный канал со стиранием (ДСКС, binary erasure channel - ВЕС), канал с аддитивным белым гауссовским шумом (АБГШ, additive white Gaussian noise - AWGN), а также канал с общими релеевскими замираниями.

Список литературы диссертационного исследования кандидат наук Лихобабин, Евгений Александрович, 2014 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Дворкович В.П., Хойбергер А. Цифровое вещание в I и II диапазонах частот // Предложения по стандартизации DRJM+.

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

3. Дворкович А.В., Дворкович В.П., Зубарев Ю.Б, Соколов А.Ю., Чернов Ю.А. Способ трансляции информационного телевидения // Патент РФ № 2219676, 08.11.2000.

4. Дворкович В.П., Дворкович А.В., Иртюга В.А., Тензина В.В. Новая аудиовизуальная информационная система // Broadcasting. Телевидение и радиовещание, 2005, № 5, с. 52-56.

5. ITU-R Document 6Е/336-Е, 6М/133-Е Increase of the Band 8 (VHF) Utilization Efficiency. - 2006.

6. Berrou C., Glavieux A, Thitimajshima P. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes", Proceedings of International Conference on Communications, Geneva, Switzerland. - 1993, May. - P. 10641070.

7. Berrou C., Glavieux A. Near optimum error correcting coding and decoding: turbo-codes, IEEE Transactions in Communications. - 1996, October. - Vol. 44. - P. 1267-1271.

8. Gallager R.G. Low-density parity-check codes // Cambridge, MA: M.I.T. Press. -1963.

9. Futaki H., Ohtsuki T. Performance of low-density parity-check (LDPC) coded OFDM systems // Proceedings of the IEEE International Conference on Communications, New York. - 2002, April. - Vol. 3. - P. 1696-1700.

10. ГОСТ P 54309-2011 Аудиовизуальная информационная система реального времени (РАВИС). Процессы формирования кадровой структуры,

канального кодирования и модуляции для системы цифрового наземного узкополосного радиовещания в ОВЧ диапазоне. Технические условия. - М.: Стандартинформ, 2012. - 42 с.

11. Шеннон К. Работы по теории информации и кибернетике /Под. ред. Р.Л.Добрушина и О.Б.Лупанова. - М.: Издательство иностранной литературы, 1963.-829 с.

12. Fresia М., Perez-Cruz F., Poor H.V., Verdu S. Joint source and channel coding // IEEE Signal processing magazine. - 2010, November. - Vol. 27. - Num. 6. -P. 104-113.

13. Richardson Т., Urbanke R. Modern coding theory // Cambridge, University press. - 2008. - pp. 572.

14. Johnson S.J. Iterative error correction. Turbo, low-density parity-check and repeat-accumulate codes // Cambridge, University Press. - 2010. - pp.335.

15. Ryan W.E., Lin S. Channel codes. Classical and modern // Cambridge, University Press. - 2009. - pp. 692.

16. Declercq D., Fossorier M., Bigleri E. Channel coding. Theory, algorithms and applications // Academic press library in mobile and wireless communications -2014.-pp. 667.

17. Wymeersch H. Iterative receiver design // Cambridge, University Press. -2007.-pp. 254.

18. Скляр Б. Цифровая связь/ Теоретические основы и практическое применение: Пер. с англ. -М.:Издательский дом «Вильяме» . -2003. - 1104 с.

19. Шлома A.M., Бакулин М.Г., Крейнделин В.Б., Шумов А.П. Новые алгоритмы формирования и обработки сигналов в системах подвижной связи / Под редакцией профессора А.М.Шломы. - М.: Горячая линия-Телеком. - 2008. - 344 с: ил.

20. Urbanke R. Efficient decoding techniques for LDPC codes // Dissertation, Wien. - 2007.

21. Вернер M. Основы кодирования // M.: Техносфера. - 2006. - 288 с.

22. Land I., Reliability information in channel decoding - practical aspects and information theoretical bounds// Ph.D. dissertation, University of Keil, Germany. -2005.

23. Золотарев B.B. Теория и алгоритмы многопорогового декодирования/ Под ред. чл.-кор. РАН, профессора, доктора техн. наук Ю.Б. Зубарева. - М.: Радио и связь, Горячая линия - Телеком. - 2006. - 232 е.: ил.

24. Wiberg N. Codes and decoding on general graphs // Linkoping University, Sweden. -1996.

25. Davey M.C. Error-correction using low-density parity-check codes // University of Cambridge. - 1999.

26. Bahl L., Cocke J., Jelinek F., Raviv J. Optimal decoding of linear codes for minimizing symbol error rate // IEEE Transactions in Information Theoiy. - 1974, March. - Vol. 20. - No. 3. - pp. 284-287.

27. MacKay D. J.C., Neal R.M. Near Shannon limit performance of low density parity check codes // Electronics Letters. - 1996, August. - Vol. 32. - pp. 1645-1646.

28. Tanner R.M. A recursive approach to low complexity codes // IEEE Transactions in Information Theory. - 1981, September. - Vol. 27. -No.5. - pp. 533547.

29. T.Tian, C.Jones, J.Villasenor, R.Wesel. Construction of irregular LDPC codes with low error floors // 2003 IEEE International Conference on Communications. - 2003, May. - pp. 3125-3129.

30. Vontobel P.O., Koetter R. Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes // IEEE Transactions on Information Theory. - 2005, December. - pp. 67.

31. Pearl J. Reverend Bayes on inference engines: a distributed hierarchical approach // Proceedings of Second National Conference on Artificial Intelligence. -1982. -pp.133-136.

32. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks and Plausible Inference // San Mateo, CA, Morgan Kaufman. - 1988. - pp. 553.

33. Sankaranarayanan S., Vasic B. Analysis of Iterative Erasure-Decoding of Linear Block Codes: A Parity-Check Orthogonalization Approach // Proceedings of 42th Allerton Conference of Comunication, Control and Computing, Monticello, IL, USA. - 2004, October.

34. Burshtein D., Miller G. Efficient maximum-likelihood decoding of LDPC codes over the binary erasure channel // IEEE Transactions on Information Theory. -2004. - Vol. 50. - No. 11. - pp. 2837-2844.

35. Месси Дж. Пороговое декодирование / Пер. с англ. под ред. Э.Л. Блоха, -М. Мир.-1966.-208 с.

36. Ardakani М. Efficient Analysis, Design and Decoding of Low-Density Parity-Check codes // Ph. D. dissertation, University of Toronto. - 2004.

37. Vellambi B.N., Fekri F. Results on the improved decoding algorithm for low-density parity-check codes over the binary erasure channels // IEEE Transactions on Information Theory. - 2007, April. - Vol. 53. -No.4. -pp.1510-1520.

38. Золоторев B.B., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник / Под. ред. чл.-кор. РАН, Ю.Б. Зубарева. - М.Горячая линия-Телеком. - 2004. - 126 с.

39. Золотарёв В.В., Зубарев Ю.Б., Овечкин Г.В. Многопороговые декодеры и оптимизационная теория кодирования/ Под. Ред академика РАН В.К. Левина. - М.:Горячая линия - Телеком. - 2012. - 239 с.

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

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

42. Лихобабин Е.А., Дворкович А.В. Использование квазиоптимальных алгоритмов декодирования LDPC кодов в системе цифрового телевизионного

вещания стандарта DVB-T2 // Труды РНТОРЕС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применения - М. Выпуск XII-1. С. 25-27. -2010.

43. Kou Y., Lin S., and Fossorier М. Low density parity check codes based on finite geometries: A rediscovery and new results // IEEE Transactions on Information Theory. - 2001, November. - Vol. 47. - pp. 2711-2736.

44. Chen J., Dholakia A., Eleftheriou E., Fossorier M., Ни X.Y. Near optimal reduced-complexity decoding algorithms for LDPC codes // Proceedings IEEE International Symposium on Information Theory, Lausanne, Switzerland. - 2002, July.

45. Fossorier M., Mihaljevich M., Imai H. Reduced complexity iterative decoding of low density parity check codes based on belief propagation, IEEE Transactions on Communications. - 1999, May. - Vol. 47. - № 5. - pp. 673-680.

46. Zhang J., Marc Fossorier P.C. A modified weighted bit-flip decoding of low-density parity-check codes // IEEE Communication Letters. - 2004, March. - Vol. 8, No. 3.

47. Wu X., Ling C., Jiang M., Xu E., Zhao C., You X. Towards Understanding Weighting Bit-Flipping Decoding // Information Theory, IEEE International Symposium on, Nice. - 2007, June. - pp. 1666-1670.

48. Кравченко A.H. Методы и аппаратура кодирования и декодирования систематического нерегулярного кода повторения-накопления (IRA) для DVB-S2 и DVB-T2 демодуляторов // Цифровая обработка сигналов. - 2009, № 4, С.41-47.

49. Кравченко А.Н. Снижение сложности декодирования низкоплотностного кода // Цифровая обработка сигналов. - 2010, № 2, С.35-41.

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

51. Белоголовый А.В., Крук Е.А. Многопороговое декодирование кодов с низкой плотностью проверок на четность // Вопросы передачи и защиты информации: Сборник статей / СПбГУАП. СПб. - 2006. - С.25-37.

52. Chen J., Tanner R.M., Jones С., Li Y. Improved min-sum decoding algorithms for irregular LDPC codes // IEEE International Symposium on Information Theory. -2005. - pp. 449-453.

53. Zhang J., Fossorier M., Gu D. Two-dimensional correction for min-sum decoding of irregular LDPC codes // IEEE Communications letters. - 2006. - Vol. 10.- No.3. -pp. 180-182.

54. Savin V. Self-corrected min-sum decoding of LDPC codes // IEEE International symposium on Information Theory. - 2008. - pp. 146-150.

55. Wu X., Zhao C., You X. Parallel weighted bit-flipping decoding, IEEE Communication Letters, Vol. 11, №. 8, August 2007.

56. Jiang M., Zhao C., Zhang L., Xu E. Adaptive offset min-sum algorithm for low-density parity check codes // IEEE Communication letters. - 2006, June. - Vol. 10.-No. 6.

57. Ngatched T.M.N., Takawira F. A List Decoding Algorithm for Short Low-Density Parity-Check Codes // 6th International ITG-Conference on Source and Channel Coding, Munich. - 2006, April. - pp. 1-6.

58. Gaudet V.C., Rapley A.C. Iterative decoding using stochastic computation, IET Electronics Letters. - 2003. - Vol. 39. - No. 3. - pp. 299-301.

59. Gross W.J., Gaudet V.C., Milner A., Stohastic implementation of LDPC decoders // IEEE Proceedings of the 39th Asilomar Conference on Signals, Systems and Computers. - 2005. - pp.713-717.

60. Sharifi Tehrani S., Gross W.J., Mannor S., Stohastic decoding of LDPC codes, IEEE Communication Letters. - 2006. - Vol. 10. - No. 10. - pp. 716-718.

61. Zhang J., Fossorier M.P.C. Shuffled iterative decoding // IEEE Transactions on communications. - 2005, February. - Vol. 53. - No. 2.

62. Wadayama T., Nakamura К., Yagita M., Funahashi Y., Usami S., Takumi I. Gradient descent bit flipping algorithms for decoding LDPC codes // Information Theory. - 2008, April.

63. Kasparis C., Evans B.G. Gradient projection decoding of LDPC codes // IEEE Communication Letters. - 2007, March. - Vol. 11. - pp. 279-281.

64. Feldman J. et al. Using linear programming to decode binary linear codes // IEEE Transactions on Information Theory. - 2005, March. - Vol. 51. - No. 3. - pp. 954-972.

65. Yang K. et al. Nonlinear programming approaches to decoding low-density parity-check codes // IEEE Journal, Selected Areas in Communications. - 2006, August. - Vol. 24. - No.8.

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

67. Scandurra A.G., Daipra A.L., Arnone L., Passoni L., Moreira J.C. A genetic-algorithm based decoder for low density parity check codes // Latin American applied research. - 2006. - №36. - pp. 169-172.

68. Vityazev V., Likhobabin E., Ustinova E., "Min-Sum Algorithm-Structure Based Decoding Algorithms for LDPC Codes", 3rd Mediterrian Conference on Embedded Computing, Budva, Montenegro. -2014, June. - pp. 256-259.

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

70. Kabashima Y., Saad D. Belief propagation vs. TAP for decoding corrupted messages // Europhysics Letters. - 1998, October. - Vol. 44. - No. 5 . - pp. 668114.

71. Yedidia J.S., Freeman W.T., Weiss Y. Understanding belief propagation and its generalizations // Exploring Artificial Intelligence Laboratory. - 2001, August. -pp. 236-239.

72. Richardson T., Novichkov V. Node processors for use in parity check decoders // United State Patent 6,938,196 B2. - 2005, August 30.

73. Hegenauer J. Iterative decoding of binary block and Convolutional codes // IEEE Transactions on Information Theory. - 1996, May. - Vol.42. - No. 2.

74. Franceschini M., Ferrari G., Raheli R. LDPC Coded Modulation // Springer. -2009.

75. Nouh A., Banihashemi A.H. Bootstrap decoding of low-density parity-check codes // IEEE Communication Letters. - 2002, September. - Vol. 6.

76. Jones C., Vallès E., Smith M., Villasenor J. Approximate-min* constraint node updating for LDPC code decoding // IEEE Military Communication Conference. - 2003, October, - pp. 157-162.

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

78. Jones С., Dolinar S., Andrews К., Divsalar D., Zhang Y., Ryan W. Functions and architectures for LDPC decoding // 2007 Information Theory Workshop. - 2007, September. - pp. 577-583.

79. Ardakani M., Kschischang F. R. Gear-shift decoding for algo- rithms with varying complexity // in Proceedings IEEE International Conference on Communications, Seoul, South Korea. - 2005, May. - Vol. 1. - pp. 500-504.

80. Zarrinkhat P., Banihashemi A.H. Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes // IEEE Transactions on Communications. - 2007, February. - Vol. 55. - No. 2. - pp. 292-302.

81. Поршнев C.B. MATLAB 7. Основы работы и программирования // Учебник. М.:Бином-Пресс. - 2006. - 320 с.

82. AHA Products Group Forward Error Correction // http://w4vw.aha.com/forward-error-correction/

83. Kozintsev I. Matlab routines for LDPC codes // http://www.kozintsev.net/soft.htnil

84. Software for Low Density Parity Check codes // https ://github. com/radfordneal/LD PC-codes

85. LDPC implementation used for the CWIT 2011 paper // https://github.com/slampoud/ldpcspa_cwit

86. С++ simulation environment for LDPC codes // https://github.com/diah/LDPC simulator

87. Jeruchim M.C., Balaban P., Shanmugan K.S. Simulation of communication systems: Modelling, Methodology, and Techniques // 2nd Ed., Kluwer Academic/Plenum, New York. - 2000.

88. Encyclopedia of sparse graph codes // http://www.inference.phv.cam.ac.uk/mackav/codes/data.html.

89. Керниган Б.У., Ритчи Д.М. Язык программирования Си // М.Вильямс. -2013.-С. 304.

90. Страуструп Б. Язык программирования С++ // М.Бином. - 2011 г. - С. 1136.

91. Лутц М. Изучаем Python // Спб.: Символ-Плюс. - 2011 г. - С. 1280.

92. Gnuplot homepage // http://www.gnuplot.info

93. Витязев B.B., Витязев С.В., Харин А.В. Многоядерные цифровые сигнальные процессоры платформы TMS320C66xx: учебное пособие / Рязанский Государственные Радиотехнический университет, Рязань. - 2013. -С. 141.

94. The OpenMP® API specification for parallel programming // http:// openmp.org/wp/

95. GCC, the GNU Compiler Collection // http://gcc.gnu.org

96. Analog, Embedded Processing, Semiconductor Company, Texas Instruments // http://www.ti.com

97. Intel® С and С++ Compilers // https://softvvare.intcl.com/en-us/c-compilers

98. Витязев B.B. Цифровая частотная селекция сигналов // М.: Радио и связь, 1993.-240 с.

99. GNU gprof // http://sourceware.org/binutils/docs/gprof7

100. Creonic IP cores and system solutions // http://www.creonic.com/en/ip-cores

101. Qaisar S. Progressive In-Network Reliability for wireless Sensor Networks // VDM Verlag Dr. Muller Publishing house ltd., USA. - 2009.

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

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

104. Baron D., Sarvotham S., Baraniuk R.G. Bayesian Compressive Sensing Via Belief Propagation // IEEE Transactions on Signal Processing. - 2010, January. -Vol.58. - No. 1. - pp.269-280.

Список используемых сокращений

BCJR - Bahl-Cocke-Jelinek-Raviv

BP - belief propagation

CN - check node

CNj - check node number j

H - проверочная матрица кода

hVj - элемент проверочной матрицы, находящийся в /-ой строке и у-ом столбце

LDPC - low density parity check

LP - linear programming

LLR - log likelihood ratio

LR - likelihood ratio

MAP - maximum a posteriori

ML - maximum likelihood

MS - min-sum

NMS - normalized min-sum

OSMLG - one step majority logic

OMS - offset min-sum

SP - sum-product

SPA - sum-product algorithm

UML - unified modeling language

VN - variable node

VN/ - variable node number i

N- число бит в коде М- число проверок в коде

N(i) - множество позиций единиц в г-ом столбце матрицы Н

МЦ) - множества позиций единиц в у-ой строке матрицы Н Щ 1)~{}} множества позиций единиц в /-ом столбце матрицы Н, за исключением у'-ой позиций соответственно

М(]Ш множества позиций единиц в у'-ой строке матрицы Н, за исключением

/-ой позиций соответственно

йс- Хеммингов вес столбца проверочной матрицы

с1г - Хеммингов вес строки проверочной матрицы

АБГШ - аддитивный белый гауссовский шум ДСКП - двоичный симметричный канал без памяти ДСК - двоичный симметричный канал ДСКС - двоичный симметричный канал со стираниями МАВ - максимум апостериорной информации

ЗС - заполнение стираний ИБ - инверсия бита АВ - апостериорная вероятность РД - распространение доверия МС - минимум-сумма СП - сумма-произведение ГА - Галлагер А ГБ - Галлагер Б

МД - мажоритарное декодирование

АЗС - алгоритм заполнения стираний АИБ - алгоритм с инверсией бита ААВ - алгоритм апостериорных вероятностей АРД - алгоритм распространения доверия АМС - алгоритм минимум-сумма

АСП - алгоритм сумма-произведение

АГА - алгоритм Галлагера А

АГБ - алгоритм Галлагера Б

АМД - алгоритм мажоритарного декодирования

РАВИС -аудиовизуальная информационная система реального времени ОСШ - отношение сигнал/шум

AMC* - алгоритм РД построенный по структуре AMC ОАМС* - обобщенный алгоритм AMC*

МОАМС* - ОАМС* использующий операцию поиска минимума в качестве

второго оператора сложения ЛОП

ЛОП - логарифм отношения правдоподобия

ОП - отношение правдоподобия