News for hackers. Stuff that matters.
Re:Fast inverse chirp z-transform found by simo_dax on Saturday October 12, 2019 @02:53AM (#21231138)
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

Re:Fast inverse chirp z-transform found by gugagore on Saturday October 12, 2019 @09:05AM (#21232752)
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.)
Re:Fast inverse chirp z-transform found by jjoonathan on Saturday October 12, 2019 @09:39AM (#21233022)
As well you should: simo_dax described the z-transform / laplace transform, not the chirp Z transform.
Re:Fast inverse chirp z-transform found by gugagore on Saturday October 12, 2019 @03:26PM (#21235593)
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.

Re:Fast inverse chirp z-transform found by ttoinou on Saturday October 12, 2019 @04:47AM (#21231565)
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 ?

Re:Fast inverse chirp z-transform found by simo_dax on Saturday October 12, 2019 @06:15AM (#21231909)
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

Re:Fast inverse chirp z-transform found by bullen on Saturday October 12, 2019 @08:02AM (#21232368)
Could this be used to improve LoRa range or bandwidth?
Re:Fast inverse chirp z-transform found by regularfry on Saturday October 12, 2019 @06:16AM (#21231912)
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.
Re:Fast inverse chirp z-transform found by dfee on Saturday October 12, 2019 @03:20AM (#21231226)
I feel like you should’ve been my signals and systems teacher.
Re:Fast inverse chirp z-transform found by burfog on Saturday October 12, 2019 @05:31AM (#21231735)
How does this relate to the chirplet transform? Are we still lacking an inverse chirplet transform?
Re:Fast inverse chirp z-transform found by simo_dax on Saturday October 12, 2019 @05:39AM (#21231771)
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
This is exactly the inverse chirplet transform, which the guys in the article found a way to compute
Re:Fast inverse chirp z-transform found by Piezoid on Saturday October 12, 2019 @04:49AM (#21231571)
Thank you for the clear explanation.

Could this find applications in (realtime ?) acoustic room correction on embedded devices ?

Re:Fast inverse chirp z-transform found by simo_dax on Saturday October 12, 2019 @06:34AM (#21232001)
It's not my field so I wouldn't know, but it's possible