DETECTION OF VACANT UNOCCUPIED FREQUENCY SUB-BANDS BY COMPRESSED MEASUREMENTS

Full Text

Введение Развитие микропроцессорной техники в последние десятилетия привело к тому, что операции обработки сигналов все чаще реализуются в цифровой форме. Причем оцифровка сигналов может осуществляться непосредственно на несущей частоте. В этом случае аналого-цифровой преобразователь подключается непосредственно к выходу антенны через согласующий усилитель. Преимущество такого построения заключается в том, что при этом исключаются операции преобразования частоты, детектирование сигналов с выделением их огибающей, что сокращает энергетические потери, повышает чувствительность приемной системы и упрощает аппаратурную реализацию [1]. Рассмотрим возможность применения полностью цифровой обработки в системах когнитивного радио (Cognitive Radio) [2], в которых обязательной процедурой является исследование определенного частотного диапазона с целью поиска в нем «свободных» частотных интервалов. Для этого заданный частотный диапазон разбивается на подынтервалов и в каждом из них вычисляется энергия реализации в течение некоторого времени . Представим выходной сигнал i-го частотного подынтервала в виде . Здесь - j-ый временной отсчет на выходе полосового фильтра с центральной частотой ; - число временных отсчетов; - вектор-столбец размера , описывающий выходной сигнал i-го полосового фильтра; «» - операция транспонирования; - вектор размера , описывающий отсчеты входной реализации; - матрица размера , элементы которой представляют собой отсчеты импульсной характеристики полосового фильтра. Таким образом, после описанных преобразований наблюдаемые данные можно представить в виде вектора с элементами , где - матрица размера (). Имея отсчетов и сравнивая их с определенным пороговым значением, можно определить номера каналов, в которых присутствует только шум, и каналов, «занятых» различными средствами. Следует отметить, что число операций умножения, требуемых для формирования всех отсчетов достаточно велико и составляет . Кроме того, требуется достаточно большая память для запоминания элементов матрицы . Действительно, размер одной матрицы составляет , а всего таких матриц . Уменьшить число операций, а также объем требуемой памяти позволяет подход, идея которого состоит в следующем. Возьмем матрицу размера () со случайными элементами и умножим ее на вектор . В результате получим вектор размера с элементами , , где . Отметим, что размер вектора () намного меньше размера вектора (), так как . При этом задача сведется к следующей. Необходимо по наблюдениям найти размера при условии, что . Подобная задача, естественно, в общем виде не решается. Однако в предположении о разреженности вектора она может быть решена. Подходы к ее решению изложены ниже. Compressive Sensing В последние годы активно развивается новая область получения и обработки информации, получившая в англоязычной литературе название Compressive Sensing (CS). Согласно этой теории сигналы, имеющие разреженное или сжатое представление в некотором базисе, могут быть точно или приближенно восстановлены по своим линейным проекциям, причем число этих проекций может быть значительно меньше размерности исходного сигнала. Рассмотрим основы этой теории. Пусть имеется дискретный сигнал, который может быть представлен вектором размера . Любой сигнал в может быть представлен в некотором базисе, образованном векторами , каждый из которых имеет размер . Используя базисную матрицу со столбцами, образованными этими векторами, сигнал может быть выражен в матричной форме как , (1) где - вектор-столбец коэффициентов . Сигнал называется -разреженным, если он является линейной комбинацией только базисных векторов, т.е только компонент в (1) отличны от нуля (, где норма определяет количество ненулевых компонент вектора ), а остальные равны нулю [3]. Следует отметить, что для вектора уже изначально может быть справедливо условие , то есть он может быть сразу разреженным без представления его в соответствующем базисе, однако здесь рассмотрен более общий случай. Наряду с определением -разреженных сигналов введем определение сжимаемых сигналов, наиболее часто встречающихся на практике. Сигнал называется сжимаемым, если у него есть представление в виде формулы (1), в которой только несколько компонент достаточно велики, а остальные относительно малы. Такие сигналы могут быть аппроксимированы разреженными сигналами, что лежит в основе трансформирующего кодирования. Недостатки, присущие традиционным способам кодирования, могут быть устранены в рамках теории CS за счет непосредственного представления сигнала в сжатой форме без промежуточного этапа получения отсчетов сигнала [3]. Рассмотрим линейный процесс измерения, в результате которого вычисляются скалярных произведений вектора и векторов , как . Если значения представить в виде вектора, а записать в качестве рядов матрицы , то в матричном виде линейный процесс измерения может быть записан как , (2) где - матрица размера . Задача состоит в том, чтобы восстановить вектор по совокупности его линейных измерений, то есть по вектору . Так как , система уравнений (2) является недоопределенной, а следовательно, имеет бесконечное множество решений. То есть однозначно восстановить вектор без дополнительной информации невозможно. Однако, если учесть, что восстанавливаемый сигнал является разреженным или сжимаемым, то при определенных условиях это становится возможным. По сути, сформулированная выше задача и есть стандартная задача CS [3]. Практический интерес в рамках этой теории представляет случай . Система уравнений (2) для -разреженного сигнала в случае, когда местоположения отличных от нуля компонент известны, может быть решена при условии . Необходимым и достаточным условием того, чтобы эта задача была хорошо обусловленной, является то, что для любого вектора , у которого имеются те же ненулевых компонент, что и в , и для некоторого справедливо неравенство [3]: . (3) Здесь - норма вектора понимается традиционным способом [4]: В общем случае местоположения отличных от нуля компонент в векторе неизвестны, однако выполнение условия (3) для произвольных -разреженных векторов является достаточным для обеспечения возможности стабильного решения задачи для любого -разреженного вектора [3]. В литературе по CS чаще используется другое условие, называемое свойством ограниченной изометрии (Restricted Isometry Property или RIP) [4]: матрица , размерности удовлетворяет свойству RIP порядка , если существует параметр , такой что для всех -разреженных векторов справедливо неравенство . (4) Для восстановления -разреженного сигнала при наблюдении с помехами или сжимаемого сигнала, достаточным является выполнение условий (3)-(4) для произвольного -разреженного вектора [3]. Прямое построение матрицы измерений такой, чтобы обладала свойством RIP, требует проверки выполнения условия (4) для каждой из возможных комбинаций положений отличных от нуля компонент в векторе длины . Однако свойство RIP может быть достигнуто с большой вероятностью за счет выбора случайной матрицы в качестве , то есть за счет рандомизации процесса измерения. При этом вектор результатов измерений представляет собой набор различных линейных комбинаций компонент вектора со случайно выбранными весами [3-5]. В общем случае, как отмечается в [4], для того, чтобы матрица удовлетворяла свойству RIP, на распределение случайных величин, выступающих элементами матрицы, необходимо наложить два условия. 1) Математическое ожидание квадрата случайной величины , то есть и, следовательно, дисперсия . 2) Распределение должно быть субгауссовским, что означает существование константы , такой, что для всех . Примерами субгауссовского распределения являются нормальное распределение, распределение Бернулли и др. Алгоритм восстановления сигнала должен на основании вектора измерений , матрицы размера (или в случае случайного характера ее формирования зная закон, в соответствие с которым она была сгенерирована), а также базиса восстановить сигнал длины или разреженный вектор коэффициентов при условии, что [3]. Наиболее эффективно задачу CS можно решить посредством минимизации нормы [3-6]: , при условии, что . (5) Это задача выпуклой оптимизации, поскольку норма является выпуклой функцией, которая может быть сведена к задаче линейного программирования, известной как выбор базиса (basis pursuit). На практике чаще встречается ситуация, описываемая не моделью (2), а моделью вида , (6) в которой вектор размера является шумовой составляющей. Вектор может представлять собой неслучайный, но неизвестный процесс, а может быть задан так, что каждый его элемент будет случайной величиной, распределенной по некоторому закону. Модель (6) является более адекватной чем (2), поскольку в любых реальных устройствах полученные данные, представленные вектором , будут искажены по крайней мере незначительным по величине шумом (с точки зрения какой-либо из его норм), что можно учесть введением дополнительного шумового вектора . Задача восстановления исходного вектора по вектору шумовых данных на основе модели (6) также может быть решена с использованием -минимизации [3-6]: , при условии, что , (7) где параметр ограничивает величину шума (в смысле какой-либо из его норм). Часто исходный дискретный сигнал может быть подвержен влиянию шума , до его преобразования в устройстве-сенсоре, то есть до осуществления линейного процесса измерения. Тогда имеем модель вида . Задача восстановления вектора в этом случае может быть записана аналогично (7) (см., например, [7]). Следует отметить, что существуют различные методы решения задач типа (5) и (7). Одними из таких методов являются так называемые «грубые» алгоритмы (greedy algorithms). К ним относятся Matching Pursuit (MP) [8], Compressive Sensing Matching Pursuit (CoSaMP) [9] и др. Оценка позиций ненулевых компонент в дискретном сигнале по совокупности его отсчетов в «сжатой» форме Рассмотрим задачу оценки положений ненулевых компонент вектора (сигнала) размера , с количеством ненулевых составляющих , где - вектор неизвестных параметров сигнала, () - номера позиций ненулевых элементов вектора . Пусть исходный вектор наблюдается на фоне шума с элементами (), представляющими собой гауссовские случайные величины с нулевыми математическими ожиданиями и одинаковыми дисперсиями , так что наблюдаемые данные до их преобразования в устройстве-сенсоре могут быть представлены в виде , где ,,- векторы размера . Пусть оценка позиций ненулевых компонент вектора осуществляется на основе анализа нового вектора размера , полученного из входного вектора в результате преобразования в устройстве-сенсоре вида , (8) где - матрица размера , а выбирается из условия . Каждый элемент нового вектора представляет собой взвешенную сумму элементов вектора , где в качестве весов выступают элементы строк матрицы . Возвращаясь к задаче и обозначениям, использованным во введении, нетрудно заметить, что эквивалентно ; вектор эквивалентен ; - математическое ожидание ; - флуктуационная составляющая ; эквивалентен . В данной работе матрица формируется так, что ее элементы () представляют собой независимые и одинаково распределенные случайные величины, имеющие распределение Бернулли, то есть с вероятностью 0,5. В настоящей работе рассмотрены два способа решения поставленной задачи: байесовский алгоритм оценки и алгоритм оценки, основанный на теории CS [10]. Байесовский алгоритм оценки. Оценка векторного параметра может быть найдена как положение абсолютного максимума отношения правдоподобия [11-12] , (9) где и - плотности вероятности вектора соответственно при наличии и отсутствии сигнала (занятых каналов), - вектор неизвестных значений отличных от нуля компонент. Для данной задачи логарифм отношения правдоподобия определяется выражением . (10) Если значения () неизвестны, то необходимо найти их оценки , решив систему уравнений относительно этих переменных [11-12] , , (11) где - вектор оценок значений ненулевых компонент. На основе (10) систему (11) можно записать следующим образом: , . (12) Найденные в результате решения системы (12) оценки () должны быть подставлены в (10), после чего оценка векторного параметра может быть найдена как положение абсолютного максимума получившегося выражения для логарифма отношения правдоподобия. Если значения () известны, то в (9) имеет место . Пренебрегая в (10) последним слагаемым, не зависящим от и отбрасывая постоянный множитель , получим выражение для достаточной статистики в виде (13) Если все значения ненулевых компонент являются известными и равными по величине, то есть (), то вместо (13) (с точностью до множителя ) будем иметь .(14) Оценка векторного параметра может быть найдена как положение абсолютного максимума достаточной статистики (13) или, в частном случае, (14), то есть как . (15) Точнее, под оценкой будем понимать новый вектор, компонентами которого являются полученные согласно (15) значения , , отсортированные в неубывающем порядке. Алгоритм оценки, основанный на теории CS. Согласно (8) после преобразования в устройстве-сенсоре вектор данных может быть представлен в виде , (16) где первое слагаемое представляет собой сигнал в «сжатой» форме (- исходный сигнал, подлежащий восстановлению), а второе является шумовой составляющей, представленной вектором , каждый элемент которого представляет собой гауссовскую случайную величину с нулевым математическим ожиданием и дисперсией . Поскольку сигнал является разреженным, то есть содержит ненулевых составляющих, где - общее число элементов в векторе, то задача оценки положений ненулевых компонент сигнала может быть решена с использованием методов теории CS. В качестве такого метода в данной работе был выбран алгоритм Compressive Sensing Matching Pursuit (CoSaMP), подробно описанный в [9]. Этот итерационный алгоритм относится к группе так называемых «грубых алгоритмов». Входными данными для него в рассматриваемом случае являются: - матрица измерений , построенная в соответствие с методом, описанным выше; - вектор данных , имеющий вид (16); - разреженность восстанавливаемого сигнала, которая принимается равной , то есть равной разреженности исходного сигнала ; - критерий остановки работы алгоритма. Сигнал, восстановленный с использованием алгоритма CoSaMP, будет содержать только ненулевых компонент. Если номера позиций этих ненулевых элементов представить в виде вектора, записав их в порядке возрастания, то полученный вектор и будет оценкой векторного параметра . Применим изложенные выше алгоритмы для оценки положений одной () и двух () одинаковых ненулевых компонент вектора. Тогда при достаточная статистика для байесовского алгоритма оценки (14) может быть записана как , а при в виде , где - вектор неизвестных параметров сигнала. Для определенности положим , где - число элементов в векторе . В качестве критерия остановки для алгоритма CoSaMP выберем достижение им в цикле заданного числа итераций, которое установим равным 20 [9]. В качестве характеристик оценки рассмотрим ее безусловное смещение и рассеяние. По результатам проведенного статистического моделирования (количество испытаний для каждого набора параметров составляло не менее 20000) для двух случаев и были получены зависимости смещения и рассеяния оценки от различных параметров для описанных выше алгоритмов. Истинные значения оцениваемых параметров, то есть номера позиций ненулевых составляющих в векторе , менялись от реализации к реализации по случайному закону с равномерным распределением на интервале . Причем для случая , то есть когда вектор содержал две ненулевые компоненты, были исключены из рассмотрения ситуации, когда номера позиций ненулевых составляющих совпадали. Также от реализации к реализации менялся вид матрицы при прежнем алгоритме ее формирования. На рис.1 изображена зависимость рассеяния оценки, нормированного на рассеяние оценки при наличии только аномальных ошибок, от отношения сигнал/шум для ряда значений в случае оценки положения одной ненулевой компоненты () байесовским алгоритмом (кривые 1 и 5) и алгоритмом CoSaMP (кривые 2 и 6), построенные при соответственно . Рис. 1. Зависимость рассеяния оценки от отношения «сигнал/шум» для байесовского алгоритма оценки и алгоритма CoSaMP при различных значениях Также на рис. 1 для случая , то есть в случае оценки положений двух ненулевых компонент, при тех же значениях изображена зависимость среднего для этих двух компонент рассеяния от отношения «сигнал/шум» для ряда значений при оценке байесовским алгоритмом (кривые 3 и 7) и алгоритмом CoSaMP (кривые 4 и 8). Рис. 2. Зависимость рассеяния оценки от отношения для байесовского алгоритма оценки и алгоритма CoSaMP при различных значениях На рис. 2 изображена зависимость нормированного рассеяния оценки от отношения для ряда значений в случае оценки положения одной ненулевой компоненты () байесовским алгоритмом (кривые 1 и 5) и алгоритмом CoSaMP (кривые 2 и 6), построенные при соответственно . Также на этом рисунке для случая , то есть в случае оценки положений двух ненулевых компонент, и при тех же значениях изображена зависимость среднего для этих двух компонент рассеяния от отношения для ряда значений при оценке байесовским алгоритмом (кривые 3 и 7) и алгоритмом CoSaMP (кривые 4 и 8). Как следует из анализа приведенных рисунков, байесовский алгоритм оценки и алгоритм оценки на основе использования метода CoSaMP дают примерно одинаковые результаты. Однако следует отметить, что с увеличением числа оцениваемых параметров, в данном случае позиций ненулевых компонент в исходном разреженном дискретном сигнале, обработка байесовским методом требует значительно большего времени, чем методом, основанным на алгоритме CoSaMP. Как показывают расчеты, смещение обеих оценок (байесовской и CS ) с ростом как , так и параметра , достаточно быстро стремится к нулю, то есть эти оценки, по крайней мере асимптотически, можно считать несмещенными. Кроме того, характеристики обеих оценок с ростом числа ненулевых компонент в векторе ухудшаются незначительно (по крайней мере, при значениях ).

About the authors

Vladimir Ivanovich Parfenov

Voronezh State University

Email: vip@phys.vsu.ru

Dmitry Yurievich Golovanov

Voronezh State University

Email: golovanov@amm.vsu.ru

References

Supplementary files