Fast inverse chirp z-transform found(techxplore.com)
techxplore.com
Fast inverse chirp z-transform found
https://techxplore.com/news/2019-10-year-old-puzzle.html
33 comments
The inverse chirp z-transform in that second paper is described as follows:
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).
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).
That complexity bound applies to polynomials over more general coefficient rings which may not have roots of unity. Over the usual complex numbers the complexity is O(n log n).
The (log (log n)) factor in asymptotic complexity notation is almost meaningless.
* 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.
* 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.
it seems they have reinvented the wheel.
It was solved in 2003:
https://specfun.inria.fr/bostan/these/These.pdf
Hi,
I tried to make an implementation of the algorithm in python.
Need input. Can you validate it please?
https://github.com/daedalus/math/blob/master/chirp_zeta_tran...
https://github.com/daedalus/math/blob/master/chirp_zeta_tran...
For the uninitiated, what does this particular breakthrough enable? I understand the point it makes about being able to reverse a decomposition but don't get what the practical consequences are.
I have worked with it a bit in my time in physical layer test and measurement.
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.
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.
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.
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?
[1]: http://hparchive.com/seminar_notes/a-137.pdf
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?
[1]: http://hparchive.com/seminar_notes/a-137.pdf
It enables applications
with spectral frequency components that are not constrained to have fixed magnitudes but also could decay or
grow exponentially.
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.
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.
My layman’s interpretation of this is that using this new transform instead of DCT will make edges less blocky in JPG images. Is that right?
Not really. The blockyness in JPEG images is from throwing away less significant terms in each 8x8 pixel block to save space. Any lossy image compression method will cause artefacts of some kind, no matter what transform or system it's based on, but JPEG's ones are particularly artificial-looking as they're square and lead to sharp visible edges. Some other methods of throwing away information aren't based on blocks and just make things blurry.
AFAIK the main source of blockyness is due to the quantization of low-frequency components, such that the decoded signal doesn't quite match from one block to the next.
The ringing around edges in the source signal, Gibbs phenomenon[1], is due to almost or entirely discarding higher frequency components.
[1]: https://en.wikipedia.org/wiki/Gibbs_phenomenon
The ringing around edges in the source signal, Gibbs phenomenon[1], is due to almost or entirely discarding higher frequency components.
[1]: https://en.wikipedia.org/wiki/Gibbs_phenomenon
A tiny bit of googling revealed this article:
https://www.embedded.com/a-dsp-algorithm-for-frequency-analy...
> 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.
> 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.
Anyone have a link to a non-paywalled version of the paper?
The link in the article was not paywalled for me (maybe it is for others?).
https://www.nature.com/articles/s41598-019-50234-9
https://www.nature.com/articles/s41598-019-50234-9
The publication itself also seems freely accessible:
https://www.nature.com/articles/s41598-019-50234-9.pdf
https://www.nature.com/articles/s41598-019-50234-9.pdf
Scientific Reports is open-access.
Small explanation for people not introduced to signals theory:
Fourier transform is the decomposition of an arbitrary signal into many sinusoids, such that their sum gives a signal identical to the starting one. Each of these sinusoids can be represented using Euler's formula as e^(i * omega * t). You can see that the exponent is purely imaginary.
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
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
I'm having a hard time understanding why it's called "chirp". The basis signals aren't chirps (a signal that if you reproduce as sound, sounds like a bird chirp. Frequency increases in time.)
As well you should: simo_dax described the z-transform / laplace transform, not the chirp Z transform.
I suspected...
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.
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.
Why is reversing the transform hard ? It's just about computing back values by following the transform definition, it should be even easier than doing the original 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 ?
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 ?
Each of these is certainly a complication, for example standard discrete-time Fourier transform is O(n^2) while the Fast Fourier Transform algorithm manages to do the same in O(nlogn), but I think the main difficulty here is that the direct transform is an integral (or series, depends if you're using continuous or discrete one) over time, which is a single real variable. The inverse is an integral over the complex variable, a+ib, and you need a whole 2D plane to represent it (the complex plane indeed), a single 1D line is not enough. So how do you take an integral of a complex value over a 2D plane? And here you start delving deep into theorems and convergence regions.. stuff that's quite difficult to grasp without having experience with complex calculus (and I don't)
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 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
Could this be used to improve LoRa range or bandwidth?
Doing it fast and accurately is the hard part. This paper touches on some of the numerical accuracy improvements they made to the algorithm to help out. It involves some rather large numbers, so numerical accuracy of the floating point calculations matters.
I feel like you should’ve been my signals and systems teacher.
How does this relate to the chirplet transform? Are we still lacking an inverse chirplet transform?
The chirplet transform is a discrete-time implementation (i.e uses samples instead of continuous functions) of the mathematical transform i've written
The corresponding inverse transform (the "sum" of the components to get the starting signal back) didn't exist before
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?