Содержание к диссертации
Введение
ГЛАВА 1. Методика синтеза нового класса помехоустойчивых комбинированных полигауссовых алгоритмов многопользовательского приема сигналов в CDMAсистемах подвижной связи 16
1.1. Основные этапы перехода к посткорреляционным моделям представления случайных явлений 17
1.2. Обоснованность методологии и практического применения полигауссового подхода 21
1.3. Обоснованность методологии и технология многопользовательского детектирования 24
1.4. Методология синтеза алгоритмов многопользовательского детектирования в каналах с аддитивным белым гауссовым шумом 28
1.5. Анализ существующих параметров эффективности алгоритмов приема сигналов в CDMA системах подвижной связи
1.5.1. Параметры эффективности с точки зрения качества обслуживания (QoS) 31
1.5.2. Параметры эффективности алгоритмов многопользовательского детектирования 33
1.5.3. Системная емкость и помехоустойчивость как основные показатели эффективности CDMA систем связи
1.5.3.1. Системная емкость 38
1.5.3.2. Помехоустойчивость 42
1.6. Комплексный показатель эффективности как средство оценки качества
комбинированных квазиоптимальных алгоритмов многопользо
вательского приема сигналов 44
1.7. Методика синтеза нового класса помехоустойчивых комбинированных полигауссовых алгоритмов многопользовательского приема сигналов в CDMA системах подвижной связи 45
1.8. Основные результаты и краткие выводы по Главе 1 47
ГЛАВА 2. Базовые подходы к синтезу алгоритмов в комплексе негауссовских помех и алгоритмов многопользовательского детектирования 49
2.1.1. Вероятностное описание сигнально-помехового комплекса в рамках полигауссовых моделей для задачи оптимального полного разрешения сигналов 49
2.1.2. Обобщенная методология полигауссового синтеза квазиоптимальных алгоритмов
2.2. Квазиоптимальные решения полигауссовых алгоритмов приема сигналов 57
2.3. Сравнительный анализ алгоритмов многопользовательского детектирования в CDMA системах связи
2.3.1. Оптимальный многопользовательский детектор по критерию максимального правдоподобия 60
2.3.2. Декоррелятор 61
2.3.3. Детектор по минимуму СКО 62
2.3.4. Многопользовательский детектор на основе полиномного разложения 63
2.3.5. Субтрактивные многопользовательские детекторы 63
2.3.6. Нелинейный многопользовательский демодулятор на основе метода Чебышева 65
2.3.7. Алгоритмы многопользовательского детектирования на основе искусственного интеллекта 66
2.3.8. Корреляционные комбинированные решения с оценкой состояния канала 68
2.4. Основные результаты и краткие выводы по Главе 2 68
ГЛАВА 3. Синтез комбинированного полигауссова алгоритма многопользовательского приема случайного числа сигналов при действии внутрисистемных помех 70
3.1. Математическая модель системы связи DS-CDMA 72
3.2. Математическая модель MMSE-алгоритма 74
3.3. Синтез комбинированного ПГ-MMSE алгоритма
3.3.1. Вводимые допущения ПГ-MMSE алгоритма и конкретизация его параметров 81
3.3.2. Функциональная схема ПГ-MMSE алгоритма 83
3.3.3. Оценка условий представления негауссовских помех малым числом компонент вероятностной смеси 87
3.3.4. Блок схема ПГ-MMSE алгоритма 101
3.4. Основные результаты и краткие выводы по Главе 3 111
ГЛАВА 4. Техническая реализация и оценка комплексного показателя эффективности устройства многопользовательского приема сигналов 112
4.1. Мультипроцессорная реализация устройства, реализующего ПГ-MMSE алгоритм 112
4.1.1. Общее описание комбинированного устройства приема сигналов при действии внутрисистемных помех 113
4.1.2. Принцип работы комбинированного устройства приема сигналов при действии внутрисистемных помех 116
4.1.3. Обобщенные временные циклы работы устройства 121
4.2. Оценка комплексного показателя эффективности ПГ-MMSE алгоритма/устройства 124
4.2.1. Расчет общего числа выполняемых операций 125
4.2.2. Оценка асимптотической эффективности 137
4.2.3. Оценка вероятности ошибки 138
4.3. Основные результаты и краткие выводы по Главе 4 140
Заключение 142
Список использованных источников
- Анализ существующих параметров эффективности алгоритмов приема сигналов в CDMA системах подвижной связи
- Обобщенная методология полигауссового синтеза квазиоптимальных алгоритмов
- Алгоритмы многопользовательского детектирования на основе искусственного интеллекта
- Оценка комплексного показателя эффективности ПГ-MMSE алгоритма/устройства
Введение к работе
Актуальность темы исследований. Современный этап развития систем связи с подвижными объектами (ССПО) характеризуется высокой потребностью по внедрению новых алгоритмических и технических решений, направленных на повышение эффективности передачи информации по выделенным частотным каналам связи.
Сложный и многообразный комплекс помех, характерный для условий работы современных ССПО с кодовым разделением каналов, приводит к возникновению негауссовских случайных процессов на входе приемных устройств и, как следствие к ограничению помехоустойчивости и системной емкости.
Анализ выполненных исследований по данной тематике показывает, что на сегодняшний день существует достаточно большое число обобщенных аналитических и технических решений полигауссовых приемников, реализующих методы дифференцированного доступа абонентов для детерминированной, квазидетерминированой и случайной моделей сигналов, обеспечивающих эффективную компенсацию негауссовских помех. Однако эти решения обладают высокой вычислительной сложностью и в большинстве практических приложений технически не реализуемы. За последние десятилетия также разработано достаточное число оригинальных решений многопользовательских приемников, обеспечивающих компенсацию помех, но только в гауссовом шуме.
В этой связи актуальным является развитие и разработка новых методов дифференцированного доступа абонентов к ресурсам систем и устройств телекоммуникаций, а также разработка новых селекторов, обеспечивающих высокую надежность обмена информацией в условиях воздействия внешних и внутренних помех и обладающих приемлемой технической сложностью реализации.
Применительно к теме диссертационных исследований решение указанной актуальной задачи связано с разработкой частных комбинированных решений многопользовательских селекторов случайного числа сигналов на фоне разнохарактерных, в том числе негауссовских помех, использующих достоинства полигауссовой и многопользовательской обработки с целью повышения эффективности функционирования CDMA систем.
Степень разработанности темы исследований.
Фундаментальные исследования, выполненные с начала шестидесятых годов в области теории синтеза алгоритмов обнаружения-различения-оценивания сигналов, объективно определили нарастающий интерес к синтезу новых классов алгоритмов многопользовательского приема случайного числа сигналов на фоне комплекса произвольных помех и развитие базовой методологии статистического синтеза и анализа информационных систем, опирающейся на потенциал используемых классов вероятностных моделей, в т.ч. моделей и алгоритмов посткорреляционного уровня.
Среди наиболее значимых работ в области синтеза алгоритмов компенсации внутрисистемных помех на основе технологии многопользовательского
детектирования необходимо отметить работы зарубежных и отечественных ученых, S. Verdu, A. Duel-Hallen, М. Honig, S. Moshavi, М. К. Varanasi, В. Aazhang, Ю.С. Шинакова, A.M. Шломы, В.Б. Крейнделина и других ученых. Однако представленные в данных работах алгоритмы обеспечивают повышение помехоустойчивости CDMA систем только в условиях воздействия аддитивного белого гауссовского шума.
В работах Ш.М. Чабдарова, А.Т. Трофимова, Н.З. Сафиуллина, А.Ф. Надеева, СВ. Козлова, И.А. Колтунова развита теория синтеза полигауссовых алгоритмов обработки сигналов в комплексе негауссовских помех на основе посткорреляционных вероятностных моделей. В работах С.А. Айвазяна исследованы процедуры разделения смесей и алгоримы классификации для различных приложений многомерного статистического анализа случайных явлений. В работах P.P. Файзуллина впервые предложен новый класс комбинированных алгоритмов, позволяющих компенсировать влияние внутрисистемных помех на основе многостадийной процедуры параллельной обработки, но обладающих существенной вычислительной сложностью. Указанные научные разработки послужили основой для получения частных решений новых комбинированных полигауссовых алгоритмов, обеспечивающих эффективную работу в негауссовских помехах и обладающих меньшей вычислительной сложностью.
Объектом исследования являются широкополосные системы связи с подвижными объектами на основе технологии кодового разделения каналов.
Предметом исследования являются помехоустойчивые алгоритмы, методы и устройства многопользовательского приема сигналов в негауссовских каналах для CDMA систем связи.
Целью научного исследования является повышение эффективности CDMA систем подвижной связи в условиях воздействия комплекса помех и шума с негауссовским характером распределения вероятности.
Для достижения указанной цели поставлены следующие задачи:
-
разработать методику синтеза комбинированных алгоритмов многопользовательского приема сигналов с компенсацией внутрисистемных помех и внешних помех с негауссовским характером распределения вероятностей.
-
разработать оригинальный комбинированный алгоритм многопользовательского приема сигналов для CDMA систем подвижной связи в условиях воздействия внутрисистемных помех, а также внешних помех с произвольным негауссовским характером распределения, позволяющий повысить помехоустойчивость, системную емкость и обладающего приемлемой вычислительной сложностью по сравнению с существующими алгоритмическими решениями;
-
численно оценить условия и возможность представления негауссовских помех малым числом компонент вероятностной смеси для получения приемлемой ошибки аппроксимации в процессе реализации адаптивных процедур анализа входных случайных процессов.
4. разработать устройство, реализующее комбинированный алгоритм, обладающее свойствами технической реализуемости и унифицируемости выполняемых вычислительных процедур;
Методы исследований. Применяются фундаментальные положения и
методы статистической радиотехники, теории оптимального приема сигналов,
теории вычислений, линейной алгебры и теории матриц, теории вероятностных
смесей распределений, комплексного подхода к совместному исследованию,
синтезу, анализу и оптимизации вероятностных моделей, алгоритмов обработки
сигналов и реализующих их программно-аппаратных средств
инфокоммуникационных систем, теории многопользовательского
детектирования, а также методы математического моделирования.
Достоверность полученных результатов подтверждается корректным и обоснованным применением математического аппарата указанных методов исследований, а также согласованностью полученных теоретических результатов и результатов математического моделирования.
Научная новизна заключается в том, что получены следующие оригинальные результаты:
-
Предложена методика синтеза класса комбинированных полигауссовых алгоритмов многопользовательского приема сигналов (ПГ-МПД) для CDMA систем подвижной связи с использованием комплексного показателя эффективности в виде множества основных системных параметров: помехоустойчивость, вычислительная сложность, асимптотическая эффективность.
-
Разработан новый помехоустойчивый комбинированный алгоритм многопользовательского приема сигналов в комплексе внутрисистемных и внешних негауссовских помех, обеспечивающий снижение вероятности ошибки, повышение системной емкости по сравнению с аналогичными алгоритмами многопользовательского приема.
-
Методом математического моделирования показано, что при ограничении на ошибку аппроксимации Д=10"3 и порога изменения є=\0"5, для полигауссова представления одного временного отсчета негауссовской помехи со значениями статистических параметров из диапазона: веса компонент: 0.2 - 0.7, СКО: 1 - 4, мат. ожидания: 0 - 2, в каналах CDMA систем практически можно использовать 3 компоненты вероятностной смеси, что крайне важно с точки зрения экономии вычислительных ресурсов как для адаптивных процедур анализа случайных входных процессов, так и общего алгоритма приема сигналов.
-
Разработано оригинальное устройство, реализующее комбинированный алгоритм приема сигналов и обладающее высоким уровнем распараллеливания векторно-матричных операций в каждую тактовую единицу времени, в виду возможности потоковой организации вычислительных процедур в параллельно конвейерном режиме обработки отсчетов входного вектора.
Теоретическая и практическая значимость работы заключается в разработке комбинированного алгоритма и устройства приема сигналов в условиях воздействия заданного комплекса внутрисистемных помех и
негауссовских помех, позволяющего на уровне отношения сигнал/помеха+шум, равным 10 дБ, снизить вероятность битовой ошибки в 1.12 раз, а на уровне 13 дБ - снизить в 5.2 раза по отношению к известному MMSE-приемнику, а также обеспечить полиномиальную вычислительную сложность от числа обрабатываемых отсчетов. Разработанное устройство реализовано конечным набором однотипных вычислительных процедур, что позволяет технически экономично реализовать алгоритм на базе существующих программируемых логических интегральных схем.
Внедрение результатов работы представлено в рамках выполнения научно-исследовательских работ по государственному заданию № 2014/55, код проекта 3469 на тему «Разработка теоретического и алгоритмического обеспечения интегрированных комплексов моделирования программно-определяемых оптико- и радиоэлектронных систем двойного назначения», в научно-исследовательских и опытно-конструкторских работах ООО «КБ Навигационные технологии», а также в образовательном процессе: 1)в виде внедрения Программы для моделирования алгоритмов обработки сигналов в мобильных системах связи «CDMA РІК», который успешно используется при подготовке выпускных квалификационных работ по направлениям 25.05.03 «Техническая эксплуатация транспортного радиооборудования», 11.03.02 «Инфокоммуникационные технологии и системы связи», 2) методического пособия «Теоретические основы передачи информации в системах беспроводной связи с кодовым разделением каналов» для подготовки выпускников по данным направлениям, что подтверждено соответствующими актами внедрения.
Положения, выносимые на защиту:
-
Методика синтеза класса комбинированных ПГ-МПД алгоритмов в CDMA-системах подвижной связи с использованием комплексного показателя эффективности в виде системных параметров: помехоустойчивость, вычислительная сложность, асимптотическая эффективность;
-
Комбинированный алгоритм многопользовательской приема сигналов (ПГ-MMSE) для CDMA систем подвижной связи в условиях воздействия внутрисистемных помех и внешних помех с произвольным негауссовским характером распределения;
-
Результаты математического моделирования для оценки условия и возможности представления негауссовских помех малым числом компонент вероятностной смеси для получения приемлемой ошибки аппроксимации в процессе реализации адаптивных процедур анализа входных случайных процессов.
-
Оригинальное устройство, реализующее разработанный ПГ-MMSE алгоритм и обладающее высоким уровнем распараллеливания выполняемых векторно-матричных операций в каждую тактовую единицу времени.
Апробация работы. Основные результаты работы были представлены и получили одобрение на XIV, XV и XVI-й межд. НТК «Проблемы техники и технологий телекоммуникаций» (Самара 2013, Казань 2014, Уфа 2015), межд. НПК «Фундаментальные и прикладные науки сегодня» (Москва 2013), VII-й
межд. НІЖ «Поиск эффективных решений в процессе создания и реализации научных разработок в российской авиационной и ракетно-космической промышленности» (Казань 2014), VIII-й межд. отраслевой НТК «Технологии информационного общества» (Москва 2014), ХШ-й и XIV-й межд. НТК «Физика и технические приложения волновых процессов» (Казань 2015, Самара 2016), 22-й Всероссийской межвуз. НТК студентов и аспирантов «Микроэлектроника и информатика-2015» (Зеленоград 2015), межд. НТК «Проблемы и перспективы развития авиации, наземного транспорта и энергетики» (Казань 2015, 2016).
Публикации. Основные положения диссертации опубликованы в 20 печатных работах, в том числе в 5 статьях рецензируемых научных изданий ВАК РФ, 1 статье, индексируемом в базе данных Scopus, 1 монографии, 1 учебном пособии, 1 патенте и 11 материалах международных научных конференций.
Личный вклад автора заключается в том, что проведена работа по
анализу, систематизации и оценке эффективности существующих алгоритмов
многопользовательской приема сигналов в гауссовских каналах и полигауссовых
алгоритмов приема сигналов в условиях воздействия негауссовских помех,
предложена методика синтеза класса комбинированных полигауссовых
алгоритмов многопользовательского приема сигналов с использованием
комплексного показателя эффективности и на основе предложенной методики
разработан новый комбинированный полигауссовый алгоритм
многопользовательского приема сигналов в негауссовских каналах, а также предложена реализация указанного алгоритма в виде оригинального устройства многопользовательского приема сигналов.
Структура и объем диссертации. Настоящая диссертационная работа изложена на 156 страницах, включает 34 иллюстраций, 15 таблиц и организована следующим образом: оглавление, список основных сокращений, введение, четыре главы, заключение и библиография, включающая 109 наименований.
Анализ существующих параметров эффективности алгоритмов приема сигналов в CDMA системах подвижной связи
Исследование и синтез алгоритмов обнаружения-различения в комплексе сосредоточенных по спектру негауссовских помех, а также обоснование возможностей ограничений ПГ моделей было проведено в работах А.Т. Трофимова [5, 39, 41, 42].
В диссертационной работе Надеева А.Ф. [26] впервые предложен новый класс - марково-смешанные вероятностные модели случайных процессов, основанные на сочетании свойств смешанных полигауссовых и марковских моделей. Эти модели основаны на двухуровневом представлении случайных процессов: т.н. компонентный уровень и смешивающий уровень.
Компонентный уровень основан на системе стандартных случайных процессов с использованием смесей стандартных вероятностных распределений, а смешивающий уровень основан на свойстве марковских цепей и конкретизирует механизм смешивания случайных процессов. На данном уровне в процессе работы алгоритма приема используется вложенный марковский процесс реализации вероятностных компонент смеси с заданными числовыми характеристиками. На этой основе синтезирован новый марково-смешанный полигауссовый алгоритм (МС-ПГ) обнаружения-различения многоэлементных сигналов.
В диссертации С.В. Козлова [12] предложен новый подкласс мультимарково-полигауссовых моделей и соответствующий оптимальный и квазиоптимальный ММ-ПГ алгоритмы, обеспечивающие линейную зависимость количества каналов от числа сигналов (в отличие от экспоненциальной зависимости как у оптимальных ПГ-алгоритмов). Для квазиоптимального алгоритма дополнительно предложен ряд улучшений, которые позволяют повысить отношение сигнал/шум исходного квазиоптимального решения, снизить дисперсию оценки сигнала пилот-тона и вероятность битовой ошибки за счет введения новых рекуррентных процедур, осуществляющих повторную обработку вектора реализации входного сигнала и учитывающих значения статистик, полученных на предыдущей итерации, а также введения процедуры корректировки коэффициентов предсказания.
В диссертации Р.Р. Файзуллина [47] предложен подход к разработке нового класса полигауссовых алгоритмов, основанных на методологии полигауссового синтеза и методологии многопользовательского приема для CDMA систем подвижной связи. Указанный подход позволяет эффективно компенсировать внутрисистемные помехи, в том числе помехи со структурой сигнала с учетом негауссовского характера распределений параметров сигналов и помех.
На основе предложенного подхода разработан адаптивный полигауссовый алгоритм многопользовательского разрешения сигналов с параллельным отсечением внутрисистемных помех, предложен оригинальный PG-PIC приемник (см. Рисунок 1.2), позволяющий добиться конкретного выигрыша в помехоустойчивости и системной емкости по сравнению с известными алгоритмами многопользовательской демодуляции.
В работах ряда многочисленных исследователей (Брейдбурд А.И., Рахимов Р.Х., Егоров А.Е., Кокунин П.А., Аднан А.М., Каримуллин Э.М., Чикрин Д.Е., Рахимов Д.Р., Коробков А.А., Гайсин А.К.) получены оригинальные алгоритмические и технические решения специализированных задач обработки сигналов, опирающихся на существующий и развивающийся потенциал ПГ и смешанных ПГ моделей и методов для различных технических систем связи, различных видов передаваемых сигналов (в т.ч. в оптическом диапазоне), условий синхронизации, условий многолучевого распространения, ограничения энергетического и частотного ресурсов, а также ряда других технических приложений.
Полигауссовое представление случайного негауссовского процесса на входе приемника системы, в том числе и случайных негауссовских помех, изначально обладает рядом существенных достоинств, важных с точки зрения их практического применения:
ПГ-модели являются универсальными, поскольку обеспечивают адекватное описание широкого класса нестандартных случайных процессов и позволяют с требуемой точностью представлять произвольные, в том числе многомодальные распределения.
ПГ-модели является замкнутыми относительно линейных преобразований, т.е. любая линейная операция над множеством отсчетов негауссовского входного процесса в результате не меняет статистических свойств данного процесса. Это свойство уникально, особенно для анализа преобразований при прохождении негауссовских случайных процессов через радиотехнические цепи.
Произвольные нестандартные случайные процессы описываются с помощью конечного набора параметров: в общем случае вектором математических ожиданий и многомерной ковариационной матрицей. Эти статистические параметры при использовании полигауссовой методологии могут быть оценены в условиях априорной неопределенности. Это крайне важно для последующей технической реализации адаптивных алгоритмов.
Применение полигауссового подхода позволяет продуктивно использовать огромный теоретический и практический потенциал, наработанный в рамках корреляционной теории и ее приложений.
ПГ-модели позволяют получать близкие к каноническим аналитические решения задач синтеза помехоустойчивых алгоритмов обработки и принятия оптимальных и квазиоптимальных решений в негауссовской постановке.
Применение полигауссового подхода позволяет получить технически реализуемые квазиоптимальные алгоритмы, структура которых принципиально состоит из множества параллельных каналов обработки группового сигнала. В каждом из таких парциальных каналов выполняется однотипный набор стандартных операций не выше второго порядка независимо от характера распределения обрабатываемой статистики исходных сигналов и помех.
Структура получаемых алгоритмов не зависит от вида вероятностных распределений, образующихся в точке приема случайных процессов, порожденных случайно флуктуирующими сигналами и помехами. Благодаря перечисленным объективным достоинствам полигауссовых моделей и методов, синтезированные на их основе алгоритмы потенциально обеспечивают большую помехоустойчивость и «комфортную» с точки зрения схемотехники техническую реализуемость приемных устройств.
Обобщенная методология полигауссового синтеза квазиоптимальных алгоритмов
В диссертации Панкратова Д.Ю. [28] на основе итерационного алгоритма Чебышева [32] синтезирован нелинейный итерационный алгоритм в каналах с АБГШ, для которого оценка вектора информационных бит осуществляется путем нелинейного преобразования предыдущей оценки согласно следующему правилу: Ьi= Ьi-і + (Y-Н/(&i_!/Z))),/ = l,2,...,/max, (2.19) где D - некоторый числовой параметр, f()- нелинейная функция, учитывающая тип модуляции (для ФМ-2 f(S) = th(S)), Y - вектор мягкой статистики с выхода традиционного демодулятора (детектора), zi - параметр алгоритма Чебышева зависящий от номера итерации и максимального числа итераций , а н - матрица взаимной корреляции расширяющих последовательностей.
В 2009 году новый класс итеративных многопользовательских детекторов (демодуляторов) был предложен проф. МТУСИ, Крейнделиным В.Б. В его работе [17, 18] предложен и синтезирован алгоритм совместной многопользовательской демодуляции и фильтрации комплексного множителя канала связи для CDMA систем связи, основанные на рекуррентном решении уравнения Стратановича. Суть данного подхода заключается в итеративном процессе демодуляции и фильтрации (оценки) комплексных множителей канала: на первой итерации на основе пилот-символов осуществляется предварительная оценка параметров канала связи и оценки информационных бит, имеющих невысокую точность, а на последующих итерациях 2..s на основе предыдущих решений получают еще
более точные оценки символов информационного канала. В указанных работах также предложен оригинальный итерационный метод, в рамках которого производится решение систем линейных уравнений, основанное на критерии минимума эмпирического риска в форме функционала Тихонова. Предложенный метод может быть использован в CDMA-системах при решении задач синтеза алгоритмов многопользовательской демодуляции-декодирования.
Осознание необходимости проведения фундаментальных исследований в области моделирования человеческого мозга и поведения человека правительство США в начале 1960 года инициировало исследования в области искусственного интеллекта. Как следствие были разработаны модели искусственных нейронных сетей (многоуровневых перцептронов) [29], представляющих собой систему взаимосвязных нейронов (процессоров) и способных к обучению (адаптации), а также методы эволюционного (эвристического) программирования, использующего в своей основе модель эволюции как процесса оптимизации [76]. Первое упоминания нейронных сетей в задачах многопользовательского детектирования представлено в работе [66, 92]. Для принятия решения использовались нейронные сети на основе логики работы многоуровневых перцептронов. Позднее, в работе [82] Markku Juntti предложил генетический алгоритм (GA-MUD) для синхронных CDMA систем, и его дальнейшая модификация [109], продемонстрировали успешность синтеза таких алгоритмов для задач компенсации MAI, получив квазиоптимальные решения в условиях АБГШ, приближающиеся к однопользовательской границе помехоустойчивости и обладающие значительно меньшей, чем у оптимального детектора, вычислительной сложностью.
Первые алгоритмы многопользовательского детектирования на основе эволюционного программирования (EP-MUD) в каналах с АБГШ были предложены в работах [87] и усовершенствован в [67]. Указанные алгоритмы направлены на поиск решения, соответствующего заданной целевой функции (целевое значение), что позволяет оценить тенденцию (траекторию) продвижения при поиске оптимального решения. Каждый эвристический алгоритм рекуррентно максимизирует логарифмическую функцию правдоподобия в каждой последующей итерации, проверяя конкретный фрейм вероятного бита кандидата (бита, включенного в так называемую популяцию на текущей стадии итерации) [82]. Каждая итерация направлена на повышение средней помехоустойчивости системы для К пользователей. Чем больше таких итераций, тем больше помехоустойчивость системы приближается к оптимальной (помехоустойчивость ОМПД). Принцип работы этих алгоритмов представлен на Рисунке 2.5.
Блок-схема работы МПД алгоритмов: GA-MUD и EP-MUD В блоке эвристической обработки по одному из выбранных алгоритмов, GA или Ep, производится принятие оценки битовых решений B1, где G – количество итераций алгоритма, g – текущая итерация алгоритма, T – размер скрещиваемой (операция crossover) популяции (определяет скорость сходимости алгоритма), p – максимальный размер популяции. Отличие этого подкласса МПД алгоритмов заключается в том, что для формирования нового поколение индивидуумов (статистики) для GA-MUD используется операция кроссовера, а для EP-MUD – мутация (операция mutation) – случайная замена информационного бита (с -1 на 1, или наоборот). На стадии замены (replacement) происходит отбор (операция selection) «лучших» (больший коэффициент пригодности) индивидуумов и их последующее замещение в выбранном поколении. Критерием останова алгоритмов, как правило, является достижение установленного количества итераций алгоритма (формирования заданного количества новых поколений) [71].
Сочетая основные достоинства линейных и нелинейных многопользовательских детекторов на протяжении двух десятков лет исследователями предлагаются различные типы комбинированных алгоритмов, позволяющих при определенных условиях повысить помехоустойчивость приема в каналах с АБГШ. Известны успешные сочетания линейных и нелинейных многопользовательских детекторов, в частности, MMSE-PIC [80], многокаскадный многопользовательский детектор с частичным отсечением помех [72], в котором устраняется недостаток классических PIC, заключающийся в распространении битовой ошибки, при некорректной оценке MAI на первом каскаде, а также многие другие решения [69].
Алгоритмы многопользовательского детектирования на основе искусственного интеллекта
Как было показано в Главе 2, помехи в беспроводных каналах связи, представленные в виде к отсчетов u = {uk},k = \,K, может быть представлены в виде линейной комбинации плотностей вероятности w„(u), различающихся своими средними или ковариациями:
Данная задача органично вписывается в теорию кластерного анализа [1, 8, 22, 48], задачу которого можно определить, как распределение элементов множества на определенные группы, называемые кластерами. Алгоритмы кластерного анализа нашли широкое применение в различных сферах: социологических исследованиях [4, 43], экономике [23], финансах, биологии, психологии и т.д. Подобное широкое применение алгоритмов кластерного анализа обусловлено актуальностью задачи анализа большого количества данных и определение степени их зависимости.
В зависимости от типа выполняемой задачи алгоритмы кластеризации можно классифицировать по ряду разных признаков. Например, по способу анализа данных - четкие и нечеткие, по времени выполнения - реального времени и не потоковые, по количеству применений - одноэтапные и многоэтапные и.т.д. [10]. Обобщенная классификация алгоритмов представлена на Рисунке 3.4 [81].
Иерархические алгоритмы кластеризации в основе своего принципа действия содержат механизм укрупнения классов, т.е. каждое анализируемое значение ик сначала воспринимается как отдельный класс, а на основе анализа расстояний между значениями (метрики) dtj = d(ui ,uj) = p(ui ,uy), і, j eK,i j. На основе данной метрики далее происходит укрупнение значений в определенные классы. В качестве такой метрики может быть выбрано Евклидово расстояние (3.33) или расстояние Чебышева (3.34): f »i,»j)= E(".--"y)2, (3.21) ., .) = тах,г- .). (3.22) Основными иерархическими алгоритмами являются односвязные (т.н. метод ближайшего соседа) или полносвязные (т.н. метод дальнего соседа). Алгоритмы кластеризации Иерархические алгоритмы Неиерархические алгоритмы Односвязные Полно связные Квадратичной ошибки Графовые алгоритмы Алгоритмы разделения смеси
Метод Варда Центроидный метод Алгоритм к - средних ЕМ алгоритм Метод средней связи Рисунок 3.4 - Обобщенная структура алгоритмов кластеризации В односвязном алгоритме на каждой итерации происходит укрупнение исходя из наименьшего расстояния между двумя любыми значениями, в полносвязном – исходя из наименьшего расстояния между двумя наиболее удаленными значениями.
Остальные иерархические алгоритмы: метод средней связи, центроидный метод и метод Варда [24] по сути являются производными от двух вышеуказанных методов, устраняющими их определенные недостатки применительно к используемой задаче [81]. Для метода средней связи расстояние между кластерами вычисляется как среднее расстояние между каждыми парами данного кластера.
Для неиерархические алгоритмов характерно разделение исходного большого кластера на меньшие. Основными неиерархическими алгоритмами являются графовые алгоритмы, квадратичной ошибки, в основе которых лежит представление начальных значений в виде графа (дерева) с узлами в виде начальных значений и соединениями узлов в виде метрик. Наибольший интерес среди алгоритмов кластеризации вызывают две группы алгоритмов: алгоритмы квадратичной ошибки (алгоритм k-средних) и алгоритм разделения смеси (ЕМ-алгоритм) ввиду того, что данные алгоритмы наиболее удобно можно адаптировать для задачи итеративного поиска оптимальных параметров полигауссовой помехи.
Алгоритм k-средних Алгоритм k-средних относится к классу алгоритмов квадратичной ошибки. Данный класс алгоритмов направлен на минимизацию квадратичной ошибки разбиения кластеров: e2(u,L)=5 ()-ro,. , (3.23) где irij - среднее значение кластера j = 1,n; u(j) - текущее значение, принадлежащее кластеру у, L - множество значений кластера.
Алгоритм Псредних является наиболее простым с точки зрения вычислительной сложности и часто используемым алгоритмом класса квадратичной ошибки.
Принцип действия данного алгоритма заключается в следующем: 1. Выбрать случайным образом некоторый вектор значений к, которые будут первоначально считаться средними значениями кластеров {щ,...,ик},к = 1,К . Очевидно, что данное количество будет равно количеству предполагаемых гауссовых компонент суммарного разложения, т.е. {щ,...,ик},к = 1,п, и на данной итерации будет считать что m = {щ,..., ик }; 2. Распределить значения входного вектора значений и к выбранным случайным образом средним значениям m; 3. Пересчитать новые средние значения mnew исходя из выбранного распределения на шаге 2; 4. В том случае, если критерий минимальности среднеквадратичной ошибки не выполняется, то необходимо повторно выполнить операцию на шаге 2. Таким образом, критерием остановки такого итеративного алгоритма может выступать как минимальное требуемое значение среднеквадратической ошибки, так и отсутствие перегруппировки значений вектора и в определенные кластеры. Основным недостатком этого алгоритма является то, что его эффективность в смысле скорости сходимости в значительной степени зависит от начального выбора центров кластеров т. Другим наиболее часто используемым алгоритмом в кластерном анализе является ЕМ-алгоритм (Estimation Maximization).
Подход, заложенный в работу ЕМ-алгоритма для задачи кластеризации, заключается в том, что соотнесение того или иного значения входного вектора значений и = {и1,и2,...,щ},кеК на основе статистической оценки отношения правдоподобия и ее максимизации, что и является критерием останова данного алгоритма. Следует отметить, что данный подход наиболее логично вписывается в задачу аппроксимации полигауссовой помехи wп(u) = g„ww(u) в виде линейной и комбинации частных гауссовских плотностей вероятности каждого кластера. Данный алгоритм строится на основании выполнения следующих операций: задание начальных значений параметров полигауссовой помехи (случайно или на основе некоторых предварительных оценок), оценка параметров апостериорных вероятностей принадлежности поступившего отсчета к определенному кластеру (т.н. шаг Е - expectation), максимизация отношения правдоподобия (т.н. шаг М -maximization).
Оценка комплексного показателя эффективности ПГ-MMSE алгоритма/устройства
Следует отметить, что поскольку формулы (3.27) - (3.30) выполняются для каждой из компонент п полигауссовой помехи п = 1 3, то для того, чтобы получить итоговую вычислительную сложность операций в канале помеха+шум необходимо суммарное количество операций в Таблицах 4.1 - 4.4. умножить на 3. При определении максимального из 3-х векторов Zпш(u) в (3.31) руководствуемся предположением о том, что каждый элемент минимальной решающей статистики в виде матрицы размером Ns lesx Ns les для одной компоненты помехи больше соответствующего элемента матрицы для другой компоненты помехи. Следуя этой логике достаточно выбрать один из соответствующих элементов в каждой матрице и сравнить их, однако для повышения достоверности будем руководствоваться следующим подходом: 1) поиск максимального элемента в каждой из матриц
Z1п ш(u), Zп ш(u) и Zп ш(u) 2) поиск максимального из полученных элементов и возврат соответствующей матрицы Zпш(u). Так как любую квадратную матрицу можно представить в виде Nsamples - векторов столбцов, каждый из которых состоит из Nsamples элементов, то вычислительная сложность поиска максимального значения одной матрицы равна 0(N les). С учетом количества компонент произвольной помехи общая вычислительная сложность равна 0(3N les). С точки зрения количества выполняемых операций сравнения получим сложность равную \Nsample-\)Nsamples+2. Формула (3.32) не влияет на количество выполняемых операций, поскольку относится к описанию служебной информации проставления флага о наличии действующей компоненты помехи пдейств. Поскольку в (3.33) при определении полигауссового функционала правдоподобия Lпш(u) априорная вероятность Рс и весовые коэффициенты qn известны, то общая вычислительная сложность значению, приведенному в Таблице 4.5.
Вычислительная сложность. Канал помеха+шум № п.п. Наименование Умножений Сложений/ вычитаний Делений Возведение в степень Прочее (поиск макс. знач., сравнение) 1 (3.27) 2 Samples + + (N sampieS-D 2Nsamples Nsamples 0 3Nsamples 2 (3.28) 3 N2samples 2 N2samples 1 N s 2 amples + 1 0 3 (3.39) 2 Samples + + (N sampieS-D 3Nsamples Nsamples 0 0 4 (3.30) 2 Samples ++ 2(Nsamples-l) 2 N samples + N aples 2Nsamples 0 0 5 (3.31) 0 0 0 0 3(Nsamples-Dx xN samples+2 6 (3.33) +2N2samples 3N2samples 0 0 Итого по типу операции 10N samples ++ 4N samples-l 7 Samples ++ 6N samples 4N samples + + 1 N s 2 amples + 1 3(Nsamples-DxxN samples+2 +3N samples Суммарное кол-во операций simples+14N samples или 0(22 атр1ез), VN sampbs 14 Таким образом, мы вычислительную сложность операций в канале помеха+шум, показали, что он зависит только от размера входного вектора отсчетов и имеет квадратичную зависимость. В то же время алгоритм обработки в канале помеха + шум требует ограниченного типа вычислительных операций. Теперь произведем оценку вычислительной сложности операций, осуществляемых в канале сигнал+помеха+шум в общем случае для R активных пользователей.
Расчет вычислительной сложности для канала обработки сигнал+помеха+шум Логика подсчета вычислительной сложности как и в канале помеха+шум в данном канале аналогичная. Отличие состоит в том, что в данном случае добавляется сигнальная компонента R активного пользователя. С учетом вышеизложенного будем оперировать формулами (3.34)-(3.47). Дискретный корреляционный интеграл для гипотезы о наличии сигнала R активного пользователя, п-й компоненты произвольной помехи и фонового шума пКп,ш(и) имеет аналогичную размерность Ns lesxNs les, что и для канала помеха+шум. Для случая зависимости отсчетов сигнала и помехи на битовом интервале необходимо вычислять ковариационные матрицы а размерностью Nsamplesx Nsample,
Вектор математических ожиданий сигнала R активного пользователя, п-й компоненты произвольной помехи и фонового шума представляет собой сумму соответствующих векторов средних, т.е. тисR,ип(и),и0 =m«сR +тпп(п) +ти0 и имеет размерность lxNsamples. В данном случае вычисление инверсной ковариационной матрицы a„cRп(o методом алгебраических дополнений является нецелесообразным, поскольку исходная матрица не является диагональной. Одним из наиболее оптимальным с точки зрения времени выполнения является алгоритм Гаусса Жордана для обращения квадратных матриц. Для нахождения обратной матрицы необходимо N]amples умножений и N]amples - N2samples сложений/вычитаний. Результаты вычислений для одного канала обработки сведем в Таблицу 4.7. В дополнении к Таблице 4.7 будем принимать во внимание, что вычислительная сложность операции по формуле (3.40) определяется выражением 0(Х log(X)) поиска максимального значения массива из X элементов и равна вычислительной сложности алгоритма быстрого поиска массива; в данном случае X = (n + R + nR)N les; 2) в соответствии с (3.47) осуществляется сравнение итогового функционала отношения правдоподобия для каждого из пользователей дсл,п,ш с некоторым пороговым значением Л0.