Fast inverse chirp z-transform found
techxplore.com
techxplore.com
There is a generalization of this transform (i.e. this transform is a particular case of a more general one): what if instead of a purely imaginary exponent we use a generic complex value a+ib? Then e^((a+ib) * t) = e^(a * t)e^(ib * t): the new term that appears is a real-valued exponential, so exponential curves can also be used describe the starting signal!
However, making a discrete-time, sample-based algorithm of this transform is tricky, and the corresponding inverse transform (the "sum" of the components to get the starting signal back) didn't exist before
And is there a finite orthogonal basis for the z-transform (of a finite length signal), even?
If I remember correctly, the motivation for the z-transform is that more functions have the transform defined for the z-transform than for the DT Fourier transform. And you less often need generalized functions (Dirac deltas, and their derivatives). But there is no place in which z-transforms show up in signal processing computations, I thought. Since then signals are finite-time and there isn't a need for the convergence benefits of the z-transform.
Unless the hard part is doing that
1. Fast
2. with Discrete values
3. inverse discrete transform( discrete transform( discrete values ) ) should be almost equal to discrete values with high accuracy
is that right ?
The inverse fourier trasnform, on the other hand, is limited to the imaginary axis of the complex plane (the exponent is a purely imaginary number), so you're restricting it to be monodimensional, hence the relative simplicity in reversing the transform
Also, keep in mind that all of this assumes you have infinite samples, so you need to use some form of windowing which doesn't distort too much the signal
The corresponding inverse transform (the "sum" of the components to get the starting signal back) didn't exist before
Could this find applications in (realtime ?) acoustic room correction on embedded devices ?
Also in this more compact paper by Bostan and Schost: https://specfun.inria.fr/bostan/publications/BoSc05.pdf
The new algorithm may be a different way to do it (I haven't studied the paper), but the authors ought to have cited previous work. Where does Nature find their referees?
Let us now focus on the computation of the inverse chirp transform. The idea is to use the Newton basis for intermediate computations: first perform a Newton interpolation, then perform a conversion from the Newton basis to the monomial basis. Both steps have complexities M(n) + O(n), which gives the estimate of 2M(n) + O(n)
The function M(n)
denotes the cost of multiplying univariate polynomials of degree less than n. Using FFT-based multiplication algorithms, M(n) can be taken in O(n log(n) log(log(n)))
So they did not reach O(n log n).
* log₂ log₂ 2⁶⁴ = 6, which is essentially a constant factor if N<2⁶⁴
* to be fair, you may need to consider (log log N), or even (log log N)² factors hidden in native computer word size if exceeding N = 2⁶⁴.
* Today's machines have gone far from the classical computational complexity models, where data access patterns and locality matter orders of magnitude more than a factor which is essentially <= 6.
I would not immediately discard a (log log n) factor, but for nearly all purposes, I would mostly disregard it. So if the only difference were O(n·log n) vs O(n·log n·log log n), then no, it would not be a big deal.
> Engineers working in the field of digital signal processing often use the fast Fourier transform (FFT) algorithm to detect tones, frequencies, signatures, and other events. In specific situations, however, other algorithms may actually work better than the FFT. ...
> Although most engineers would use the FFT, another, lesser-known algorithm gives you additional flexibility to specify both spectral analysis bandwidth and the resolution within that bandwidth and provides real and imaginary outputs from which you can compute spectral magnitude and phase. In this article, I'll introduce you to that algorithm, known as the Chirp-Z transform (CZT), and we'll compare it to the better known Goertzel and FFT.
And the opening paragraph from wikipedia:
> 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.
https://en.wikipedia.org/wiki/Chirp_Z-transform
Sounds like a pretty awesome milestone to me. So, perhaps in the near future, new compression schemes might allow for reduced mp3 and mp4 file sizes, which means that for the same bandwidth we could see increased resolution/ higher frame rates.
I’ll cover some quick basics then explain why chirp z is useful.
Ohm’s law: voltage = current * resistance. Resistance is considered a steady state value. Impedance is resistance across frequency. In the real world channels (cables, the air, etc.) do not have a flat impedance (the same resistance across all frequencies). Similarly, transmitters and receivers do not have flat resistance. If you try to send a signal through a channel that has too much insertion loss, then the receiver won’t be able to decode it. If the impedance of a transmitter/receiver is different than the channel there will be reflections that damage signal integrity (there are good/easy physical analogs to explain this, but I won’t. Think back to waves in physics class).
We can measure impedance over frequency directly using a vector network analyzer (VNA) or a time domain reflectometer (TDR). A VNA sweeps across frequencies and listens to the response. A TDR sends a pulse then waits for the response at a given delay. It sends many pulses and looks at many delays to build up an impedance over time plot. This impedance over time is very useful because it can show jumps in impedance at given electrical lengths. Like you can see impedance jump at 30 ns in where you expect to have the connector soldered to board, etc. However, TDRs compared to VNAs, are expensive, difficult to calibrate, and take data very slowly. So the industry has moved towards VNAs. However standards bodies (like the IEEE) are starting to appreciate the use of time domain impedance.
Now to why chirp z is useful. You can reversibly convert from the time domain to the frequency domain using a fourier transform. Great. You just have to assume that your signal repeats for all time. Hmm. Zero pad and don’t worry about it. What do we not get from this assumption though? Low frequency information. So let’s start with a frequency domain data set (a la VNA) and convert to the time domain. Well that missing low frequency information is very important. You can extrapolate the missing values. The error in the extrapolation will shift your entire impedance profile by huge amounts. In comes chirp z. It is able to handle the missing spectrum much better than the fourier transform.
To summarize: validating new hardware before mass production requires impedance measurement. Impedance measurement has two instrument options with large tradeoffs. Advancements in the chirp z algorithm reduce the penalties of one of those options.
So, it seems likely that you're right about the CZT being used in time-domain netowrk analysis, since I've seen documentation indicating that it was used for that purpose as far back as the HP 8510.[1] But I still don't grok why, and Rytting's brief explanation on page 13 of that document makes no sense whatsoever.
From a practical perspective, the chirp-Z transform just lets us use arbitrary start/end frequencies rather than the entire DC-Nyquist range that traditional FFTs encompass, correct? If I'm emulating lowpass TDR with a VNA, I'll have to extrapolate the DC response, as you point out... but what specifically makes the CZT better suited to this extrapolation process?
I think this exponential decay or growth is the major difference compared to an IFFT, and hence the algorithm can work more efficient over a larger time/frequency domain.
Think of improvements anywhere FFT is used today, but where there is a need to work over a non-linear time/frequency domain.
The ringing around edges in the source signal, Gibbs phenomenon[1], is due to almost or entirely discarding higher frequency components.
If you think of FFT/IFFT only working for special cases, then works in the general sense.
https://github.com/daedalus/math/blob/master/chirp_zeta_tran...