Содержание к диссертации
Введение
1 Обзор существующих методов помехоустойчивого кодирования 16
1.1 Обзор и классификация помехоустойчивых кодов 16
1.2 Низкоплотностные корректирующие коды
1.2.1 Декодирование по алгоритму с инвертированием бита 27
1.2.2 Декодирование по алгоритму распространения доверия 31
1.3 Выводы 40
2 Моделирование корректирующих кодеков телекоммуникационных устройств в гетерогенных вычислительных системах 42
2.1 Моделирование источника сигнала 42
2.2 Моделирование источника помех 44
2.3 Моделирование процесса коррекции ошибок в канале связи 56
2.3.1 Оценка основных параметров, характеризующих качество системы кодирования 56
2.3.2 Обеспечение статистической устойчивости оценок параметров 59
2.4 Выводы 62
3 Программная реализация моделей телекоммуникационных систем с корректирующим низкоплотностным кодированием с использованием массивно-параллельных вычислений 64
3.1 Выбор целевой аппаратной платформы и среды разработки 64
3.2 Особенности обеспечения производительности вычислений в гетерогенных системах 70
3.2.1 Вопросы коммуникационных взаимодействий уровней хост — вычислитель 70
3.2.2 Вопросы случайного доступа и высокой латентности глобальных разделов памяти графического ускорителя 79
3.3 Схема параллельных вычислений, применяемая при декодировании 81
3.4 Методика моделирования низкоплотностных кодеков в однопроцессорных гетерогенных вычислительных системах 88
3.5 Выводы 94
4 Программная реализация средств моделирования низкоплотностных кодеков 96
4.1 Архитектура программного обеспечения 96
4.1.1 Комплекс библиотек моделирования 96
4.1.2 Тестовая моделирующая оболочка 100
4.2 Моделирование помехоустойчивых систем связи с низкоплотностным кодеком 106
4.3 Производительность вычислений в гетерогенных системах различной конфигурации 109
4.4 Выводы 115
Заключение 117
Список литературы
- Декодирование по алгоритму с инвертированием бита
- Моделирование процесса коррекции ошибок в канале связи
- Особенности обеспечения производительности вычислений в гетерогенных системах
- Моделирование помехоустойчивых систем связи с низкоплотностным кодеком
Декодирование по алгоритму с инвертированием бита
В процессе разработки системы связи, содержащей подсистему помехоустойчивого кодирования, часто приходится выполнять оптимизацию и, соответственно, моделирование этой подсистемы на ЭВМ. Во многих случаях решение задачи подбора эффективной низкоплотностной проверочной матрицы требует проведения большого числа опытов с вариацией параметров и поэтому сопряжено со значительными затратами времени. Кроме того, при моделировании почти полностью занимается вычислительный ресурс ЭВМ, что тоже может рассматриваться как фактор увеличения нежелательных совокупных затрат на разработку. Наиболее часто для моделирования используется программный пакет MATLAB (от англ. Matrix Laboratory), являющийся мощным инструментом для инженерных расчетов. Вместе с тем, универсальность данного пакета прикладных программ и его ориентация на решение типовых задач зачастую ограничивает его применимость для решения узкоспециализированных задач. Этот недостаток присущ множеству универсальных САПР и обуславливает их непригодность для решения специальных задач по следующим причинам [48]: 1) математическое обеспечение универсальных САПР, ориентированных на решение широкого круга технических задач, часто является недостаточно полным для решения специфических задач; 2) универсальные средства зачастую оказываются недостаточно оптимизированными, уступая в производительности «ручной» пользовательской реализации; 3) прямое использование кода программ моделирования или их фрагментов в большинстве случаев затруднительно; 4) программные средства универсальных САПР имеют весьма высокую стоимость, что существенно ограничивает их доступность и ставит под вопрос целесообразность использования для решения узкоспециальных задач.
В свою очередь, развитие тематики гетерогенных вычислений позволяет говорить о перспективности их применения для ускорения расчетов. В данном смысле ЭВМ, обладающая дополнительным вычислительным ресурсом (кроме ресурса центрального процессора), фактически может рассматриваться как гетерогенная вычислительная система. Примером дополнительного ресурса может быть ресурс графического процессора, отличающегося от центрального процессора значительным числом вычислительных ядер. С учетом допустимости применения параллельных вычислений при декодировании низкоплотностных кодов, использование гетерогенных вычислений для моделирования низкоплотностных кодеков представляется весьма перспективным. В связи с этим особую актуальность приобретает задача разработки инструментальных средств, способных обеспечить моделирование системы помехоустойчивого низкоплотностного кодирования с учетом высоких требований к уровню производительности вычислений.
Источник сообщений — это устройство, осуществляющее выбор сообщений из ансамбля сообщений [11]. В общем случае источником сообщений может быть датчик, микропроцессорное устройство и т. п. Сообщение может поступать в форме последовательности кодовых знаков. С математической точки зрения, источник информации характеризуется множеством возможных сообщений и вероятностной мерой, заданной на этом множестве. Так как интерес представляют источники, изменяющие свое состояние с течением времени, источник сообщений можно рассматривать как случайный процесс с реализациями X(t).
Передаваемое сообщение отражается сигналом — изменяющимся во времени физическим процессом. В зависимости от принимаемых аргументом (время t) и уровнем сигнала значений, сигналы могут быть нескольких типов.
Непрерывные случайные сигналы также называются непрерывными случайными процессами. Непрерывный сигнал по уровню может принимать любое значение из некоторого заданного диапазона и определен для любого промежутка времени. Наиболее часто физические процессы непрерывны и порождаемые ими сигналы аналогичны порождающим процессам, т.е. являются аналоговыми.
Непрерывный сигнал может быть заменен дискретным путем квантования по времени и уровню с любой заранее заданной точностью. Дискретизация по времени основана на теореме Котельникова (в англоязычной литературе — теорема Найквиста — Шеннона, или теорема отсчетов), в соответствии с которой аналоговый сигнал X(t) может быть восстановлен однозначно и без потерь по своим отсчетам, взятым с частотой, большей или равной удвоенной верхней частоте FB [Гц], если сигнал X(t) имеет конечный (ограниченный по ширине) спектр [11]. Дискретно непрерывные случайные сигналы, именуемые также дискретными по времени сигналами или непрерывными случайными последовательностями, являются процессами с дискретным временем. Дискретно непрерывный сигнал по уровню может принимать любое значение из некоторого заданного диапазона и определен лишь в отдельные моменты времени. В случае если интервал между соседними реализациями At одинаков, можно говорить о дискретизации сигнала с интервалом дискретизации At.
Дискретные по уровню или квантованные случайные сигналы являются дискретными случайными процессами. Квантованный сигнал по уровню может принимать только фиксированные значения из некоторого заданного диапазона и определен для любого промежутка времени. В случае если интервал Ах между разрешенными значениями уровней одинаков, можно говорить о квантовании сигнала с интервалом квантования Ах .
Дискретные по уровню и времени случайные сигналы называются дискретными случайными последовательностями. Дискретный по уровню и времени сигнал может принимать только фиксированные значения из некоторого заданного диапазона и определен лишь в отдельные разрешенные моменты времени.
Моделирование процесса коррекции ошибок в канале связи
Основной и часто применяемой моделью шума является модель аддитивного белого гауссовского шума (АБГШ, от англ. AWGN). Она предполагает, что значения амплитуды шума распределены нормально, спектральная плотность равномерна, а способ воздействия на сигнал — аддитивный. Кроме того, как упоминалось ранее, характеризуется дискретным входом, непрерывным выходом и переходными вероятностями (выражение 1.2). При этом в контексте рассмотрения представляющего непосредственный интерес в рамках данной работы блока — блока системы кодирования, или кодека (рисунок 1.1), имеющего дело с дискретными сообщениями, важно упомянуть часто используемую модель дискретного канала — двоичного симметричного канала (ДСК).
В общем случае характеристики дискретного канала зависят от непрерывного канала и структуры модулятора/демодулятора (модема). Дискретный канал определяется условной вероятностью P(yj \st) перехода из множества входных символов {Sj}, i = \,Ls в множество выходных символов {у,}, j = \,Ly и длительностью символов т, которая обычно одинакова для всех символов. Обычно Ly Ls, в частности более часто Ly=Ls. Принимаемая последовательность символов Y = (уь у2, ... , Уп) обычно представляется как сумма переданной последовательности S = (si, s2, ... , sn) и вектора ошибки Е = (еь е2, ... , еп), где под суммой подразумевают покомпонентное сложение векторов по модулю Ls. В случае двоичного канала, st = уи если ех= О и st Ф у І В противном случае. Модели отличаются распределением вектора Е.
В случае если et являются независимыми, канал является каналом без памяти. В случае если прием символа ег зависит от результата приема предыдущих символов, канал является каналом с памятью. В случае если вероятность возник 46 новения ошибок при приеме постоянна и не зависит от времени, считается, что канал стационарен [11].
При использовании двоичной модуляции и жестких решений демодулятора можно говорить о двоичном (бинарном) канале (рисунок 2.1). Представление сигнала двоичным кодом оправдано ввиду простоты технической реализации.
Для ДСК переходные вероятности соответствуют следующим соотношениям: Р(1\1) =Р(0\0) =1 р; Р(1\0) =Р(0\1) =р. Здесь р — средняя вероятность искажения символа. Для случая стационарного симметричного канала без памяти/? = P(et = 1); 1-р = P(et = 0). Кроме того, средняя вероятность искажения символа связана с отношением сигнал/шум согласно выражению [11, 19]:
Вероятность искажения символа в ДСК без кодирования соответствует вероятности битовой ошибки при бинарной фазовой манипуляции (двоичной фазовой манипуляции) в канале с аддитивным белым гауссовским шумом, которая при моделировании предполагает отображение символов [27]:
В случае если в выходном алфавите двоичного канала помимо символов 0 и 1 присутствует символ стирания — «?», канал можно назвать каналом без памяти со стиранием, появляющемся в случае невозможности принять решение демодулятором, что обычно применяется в телекоммуникационных системах с обратной связью при требовании повторной передачи сообщения. Данным способом достигается значительное повышение вероятности безошибочного приема за счет меньшей скорости информационного обмена.
В общем случае, когда входом и выходом канала являются L-ичные символы, принято рассматривать модель дискретного канала без памяти (ДКБП), графически представленную на рисунке 2.3.
ДКБП характеризуется тем, что выходной символ зависит лишь от текущего входного символа, а переходные вероятности представляют собой набор из LsLy условных вероятностей вида P(yt\Sj) = P(y=yi\s=Sj). Переходные вероятности постоянны и не зависят от времени и друг от друга.
При использовании модулятором набора из q ортогональных сигналов и принятии демодулятором жестких решений, можно говорить о частном случае ДКБП — дСК канале. В соответствии с [19]: вероятность ошибки на символ, определяется выражением Стоит кратко упомянуть модели дискретных каналов с памятью. Простейшей моделью данных каналов является Марковский канал, символы вектора ошибки которого образуют простую цепь Маркова, причем вероятность искажения символа зависит от результата приема предыдущего символа. Также стоит упомянуть модель канала с ошибками, группирующимися в пакеты ошибок. Такой эффект проявляется, если в непрерывном канале, составляющем дискретный канал, действуют импульсные помехи или замирания большой по сравнению со временем передачи символов длительностью. Такие каналы задаются условной вероятностью ошибочного приема пакета из к символов подряд [11].
Точность результатов моделирования определяются качеством (в смысле адекватности; уровня соответствия реальным процессам) используемых моделей, составляющих канал. Основной элемент модели, имитирующей помехи в канале — источник шума, построенный чаще всего на основе генератора псевдослучайных чисел (ГПСЧ). Видов ГПСЧ, в зависимости от решаемых задач, применяется значительное количество. Так, например, в работе [27] для моделирования канала с аддитивным белым гауссовым шумом (АБГШ) применялся стандартный для среды Visual C++ ГПСЧ — функция rand() из стандартной библиотеки cstdlib (stdlib.h — С Standard General Utilities Library).
Функция rand возвращает псевдослучайное целое в интервале от 0 до 32767. Для генерации используется линейный конгруэнтный метод [52]. Линейным конгруэнтным методом псевдослучайное число генерируется по формуле: Хп = (аХп_]+с) mod т. (2.2) Хо — значение, инициализирующее состояние генератора. Для функции rand коэффициенты выбраны: а = 214013, с = 2531011, т = 2, / — число бит в машинном слове, используемом для хранения X; I = 32. ГПСЧ rand возвращает старшие 15 бит (30..16), что связано с плохими статистическими показателями поведения младших бит. Период ГПСЧ, таким образом, оказывается 2 . Для получения более правдоподобных оценок предложено использовать один из вариантов ГПСЧ с большим периодом. Был выбран ГПСЧ MWC64X, что связано с удобной реализацией для среды OpenCL [102]. Для генерации используется метод, предложенный G. Marsaglia (multiply-with-carry (MWC) — умножение с переносом). В общем случае, псевдослучайное число генерируется по формуле:
Особенности обеспечения производительности вычислений в гетерогенных системах
Этап а) (рисунок 3.1) соответствует первому шагу этапа обработки сообщений (этап 2.1 на схеме, данной на рисунке 1.7) алгоритма ВР. В результате каждой /-й проверочной вершиной (узлом типа 1 на графе) независимо вычисляется Kt значений Лд Ввиду независимости этих вычислений они могут производиться как последовательно для каждой вершины, друг за другом, так и сразу параллельно для всех М вершин. Аналогичная ситуация характерна и для второго шага этапа обработки сообщений (этап 2.2 на схеме, данной на рисунке 1.7) алгоритма ВР, схематично представленного на рисунке 3.1 б). На этом этапе каждой /-й кодовой
вершиной (узлом типа 2 на графе) независимо вычисляется Jt значений л . Эти
вычисления также могут быть произведены как последовательно, так и параллельно, сразу для N вершин. В зависимости от последовательных либо параллельных вычислений на этих этапах, декодер может быть построен по нескольким вариантам свойственной ему архитектуры. Нас главным образом будет интересовать параллельная архитектура, возлагающая значительные требования на количество необходимых вычисляющих элементов, но обладающая несомненными преимуществами в части скорости вычислений над последовательной реализацией [4]. Как будет показано далее, при достаточном размере проверочной матрицы (достаточном числе кодовых и проверочных узлов), достигаемый за счет параллелизма архитектуры временной выигрыш при декодировании будет достаточен, чтобы превзойти при моделировании последовательную реализацию с концентрацией вычислений на центральном процессоре ЭВМ. Обобщенная архитектура реализации параллельного декодера представлена на рисунке 3.2. ( Вход )
Наличие параллелизма открывает путь к использованию в вычислениях ресурсов графических процессоров (GPU, рисунок 3.3), которые, с одной стороны, прекрасно подходят для решения задач параллельных вычислений, а с другой,— массово распространены и фактически всегда находятся в составе графических ускорителей ЭВМ. Использование этих ресурсов позволяет рассматривать ЭВМ в качестве гетерогенной вычислительной системы с основным вычислительным устройством — ЦП и неосновным — ГП графического ускорителя [28, 38].
Термин GPU (от англ. Graphics Processing Unit) введен корпорацией Nvidia с целью акцентирования внимания на том, что графический ускоритель стал мощным программируемым устройством (процессором), пригодным для решения широкого круга задач, никак не связанных с графикойt фактически представляя собой SIMD-процессор (от англ. Single Instruction Multiple Data - параллельный процессор, способный одновременно выполнять одну и ту же операцию над многими данными). Современные ГП являются массивно-параллельными вычислительными устройствами с очень высоким быстродействием (свыше 1 терафлопс (от англ. FLoating-point Operations Per Second)) и большим объемом собственной памяти (DRAM) [7]. Динамика роста производительности и пропукной способности памяти ГП, в сравнении с аналогичным показателем для ЦП, по данным [93], представлена на рисунках 3.4 и 3.5 соответственно. GFLOP/s 5750
Динамика роста теоретической пропускной способности памяти процессоров Поддержка современными ГП возможности обработки текстур со значениями в форматах с плавающей точкой (16- и 32-битовые типы float вместо используемых ранее 8-битовых беззнаковых целых чисел) позволяет применять фрагментные процессоры для обработки больших массивов данных. Рассматривая возможность компьютерных вычислений при помощи графических процессоров, появление высокоуровневых языков для написания программ для ГП, таких как Cg, GLSL,HLSL и др. заметно облегчило создание программ, реализующих такие вычисления. Результатом этого стало возникновение GPGPU (от англ. General-Purpose computing on Graphics Processing Units — вычисления общего назначения на ГП) — техники использования ГП графического ускорителя для общих вычислений, которые обычно проводит ЦП. Фактически стало возможным использовать мощный параллельный процессор, способный обработать большой массив данных [7].
Таким образом, в качестве целевой аппаратной платформы рассматривается гетерогенная вычислительная система, содержащая в составе дополнительных вычислительных средств графический ускоритель.
Тематика вычислений на ГП ввиду перспективности результатов и их актуальности активно развивается, в том числе разработчиками графических карт, обеспечивающих пользователей средствами доступа к внутренним ресурсам карт, средами написания компьютерных программ для выполнения на ГП. Лидерами в области ПО, реализующем технику GPGPU, безусловно, являются AMD и Nvidia и их продукты OpenCL (от англ. Open Computing Language — открытый язык вычислений) и CUDA (от англ. Compute Unified Device Architecture — программно-аппаратная архитектура параллельных вычислений) соответственно. Лидирующую позицию с точки зрения производительности и стабильности занимает технология CUDA от Nvidia, однако эта программно-аппаратная архитектура ограничена использованием лишь аппаратных решений Nvidia. Использование CUDA обрекает на отсутствие аппаратной независимости, что в современных условиях является достаточно весомым фактором, заставляющим отказаться от использования данной технологии в пользу ее конкурента от AMD — OpenCL. OpenCL является полностью открытым стандартом реализации техники GPGPU, обеспечивающим написание кроссплатформенных (аппаратно-независимых) программ, исполняемых в гетерогенных системах.
Таким образом, в качестве среды разработки рассматривается OpenCL, при этом основным инструментом разработки выбран бесплатно предоставляемый продукт компании Microsoft — Visual Studio 2010 Express.
Моделирование помехоустойчивых систем связи с низкоплотностным кодеком
Рассмотрим процесс оптимизации системы помехоустойчивого кодирования с низкоплотностным кодеком. Типичной задачей является задача определения по результатам моделирования кода, обладающего лучшей корректирующей способностью. Очевидно, что большей помехоустойчивости удастся добиться при использовании кодов большей длины, кроме этого большей окажется и пропускная способность, так как для передачи одного и того же числа бит для кода большей длины потребуется меньше блоков, а значит и меньшее количество вспомогательных операций. Таким образом, решение по большей части будет определяться доступным для декодирования количеством вычислительных процессорных элементов.
Однако для кодов одинаковой длины решение оказывается неочевидным — уровень корректирующей способности будет определяться конфигурацией проверочной матрицы: количеством бит на строку и столбец, наличием в матрице циклов и размером этих циклов. Показателен пример моделирования кодов 4000.2000.3.243
Моделирование производилось в канале с АБГШ в диапазоне 0 - 2,5 дБ с интервалом в 0,25 дБ; верификация производилось по ожидаемому уровню вероятности битовой ошибки 10"5, с отклонением в 10 % с вероятностью 0,9, т.е. по каналу во всех случаях передавалось приблизительно одинаковое количество бит. Декодирование осуществлялось в 10 итераций по алгоритму ВР. В конфигурации вычислителя — GPU + параллельный ГПСЧ моделирование заняло: 4000.2000.3.243 — 164 с, 4000.2000.4.244 — 233 с, 8000.4000.3.483 — 123 с, 8000.4000.4.484 — 207 с, т.е. при декодировании кодов с N= 8000 удалось достичь большей пропускной способности. При этом в указанном диапазоне группа кодов с J= 3 оказалась более эффективной. Однако моделирование с верификаци-ей по ожидаемому уровню вероятности битовой ошибки 10" для кодов длиной
График зависимости BER-SNR для кодов (8000,3,6) и (8000,4,8) с верификацией по уровню вероятности битовой ошибки 10"
Таким образом, при SNR=2,625 дБ для системы помехоустойчивого кодиро-вания с требованием по значению вероятности битовой ошибки 10" оказывается выгодным использование кода (8000,3,6), однако для высоконадежной системы с требованием BER 10"7 выгодно использовать код (8000,4,8).
Отметим, что отношение производительностей вычислений, оцененное при помощи процедуры, описанной в п. 3.4, в сравнении с однопоточными последовательными вычислениями на ЦП оказывается не менее 14 раз для кода (8000,3,6) и 16 раз для кода (8000,4,8), т.е. в однопоточном режиме для построения графиков
Производительность вычислений, выполняемых разработанным программным обеспечением, оценивалась по временным затратам на решение одинаковых задач в различных конфигурациях вычислителей. В качестве основного вычислителя выступал ЦП — Intel Core 2 Duo Е8400 (ядер - 2, с частотой 3,6 ГГЦ) в одно-поточном и многопоточном режимах. Дополнительный вычислитель — ГП — AMD Radeon HD 5770 (процессор Juniper (R800), 800 потоковых процессоров с частотой 850 МГц).
Удалось добиться следующих результатов. Моделирование производилось для низкоплотностных кодов скоростью 0.5, длиной N= 96, 204, 504, 1008, 2640, 4000, 4896, 8000, 9972; J= 3, К = 6. При декодировании по алгоритму BF моделировался канал с АБГШ при уровне шума от 0 до 8.1 дБ с инкрементом в 0.9 дБ; 3408 кодовых слов декодировалось в 20 итераций. Время, потребовавшееся для расчетов в различной конфигурации вычислительного устройства, сведено в таблицу 4.1.
Для удобства восприятия результаты представлены графически на рисунке 4.7. Алгоритм BF, как упоминалось в п. 1.2.1.1, вычислительно не сложен, поэтому выигрыш, достигаемый за счет параллелизма (графики MWC, паралл. MWC), проявляется при больших значениях длины кода. Как следствие, существенную роль здесь играют проблемы коммуникационных взаимодействий уровней хост—графический процессор, поэтому в конфигурации вычислительного устройства с использованием ГП худшие результаты отражает график MWC: в данной конфигурации модель источника шума реализуется на уровне хоста. Наилучших результатов удалось добиться применением методики п. 3.4 (график GPU+CPU). В сравнении с вычислениями на ЦП в однопоточном режиме применение данной методики является выгодным независимо от длины кода. При длине кода 7V 1800, применение методики выгодно и по отношению к вычислениям на ЦП в многопоточном режиме. Относительный временной выигрыш вычислений в конфигурации GPU+CPU при декодировании по алгоритму BF отражен графиком, представленным на рисунке 4.8.
Иначе обстоит дело при декодировании по алгоритму распространения доверия. При декодировании по алгоритму ВР и logBP моделировался канал с АБГШ при уровне шума от 0.1 до 2.5 дБ с инкрементом в 0.25 дБ; 100 кодовых слов декодировалось в 10 итераций. Время, потребовавшееся для расчетов в различной конфигурации вычислительного устройства, сведено в таблицу 4.2. Конфигурации вычислительного устройства:
