Chirp Z-преобразование

Чирповое Z-преобразование ( CZT ) является обобщением дискретного преобразования Фурье (ДПФ). В то время как ДПФ производит выборку плоскости Z в равномерно расположенных точках вдоль единичной окружности, Чирп-Z-преобразование преобразует выборки вдоль спиральных дуг в плоскости Z, что соответствует прямым линиям в S. плоскости ДПФ, реальное ДПФ и масштабируемое ДПФ можно рассчитать как частные случаи CZT.

В частности, преобразование Z с чирпом вычисляет преобразование Z в конечном числе точек z _k вдоль логарифмического спирального контура, определяемого как:

$X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}$

$z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1$

где A — комплексная начальная точка, W — комплексное соотношение между точками, а M — количество точек для расчета.

Как и ДПФ, чирповое Z-преобразование может быть вычислено за O( n log n ), где $n=\max(M,N)$. Алгоритм O( N log N ) для обратного чирпового Z-преобразования (ICZT) был описан в 2003 году: и в 2019 году.

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

Алгоритм Блюстейна выражает CZT как свертку и эффективно реализует ее с помощью БПФ /ОБПФ.

Поскольку ДПФ является частным случаем ЦЗТ, это позволяет эффективно вычислять дискретное преобразование Фурье (ДПФ) произвольных размеров, включая простые размеры. (Другой алгоритм для БПФ простых размеров, алгоритм Рейдера , также работает, переписывая ДПФ как свертку.) Он был задуман в 1968 году Лео Блюстейном . Алгоритм Блюстейна можно использовать для вычисления более общих преобразований, чем ДПФ, на основе (одностороннего) z-преобразования (Rabiner et al. , 1969).

Напомним, что ДПФ определяется по формуле

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.$

Если заменить произведение nk в показателе на тождество

$nk={\frac {-(k-n)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}$

таким образом мы получаем:

$X_{k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{-{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(k-n)^{2}}\qquad k=0,\dots ,N-1.$

Это суммирование представляет собой в точности свертку двух последовательностей a _n и bn _, определяемых формулой:

$a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}$

$b_{n}=e^{{\frac {\pi i}{N}}n^{2}},$

с результатом свертки, умноженным на N фазовых коэффициентов b _k ^* . То есть:

$X_{k}=b_{k}^{*}\left(\sum _{n=0}^{N-1}a_{n}b_{k-n}\right)\qquad k=0,\dots ,N-1.$

Эта свертка, в свою очередь, может быть выполнена с помощью пары БПФ (плюс заранее вычисленного БПФ комплексного чирпа b _n ) с помощью теоремы о свертке . Ключевым моментом является то, что эти БПФ не имеют одинаковой длины N : такую ​​свертку можно точно вычислить на основе БПФ только путем дополнения ее нулями до длины, большей или равной 2 N –1. В частности, можно дополнить до степени двойки или какого-либо другого сложного размера, для которого БПФ может быть эффективно выполнено, например, с помощью алгоритма Кули-Тьюки за время O( N log N ). Таким образом, алгоритм Блюстейна обеспечивает O( N log N ) способ вычисления ДПФ простого размера, хотя и в несколько раз медленнее, чем алгоритм Кули-Тьюки для составных размеров.

Использование заполнения нулями для свертки в алгоритме Блюстейна заслуживает дополнительного комментария. Предположим, мы заполняем нулями до длины M ≥ 2 N –1. Это означает, что a _n расширяется до массива An _{= 0} длины M , где A _n = a _n для 0 ≤ n < N и A _n в противном случае — обычное значение «дополнения нулями». Однако из-за члена b _{k – n} в свертке так и отрицательные значения n требуются для b _n (отметим, что b _{– n} = bn _{как положительные ,} ). Периодические границы, подразумеваемые ДПФ массива, дополненного нулями, означают, что – n эквивалентно M – n . , bn _n расширяется до массива n _длины M , где B ₀ = b ₀ , B _n = BM _{Таким образом – n} = bn _B для 0 < n < N и B _{= 0 в противном} случае. Затем A и B подвергаются БПФ, умножаются поточечно и подвергаются обратному БПФ для получения свертки a и b в соответствии с обычной теоремой о свертке.

Давайте также уточним, какой тип свертки требуется в алгоритме Блюстейна для ДПФ. Если бы последовательность bn _{, а} была периодической по n с периодом N , то это была бы циклическая свертка длины N заполнение нулями было бы сделано только для удобства вычислений. Однако, как правило, это не так:

$b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}\left[e^{{\frac {\pi i}{N}}(2Nn+N^{2})}\right]=(-1)^{N}b_{n}.$

Следовательно, для N даже свертка является циклической, но в этом случае N является составным , и обычно можно использовать более эффективный алгоритм БПФ, такой как Кули – Тьюки. для нечетного N Однако bn _{, и} является антипериодическим технически мы имеем негациклическую свертку длины N . нулями Однако такие различия исчезают, когда дополняют число _n до длины по меньшей мере 2 N -1, как описано выше. Поэтому, возможно, проще всего думать об этом как о подмножестве результатов простой линейной свертки (т. е. без концептуальных «расширений» данных, периодических или каких-либо других).

z-преобразования

Алгоритм Блюстейна также можно использовать для вычисления более общего преобразования, основанного на (одностороннем) z-преобразовании (Rabiner et al. , 1969). В частности, он может вычислить любое преобразование вида:

$X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,$

для произвольного комплексного числа z и для разных чисел N и M входов и выходов. Учитывая алгоритм Блюстейна, такое преобразование можно использовать, например, для получения более точной интерполяции некоторой части спектра (хотя разрешение по частоте по-прежнему ограничено общим временем выборки, аналогично БПФ масштабирования), улучшения произвольного полюса в анализе передаточных функций и т. д.

Алгоритм был назван алгоритмом чирпового z-преобразования, потому что для случая преобразования Фурье (| z | = 1) последовательность b _n сверху представляет собой комплексную синусоиду линейно возрастающей частоты, которая называется (линейным) чирпом в радиолокационные системы.

См. также

• Дробное преобразование Фурье

Ссылки

Общий

• Лео И. Блюстейн, «Подход к расчету дискретного преобразования Фурье с помощью линейной фильтрации», Протокол Northeast Electronics Research and Engineering Meeting Record 10 , 218–219 (1968).
• Лоуренс Р. Рабинер, Рональд В. Шафер и Чарльз М. Рейдер, « Алгоритм чирпового z-преобразования и его применение », Bell Syst. Тех. Дж. 48 , 1249–1292 (1969). Также опубликовано в: Рабинер, Шафер и Рейдер, « Алгоритм z-преобразования с чирпом », IEEE Trans. Аудио-электроакустика 17 (2), 86–92 (1969).
• Д. Х. Бэйли и П. Н. Шварцтраубер, «Дробное преобразование Фурье и его приложения», SIAM Review 33 , 389–404 (1991). (Обратите внимание, что эта терминология для z-преобразования нестандартна: дробное преобразование Фурье обычно относится к совершенно другому, непрерывному преобразованию.)
• Лоуренс Рабинер, «Алгоритм z-преобразования с чирпом — урок счастливой случайности», IEEE Signal Processing Magazine 21 , 118–119 (март 2004 г.). (Исторический комментарий.)
• Владимир Сухой и Александр Стойчев: «Обобщение обратного БПФ от единичного круга» (октябрь 2019 г.). # Открытый доступ.
• Владимир Сухой и Александр Стойчев: «Численный анализ ошибок алгоритма ICZT для чирпирующих контуров на единичной окружности» , Sci Rep 10, 4852 (2020).

Внешние ссылки

• Алгоритм DSP для частотного анализа — преобразование Chirp-Z (CZT).
• Решение головоломки 50-летней давности в области обработки сигналов, часть вторая