6.6. АЛГОРИТМ ПРЕРЫВИСТОГО Z-ПРЕОБРАЗОВАНИЯ

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

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

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

Другой процедурой, которая во многих ситуациях наиболее эффективна, является алгоритм прерывистого -преобразования Этот алгоритм предназначен для вычисления -преобразования на спиральном контуре с точками, равноудаленными по углу на некоторой части спирали. А именно, пусть обозначает точечную последовательность, — ее -преобразование. Используя алгоритм прерывистого -преобразования, можно вычислить в точках вида

где положительные действительные числа.

Следовательно, контур, на котором получаются выборки, имеет вид, показанный на рис. 6.31.

Этот контур является спиралью на -плоскости. Параметр управляет смуростью «закрутки» спирали; если больше единицы, то спираль закручивается к началу координат при увеличении к, а если меньше единицы, то спираль раскручивается при увеличении Параметры определяют расстояние от начала координат и угол первой

Рис. 6.31. Контур В Z-ПЛОСКОСТИ для прерывистого -преобразования

выборки (т. е. при ) соответственно. Остальные выборки расположены по спиральному контуру с угловым разносом Следовательно, если то спираль в действительности является дугой окружности, и при эта дуга является частью единичной окружности.

При определяемых выражением (6.38), необходимо вычислить

где является длиной последовательности Используя тождество

выражение (6.39) можно записать в виде

Полагая можно записать

В , представленном в виде (6.41), узнаем свертку последовательности с последовательностью Поэтому вычисления по (6.41) можно представить так, как показано на рис. 6.32, где Если А и равны единице, то последовательность можно понимать как комплексную экспоненциальную последовательность с линейно-нарастающей частотой. Системы, аналогичные изображенным на рис. 6.32, обычно используются при спектральном анализе в радиолокации.

Рис. 6.32. Интерпретация выражения (6.41) как операций, производимых линейной системой

Так как последовательность имеет конечную длительность, то согласно гл. 3 свертка (6.41) может быть выполнена с помощью дискретного преобразования Фурье, с использованием, конечно, алгоритма

В то время как последовательность имеет конечную длительность, последовательность имеет бесконечную длительность. Следовательно, если выполнять свертку с помощью

дискретного преобразования Фурье, то придется разбивать последовательность на секции. Отметим также, что, хотя результат свертки имеет бесконечную длительность, нам нужны только выборки при Следовательно, при секционировании последовательности было бы полезно выбрать секции так, чтобы результат вычисления одной секции давал М требуемых выходных точек. На рис. 6.33 изображены последовательности, участвующие в этом процессе, для случая Последовательности изображены на рис. 6.33 а, б соответственно.

Рис. 6.33. Последовательности в алгоритме при

Для получения результата в промежутке от 0 до при осуществлении свертки необходима только часть последовательности а именно часть от до включая конечные точки. Эта часть последовательности расположена между штриховыми линиями А и В на рис. 6.33 б.

Следовательно, свертка может быть осуществлена посредством вычисления -точечного ДПФ от (пополненной, конечно, нулем) и -точечного ДПФ части последовательности в области от A до Б на рис. 6.33 б.

Обратное преобразование от произведения этих двух дискретных преобразований Фурье будет круговой сверткой последовательности с секцией последовательности Как ясно из рассмотрения метода перекрытия с накоплением, часть круговой свертки будет соответствовать линейной свертке, а оставшаяся часть не будет. Можно сделать так, что «хорошие» точки появятся в интервале считая индекс вычетом по модулю Это означает, что требуется вычислять ДПФ последовательности вида

изображенной на рис. 6.33 в. Если перемножить дискретные преобразования Фурье последовательностей то первые М

значений обратного преобразования будут требуемыми значениями свертки Чтобы получить требуемые М значений согласно (6.41), нужно произвести умножение на

В предыдущем обсуждении порядок ДПФ, которое необходимо вычислить, был равен Если для вычисления дискретного преобразования Фурье требуется применить алгоритм, рассчитанный на число точек, равное степени 2, то это можно легко сделать, пополняя -точечные последовательности достаточным числом нулей с тем, чтобы их полная длина равнялась степени 2. Так как число комплексных умножений, требуемых для вычисления каждого ДПФ, имеет порядок то ясно, что общее количество арифметических операций для вычисления по (6.39) с использованием алгоритма пропорционально

В противоположность этому прямой метод вычисления по (6.39) потребует количество операций, пропорциональное Ясно, что прямой метод будет наиболее эффективен для малых М и Однако для достаточно больших М и (порядка 50) алгоритм будет и самым эффективным.

Вдобавок к высокой эффективности обеспечивает большую гибкость при вычислении йыборок

z-преобразования последовательности конечной длины. Нам не требуется выполнения равенства как в случае рассмотренных алгоритмов БПФ, а также не требуется, чтобы и М были составными числами с большим числом сомножителей; они могут быть простыми, если угодно. Тогда как в алгоритме БПФ требуется, чтобы параметр был равен в алгоритме — произвольно. К тому же выборки -преобразования берутся на контуре более общего вида, частным случаем которого является единичная окружность.

Рис. 6.34. Использование алгоритма

а) диаграмма полюсов для синтетического речевого сигнала; б) расчеты -преобразования для нескольких спиральных контуров [13]

Алгоритм является примером того, как можно осуществить анализ Фурье при помощи линейной фильтрации (алгоритм Герцеля является другим таким примером). В [15] показано, что аналогичная процедура может быть использована для вычисления дискретного преобразования Фурье при простом

Пример. Пример использования алгоритма для обострения резонансных пнков посредством вычисления -преобразования вне единичной окружности показан на рис. 6.34. Анализируемый сигнал является отрезком конечной длины синтетического речевого сигнала. Этот речевой сигнал был получен путем возбуждения пятиполюсной системы периодической импульсной последовательностью. Имитируемая система соответствовала частоте выборок Полюсы соответствовали центральным частотам и 4500 Гц с полосами 30, 50, 60, 87 и 140 Гц соответственно.

На рис. 6.34 а изображена диаграмма полюсов, используемых для генерации сигнала. Алгоритм был применен к одному периоду исходных данных в установившемся режиме при пяти различных значениях Результаты показаны на рис. 6.346. Первые два спектра соответствуют спиральным контурам вне единичного круга; при этом произошло расширение резонансных пиков. Значение соответствует вычислению -преобразовання на единичной окружности. При дальнейшем увеличении контур проходит внутри единичного круга, приближаясь к полюсам, что приводит к обострению резонансных пиков.