К. т. н. Егоров А. Е.

Казанский национальный исследовательский технический университет

  имени А. Н. Туполева, Российская Федерация

В ычислительная сложность поликорреляционных алгоритмов обработки сигналов

 

Для оценки вычислительной сложности поликорреляционных алгоритмов обработки сигналов, в частности марково-смешанного полигауссового (МС-ПГ) алгоритма разрешения сигналов синтезированного в [1] устройства разрешения и подобного класса алгоритмов произведен анализ зависимости числа матричных операций умножения, необходимых для реализации алгоритма работы устройства от числа сигналов в ансамбле J и числа одновременно разрешаемых сигналов R . В общем случае число возможных гипотез, просчитываемых в процессе работы алгоритма, определяется как , где -максимальное число сигналов одновременно присутствующих во входном колебании. Это число гипотез можно представить в виде многослойной структуры, где каждый из слоев соответствует определенному числу одновременно присутствующих сигналов; номер слоя перекрывает все многообразие ситуаций от (сигналы отсутствуют, присутствует только шум) до (присутствует шум и R сигналов разных (одинаковых) типов). Определим общее число возможных ситуаций на входе устройства при условии, что ансамбль состоит из J типов сигналов. Для простоты положим, что распределение каждого сигнала в рамках k-й временной позиции аппроксимируется набором равного числа N гауссовских компонент (т. е. примем число компонент распределения элементарных сигналов   равным N).

Объединим в слое все ситуации с одинаковым числом сигналов безотносительно к их типам. Тогда число гипотез о комбинациях сигналов в r-м слое составит ( , т. к. в этом случае присутствует только шум):

,                           (1)

а общее число комбинаций гауссовских компонент в r-м слое составит:

,                          (2)

Общее число отношений правдоподобия, которое необходимо вычислить на k-м шаге работы алгоритма ( k-й временной позиции) составит:

,                          (3)

Число матричных операций умножения в этом случае равно числу отношений правдоподобия .

На рис. 1 показано многослойное представление процесса работы алгоритма для случая J=10, R=10.

 

Рис. 1. Многослойная структура процедуры формирования функционалов

отношения правдоподобия МС-ПГ алгоритма разрешения МЭС

 

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

С помощью пакета Mathcad Prime был произведен анализ зависимости числа частных функционалов отношения правдоподобия, вычисляемых в процессе работы МС-ПГ алгоритма разрешения МЭС, от числа разрешаемых сигналов и числа сигналов в ансамбле. Результаты оценки представлены на рис. 2, рис. 3.

Рис. 2. Зависимость числа функционалов отношения правдоподобия

МС-ПГ алгоритма полного разрешения от числа сигналов в ансамбле (при R=1..10)

Рис. 3. Зависимость числа функционалов отношения правдоподобия МС-ПГ алгоритма

полного разрешения от числа одновременно разрешаемых сигналов (при J=1..10)

 

Видно, что число частных функционалов отношения правдоподобия, а соответственно и вычислительная сложность, растет по показательному закону при увеличении как числа сигналов в ансамбле J, так и при увеличении числа одновременно разрешаемых сигналов R, и при J>10 и R>10 превышает величину 10 ¹⁰ , что крайне затрудняет практическую реализацию синтезированных оптимальных алгоритмов разрешения. Вообще говоря, оптимальный приёмник существует строго в рамках задачи, в которых он синтезирован. И, поскольку исчерпывающее описание реальных сигнально-помеховых ситуаций крайне затруднительно, а выбранный критерий качества, так или иначе, приносит ошибки, то актуальным становится вопрос о синтезе квазиоптимальных методов приема. Тем более что оптимальный приемник практически реализовать почти невозможно, поэтому оптимальные алгоритмы имеют ценность, прежде всего в теоретическом отношении и для расчетов потенциальной помехоустойчивости в сложном комплексе помех.

 

Список использованных источников:

1.              Патент РФ №2269205 от 27.01.2006 г. Устройство разрешения сигналов на фоне произвольной помехи / [Ш. М. Чабдаров , А. Ф. Надеев , Р. Р. Файзуллин , А. Е. Егоров].