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

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

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

$X\; k\; Знак\; равно\; \sum \; N\; =\; 0\; N\; -\; 1\; Икс\; (N)\; ZK\; -\; N\; \{\backslash \; Displaystyle\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\; (n)\; z\_\; \{k\}\; ^\; \{-\; n\}\; \}$

$zk\; =\; A\; \cdot \; W\; -\; k,\; k\; =\; 0,\; 1,\dots ,\; M\; -\; 1\; \{\backslash \; displaystyle\; z\_\; \{k\}\; =\; A\; \backslash \; cdot\; W\; ^\; \{-\; k\},\; k\; =\; 0,1,\; \backslash \; dots,\; M-1\}$

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

Подобно DFT, Z-преобразование chirp может быть вычислено за O (n log n) операций, где $n\; =\; max\; (M,\; N)\; n\; =\; \backslash \; max\; (M,\; N)$. Алгоритм O (N log N) для Z-преобразования обратного чирпа (ICZT) был описан в 2003 и 2019 годах.

Содержание

• 1 Алгоритм Блюстейна
• 2 z-преобразования
• 3 См. Также
• 4 Ссылки
  • 4.1 Общие
• 5 Внешние ссылки

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

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

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

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

$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; xne\; -\; 2\; \pi \; i\; N\; nkk\; =\; 0,\dots ,\; N\; -\; 1.\; \{\backslash \; displaystyle\; X\_\; \{k\; \}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{2\; \backslash \; pi\; i\}\; \{N\}\}\; nk\}\; \backslash \; qquad\; k\; =\; 0,\; \backslash \; dots,\; N-\; 1.\}$

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

$nk\; =\; -\; (k\; -\; n)\; 2\; 2\; +\; n\; 2\; 2\; +\; k\; 2\; 2\; \{\backslash \; displaystyle\; nk\; =\; \{\backslash \; frac\; \{-\; (\; kn)\; ^\; \{2\}\}\; \{2\}\}\; +\; \{\backslash \; frac\; \{n\; ^\; \{2\}\}\; \{2\}\}\; +\; \{\backslash \; frac\; \{k\; ^\; \{2\}\}\; \{2\}\}\}$

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

$X\; k\; =\; e\; -\; \pi \; i\; N\; k\; 2\; \sum \; n\; =\; 0\; N\; -\; 1\; (xne\; -\; \pi \; i\; N\; n\; 2)\; e\; \pi \; i\; N\; (k\; -\; n)\; 2\; k\; =\; 0,\dots ,\; N\; -\; 1.\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; e\; ^\; \{-\; \{\backslash \; frac\; \{\backslash \; pi\; i\}\; \{N\}\}\; k\; ^\; \{2\}\}\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; \backslash \; left\; (x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{\backslash \; pi\; i\}\; \{N\}\}\; n\; ^\; \{2\}\}\; \backslash \; right)\; e\; ^\; \{\{\backslash \; frac\; \{\backslash \; pi\; i\}\; \{N\}\}\; (kn)\; ^\; \{2\}\}\; \backslash \; qquad\; k\; =\; 0,\; \backslash \; dots,\; N-1.\}$

Это суммирование в точности представляет собой свертку двух последовательностей a n и b n, определенных следующим образом:

$an\; =\; xne\; -\; \pi \; я\; N\; N\; 2\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{\backslash \; pi\; i\}\; \{N\}\}\; n\; ^\; \{2\}\}\}$

$bn\; =\; e\; \pi \; i\; N\; n\; 2,\; \{\backslash \; displaystyle\; b\_\; \{n\}\; =\; e\; ^\; \{\{\backslash \; frac\; \{\backslash \; pi\; i\}\; \{N\}\}\; n\; ^\; \{2\}\},\}$

с выводом множителя свертки определяется N фазовыми факторами b k. То есть:

$Икс\; k\; =\; bk\; *\; (\sum \; n\; =\; 0\; N\; -\; 1\; anbk\; -\; n)\; k\; =\; 0,\dots ,\; N\; -\; 1.\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; b\_\; \{k\}\; ^\; \{*\}\; \backslash \; left\; (\backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; a\_\; \{n\}\; b\_\; \{kn\}\; \backslash \; right)\; \backslash \; qquad\; k\; =\; 0,\; \backslash \; dots,\; N-1.\}$

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

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

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

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

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

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

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

$Икс\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; xnznkk\; =\; 0,\dots ,\; M\; -\; 1,\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\; \}\; ^\; \{N-1\}\; x\_\; \{n\}\; z\; ^\; \{nk\}\; \backslash \; qquad\; k\; =\; 0,\; \backslash \; dots,\; M-1,\}$

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

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

См. Также

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

Ссылки

Общие

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

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

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