Содержание к диссертации
Введение
Глава 1. Поисковые процедуры 13
1.1. Предмет поиска в радиотехнике 13
1.2. Классификация задач поиска 16
1.3. Пути повышения эффективности поисковых процедур... 19
1.3.1. О выборе поискового алгоритма 19
1.3.2. О выборе типа и параметров решающего устройства...28
1.3.3. О реализации поисковых процедур 31
1.4. Выводы 39
Глава 2. Оптимизация последовательных поисковых алгоритмов 41
2.1. Подходы к оптимизации поиска 41
2.2. Поиск сигналов в частотном диапазоне 44
2.2.1. Однопроходный поиск с ОПРУ 44
2.2.2. Циклический поиск с ОПРУ 48
2.2.3. Однопроходный поиск с ДПРУ 49
2.2.4. Циклический поиск с ДПРУ 54
2.3. Поиск сигнала во временной области и раскрытие кодовой структуры сигнала 57
2.4. Выводы 59
Глава 3. Исследование дихотомических поисковых алгоритмов 61
3.1. Подходы к оптимизации поиска 61
3.2. Поиск сигнала в частотной области 63
3.2.1. Дихотомический поиск с ОПРУ 63
3.2.2. Применение ДПРУ последовательного анализа 71
3.3. Поиск сигнала во временной области 79
3.4. Раскрытие кодовой структуры сигнала 87
3.5. Выводы 88
Глава 4. Сравнительный анализ последовательного и дихотомического алгоритмов поиска 90
4.1. Поиск сигнала в частотном диапазоне 90
4.2. Поиск сигнала во временной области 100
4.3. Выводы 106
Глава 5. Моделирование поисковых алгоритмов 108
5.1. Структура программной модели 108
5.2. Обоснование требуемого объема статистики при моделировании поиска 110
5.3. Моделирование последовательного поиска 111
5.4. Моделирование дихотомического поиска 116
5.4.1. Поиск в частотном диапазоне 116
5.4.2. Поиск во временной области 120
5.5. Выводы 124
Заключение 126
Список литературы 128
- Классификация задач поиска
- Однопроходный поиск с ОПРУ
- Дихотомический поиск с ОПРУ
- Поиск сигнала во временной области
Введение к работе
Актуальность темы. Поисковые процедуры в том или ином виде
часто встречаются в самых различных областях техники. Примером может быть техническая и медицинская диагностика, обработка изображений, экспериментальная физика и многое другое. Однако в радиотехнике поиск сигналов по частоте и времени занимает особое место, поскольку используется в большинстве систем связи, при радиоразведке, радиомониторинге, во многом определяя их основные характеристики.
Анализ распределения аппаратных ресурсов радиотехнических систем показывает, что значительная их часть, характеризуемая быстродействием, объемом памяти и, в конечном счете, стоимостью, отводится на решение задач поиска. При этом, в отличие от других процедур, например декодирования и демодуляции, поиск выполняется во всех режимах работы радиосредств, во многом определяя их энергопотребление. Так в широкополосных системах связи осуществляется поиск частоты узкополосных помех с целью их последующей режекции. В сотовых системах связи IS-95, Cdma-2000 выполняется поиск с целью синхронизации при вхождении в связь и поиск сигналов соседних базовых станций для организации эстафетной передачи, на что отводится до половины вычислительных ресурсов цифрового модема. Таким образом, проблема повышения эффективности поиска — это часть общей актуальной проблемы снижения стоимости и улучшения эксплуатационных характеристик радиотехнических систем.
Поиск является частным случаем процедуры оценки, предполагающим пошаговое снижение неопределенности, существующей относительно интересующего параметра сигнала. Его используют в тех случаях, когда одновременный анализ всего диапазона возможных значе-
ний выполнить невозможно или нецелесообразно. При этом на каждом шаге посредством одного или нескольких измерительных каналов, включающих, в общем случае, взаимнокорреляционный приемник (ВКП) и решающее устройство (РУ), производится тест на соответствие оцениваемого параметра одному или нескольким конкретным значениям. Наиболее важными характеристиками поиска являются вероятность успешного завершения и среднее время поиска, а более эффективным следует считать поисковое устройство, обеспечивающее требуемые значения данных величин при меньших, по сравнению с другими, аппаратных затратах.
В том случае, когда время поиска с одноканальным устройством больше требуемого, используют дополнительные измерительные каналы. Однако при анализе и оптимизации поисковых процедур достаточно рассмотреть поиск, использующий один измерительный канал, поскольку многоканальную процедуру всегда можно свести к совокупности одноканальных. В некоторых случаях одноканальный поиск называется двоичным, поскольку подразумевает двухальтернативные тесты с результатом ДА/НЕТ. Таким образом, оптимизация двоичного поиска может привести к снижению времени многоканального поискового устройства в целом. При сохранении требуемого времени и вероятности успешного завершения поиска это позволит сократить число используемых измерительных каналов и тем самым снизить его стоимость и энергопотребление.
Повышение эффективности поиска, или оптимизацию, можно проводить по двум направлениям:
выбор эффективного поискового алгоритма;
выбор и оптимизация параметров РУ.
Решению данной проблемы посвящено много работ. В условиях воздействия помех широкое распространение получил последователь-
7 ный поисковый алгоритм [5, 18, 33, 35], предполагающий поочередный просмотр области неопределенности с шагом, равным требуемой точности оценки интересующего параметра сигнала при этом.
При отсутствии помех, при равенстве временных ресурсов, отводимых на каждый шаг, и равномерном распределении параметра сигнала в области неопределенности оптимальным, с точки зрения минимума времени поиска, является дихотомический алгоритм. При этом алго-
ритме на каждом шаге область делится пополам и определяется часть, содержащая сигнал, а по достижении требуемой точности оценки деление прекращается. [12, 15, 34, 50]. Подтверждением возможности преимущества дихотомического алгоритма при указанных условиях служит сравнение по числу шагов, которых заметно меньше. Однако из-вестные исследования дихотомического поиска проведены для специальных последовательностей быстрого поиска, тогда как общие случаи, в частности поиск в частотном диапазоне, синхронизация широкополосных сигналов, рассмотрены недостаточно. Вместе с тем предположение о шагах одинаковой длительности оправдано только при сильных сигналах, или высоком отношении сигнал/шум (ОСШ), что ставит
преимущество дихотомического алгоритма под сомнение. Таким обра-»
зом, в целях повышения эффективности поиска можно выбрать один из
двух конкурирующих алгоритмов, исходя из конкретных условий, таких как ОСШ, размер диапазона возможных состояний искомого сигнала и т.д.
Время и вероятность успешного завершения поиска, в рамках кон
кретного алгоритма, определяются типом и параметрами РУ - интерва
лами анализа и порогами, устанавливаемыми на каждом из шагов. Из
вестно, что наиболее эффективными являются РУ с накоплением энер-
4 гии полезного сигнала [22], наилучшее из которых - двухпороговое РУ
(ДПРУ) последовательного анализа Вальда [28]. В то же время однопо-
8 роговое РУ (ОПРУ) с последетекторным накоплением [21], являясь более простым, в некоторых случаях ему не уступает. В результате при оптимизации поиска необходимо делать оправданный выбор РУ и устанавливать его параметры, приводящие к минимуму времени поиска вцелом.
В ходе анализа последовательного поиска большинство авторов предполагают, что параметры РУ остаются одинаковыми на всех шагах [13, 14]. Однако представляется логичным уменьшать пороги по мере сужения области неопределенности, поскольку апостериорная вероятность присутствия сигнала в ходе поиска растет, и вероятность его пропуска должна снижаться [19, 20].
В отличие от последовательного поиска, при дихотомическом алгоритме на каждом шаге анализируются сегменты области неопределенности различной величины. При этом в ходе поиска изменяется мощность флуктуационной составляющей по выходу взаимнокорреля-ционного приемника, что при использовании одинаковых интервалов анализа приводит к тому, что на первых шагах достоверность вынесения решения существенно ниже, чем на последних. Поскольку вероятность успеха дихотомического поиска равна произведению достоверно-стей всех шагов, то в таком случае она будет определяться достоверностью только первого шага. Данный факт позволяет считать использование одинаковых интервалов анализа на всех шагах дихотомического поиска, что предлагается некоторыми авторами [15], неоправданным. В результате основной задачей при проектировании дихотомического поискового устройства является нахождение приемлемого варианта распределения общего времени поиска между шагами.
Таким образом, проблема выбора типа и оптимизации параметров РУ при поиске сигналов решена не полностью, и в данном направлении есть резерв повышения его эффективности.
9 Работа выполнена в рамках научного направления ВГТУ "Защита информации каналов связи и управления".
Целью диссертации является улучшение характеристик и сниже-ние стоимости систем связи и управления за счет повышения эффективности процедур поиска и синхронизации.
Достижение поставленной цели потребовало решения следующих задач:
Анализ путей повышения эффективности поисковых процедур.
Разработка методов оптимизации параметров решающих устройств применительно к последовательному и дихотомическому поиску радиосигналов.
Сравнение эффективности для целей поиска однопорогового и двух-порогового решающих устройств.
Сравнительный анализ последовательного и дихотомического алгоритмов с целью выявления условий их преимущественного применения.
Анализ характеристик последовательного и дихотомического алгоритмов поиска на основании статистического моделирования с целью проверки адекватности различных методов оптимизации.
Методы исследования. В основу исследования положены методы оптимальной оценки параметров сигналов на фоне помех, теория вероятности, теория информации, теория скрытности, математические методы оптимизации, численные методы и методы имитационного компьютерного моделирования.
Научная новизна работы заключается в следующем:
1. Разработан метод комплексной оптимизации процедур поиска сиг
налов, позволяющий, в отличие от известных, обоснованно выбирать
^ поисковый алгоритм и рассчитывать оптимальные параметры РУ, что
10 дает возможность построить наиболее эффективное поисковое устройство исходя из конкретных условий проведения поиска.
Предложен метод вычисления параметров РУ при проведении последовательного поиска радиосигнала, отличающийся переменными от шага к шагу порогами обнаружения и интервалами анализа, что позволяет при фиксированном числе измерительных каналов повысить вероятность успешного завершения и снизить среднее время поиска. Метод использован при построении устройств поиска, защищенных патентами России [52, 70].
Разработан метод расчета параметров РУ при проведении дихотомического поиска радиосигнала, отличием которого является получение оптимальных значений пороговых уровней и интервалов анализа. Метод приводит к различной для каждого из шагов поиска вероятности правильного решения, что позволяет максимизировать вероятности успеха поиска при заданном среднем времени.
Выполнен сравнительный анализ характеристик оптимизированного дихотомического поиска и поиска с равнодостоверными шагами, показавший, что оптимизированный вариант имеет существенный выигрыш по времени поиска, особенно при низком отношении сигнал/шум (ОСШ).
Проведен сравнительный анализ последовательного и дихотомического алгоритмов поиска радиосигнала, в ходе которого найдены граничные ОСШ: при их превышении дихотомический алгоритм эффективнее последовательного. Показано, что при поиске в частотном диапазоне данные ОСШ относительно невелики и в большинстве случаев дихотомический поиск значительно быстрее последовательного, в то время как при поиске во временной области ситуация обратна.
Практическая ценность диссертации состоит в следующем:
Предложенные методы оптимизации поисковых алгоритмов не имеют технических и технологических ограничений при использовании, а их применение позволяет повысить эффективность поиска радиосигна-лов и тем самым улучшить характеристики и снизить стоимость ССУ.
Результаты сравнительного анализа различных поисковых алгоритмов позволяют выбрать наиболее эффективный алгоритм в зависимости от заданных условий проведения поиска, таких как характер и размер
области неопределенности, ОСШ.
Характеристики различных поисковых алгоритмов, полученные рас-четно-теоретическим путем, а также с помощью статистического моделирования, позволяют оценить потенциальные возможности устройств поиска на стадии проектирования.
Полученные выражения могут быть использованы для выбора и расчета параметров РУ при построении алгоритмов последовательного и дихотомического поиска, обладающих потенциальными или близкими к ним характеристиками, что позволяет существенно снизить трудоемкость разработки поисковых устройств.
Разработанные на языке C++ программы моделирования поисковых процедур, реализующих различные поисковые алгоритмы, могут слу-жить основой при создании реальных поисковых устройств.
Внедрение результатов работы. Результаты диссертации исполь
зованы в НИР «Регул-S», ОКР «Кодокан» при разработке алгоритма
поиска абонентской станции в режиме доступа в сотовой системе связи
CDMA стандарта IS-95, а также в ОКР «Samsung» при разработке алго
ритма быстрого захвата сигнала базовой станции в системе сотовой
связи UMTS. Акт внедрения прилагается к диссертации. По результа
там работы получены два патента.
^ Апробация работы. Основные результаты работы докладывались
и обсуждались на Всероссийской научно-технической конференции
«Направления развития систем и средств радиосвязи» (Воронеж, 1995), Всероссийской научно-технической конференции «Радио и волоконно-оптическая связь, локация и навигация» (Воронеж, 1997, 2002), 5-й межрегиональной конференции Московского и Псковского обл. НТО РЭС им. А.С. Попова (Пушкинские горы, 1995), научно-технической конференции «Информационная безопасность автоматизированных систем» (Воронеж, 1998).
Публикации. По материалам диссертации опубликовано 11 печатных работ, из них 2 патента на изобретения. В работах, опубликованных в соавторстве и приведенных в конце диссертации, лично соискателю принадлежит: [52, 70] — разработка и моделирование способа поиска широкополосного сигнала; [19, 20, 56, 57] - теоретический анализ, моделирование, написание текста.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 70 наименований. Основная часть работы изложена на 132 страницах, содержит 91 рисунок и 10 таблиц.
Классификация задач поиска
Тема "Поиск" в общем смысле весьма широка и сложна, однако в радиотехнических приложениях, рассмотрением которых ограничена данная работа, как правило, известно, какая цель преследуется при поиске и какими средствами его можно осуществлять. В данной ситуации интерес представляет максимизация эффективности поисковой проце дуры при известных ограничениях на аппаратные и вычислительные возможности. J? Эффективность можно трактовать по-разному в зависимости от условий проведения поиска, которые можно разбить на две группы: поиск проводится в отсутствие возможности подтверждения результата; существует возможность подтверждения результата поиска по исте-чении некоторого времени, называемого штрафным временем ложной тревоги Гштр, в течение которого выполняется определенная проверка. Наиболее характерные варианты задачи поиска для первой группы условий [11]: необходимо обнаружить сигнал с требуемой вероятностью успеха Q за минимальное время; необходимо обнаружить сигнал с максимально возможной вероятностью успеха Q в рамках фиксированного времени. Отсюда поисковым устройством, более эффективным в рамках і первой задачи, будет то, которое обеспечит меньшее время поиска, а в - рамках второй - большую вероятность успеха. Следует отметить, что с точки зрения типа и параметров поискового устройства обе задачи эквивалентны [30], т.е. устройству, приводящему к максимуму вероятности успеха Q за ограниченное время, потребуется минимальное время для достижения требуемой Q. Поскольку время поиска в большинстве случаев является случайной величиной, то в зависимости от конкретной задачи в данном качестве могут рассматриваться [13, 14, 42]: іО среднее значение времени поиска; среднее значение максимального времени поиска; максимальное время поиска. Первая формулировка чаще всего используется в литературе, а также наиболее универсальна с точки зрения типа поискового алгоритма, в связи с чем в дальнейшем используется именно она. Вторая группа условий более характерна для поиска с целью организации связи. В этом случае по окончании поиска выполняется проверка, например прием контрольного сообщения, и в случае отрицательного ее результата поиск повторяется. При проектировании поискового устройства в данных условиях требуется минимизировать среднее время. В большинстве случаев для решения задач поиска используют многоканальные схемы, поскольку требования по времени поиска, как правило, довольно жесткие.
Однако зависимость вероятностных характеристик, в частности вероятности успешного завершения Q, для L-канального поиска в параллельно-последовательном варианте [42] определяется теми же выражениями, что и для одноканального. Отличие заключается в выигрыше по скорости, который не превышает L раз. Отсюда следует, что максимизация эффективности поиска в самом простом одноканальном варианте также приведет к наилучшим характеристикам многоканальной схемы в целом. С учетом вышесказанного для решения задач поиска оправданным является рассмотрение одноканальных схем с последующим использо-ванием, при необходимости, полученных параметров в многоканальных обнаружителях. В предыдущем параграфе было отмечено, что лучшей следует считать поисковую процедуру, обеспечивающую наименьшее среднее время поиска при прочих равных условиях. В свою очередь среднее время складывается из интервалов анализа, затрачиваемых на всех шагах, число которых определяется алгоритмом, реализуемым при поиске. Для определения алгоритма поиск можно представить следующей моделью. Объект поиска может находиться в одном из присущих ему состояний ХІЄХ, где Х={хі, Х2 , ... ХА} — множество состояний. Геометрически состояния можно изобразить в виде точек в многомерном пространстве, a Xj при этом будет вектором, координаты которого определяются различными параметрами объекта поиска. Если искомым является радиосигнал, то его параметры - несущая частота, время прихода, поляризация и т.д.
Множество X полагается заданным, если указаны вероятности (закон распределения) всех его возможных состояний 1=1 Целью поиска в данной постановке является снижение исходной неопределенности, или энтропии, объекта поиска до требуемой величины. Для этого осуществляется разбиение множества X на части и выполняется тест на принадлежность объекта поиска одной из них. Последующие шаги используют аналогичные операции над подмножествами, в пользу которых вынесено решение на предыдущих и т.д. Наиболее простым является двухальтернативный тест с результатами ДА/НЕТ, производимый одноканальным двоичным измерителем. Другие тесты также могут быть сведены к двухальтернативным. Порядок разбиения области неопределенности на части, называемый алгоритмом поиска, наглядно описывается деревом поиска, вариант которого приведен на рис. 1.2. Деревья, или графы, широко используются при анализе многих систем и процессов. Примером могут служить системы с обратной связью, решетчатые коды и т.д. На каждый шаг поиска затрачиваются ресурсы поисковой процедуры, временные и/или аппаратные. Очевидно, что наилучшим является алгоритм, приводящий к цели за счет минимальных ресурсов. При равенстве ресурсов, отводимых на каждый шаг, и при отсутствии ошибок минимальные ресурсы будет привлекать алгоритм с наименьшим числом шагов. Поскольку число возможных деревьев может быть очень велико, нахождение оптимального дерева путем простого перебора перспектив не имеет. Задача в указанной постановке решается методом Циммерма-на-Хаффмана, известного из теории безызбыточного префиксного кодирования [69]. Входными данными для такой задачи служит закон распределения (1), а выходными - дерево поиска. В некоторых практических случаях, таких как поиск с целью подстройки параметров приемного устройства — когда уход текущего значения параметра от предыдущего невелик - закон распределения инте з ресующего параметра объекта поиска может отличаться от равномерного. Однако в большинстве ССУ проблемы такого рода решаются с помощью классических схем, содержащих частотный или временной дискриминатор [43, 44, 50]. Поэтому при построении поисковой процедуры чаще всего предполагается, что параметр равновероятно распределен в априорном интервале. Решение задачи при равновероятных состояниях объекта поиска, равенстве ресурсов, отводимых на каждый шаг, и в отсутствие ошибок приводит к дихотомическому алгоритму, когда на каждом шаге анализируемое подмножество разбивается пополам. Число шагов при этом равно N=log2A, что является минимально возможным при двоичном поиске. Дерево дихотомического поиска представлено на рис. 1.3.
Однопроходный поиск с ОПРУ
При поиске в частотном диапазоне неопределенным параметром сигнала является центральная частота его спектра. В качестве ВКП обнаружителя используется перестраиваемый фильтр с полосой пропускания, равной ширине спектра сигнала Д/о- На -ом шаге поиска, =1,2../4-1, выполняется анализ одного частотного канала шириной Д/о в течение интервала времени 1k. Для удобства анализа будем считать t/c дискретной величиной численно равной T A/Q, т.е. числу некоррелированных отсчетов шума, прошедшего через фильтр [21]. По результатам анализа РУ, в данном случае однопороговое, выносит решение об отсутствии или наличии сигнала. При этом вероятности ложной тревоги и пропуска сигнала равны где W0(x,xk), (x,Tt) - плотности распределения вероятности (ПРВ) сигнала на выходе последетекторного сумматора (см. рис. 1.9), h2 - ставляющей на выходе фильтра. При линейном детекторе и отсутствии сигнала ПРВ равна [18] В присутствии сигнала с постоянной огибающей ПРВ равна и при нормальном сигнале В ходе оптимизации ожидается получение т и V приводящих к минимуму среднего времени поиска Гср с требуемой вероятностью успеха Q, либо максимума вероятности успеха при фиксированном среднем времени. Третий вариант оптимизации с фиксированными т =То и Vk Vo (см. пп. 2.1) можно взять в качестве базового, поскольку при данных ограничениях не требуется сложных вычислительных методов и перестройки РУ в ходе поиска. Характеристики поисковой процедуры определяются выражениями (1)-(4), (9)-(12) (см. пп.1.3.1). Иллюстрация метода нахождения параметров то и VQ приведена на рис. 2.1. Здесь и далее То и Гср представлены относительно интервала времени 1/А/о» а порог обнаружения нормирован на среднеквадратическое отклонение шума Со на выходе фильтра. поскольку по мере сужения области неопределенности (в данном случае анализируемого частотного диапазона), возрастает вероятность присутствия сигнала в проверяемой ячейке (частотном канале). В рамках первого варианта оптимизации предполагается, что интервал анализа т линейно возрастает от первых шагов к последним, т.е. хк =В(к—А/2)+хА/2 и при таком условии находятся оптимальные пороги Vk. При этом можно подобрать такой наклон зависимости В и такое значение интервала анализах , чтобы минимизировать Гср при требуемой вероятности успеха Q. Зависимость минимального среднего времени поиска от величины h2 представлены на рис. 2.3 и рис. 2.4. Анализ характеристик оптимизированного последовательного поиска показывает, наибольший эффект от применения перестраиваемых порога и времени анализа т имеет место при низком ОСШ h2. Поиск сигнала в виде узкополосного нормального случайного процесса занимает несколько большее время, по сравнению с сигналом с постоянной огибающей, причем при низком h2 разница меньше, чем при высоком.
Таким образом, использование самого простого вида оптимизации, предполагающего фиксированные интервал анализа на шаге поиска т = То и порог обнаружения Ук=Уо является наиболее оправданным. Поэтому в дальнейшем будет рассматриваться только данный подход. В ситуациях, когда факт обнаружения/необнаружения сигнала спустя время Гштр может быть подтвержден, поиск представляет собой циклический алгоритм [18]. Оптимизация в данном случае также состоит в выборе порога обнаружения Vo и интервала анализа То, при которых среднее время поиска минимально. Пример оптимизации циклического поиска представлен на рис. 2.5. Параметры циклического поиска с ОПРУ представлены на рис. 2.6, где рассмотрены ситуации: Гштр = 1, Гштр = 10 и Гштр = 100. Линии отражают зависимость среднего времени поиска при использовании некогерентного накопления, а маркеры без линии - зависимость без использования накопления (т0=1). Рис. 2.6. Среднее время циклического поиска, ОПРУ, А=32 Из рис. 2.6 следует, что среднее время поиска сигнала, в рамках циклического алгоритма, в значительной степени определяется величиной Гштр, особенно в области низких значений h2. Так, при h2=0 дБ изменение Гштр на порядок приводит к такому же увеличению среднего времени поиска. Применение некогерентного накопления в рамках циклического алгоритма оказывается эффективным только при большом штрафном времени ложной тревоги Гштр 100 и низком h2. Характеристики поиска нормального сигнала и сигнала с постоянной огибающей практически идентичны. В рамках двухпороговой процедуры принятия решения Вальда при получении очередного я-го отсчета сигнала с выхода фильтра вычисля ется отношение правдоподобия (ОП), которое сравнивается с двумя пороговыми уровнями где W n){x) — ПРВ п выходных отсчетов фильтра в присутствии искомого сигнала в проверяемом канале, WQ"\X) - условная ПРВ в его отсутствии. В результате сравнения выносится решение в пользу гипотезы: Л(л) : Н\ - сигнал есть в проверяемом канале; Л л) V0: Н0- сигнала нет; V0 Л(п) Vx - продолжить анализ. Если отсчеты сигнала некоррелированы (в данном случае отстоят на интервал времени т0=1/А/о), то ОП можно представить в виде Для вынесения решения ЛОП сравнивается с верхним и нижним пороговыми уровнями V\ и Го, и в случае попадания между ними вычисляется (л+1)-й ЛОП и т.д.
Математическое исследование последовательного анализа было произведено Вальдом [28], который показал, что для очень широкого класса распределений реализаций сигнала вероятность того, что поиск закончится в течение конечного времени, равна единице. ДПРУ вынесет решение о наличии сигнала в канале при следующем условии Неравенство (33) выполняется для всех х, попадающих в область принятия гипотезы Н\. Если проинтегрировать обе части (33) по этой области, то получим Интеграл в левой части (34) равен (1-/?пр), а в правой - рлт. В предположении, что при окончании проверки канала ОП (29) оказывается точно равно верхнему или нижнему порогу (нет перехода за границы), верхний пороговый уровень равен Проведя аналогичные рассуждения для нижнего порогового уровня, получим При поиске сигнала с постоянной огибающей ОП (29) будет равно откуда ЛОП равен Таким образом, при проверке А го частотного канала после получения очередного отсчета сигнала JC,- С выхода линейного детектора огибающей вычисляется отношение правдоподобия (37), сравнивается с a порогами (35), (36) и выносится решение в пользу гипотезы Н\ или Щ. В противном случае анализ частотного канала продолжается. Для нормального сигнала ОП можно вычислить как
Дихотомический поиск с ОПРУ
Использование дихотомического алгоритма для решения поисковых задач является актуальным, поскольку, в отличие от последовательного поиска, он требует N=log2(A) шагов, в то время как при последовательном поиске следует проверить в среднем (А+\)/2 гипотез. Тем не менее существуют причины, по которым эффективность дихотомии может быть ниже ожидаемой. Отправной точкой оптимизации дихотомического поиска может быть вариант, когда выделяемое на поиск время Т распределено между шагами так, что вероятность правильного решения Qk на всех шагах одинакова [55, 56, 57], т.е. равна Qk = jQt где Q - финальная вероятность успеха. При этом каждому шагу поиска соответствует время ана N лиза Ть а общее время поиска равно Т = \к. Оптимизация представим ляет собой перераспределение общего времени поиска Т между шагами с целью максимизации вероятности успеха поиска Q. Оптимизация дихотомического поиска сигнала между шагами методом динамического программирования [47, 53, 58] приведена ниже. Если на поиск из узла, находящегося на последнем уровне (см. рис.1.3), выделено время / и предыдущие шаги были безошибочными, то вероятность правильного завершения поиска qN(t) равна Та же вероятность для предпоследнего уровня равна где т - время, отводимое на (N-l)-u шаг, a (t-z) - на следующий. В общем случае для k-то шага имеем при этом (/-т) — время, отводимое на все последующие шаги. Оптимизация методом динамического программирования заключается в том, что для каждого уровня дерева поиска, начиная с последнего, рассчитывается вероятность успешного завершения поиска q if) для всех возможных значений t = Аг,2Аг,...Г, где Ах — некоторый интервал разбиения общего времени поиска Т. Расчет выполняется следующим образом: Выражение (52) представляет собой функцию Беллмана, и ее значение, рассчитанное для первого шага от аргумента Г, есть максимально достижимая вероятность успеха при заданном времени поиска Т.
Повторный проход по дереву поиска, но уже от первого уровня к последнему, позволяет восстановить значения времен анализа т#, приведших к найденной вероятности успеха. Исходя из известных т можно определить вероятности правильного решения на каждом из шагов поиска Qk. Зависимость вероятности правильного решения на шаге поиска от его длительности QSJ), входящая в (52), определяется следующими факторами: видом дихотомического обнаружителя (одноканальный или двухка-нальный); типом РУ (ОПРУ или ДПРУ Вальда); видом области неопределенности; видом искомого сигнала, например с постоянной огибающей или нормальный. Дихотомический обнаружитель сигнала с неизвестной центральной частотой можно построить по одноканальнои или двухканальнои схеме. В первом случае обнаружитель включает в себя один полосовой фильтр с перестраиваемой полосой и центральной частотой, детектор огибающей, устройство последетекторного накопления и РУ. Двухка-нальный обнаружитель имеет два фильтра, два детектора, вычитатель, устройство последетекторного накопления и РУ. В обоих случаях поиск будет двоичным, поскольку шаге поиска выносится двухальерна-тивное решение, позволяющее судить о том в какой из двух возможных поддиапазонов находится сигнал. Блок-схемы данных устройств представлены на рис. 3.1. На k-u шаге поиска анализируемая полоса частот (полоса пропускания одного фильтра) равна где k=\,N. На всех шагах поиска, кроме последнего, анализируемая полоса частот будет больше ширины спектра искомого сигнала. В присутствии белого гауссовского шума мощность прошедшей через фильтр помехи на к-м шаге равна Аналогично последовательной процедуре задача поиска может быть решена с применением ОПРУ или ДПРУ последовательного анализа Вальда. Предполагается, что на к-м шаге решение о наличии сигнала в полосе того или другого фильтра выносится на основе анализа огибающей на интервале времени Г секунд. В случае идеального П-образного фильтра отсчеты, отстоящие на тк = l/A/t , строго некоррелированы между собой и, т.к. шум - гауссовский, независимы, поэтому можно считать, что время анализа содержит nk =TkAfk независимых отсчетов шума, на основе которых принимается решение. Рассмотрим поиск сигнала с постоянной огибающей. Для одно-фильтрового обнаружителя оптимальное правило решения, основанное на критерии идеального наблюдателя, осуществляемого по выходным отсчетам детектора огибающей X = {XI,X2.JC„}, равно (55) где W{n)(X) — совместная ПРВ п отсчетов огибающей выходного сигнала фильтра в случае, если искомый сигнал есть, и W0n (X) - совместная ПРВ в отсутствии сигнала. Для к-го шага поиска сигнала с постоянной огибающей данные функции имеют вид После подстановки (56) в (55) и логарифмирования получим При выполнении данного неравенства выносится решение о том, что в полосе фильтра есть сигнал, а в противном случае, что сигнал - в смежной полосе.
Для двухфильтрового обнаружителя оптимальное правило решения, осуществляемого по выходным отсчетам детекторов огибающей В результате в обоих случаях обнаружение сводится к накоплению выходных отсчетов фильтров, прошедших через детектор огибающей с характеристикой 1п(1о(х)) и последующим сравнением накопленного значения с порогом. При большем числе накапливаемых отсчетов п, напряжение является нормальной случайной величиной с математическим ожиданием и дисперсией Вероятность вынесения правильного решения на шаге поиска с однофильтровым обнаружителем, при условии, что сигнал в полосе фильтра присутствует с вероятностью 1/2, рассчитывается как где порог Fjt , максимизирующий вероятность ь находится из квадратного уравнения, получаемого после приравнивания к нулю производной выражения (60) При использовании двухфильтрового обнаружителя распределения решающей величины по обеим гипотезам симметричны относительно нуля, поэтому вероятность вынесения правильного решения равна Ітг k+DQk) Анализ дихотомического поиска нормального сигнала представляет определенные затруднения, поскольку совместная плотность распределения вероятности W n){Xx)y входящая в (55) и (58) неизвестна. Следует подчеркнуть, что в этом случае продетектированные выходные отсчеты фильтра ду представляют собой огибающую смеси гауссовского шума, занимающего частотную полосу Afk, и сигнала полосой А/0 Afk . Поскольку отсчеты взяты с интервалом хк = 1/А/л , то, вследствие коррелированности отсчетов искомого сигнала, они также коррелированы. Поэтому совместная ПРВ Wxn){Xx) не является результатом перемножения одномерных ПРВ Wfa), как это было в случае поиска сигнала с постоянной огибающей. Тем не менее можно предположить, что однофильтровый обнаружитель нормального сигнала выглядит так же, как и сигнала с постоянной огибающей, т.е. - это детектор огибающей и накопитель. После линейного детектора сигнал имеет следующую корреляционную функцию (КФ) [40, 48]:
Поиск сигнала во временной области
В главе 2 было показано, что выражения для характеристик поиска во временной области и для раскрытия кодовой структуры идентичны, поэтому сравнительные характеристики последовательного и дихотомического алгоритмов, приведенные в данном параграфе, верны для обоих случаев. При сравнении предполагается, что ОСШ на выходе согласованного устройства (согласованного фильтра, коррелятора) одинаково для 101 обоих алгоритмов, и в ходе дальнейшей обработки осуществляется некогерентное накопление. Результаты сравнения для ОПРУ приведены на рис. 4.18-4.20. То же самое для поиска при возможности подтверждения результатов — на рис. 4.21-4.23. Как показывают рисунки, среднее время последовательного поиска ниже дихотомического. Также имеют место следующие факты. При однопроходном поиске выигрыш последовательного алгоритма падает с ростом h2; данное поведение можно объяснить повышением эффективности дихотомического алгоритма при большом ОСШ h2; выигрыш последовательного алгоритма увеличивается с ростом величины области неопределенности А; зависимость отношения средних времен поиска практически не зависит от вероятности успеха Q (в данном случае идентична для Q=0.9 и 0=0.99). При поиске с подтверждением результатов по истечении штрафного времени Гштр выигрыш последовательного алгоритма падает с ростом h , скорость роста отношения средних времен выше при низком Гщтр и падает с его увеличением; характер зависимости отношения средних времен от А определяется величиной Гштр и при малом Гштр зависимость от А практически отсутствует, а с его ростом имеет спадающий характер; выигрыш последовательного алгоритма растет с ростом штрафного времени ложной тревоги. Результаты сравнения последовательного и дихотомического поиска во временной области при использовании ДПРУ приведены на рис. 4.24-4.26. То же самое для поиска с возможностью подтверждения результатов - на рис. 4.27—4.29. 1. Проведенное сравнение одноканального и двухканального дихотомического поиска с последовательным поиском показало, что существует граничное ОСШ, при превышении которого дихотомический поиск предпочтительнее последовательного.
Данная величина имеет тенденцию к снижению с увеличением размера области неопределенности А при поиске в частотном диапазоне и к росту при поиске во временной области. 2. При поиске в частотном диапазоне граничное ОСШ ниже 0 дБ при использовании ОПРУ и порядка 3 дБ при ДПРУ. При поиске во временной области граничное ОСШ выше 10 дБ. 107 3. Выигрыш дихотомического алгоритма по времени поиска увеличивается с ростом ОСШ, достигая в пределе А/4 при поиске в частотном диапазоне и (A + l)/2\og2A при поиске во временной области. 4. Выигрыш дихотомического алгоритма при поиске в частотном диапазоне нормального узкополосного сигнала выше, чем при поиске сигнала с постоянной огибающей. В результате наблюдаются существенные отличия сравнительных характеристик поиска сигнала в частотном диапазоне и временной области, объясняемые изменением интервала корреляции помехи в ходе дихотомического поиска в частотном диапазоне. В связи с этим дихотомический поисковый алгоритм здесь является более предпочтительным. Так, его использование для поиска узкополосного сигнала с шириной спектра 30 кГц в диапазоне 3.84 МГц при ОСШ 10 дБ позволит определить центральную частоту за 0.8 мс с вероятностью успеха 0=0.99, в то время как последовательный поиск — за 2.1 мс. При поиске во временной области данное явление отсутствует и последовательный поиск быстрее дихотомического при ОСШ на выходе ВКП менее 10-15 дБ. Глава посвящена компьютерному моделированию поисковых процедур, исследование которых было проведено в предыдущих главах.
Необходимость проведения моделирования объясняется следующими причинами: в настоящее время именно моделирование является основным инструментом верификации результатов исследований; возможность создания моделей разной степени адекватности позволяет подтвердить (или опровергнуть) как потенциальные характеристики исследуемых алгоритмов и устройств, так и реально достижимые при практической реализации; в ходе анализа делаются допущения, которые приводят к расхождению теоретически полученных и экспериментальных результатов; данные расхождения могут быть оценены посредством моделирования; на основе компьютерной модели удобно оценивать сложность реализации того или иного алгоритма, которая, наряду с другими характеристиками, является фактором, позволяющим судить о его преимуществах и недостатках; моделирование позволяет проводить оптимизацию сложности устройства, реализующего тот или иной алгоритм, при невысоких временных и финансовых затратах, по сравнению с реализацией и отладкой устройств на макетах. Общая структурная схема программной модели, используемой при имитационном статистическом моделировании устройств поиска, реализующих исследуемые поисковые процедуры, показаны на рис. 5.1. Рис. 5.1. Структура программной модели Модели передатчика искомого сигнала существенно различаются для случаев поиска в частотной и временной областях, в частности, сигнал с постоянной огибающей в частотной области представлен комплексной экспонентои с частотой изменяющейся случайно от одного эксперимента к другому в пределах заданного частотного диапазона. Нормальный сигнал представлен суммой экспонент со случайными начальными фазами и частотами, определенными в [48]. Среднее значение частоты суммируемых экспонент равно центральной частоте спектра сигнала. Сигнал во временной области - это М-последовательность с периодом, много большим величины области неопределенности. Начальное состояние генератора определяет искомое событие. Модель канала распространения состоит из усилителя искомого сигнала и генератора нормального шума, добавляемого к искомому сигналу. Усилитель сигнала включен в модель канала распространения для тестирования устройств поиска при разных ОСПІ h .
