ЛЧМ Z-преобразование ( CZT ) является обобщением дискретного преобразования Фурье (ДПФ). В то время как DFT выбирает плоскость Z в точках, равномерно разнесенных вдоль единичной окружности, Z-преобразование щебета производит выборку вдоль спиральных дуг в Z-плоскости, соответствующих прямым линиям в S-плоскости . [1] [2] ДПФ, реальное ДПФ и ДПФ с увеличением могут быть вычислены как частные случаи CZT.
В частности, преобразование chirp Z вычисляет преобразование Z в конечном числе точек z k вдоль логарифмического спирального контура, определяемого как: [1] [3]
где A - комплексная начальная точка, W - комплексное соотношение между точками, а M - количество точек для расчета.
Как и ДПФ, Z-преобразование chirp может быть вычислено за O ( n log n ) операций, где. Алгоритм O ( N log N ) для обратного Z-преобразования чирпа (ICZT) был описан в 2003 г. [4] [5] и в 2019 г. [6]
Алгоритм Блюстейна
Алгоритм Блюстайна [7] [8] выражает CZT как свертку и эффективно реализует его с помощью БПФ / ОБПФ.
Поскольку ДПФ является частным случаем CZT, это позволяет эффективно вычислять дискретное преобразование Фурье (ДПФ) произвольных размеров, включая простые размеры. (Другой алгоритм для БПФ простых размеров, алгоритм Рейдера , также работает, переписывая ДПФ как свертку.) Он был разработан в 1968 году Лео Блюстайном . [9] Алгоритм Блюстейна может использоваться для вычисления более общих преобразований, чем ДПФ, на основе (одностороннего) z-преобразования (Rabiner et al. , 1969).
Напомним, что ДПФ определяется формулой
Если в экспоненте заменить произведение nk на тождество
таким образом получаем:
Это суммирование в точности представляет собой свертку двух последовательностей a n и b n, определенных следующим образом:
с выходом свертки, умноженным на N фазовых множителей b k * . Это:
Эта свертка, в свою очередь, может быть выполнена с парой БПФ (плюс предварительно вычисленное БПФ комплексного щебета b n ) с помощью теоремы свертки . Ключевым моментом является то, что эти БПФ не имеют одинаковой длины N : такую свертку можно точно вычислить из БПФ только путем заполнения нулями до длины, большей или равной 2 N –1. В частности, можно дополнить до степени двух или какого-либо другого очень сложного размера, для которого БПФ может быть эффективно выполнено, например, с помощью алгоритма Кули-Тьюки за время O ( N log N ). Таким образом, алгоритм Блюстейна обеспечивает способ вычисления ДПФ простого размера за O ( N log N ), хотя и в несколько раз медленнее, чем алгоритм Кули-Тьюки для составных размеров.
Использование нулевого заполнения для свертки в алгоритме Блюстайна заслуживает некоторых дополнительных комментариев. Предположим, мы выполняем обнуление до длины M ≥ 2 N –1. Это означает , что п расширен до массива А п длины М , где А п = с п при 0 ≤ п < N и А п = 0 в противном случае-обычного значения «нулевого заполнения». Тем не менее, из-за б к - п термина в свертке, как положительные , так и отрицательные значения п требуются для б п (заметим , что б - п = б п ). Периодические границы, подразумеваемые ДПФ массива с нулями, означают, что - n эквивалентно M - n . Таким образом, b n расширяется до массива B n длины M , где B 0 = b 0 , B n = B M - n = b n для 0 < n < N , и B n = 0 в противном случае. Затем A и B подвергаются БПФ, умножаются поточечно и обратным БПФ для получения свертки a и b в соответствии с обычной теоремой свертки.
Давайте также уточнить, какой тип свертки требуется в алгоритме Блюстейна для ДПФ. Если бы последовательность b n была периодической по n с периодом N , тогда это была бы циклическая свертка длины N , а заполнение нулями было бы только для удобства вычислений. Однако обычно это не так:
Следовательно, для N даже свертка является циклической, но в этом случае N является составным, и обычно можно использовать более эффективный алгоритм БПФ, такой как Кули – Тьюки. Для N нечетен, однако, затем б п является антипериодическим и мы технически имеем negacyclic свертки длина N . Такие различия исчезают , когда один нуль подушечки п до длины , по меньшей мере , 2 Н -1 , как описано выше, однако. Поэтому, возможно, проще всего думать об этом как о подмножестве выходных данных простой линейной свертки (т. Е. Без концептуальных «расширений» данных, периодических или иных).
z-преобразования
Алгоритм Блюстейна также можно использовать для вычисления более общего преобразования, основанного на (одностороннем) z-преобразовании (Rabiner et al. , 1969). В частности, он может вычислить любое преобразование формы:
для произвольного комплексного числа z и для различных чисел N и M входов и выходов. Учитывая алгоритм Блюстайна, такое преобразование можно использовать, например, для получения интерполяции с более мелкими интервалами некоторой части спектра (хотя разрешение по частоте по-прежнему ограничено общим временем выборки, аналогично Zoom FFT), улучшить произвольные полюса в анализе передаточной функции и т. д.
Алгоритм был назван алгоритмом z-преобразования chirp, потому что для случая преобразования Фурье (| z | = 1) последовательность b n сверху представляет собой комплексную синусоиду с линейно возрастающей частотой, которая называется (линейной) chirp в радиолокационные системы.
Смотрите также
Рекомендации
- ^ a b Исследование Z-преобразования Chirp и его приложений - Шиллинг, Стив Алан
- ^ "Чирп Z-преобразование - MATLAB czt" . www.mathworks.com . Проверено 22 сентября 2016 .
- ^ Мартин, Грант Д. (ноябрь 2005 г.). "Оптимизация спектрального масштабирования Chirp Z-преобразованием с помощью MATLAB®" (PDF) .
- ^ Бостан, Алин (2003). Эффективный алгоритм для базовых операций в расчетной форме (PDF) (PhD). Политехническая школа.
- ^ Бостан, Алин; Шост, Эрик (2005). «Полиномиальное вычисление и интерполяция на специальных наборах точек». Журнал сложности . 21 (4): 420–446. DOI : 10.1016 / j.jco.2004.09.009 .
- ^ Инженеры решают загадку 50-летней давности в обработке сигналов - Z-преобразование обратного щебета , Государственный университет штата Айова, 10 октября 2019 г.
- ^ Блюстайн, Л. (1970-12-01). «Линейный подход фильтрации к вычислению дискретного преобразования Фурье». IEEE Transactions по аудио и электроакустике . 18 (4): 451–455. DOI : 10.1109 / TAU.1970.1162132 . ISSN 0018-9278 .
- ^ «Алгоритм БПФ Блюстейна» . DSPRelated.com.
- ^ Блюстейн, Л. (1970). «Линейный подход фильтрации к вычислению дискретного преобразования Фурье». IEEE Transactions по аудио и электроакустике . 18 (4): 451–455. DOI : 10.1109 / TAU.1970.1162132 .
Общий
- Лео И. Блюстайн, "Подход с линейной фильтрацией к вычислению дискретного преобразования Фурье", Northeast Electronics Research and Engineering Meeting Record 10 , 218-219 (1968).
- Лоуренс Р. Рабинер, Рональд В. Шафер и Чарльз М. Рейдер, « Алгоритм z-преобразования chirp и его применение », Bell Syst. Tech. J. 48 , 1249–1292 (1969). Также опубликовано в: Rabiner, Shafer, and Rader, " The chirp z-transform algorithm ", IEEE Trans. Аудио электроакустика 17 (2), 86–92 (1969).
- DH Bailey и PN Swarztrauber, "Дробное преобразование Фурье и приложения", 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-летней давности в области обработки сигналов, часть вторая