Чёрп Z-преобразование: обобщение и алгоритмы вычисления
Chirp Z-transform
Chirp Z-преобразование (CZT): обобщение DFT для эффективного анализа сигналов. Вычисление в Z-плоскости по спиральным траекториям, алгоритмы O(n log n).
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Чирп-Z-преобразование (CZT) является обобщением дискретного преобразования Фурье (DFT). В то время как DFT дискретизирует Z-плоскость в равномерно расположенных точках вдоль единичной окружности, чирп-Z-преобразование дискретизирует её вдоль спиральных дуг в Z-плоскости, что соответствует прямым линиям в S-плоскости. DFT, действительное DFT и зум-DFT могут быть вычислены как частные случаи CZT. В частности, чирп-Z-преобразование вычисляет Z-преобразование в конечном числе точек zk вдоль логарифмической спирали, определяемой как:
The chirp Z transform (CZT) is a generalization of the discrete Fourier transform (DFT). While the DFT samples the Z plane at uniformly spaced points along the unit circle, the chirp Z transform samples along spiral arcs in the Z plane, corresponding to straight lines in the S plane. The DFT, real DFT, and zoom DFT can be calculated as special cases of the CZT. Specifically, the chirp Z transform calculates the Z transform at a finite number of points zk along a logarithmic spiral contour, defined as:
где A – комплексная начальная точка, W – комплексное отношение между точками, а M – количество точек для вычисления. Как и DFT, чирп-Z-преобразование может быть вычислено за O(n log n) операций. Алгоритм O(N log N) для обратного чирп-Z-преобразования (ICZT) был описан в 2003 и 2019 годах.
where A is the complex starting point, W is the complex ratio between points, and M is the number of points to calculate. Like the DFT, the chirp Z transform can be computed in O(n log n) operations where An O(N log N) algorithm for the inverse chirp Z transform (ICZT) was described in 2003, and in 2019.
z-трансформации
Алгоритм Блюштейна также может использоваться для вычисления более общего преобразования, основанного на (одностороннем) z-преобразовании (Rabiner et al., 1969). В частности, он может вычислить любое преобразование вида:
Bluestein's algorithm can also be used to compute a more general transform based on the (unilateral) z transform (Rabiner et al., 1969). In particular, it can compute any transform of the form:
для произвольного комплексного числа z и для различного числа N входов и M выходов. Используя алгоритм Блюштейна, такое преобразование можно применить, например, для получения более детальной интерполяции некоторой части спектра (хотя частотное разрешение все равно ограничено общей длительностью выборки, подобно Zoom FFT), для усиления произвольных полюсов при анализе передаточной функции и т.д. Алгоритм получил название алгоритма chirp z-преобразования, поскольку для случая преобразования Фурье (|z| = 1) последовательность bn, указанная выше, представляет собой комплексную синусоиду с линейно возрастающей частотой, которая называется (линейным) чирпом в радиолокационных системах.
for an arbitrary complex number z and for differing numbers N and M of inputs and outputs. Given Bluestein's algorithm, such a transform can be used, for example, to obtain a more finely spaced interpolation of some portion of the spectrum (although the frequency resolution is still limited by the total sampling time, similar to a Zoom FFT), enhance arbitrary poles in transfer function analyses, etc. The algorithm was dubbed the chirp z transform algorithm because, for the Fourier transform case (|z| = 1), the sequence bn from above is a complex sinusoid of linearly increasing frequency, which is called a (linear) chirp in radar systems.
Общий
Лео И. Блюштейн, "Линейный фильтрующий подход к вычислению дискретного преобразования Фурье", Northeast Electronics Research and Engineering Meeting Record 10, 218–219 (1968). Лоуренс Р. Рабинер, Рональд В. Шафер и Чарльз М. Радер, "Алгоритм преобразования chirp z и его применение", Bell Syst. Tech. J. 48, 1249–1292 (1969). Также опубликовано в: Rabiner, Shafer, and Rader, "Алгоритм преобразования chirp z", IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969). Д. Х. Бейли и П. Н. Свартцтраубер, "Преобразование Фурье дробного порядка и его применение", SIAM Review 33, 389–404 (1991). (Следует отметить, что данная терминология для z-преобразования является нестандартной: преобразование Фурье дробного порядка обычно относится к совершенно другому, непрерывному преобразованию.) Лоуренс Рабинер, "Алгоритм преобразования chirp z – урок, рожденный случайно", IEEE Signal Processing Magazine 21, 118–119 (март 2004). (Исторический комментарий.) Владимир Сухой и Александр Стоитчев: "Обобщение обратного FFT за пределами единичной окружности" (октябрь 2019). # Открытый доступ. Владимир Сухой и Александр Стоитчев: "Численный анализ ошибок алгоритма ICZT для контуров чирпа на единичной окружности", Sci Rep 10, 4852 (2020).
Leo I. Bluestein, "A linear filtering approach to the computation of the discrete Fourier transform," Northeast Electronics Research and Engineering Meeting Record 10, 218 219 (1968). Lawrence R. Rabiner, Ronald W. Schafer, and Charles M. Rader, "The chirp z transform algorithm and its application," Bell Syst. Tech. J. 48, 1249 1292 (1969). Also published in: Rabiner, Shafer, and Rader, "The chirp z transform algorithm," IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969). D. H. Bailey and P. N. Swarztrauber, "The fractional Fourier transform and applications," SIAM Review 33, 389 404 (1991). (Note that this terminology for the z transform is nonstandard: a fractional Fourier transform conventionally refers to an entirely different, continuous transform.) Lawrence Rabiner, "The chirp z transform algorithm—a lesson in serendipity," IEEE Signal Processing Magazine 21, 118 119 (March 2004). (Historical commentary.) Vladimir Sukhoy and Alexander Stoytchev: "Generalizing the inverse FFT off the unit circle", (Oct 2019). # Open access. Vladimir Sukhoy and Alexander Stoytchev: "Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle", Sci Rep 10, 4852 (2020).