Методики моделирования низкоплотностных кодеков с использованием массивно-параллельных вычислений тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Науменко, Юрий Сергеевич

• Науменко, Юрий Сергеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Науменко, Юрий Сергеевич

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

1.1 Обзор и классификация помехоустойчивых кодов

1.2 Низкоплотностные корректирующие коды

1.2.1 Декодирование по алгоритму с инвертированием бита

1.2.2 Декодирование по алгоритму распространения доверия

1.3 Выводы

2 МОДЕЛИРОВАНИЕ КОРРЕКТИРУЮЩИХ КОДЕКОВ ТЕЛЕКОММУНИКАЦИОННЫХ УСТРОЙСТВ В ГЕТЕРОГЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

2.1 Моделирование источника сигнала

2.2 Моделирование источника помех

2.3 Моделирование процесса коррекции ошибок в канале связи

2.3.1 Оценка основных параметров, характеризующих качество системы кодирования

2.3.2 Обеспечение статистической устойчивости оценок параметров

2.4 Выводы

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

3.1 Выбор целевой аппаратной платформы и среды разработки

3.2 Особенности обеспечения производительности вычислений

в гетерогенных системах

3.2.1 Вопросы коммуникационных взаимодействий уровней хост — вычислитель

3.2.2 Вопросы случайного доступа и высокой латентности

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

3.3 Схема параллельных вычислений, применяемая при декодировании

3.4 Методика моделирования низкоплотностных кодеков

в однопроцессорных гетерогенных вычислительных системах

3.5 Выводы

4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СРЕДСТВ МОДЕЛИРОВАНИЯ НИЗКОПЛОТНОСТНЫХ КОДЕКОВ

4.1 Архитектура программного обеспечения

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

4.1.2 Тестовая моделирующая оболочка

4.2 Моделирование помехоустойчивых систем связи

с низкоплотностным кодеком

4.3 Производительность вычислений в гетерогенных системах различной конфигурации

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А

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

ВВЕДЕНИЕ

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

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

Одними из самых энергетически эффективных и поэтому часто применяемых на практике кодов являются низкоплотностные коды или коды с малой плотностью проверок на четность (LDPC-код от англ. Low-Density Parity-Check code). Такие коды являются базовыми во многих технических стандартах в области телекоммуникаций, например IEEE 802.11 WiFi, ETSI EN302307-2 DVB-S2X и др. При реализации процедур декодирования низкоплотностных кодов результатив-

ным оказывается применение параллельных схем вычислений. В этой связи в задаче моделирования низкоплотностных кодеков перспективно применение гетерогенных вычислений с использованием ресурса графического процессора (ГП, GPU от англ. Graphics Processing Unit) ЭВМ, который обычно не задействован, в отличие от ее центрального процессора (ЦП, CPU от англ. Central Processing Unit,). Для ГП характерна массивно-параллельная архитектура, поэтому при достаточной степени распараллеливания алгоритмов моделирования вычисления с помощью ГП оказываются более производительными.

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

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

Однако вопросы применения параллельных вычислений в гетерогенных системах для решения задач моделирования низкоплотностных кодеков лишь частично затронуты в некоторых работах зарубежных авторов (J.R. Cavallaro, С. Chang, G. Falcao, S. Kang, G. Wang, Q. Wu) и фактически остаются открытыми. При этом основной акцент сделан преимущественно на задаче адаптации известных алгоритмов декодирования для реализации вычислений при помощи ГП, а процесс моделирования в целом, с учетом полного состава моделей в их взаимосвязи и особенностей реализации в гетерогенной системе рассмотрен недостаточно полно. Кроме того, проверка известных результатов на практике затруднитель-

на, в связи с высокими аппаратными требованиями (G. Falcao, G. Wang) и реализацией аппаратно-зависимых решений ввиду использования программно-аппаратной архитектуры CUDA (S. Kang, S. Cheng).

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

Работа выполнена в рамках одного из основных научных направлений Воронежского государственного технического университета «Перспективные радиоэлектронные и лазерные устройства и системы передачи, приема, обработки и защиты информации» и ГБ НИР 2013.17 «Исследование и разработка методов оптимального проектирования устройств и комплексов радиоэлектронных средств».

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

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

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

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

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

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

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

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

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

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

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

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

Основные теоретические и практические результаты работы в виде методик и автоматизированных средств внедрены на предприятии ОАО «Концерн «Созвездие» города Воронежа, а также в учебный процесс ФГБОУ ВПО «Воронежский государственный технический университет» по дисциплине «Основы конструирования электронных средств» для подготовки бакалавров по направлению 211000.62 — Конструирование и технология электронных средств (профиль «Проектирование и технология радиоэлектронных средств») для всех форм обучения.

Методология и методы исследования. В диссертационном исследовании использованы методы теории систем передачи информации, теории вероятностей и математической статистики, математического моделирования, методы параллельных вычислений на ЭВМ и программирования на языке С++.

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

/

1. Полно-параллельная архитектура декодера низкоплотностного (УУДАГ) кода по алгоритму распространения доверия может быть реализована с использованием массивно-параллельных вычислений на ГП по измененной схеме за счет применения дополнительных процессорных элементов. Экспериментально оцененный выигрыш в производительности вычислений по сравнению с известной схемой для кодов (96,3,6)...(9972,3,6) в среднем составляет 1,85 раза.

2. Для ограничения коммуникационных взаимодействий уровней ЦП-ГП модель источника помех целесообразно реализовывать на уровне процессорных элементов ГП. Использование разработанной методики моделирования источника помех обеспечивает достаточную точность получаемых результатов и повышение производительности вычислений за счёт уменьшения количества обращений к внешнему регистру состояния генератора псевдослучайных чисел. Экспериментально оцененный прирост производительности вычислений достигает 30 %.

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

работанных схем вычислений, предусматривающих минимизацию обращений к этим разделам памяти и применение процедур кэширования. Экспериментально оцененный прирост производительности вычислений для кодов длиной 96...9972 в среднем составляет 11 %.

4. Типовая схема организации гетерогенных вычислений в задаче моделирования низкоплотностных кодеков может быть модифицирована за счет использования дополнительного потока расчетов на ЦП. Применение разработанной методики моделирования низкоплотностных кодеков в однопроцессорных гетерогенных системах позволяет повысить производительность вычислений для кодов длиной 96...3000. Экспериментально оцененный выигрыш при малых значениях длины (до 273) составляет 80...41 %, для длин 273...3000 устанавливается на уровне 21 %.

5. Результаты моделирования, полученные при использовании разработанных автоматизированных средств, соответствуют известным, в частности, приведенным в работах Р. Морелос-Сарагоса, при этом экспериментально оцененный выигрыш в производительности параллельных вычислений по отношению к од-нопоточным при длине кода .N>2000 составляет при использовании декодера: по алгоритму с инвертированием бита — 1,1-5,3 раз; по алгоритму распространения доверия — 6,4-15 раз; по логарифмической версии алгоритма распространения доверия — 47-76 раз.

Степень достоверности и апробация результатов подтверждается применением стандартных методик и известных моделей для исследования характеристик устройств телекоммуникаций, известных методов обеспечения статистической достоверности полученных результатов, сопоставлением результатов экспериментальных исследований с известными данными других авторов. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах: Всероссийской научно-технической конференции «Современные проблемы радиоэлектроники» (Красноярск, 2013); Международном симпозиуме «Надежность и качество» (Пенза, 2013); Международной научно-практической конференции «Охрана, безопасность, связь — 2013» (Воронеж, 2013); Региональной научной конференции студентов, аспи-

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

По результатам работы в государственном информационном фонде неопубликованных документов ФГАНУ «ЦИТиС» № 50201450816 от 04.12.2014 зарегистрировано программное средство, а также подана заявка № 2014145373 от 11.11.2014 на выдачу патента на изобретение «Способ организации вычислений на графических процессорах для моделирования помехоустойчивых низкоплотно-стных кодеков».

Публикации. По теме диссертации опубликовано 16 печатных работ, в том числе 10 — в изданиях, рекомендованных ВАК РФ

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 106 наименований и приложения. Основная часть работы изложена на 128 страницах, содержит 47 рисунков и 4 таблицы.

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

Особое внимание уделено анализу процедуры декодирования, являющейся наиболее ресурсоемкой и во многом определяющей результат применения кодирования. Рассмотрены типовые, пригодные для программной реализации, алгоритмы декодирования кодов с малой плотностью проверок на четность — алгоритм с инвертированием бита (BF от англ. Bit Flip; с жесткими решениями) и ал-

горитм распространения доверия (BP от англ. Belief Propagation; с мягкими решениями) и его логарифмическая версия (logBP). Приведены оценки эффективности алгоритмов для низкоплотностных кодов различной длины.

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

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

1) математическое обеспечение универсальных САПР, ориентированных на решение широкого круга технических задач, часто является недостаточно полным для решения специфических задач;

2) универсальные средства зачастую оказываются недостаточно оптимизированными, уступая в производительности «ручной» пользовательской реализации;

3) прямое использование кода программ моделирования или их фрагментов в большинстве случаев затруднительно;

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

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

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

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

Отдельно рассмотрена модель источника помех и его главный элемент - генератор псевдослучайных чисел, качество которого определяет адекватность получаемых результатов. Предложена программная реализация модели двоичного симметричного канала с аддитивным белым гауссовским шумом, обеспечивающая за счет использования генератора псевдослучайных чисел с повышенным периодом достаточную для практики проектирования кодеков точность и высокую производительность. Проведена экспериментальная сравнительная оценка характеристик модели источника помех с ГПСЧ с повышенным периодом (263) по отношению к известным реализациям с применением стандартного для среды Visual С++ ГПСЧ rand (период 232). Модель источника помех с ГПСЧ с повышенным периодом и использованием преобразования Бокса-Мюллера показывает лучшие результаты, близкие к представленным в работах Р. Морелос-Сарагоса.

Для обеспечения статистической устойчивости получаемых результатов и определения необходимого количества циклов вычислений использовано выражение, предлагаемое в работах Б.В. Матвеева. Выражение определяет требуемый объем выборки N, при этом ожидаемая вероятность битовой ошибки Р* входит в относительный интервал 5 с доверительной вероятностью р. Для удобства программной реализации, вместо таблиц вычисления нормальной квантилыюй функции Ф"1 (функции обратной нормальной функции распределения) использован

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

В третьей главе обоснован выбор целевой аппаратной платформы и среды разработки средств моделирования низкоплотностных кодеков. Рассмотрена параллельная архитектура декодера по алгоритму распространения доверия и сделан вывод о возможности ее реализации в массивно-параллельной среде. Показано, что такие вычисления можно выполнять с помощью гетерогенной ЭВМ с графическим ускорителем (адаптером). Рассмотрена условная архитектура центрального процессора по отношению к графическому процессору. Как удобная для выполнения вычислений общего назначения на ГП применена открытая аппаратно-независимая среда OpenCL (от англ. Open Computing Language — открытый язык вычислений), для взаимодействия с которой использована среда разработки Visual Studio 2010.

Модифицирована известная схема параллельных вычислений для декодера низкоплотностного (N,J,K) кода по алгоритму распространения доверия: применение массивно-параллельных вычислителей позволяет дополнительно использовать М*К, M=N"xJ/K процессорных элементов на первом этапе алгоритма и N*J процессорных элементов на втором этапе. Изменению подверглись блоки обработки сообщений от кодовых вершин к проверочными от проверочных — к кодовым.

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

Для определения размеров рабочих групп ГП разработаны соответствующие аналитические выражения.

Вычислительные эксперименты показали, что применение новой архитектуры с измененной схемой параллельных вычислений вместо известной полнопараллельной обеспечивает увеличение производительности для кодов (96,3,6)...(9972,3,6) в среднем в 1,85 раза.

Рассмотрена проблема снижения производительности вычислений вследствие коммуникационных взаимодействий уровней ЦП — ГП. Для ее'решения предложено перенести расчеты для модели источника помех на процессорные элементы ГП и, соответственно, использовать параллельный ГПСЧ. Разработана архитектура параллельной реализации модели источника помех, пригодная для переноса расчетов на ГП.

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

Вычислительные эксперименты показали, что применение параллельного ГПСЧ с реализацией на уровне ГП обеспечивает прирост производительности до 30%; ' • ■

Проанализированы ограничения, связанные со случайным доступом к памяти графического ускорителя и высокой латентности ее глобальных разделов. Предложено минимизировать число обращений в первую очередь к медленной глобальной и во вторую — к локальной памяти, а также рекомендовано применять кэширование. Вычислительные эксперименты показали,- что применение кэширования для кодов длиной-96^.9972 обеспечивает прирост .производительности в среднем до 11 %.

Приведено описание разработанной методики моделирования низкоплотно-стных кодеков в однопроцессорных гетерогенных системах. Новая методика предусматривает процедуру предварительной оценки производительности вычислений на ГП и ЦП и позволяет повысить производительность вычислений за счет повышения нагрузки на ЦП. Установлено, что эффективность применения предложенной методики зависит от длины кода и аппаратных характеристик вычислителей. Вычислительные эксперименты показали, что наибольший положительный эффект от применения данной методики характерен для кодов длиной (96...3000), причем прирост производительности при малых значениях длины (до 273) достигает 80-41 % и устанавливается на уровне 21 % для кодов большей длины.

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

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

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

Рассмотрены особенности оптимизации системы помехоустойчивого низ-

t

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

В экспериментальных исследованиях использовались ЦП Intel Core 2 Duo Е8400 (ядер - 2, с частотой 3,6 ГГЦ); ГП AMD Radeon HD 5770 (процессор Juniper (R800), 800 потоковых процессоров с частотой 850 МГц). Полученные результаты ' позволили сделать вывод, что при весьма высоких требованиях к вычислительным ресурсам для получения объема выборки, достаточного для принятия решения в течение приемлемого по срокам проектирования времени, разработанные в диссертации средства повышенной производительности дают наибольший положительный эффект по сравнению с традиционными.

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

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

1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ПОМЕХОУСТОЙЧИВОГО

КОДИРОВАНИЯ

1.1 Обзор и классификация помехоустойчивых кодов

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

Список литературы диссертационного исследования кандидат наук Науменко, Юрий Сергеевич, 2014 год

СПИСОК ЛИТЕРАТУРЫ

1. Бараш Л.Ю. Генерация случайных чисел и параллельных потоков случайных чисел для расчетов Монте-Карло. / Л.Ю. Бараш, Л.Н. Щур // Моделирование и анализ информационных систем. Т. 19, № 2. 2012. С. 145-162.

2. Бараш Л.Ю. О генерации параллельных потоков псевдослучайных чисел. / Л.Ю. Бараш, Л.Н. Щур // Программная инженерия. № 1. 2013. С. 24-32.

3. Баркалов К.А. Методы параллельных вычислений. Н. Новгород: Изд-во Нижегородского госуниверситета им. Н.И. Лобачевского, 2011. 124 с.

4. Башкиров A.B. Преимущество параллельных алгоритмов цифровой обработки сигналов над последовательными алгоритмами при реализации на ПЛИС /

A.B. Башкиров, A.B. Муратов // Вестник Воронежского государственного технического университета, том 8, N1. Воронеж. 2012. С. 89-92.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки. Перевод с англ.: И.И. Грушко, В.М. Блиновский. Под редакцией: К.Ш. Зигангирова М.: Мир, 1986.576 с.' . . : '

6. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. 448 е., ил.

7. Боресков A.B. Основы работы с технологией CUDA. / A.B. Боресков, A.A. Харламов // М.: ДМК Пресс, 2010. 232 е.: ил.

8. Быков, В.В. Цифровое моделирование в статистической радиотехнике /В.

B. Быков. М.: Сов. Радио, 1971. 328 с.

9. Варгаузин В.А. Вблизи границы Шеннона // ТелеМультиМедиа. 2005, №3, С. 3-10.

10. Васильев К.К. Теория электрической связи: учебное пособие / под общ. ред. К.К. Васильева. / К.К. Васильев, В.А. Глушков, A.B. Дормидонтов, А.Г. Не-стеренко// Ульяновск: УлГТУ, 2008. 452 с.

11. Васильев К.К. Математическое моделирование систем связи : учебное пособие / К.К. Васильев, М.Н. Служивый // 2-изд., перераб. и доп. Ульяновск : УлГТУ, 2010. 170 с.

12. Вентцель Е.С. Теория вероятностей: учебник для втузов/ Е.С. Вентцель. 8-е изд., перераб. и доп. М. : Физматлит, 1999. 576 с.

И.Вишневский В.М. Энциклопедия WiMAX. Путь к 4G. / В.М. Вишневский, СЛ. Портной, И.В. Шнхнович // Москва: Техносфера, 2009. 472 с.

14. Воробьев К.А. Методы построения и декодирования недвоичных низко-плотностных кодов//Теория и практика системного анализа. 2010. т. II. С. 96-102.

15. Гаранин М.В. Системы и сети передачи информации: Учебное пособие для вузов / М.В. Гаранин, В.И. Журавлев, C.B. Кунегин. М.: Радио и связь, 2001. 336 с: ил.

16. Дьяконов В. П. MATLAB6.5 SP1/7.0 + Simulink5/6: Основы применения / В. П. Дьяконов. М.: Солон-Пресс, 2005. 800 с.

17. Жмуров A.A. Эффективные генераторы псевдослучайных чисел при молекулярном моделировании на видеокартах / A.A. Жмуров, В.А. Варсегов, C.B. Трифонов, Я.А. Холодов, A.C. Холодов // Компьютерные исследования и моделирование. 2011. Т. 3. № 3. С. 287-308. . . , " • .

18. Золотарев В.В.' Обзор исследований и разработок методов помехоустойчивого кодирования (по состоянию на 2005 год). / B.BI Золотарев,' Г.В. Овечкин // URL: http://www.mtdbest.ru/articles/obzor_po_kodir2.pdf.

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

20. Золотарев В.В. Сложность реализации эффективных методов декодирования помехоустойчивых кодов / В.В. Золотарев, Г.В. Овечкин // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Тез. докл. 12-й Междунар. науч.-техн. конф. Рязань: РГРТА, 2004. С. 12-14

21. Иванов Иванов И.В. Теория информационных процессов систем: учебное пособие / И.В. Иванов. Белгород: Изд-во БГТУ, 2007. 156 с.

22. Кларк Дж. мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи / Пер. с англ. под ред. Б.С. Цыбакова. М.: Радио и связь, 1987. 392с.

23. Комашинский В.И. Системы подвижной радиосвязи с пакетной передачей информации. Основы моделирования / В.И. Комашинский, A.B. Максимов. М.: Горячая линия-Телеком, 2007. 176 с. ' •

24. Кукунин Д.С. Построение каскадных кодов на основе Боуза-Чоудхури-Хоквингема и Рида-Соломона. / Д.С. Кукунин, М.С. Новодворский, В.М. Охорзин // СПб, ГУТ им. проф. М.А. Бонч-Бруевича, 2004. 58 с.

25. Матвеев Б.В. Основы корректирующего кодирования: теория и лабораторный практикум: учеб. пособие для вузов / Б.В. Матвеев. Воронеж: ФГБОУ ВПО «Воронежский государственный технический университет», 2012. 216 с.

26. Месси Дж. Пороговое декодирование / Пер. с англ. Ю.Л. Сагаловича

I

под ред. Э.Л. Блоха. М.: Мир, 1966. 208 с.

27. Морелос-Сарагосса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. / Р.Морелос-Сарагосса. М.:Техносфера, 2005. 320 с. Коды программ доступны на сайте http://the-art-of-ecc.com.

28. Науменко Ю.С. Архитектурные особенности графических процессоров семейства Radeon и их применение в сфере ресурсоемкого моделирования помехоустойчивых кодеков. 7 Ю.С. Науменко, A.B. Башкиров, A.M. Белицкий, А.И. Климов, A.C. Самодуров, В.М. Питолин // Радиотехника. 2014. №11. С. 15-18.

29. Науменко Ю.С. Влияние характеристик используемых в моделировании генераторов шума на качество оценки параметров помехоустойчивых кодеков. / Ю.С. Науменко, A.B. Башкиров, А.И. Климов, Л.Н. Короткое // Радиотехника. 2014. № 3. С. 14-18.

30. Науменко Ю.С. Возможности недвоичного применения блочных и сверточных кодов с исправлением ошибок. / Ю.С. Науменко, A.B. Башкиров, Л.Н. Коротков // Радиотехника. 2014. № 3. С. 59-61.

31. Науменко Ю.С. Исследование влияния характеристик цифровых генераторов шума на результаты оценки параметров помехоустойчивых кодеков. / Ю.С. Науменко, A.B. Башкиров // Охрана, безопасность, связь — 2013: материалы Междунар. научн.-практ. конференции. 4.1. Воронеж: Воронежский институт Министерства внутренних дел России, 2014. С. 49-51.

32. Науменко Ю.С. Массивные параллельные вычисления в гетерогенных системах при моделировании низкоплотносных кодеков.. / Ю.С. Науменко // Радиотехника. 2014. № 6. С. 43-46.

33. Науменко Ю.С. Недвоичные низкоплотностные коды: алгоритмы декодирования и их вычислительная сложность. / Ю.С. Науменко, A.B. Башкиров, А.И. Климов // Пензенский государственный университет // Труды международного симпозиума Надежность и качество. 2013. Т. 2. № 1-1. С. 19.

34. Науменко Ю.С. Обзор методов турбо-кодирования в контексте сложности их аппаратной реализации. / Ю.С. Науменко, A.B. Башкиров // Радиотехника. 2012. № 8. С. 70-74.

35. Науменко Ю.С. Обзор основных технологий, реализующих эффективные методы по-мехоустойчивого кодирования, нечувствительных к задержке сигнала. / Ю.С. Науменко, A.B. Башкиров, A.M. Белицкий, А.И. Климов, A.B. Муратов//Радиотехника. 2013. № 12. С. 30-33.

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

« ' ' ', ' . * • ' . ь • ,, , '

сигнала. / Ю.С. Науменко, A.B. Башкиров // Радиотехника. 2013. № З.С. 89-92. •

37. Науменко Ю.С. Особенности обеспечения производительности вычислений при моделировании помехоустойчивых низкоплотностных кодеков в гетерогенных системах / Ю.С. Науменко // Системные проблемы надежно-сти, качества, компьютерного моделирования, информационных и электронных технологий в инновационных проектах (ИННОВАТИКА—2014): материалы междунар. конф., российской научной школы и форума. М. 2014. С. 105-107.

38. Науменко Ю.С. Перспективы моделирования параметров алгоритмов помехоустойчивого кодирования с высокой степенью параллелизма при помощи аппаратной платформы на базе GPU. / Ю.С. Науменко, A.B. Башкиров, А.И. Климов, A.B. Муратов, B.C. Цымбалюк // Радиотехника. 2013. № 12. С. 26-29.

39. Науменко Ю.С. Построение алгоритмов верификации функциональных моделей декодеров. / A.B. Башкиров, A.B. Муратов, Ю.С. Науменко, A.B. Ситников. // Радиотехника. 2014. № 3. С. 72-76.

I I

123

40. Науменко Ю.С. Проблемы моделирования помехоустойчивых кодеков в гетерогенных системах. / Ю.С. Науменко // Радиотехника. 2014. № 3. С. 80-82.

41. Науменко Ю.С. Современные методы декодирования недвоичных кодов с малой плотностью проверок на четность: краткий обзор и сравнение. / Ю.С. Науменко, A.B. Башкиров // Современные проблемы радиоэлектроники: труды всероссийской науч.-техн. конф. Красноярск. 2013. С. 414-416.

42. Науменко Ю.С. Среда ускоренного моделирования помехоустойчивых низкоплотностных кодеков в гетерогенных вычислительных системах. / Ю.С. Науменко // Научно-техническая конференция молодых ученых и специалистов Воронежской области в сфере промышленности и высоких технологий. Научная конференция студентов, аспирантов и молодых ученых, 16-17 апреля 2014 г. Сб. докладов. Воронеж: Воронежский ЦНТИ — филиал ФГБУ «РЭА» Минэнерго РФ, 2014. С. 163-166.

43. Науменко Ю.С. Стандарты применения кодов с малой плотностью проверок на четность / Ю.С. Науменко, A.B. Башкиров // Современные проблемы радиоэлектроники: труды всероссийской науч.-техн. конф. Красноярск. 2013. С. 420-421.

44. Никитин Г.И. Основы кодирования сообщений в системах связи: Методические указания к выполнению лабораторных работ N 1-4. СПб.: ГУАП, 2004. 136 с.

45. Никитин Г.И. Помехоустойчивые циклические коды: Учебное пособие. СПб.: ГУАП, 2003. 33 с.

46. Никитин Г.И. Сверточные коды: Учеб. пособие/ СПбГУАП. СПб, 2001. 80 с: ил.

47. Сагалович Ю.Л. Введение в алгебраические коды: Учебное пособие. М.: МФТИ, 2007. 260 с.

48. Савинков А.Ю. Автоматизация проектирования систем цифровой обработки сигнала на основе интегрированной среды имитационного моделирования и оптимизации : Дис. ... д-ра техн. наук : 05.13.12 Воронеж, 2006 270 с. РГБ ОД, 71:06-5/444

49. Сизиков B.C. Устойчивые методы обработки результатов измерений: учебное пособие / B.C. Сизиков. СПб. : СпецЛит, 1999. 240 с.

50. Тихонов В.И. Статистический анализ и синтез радиотехнических устройств и систем. / В.И. Тихонов, В.Н. Харисов // М.: Радио и связь, 1991. 608 с.

51. Уэйкерли Д. Проектирование цифровых устройств Том I. М.: Постмар-кет. 2002. 1088 е., ил.

52. Шнайер, Б., Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С "Триумф", 2002. 816 с.

53. Andrews К., Dolinar S., Thorpe J. Encoders for Block-Circulant LDPC Codes., ISIT (Adelaide, Australia), Sept 4-9, 2005.

54. Barnault L., Declercq D. "Fast Decoding Algorithm for LDPC over GF(2q)," The Proc. 2003 Inform. Theory Workshop, Paris, France, pp. 70-73, Mar. 2003.

55. Bauke H., Mertens S. Random Numbers for Large Scale Distributed Monte Carlo Simulations. Physical Review E, vol. 75, nr. 6, article 066701 (2007)

56. Bauke H. Tina's Random Number Generator Library. Version 4.17. August 5, 2014.'URL http://numbercrunch.de/trng/ / ,

57. Berrou C., Glavieux A. and Thitimajshima P., «Near Shannon Limit Error-Correcting Coding and Decoding Turbo-Codes» Proc 1993 IEEE Int Conf Comm (ICC'93), pp 1064-1070, Geneve, Switzerland, May 1993

58. Bradley Т., Toit J., Giles M., Tong R., Woodhams P. Parallelisation techniques for random number generators. GPU Computing Gems, Volume 1, Morgan Kaufmann, 2010.

59. Chang C., Chang Y., Huang M., Huang B. Accelerating Regular LDPC Code Decoders on GPUs. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 4, no. 3, September, 2011.

60. Declercq D., Fossorier M., "Decoding Algorithms for Nonbinary LDPC Codes over GF(q)," IEEE Trans, on Commun., vol. 55(4), pp. 633-643, April 2007.

61. Declercq D., Fossorier M., Poulliat C. "Design of regular (2,dc)-LDPC codes over GF(q) using their binary images", in IEEE Trans. Commun., vol. 56(10), pp. 1626 - 1635, October 2008.

62. Declercq D. Regular ultra-sparse graphs and related non-binary LDPC codes. URL: http://perso-etis.ensea.fr/~declercq/graphs.php

63. Elias P., «Error-Free Coding, «IRE Trans, vol PGIT-4, pp 29-37, 1954

64. ETSI TS 102 831 Vl.2.1 (2012-08) Digital Video Broadcasting (DVB-T2); RTS/JTC-DVB-316 URL:

http://www.etsi.Org/deliver/etsi_ts/l 02800_102899/102831/01.02.0 l_60/ts_l 02831 vO 1 0201p.pdf

65. ETSI EN 302 307-2 VI.1.1 (2014-10) Digital Video Broadcasting (DVB-S2); DEN/JTC-DVB-341-2 URL:

http://www.etsi.org/deliver/etsi_en/302300_302399/30230702/01.01.01_20/en_302307 02v010101a.pdf

66. Falcao G., Sousa L., Silva V. How GPUs can outperform ASICs for fast LDPC decoding. ACM, p. 10, 2009.

67. Falcao G., Sousa L., Silva V. Massively LDPC decoding on multicore architectures. IEEE Trans. Parallel Distrib. Syst., vol. 22, no. 2, pp. 309-322, Feb. 2011.

" 68. Fossorier M.P.C., Mihaljevic M., Imai H. 1999. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation. IEEE Trans. Commun. 47, 5, 673-680.

69. Gallager R.G. "Low Density Parity Check Codes". - Cambridge:M.I.T. Press, 1963.-P. 90.

70. Gallager R. G., «Low-Density Parity-Check Codes, «IRE Trans Info Theory, vol 8, no 1, pp 21-28, Jan 1962

71. Giles, M. Approximating the erfinv function. In: Hwu W.W. GPU Computing Gems. Volume 2, Burlington: Morgan Kaufman., pp 109-116, 2011

72. Gradshteyn I, Ryzhik I. Table of integrals, series and products. US: Academic Press Inc.; 1966.

73. Guilloud F., Boutillon E., Tousch J., Danger J.L. "Generic description and synthesis of LDPC decoder", IEEE Transactions On Communications, IEEE Transactions on Communications, Vol. 55, n°l 1, pp 2084 - 2091, nov. 2007.

74. Hanzo L., Liew T. H., Yeap B. L. Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Wireless Channels. Department of Electronics and Computer Science, University of Southampton, UK. -2002. - 764 c.

75. IEEE 802.3: ETHERNET http://standards.ieee.Org/about/get/802/802.3.htmI

76. IEEE 802.11: Wireless LANs.

URL: http://standards.ieee.Org/about/get/802/802.l 1.html

77. IEEE 802.15: WIRELESS PERSONAL AREA NETWORKS (PANs) http://standards.ieee.org/about/get/802/802.15.html

78. IEEE 802.16: BROADBAND WIRELESS METROPOLITAN AREA NETWORKS (MANs) httpi//stand^

79. IEEE 802.22: WIRELESS REGIONAL AREA NETWORKS http://standards.ieee.org/about/get/802/802.22.html

80. Johnson S.J., Weller S.R. "A family of irregular LDPC codes with low encoding complexity", IEEE Commun. Lett., vol. 7, no. 2, pp.79-81 2003

81. Kang S., Moon J. Parallel,LDPC Decoder Implementation on GPU based on Unbalanced Memory Coalescing, in Proceedings of the IEEE International Conference on Communications (ICC), 2012.

82. Kobayashi K. Shibuya T. "Generalization of Lu's linear time encoding algorithm for LDPC codes", Information Theory and its Applications (ISITA), 2012 International Symposium on, On page(s): 16-20, Volume: Issue:, 28-31 Oct. 2012

83. Khronos OpenCL Working Group. "The OpenCL Specification". Version: 2.0. Document Revision: 19. 11/14/2013. 283 p.

84. LDPC Decoder Applications URL: http://www.ldpc-decoder.com/en/Idpc-decoder-applications

85. MacKay D., Davey M., Lafferty J. Alist format. http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html

86. MacKay D. Encyclopedia of Sparse Graph Codes: Database, under construction, containing performance results for many sparse graph codes; also includes some parity check matrices, http://www.inference.phy.cam.ac.uk/mackav/codes/data.html

127 '

■ ■ ■ < *

87. MacKay, D. J. C., and M. C. Davey. 2000. "Evaluation of Gallager Codes for Short BlockLength and High Rate Applications." In Codes, Systems and Graphical

Models, edited by B. Marcus and J. Rosenthal, Volume 123 of IMA Volumes in Ma-

(

thematics and its Applications, 113-130. New York: Springer.

88. MacKay, D. J. C. and Neal, R. M. (1995) "Good codes based on very sparse matrices", in C. Boyd (editor) Cryptography and Coding: 5th IAM Conference, Lecture Notes in Computer Science No. 1025, pp. 100-111.

89. Manssen M., Weigel M., Hartmann A. Random number generators for massively parallel simulations on GPU. Eur. Phys. J. Special Topics, Vol. 210 (2012), pp. 53-53

90. MasseyJ. L., Threshold Decoding, MIT Press, 1963

91. Neal R.M. Faster encoding for low-density parity check codes using sparse matrix methods", IMA workshop on Codes, Systems and Graphical Models, Minneapolis, 1999

92. Neal R.M. Monte Carlo Decoding of LDPC Codes. University of Toronto http://www.cs.utoronto.ca/radford URL: '.. • <. ' http://www.cs.toronto.edu/~radford/ftp/mcdecode-talk.pdf

93. Nvidia CUDA C Programming Guide. Design Guide. PG-02829-001_v6.5 | www.nvidia.com.August2014.241 p.

94. Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems : Networks of Plausible Inference. San Mateo: CA : Morgan Kaufmann..

95. Perez J.M., Andrews K. Low-Density Parity-Check Code Deign Techniques to Simplify Encoding. IPN Progress Report 42-171, Nov. 2007.

96. Richardson T.J., Urbanke R.L. Efficient encoding of low-density parity-check codes. IEEE Transactions on Information Theory 47(2): 638-656 (2001)

97. Seghers J. On the Free Distance of TURBO Codes and Related Product Codes // Final Report, Diploma Project SS 1995, Number 6613, (Swiss Federal Institute of Technology Zurich, Switzerland). -1995. - August.

98. Shams B. «Les codes LDPC non-binaire du nouvelle generation», Digital Solutions for Innovative IPs Team - STMicroelectronics Crolles. pp 52-53, 08-12-2010.

99. Shibuya T. "Block-triangularization of parity check matrices for efficient encoding of linear codes", Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pp 533-537.

100. Strecok A.J. On the calculation of the inverse of the error function. Mathematics of Computation, 22(101): 144-158, 1968.

101. Tanner R.M., Michael R., Sridhara D., Fuja T. A Class of Group-Structured LDPC Codes. 2001.

102. Thomas D.B. The MWC64X random number generator. http://www.doc.ic.ac.uk/~dtl0/research/rngs-gpu-mwc64x.html, 2011. URL http://cas.ee.ic.ac.uk/people/dtl0/research/rngs-gpu-mwc64x.html.

103. Wang S., Cheng S., Wu Q. "A Parallel Decoding Algorithm of LDPC Codes Using CUDA," Asilomar Conference on Signals, Systems, and Computers, pp. 171-175, Pacific Grove, CA, October 2008.

104. Wang G., Wu M., Sun Y., Cavallaro J.R. GPU Accelerated Scalable Parallel Decoding of LDPC Codes. 45th Asilomar Conference on Signals, Systems, and Computers, 2011

105. Wang G., Wu M., Sun Y., Cavallaro, J.R.: A massively parallel implementation of QC-LDPC decoder on GPU. ;Symposium on Application Specific Processors -SASP(2011)82-85

106. Zhang T, Parhi K. Joint (3;k)-regular LDPC code and decoder/encoder design. IEEE Transactions on Signal Processing, 2004, 52(4): 1065-1079.