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-летней давности в области обработки сигналов, часть вторая