Секторе z-плоскости

Алгоритмы спектрального анализа в ограниченном

6.1. Алгоритм анализа с использованием БПФ

Пусть заданы N отсчетов сигнала, и необходимо найти z -преобразование в точках, расположенных на дуге окружности в z -плоскости. Пусть N=64, а количество искомых спектральных отсчетов, положение которых показано на рис. 6.1, а, равно 16. В данном случае выражение для z -преобразования имеет следующий вид:

так что

Из формулы (6.2) следует, что после предварительного умножения x(n) на r-ne-jnqзадача расчета z -преобразования сводится к задаче спектральных измерений на дуге единичной окружности, которая изображена на рис. 6.1, б.

Рис. 6.1. а - круговой сектор в z -лоскости; б - преобразование кругового сектора в дугу окружности с помощью предварительного умножения массива сигнала.

Для эффективности расчета спектра методом БПФ точки zk следует перераспределить таким образом, чтобы они равномерно располагались на единичной окружности. Этого можно достичь, прореживая отсчеты сигнала и комбинируя затем получающиеся спектры. Перечислим последовательность выполняемых при этом операций.

1. Вычислить 16-точечное БПФ отсчетов сигнала с номерами 0, 4, 8,..., 60, что даст X0(k).

2. Вычислить 16-точечное БПФ отсчетов с номерами 1, 5, 9,..., 61, что дает X1(k).

3. Повторить то же для отсчетов 2, 6, 10,..., 62 и 3, 7, 11,..., 63, что дает X2(k) и X3(k) соответственно.

4. Сложить коэффициенты БПФ по формуле

, (6.3)

Этот же результат можно получить иначе, вычислив 64-точечное БПФ и взяв первые 16 коэффициентов БПФ. В этом случае потребовалось бы выполнить (N/2)log2N=192 базовых операций, тогда как при использовании четырех 16-точечных преобразований их нужно было бы 128. Таким образом, в зависимости от параметров системы можно использовать по крайней мере два различных метода вычисления спектра вдоль дуги в z -плоскости, изображенной на рис. 6.1, а.

6.2. Алгоритм Блюстейна

Алгоритм БПФ позволяет существенно уменьшить время вычисления N-точечного ДПФ, но при условии, что N раскладывается на простые сомножители. Существуют другие эффективные алгоритмы расчета ДПФ последовательностей (также Nlog2N операций). Один из них, называемый алгоритмом Блюстейна, дает способ вычисления ДПФ N-точечной последовательности с помощью весовой обработки выходных отсчетов на выходе ЛЧМ-фильтра (его импульсная характеристика имеет вид колебания с линейной частотной модуляцией). Он применяется при любых N и основан на цифровой фильтрации, эквивалентной вычислению ДПФ.

Рассмотрим цифровой фильтр с импульсной характеристикой h(n) вида

Фильтр с такой импульсной характеристикой обычно называют ЛЧМ-фильтром из-за его сходства с аналоговым фильтром, согласованным с ЛЧМ-сигналом. При подаче на его вход N-точечной последовательности x(n) (отсчеты x(n) отличны от нуля только на интервале [0,N-1]) выходная последовательность y(n) (nÎ[N,2N-1]) будет равна

Введя в эту формулу новую переменную k=n-N, получим:

откуда

Из формулы (6.7) следует, что выходная последовательность y(k) равна взвешенным c весами

отсчетам ДПФ N-точечной последовательности вида

Следовательно, чтобы получить N-точечное ДПФ последовательности f(n), необходимо в соответствии с (6.7) подать на вход фильтра последовательность x(n)=f(n)ej2pn/N, а отсчеты выходной последовательности y(n) с номерами N£n£N-1 умножить на весовые коэффициенты

Все эти операции, необходимые для вычисления N-точечного ДПФ последовательности f(n), представлены на рис. 6.2.

Рис. 6.2

Для некоторых значений N (а именно, если N равно квадрату целого числа) количество операций, используемых в цифровом фильтре, может быть пропорционально N1,5.

Основной смысл алгоритма Блюстейна состоит в том, что с его помощью показана возможность получения ДПФ последовательности посредством ее фильтрации ЛЧМ-фильтром.

6.3. Алгоритм z -преобразования с использованием ЛЧМ-фильтрации

Алгоритм z -преобразования с ЛЧМ-фильтрацией является вторым эффективным алгоритмом вычисления z-преобразования конечной последовательности вдоль определенного контура на z-плоскости. Этот алгоритм также используется для вычисления ДПФ последовательности даже при простых N.

Пусть заданная N-точечная последовательность {x(n)}, 0£n£N-1, имеет z -преобразование

ДПФ X(k) заданной последовательности по определению равно

Используя алгоритм z -преобразования с ЛЧМ-фильтрацией, можно найти z -преобразование в соответствии с формулой (6.3) вдоль контура более общего вида:

Здесь M - произвольное целое число (не обязательно равное N), а А и W - произвольные комплексные числа, равные

На рис. 6.3 изображен контур в z -плоскости, удовлетворяющий формуле (6.10), и графически представлены величины A0, W0, q0и j0.

Рис. 6.3. Контур расчета z -преобразования с ЛЧМ-фильтрацией в z-плоскости.

Как следует из рис. 6.3 и формул (6.10) - (6.12), при A=1, M=N и W=ej2p/N имеем zk=ej2pk/N, т. е. точки вдоль контура будут соответствовать положениям спектральных отсчетов при вычислении N-точечного ДПФ последовательности.

Постоянная W0определяет скорость ухода контура внутрь окружности радиуса A0или наружу от нее. При W0>1 контур будет скручиваться, а при W0<1 - раскручиваться. Несколько проще интерпретировать скручивание контура в z -плоскости, рассматривая эквивалентный контур в s -плоскости. Введя подстановку

получим

или

Далее, поскольку

то

На рис. 6.4, в в s -плоскости изображен контур, эквивалентный контуру, показанному на рис. 6.1, а. Таким образом, спиралеобразные контуры в z -плоскости соответствуют прямым линиям в s -плоскости, причем скорость закручивания определяет угол наклона прямой в s -плоскости.

Рис. 6.4. Контур расчета z -преобразования с ЛЧМ-фильтрацией в s -плоскости

Покажем теперь, как эффективно расчитывать z -преобразование последовательности согласно формуле (6.8) вдоль контура (6.10). Обозначив через Xkискомые значения z -преобразования при z=zk, т. е.

и учитывая (6.10), находим

Подстановка в формулу (6.14) выражения

дает

или

, где

Из (6.17) видно, что значения Xkможно найти, рассчитав взвешенную свертку последовательностей y(n) и v(n); последнее можно эффективно провести, используя алгоритм быстрой свертки на основе БПФ. На рис. 6.5 приведены все основные операции алгоритма z-преобразования с ЛЧМ-фильтрацией.

Рис. 6.5

Прежде, чем перейти к детальному описанию алгоритма z -преобразования с ЛЧМ-фильтрацией, перечислим преимущества этого алгоритма по сравнению со стандартным алгоритмом БПФ:

1) Число отсчетов входной последовательности N не обязательно должно быть равно числу точек M, в которых рассматривается z- преобразование.

2) Ни N, ни M могут не быть составными числами; в частности, они могут быть простыми.

3) Угловое смещение точек zkможет быть произвольным, так что и частотное разрешение может быть любым.

4) Контур не обязательно должен быть окружностью в z -плоскости. В частности, использование спиралевидного контура в анализаторе речи дает некоторые преимущества.

5) Начальная точка контура в z -плоскости произвольна. Это свойство особенно полезно при анализе в узкой полосе, когда высокое частотное разрешение (п. 3) сочетается с произвольной начальной частотой.

6) При A=1, M=N и W=e-j2p/N z -преобразования с ЛЧМ-фильтрацией выполняются в несколько следующих этапов, иллюстрируемых с помощью рис. 6.5:

a) Выбор L - наименьшего целого числа, большего или равного (N+M-1), которое можно было бы использовать в обычном алгоритме БПФ. Величина L определяет размер преобразований, которые выполняются при расчете быстрой свертки в системе, изображенной на рис. 6.5.

Рис. 6.6. Последовательность выполнения алгоритма z -преобразования с

ЛЧМ-фильтрацией

б) Формирование L-точечной последовательности y(n) вида

Типичные последовательности x(n) и y(n) изображены на рис. 6.6, а и б.

в) Расчет L-точечного ДПФ последовательности y(n) с помощью обычного алгоритма БПФ, результаты расчета обозначаются через Yr. На рис. 6.6, в изображена типичная последовательность Yr.

г) Формирование L-точечной последовательности v(n) по формуле

Последовательности и v(n) изображены на рис. 6.6, г и д соответственно.

д) Расчет L-точечного ДПФ последовательности v(n), результаты которого обозначаются через Vr(рис. 6.6, е).

е) Почленное умножение последовательностей Vrи Yr, что дает Gr=VrYr(рис. 6.6, ж).

ж) Расчет обратного ДПФ последовательности Gr, результаты которого обозначаются через gk(рис.6.6, з).

з) Умножение gkна Wk2/2, что дает Xk, т. е.

Значения gkпри k³M не имеют смысла и отбрасываются.

Последовательность Xkизображена на рис. 6.6, и.

Остается показать, что алгоритм z -преобразования с ЛЧМ-фильтрацией эффективнее прямого вычисления z -преобразования заданной последовательности. Для этого достаточно подсчитать число комплексных умножений, используемых при выполнении z -преобразования с ЛЧМ-фильтрацией. Подсчет показывает, что основными операциями при вычислении z -преобразования с ЛЧМ-фильтрацией являются три (иногда два) L-точечных БПФ, поэтому время вычисления будет пропорционально Llog2L (напомним, что L³N+M-1), но только коэффициент пропорциональности будет в два-три раза больше, чем при БПФ. Таким образом, рассматриваемый алгоритм является эффективным инструментом расчета z-преобразования последовательности вдоль определенного контура в z -плоскости.

Дата добавления: 2015-05-09