SYSTEMS AND METHODS FOR INVERTING THE CHIRP Z-TRANSFORM IN O(n log n) TIME AND O(n) MEMORY
AssigneeIowa State University Research Foundation, Inc.
InventorsVolodymyr Sukhoy, Alexander Stoytchev
Life of this patent
Estimating the term…
Abstract
Embodiments of the present disclosure describe an efficient O(n log n) method that implements the Inverse Chirp Z-Transform (ICZT). This transform is the inverse of the well-known forward Chirp Z-Transform (CZT), which generalizes the fast Fourier transform (FFT) by allowing the sampling points to fall on a logarithmic spiral contour instead of the unit circle. Thus, the ICZT can be viewed as a generalization of the inverse fast Fourier transform (IFFT).
Claims20
A method of processing audio and/or image signals using a computational system comprising a processor and a memory device, the method comprising:
- receiving a stream of the audio and/or image signals and storing the stream of audio and/or image signals in a first vector in the memory device, the first vector being a time domain vector;
- converting, using the processor, the first vector into a second vector using a Chirp Z-Transform (CZT) or a Fast Fourier Transform (FFT), the second vector being a frequency domain vector comprising a plurality of elements;
- filtering, using the processor, the second vector to remove or modify one or more elements of the plurality of elements and storing a filtered second vector in the memory device;
- converting, using the processor, the filtered second vector to a third vector using an inverse CZT (ICZT), the third vector being a time domain vector that is not equal to the first vector;
- wherein converting the filtered second vector has a computational complexity of O(n2) or less and utilizes no more than O(n) memory of the memory device.
A computational system configured to process audio and/or image signals, comprising:
- a processor;
- and
- a memory device;
- wherein the memory device is configured to store a stream of the audio and/or image signals in a first vector in the memory device, the first vector being a time domain vector;
- wherein the processor is configured to
- convert the first vector into a second vector using a Chirp Z-Transform (CZT) or a Fast Fourier Transform (FFT), the second vector being a frequency domain vector comprising a plurality of elements;
- filter the second vector to remove or modify one or more elements of the plurality of elements to provide a filtered second vector stored in the memory device;
- and
- convert the filtered second vector to a third vector using an inverse CZT (ICZT), the third vector being a time domain vector that is not equal to the first vector;
- wherein converting the filtered second vector has a computational complexity of O(n2) or less and utilizes no more than O(n) memory of the memory device.
Dependencies are inferred from the claim text.