Submitted via IRC for Bytram
Engineers solve 50-year-old puzzle in signal processing
Something called the fast Fourier transform is running on your cell phone right now. The FFT, as it is known, is a signal-processing algorithm that you use more than you realize. It is, according to the title of one research paper, "an algorithm the whole family can use."
Alexander Stoytchev—an associate professor of electrical and computer engineering at Iowa State University who's also affiliated with the university's Virtual Reality Applications Center, its Human Computer Interaction graduate program and the department of computer science—says the FFT algorithm and its inverse (known as the IFFT) are at the heart of signal processing.
And, as such, "These are algorithms that made the digital revolution possible," he said.
They're a part of streaming music, making a cell phone call, browsing the internet or taking a selfie.
The FFT algorithm was published in 1965. Four years later, researchers developed a more versatile, generalized version called the chirp z-transform (CZT). But a similar generalization of the inverse FFT algorithm has gone unsolved for 50 years.
Until, that is, Stoytchev and Vladimir Sukhoy—an Iowa State doctoral student co-majoring in electrical and computer engineering, and human computer interaction—worked together to come up with the long-sought algorithm, called the inverse chirp z-transform (ICZT).
Like all algorithms, it's a step-by-step process that solves a problem. In this case, it maps the output of the CZT algorithm back to its input. The two algorithms are a little like a series of two prisms—the first separates the wavelengths of white light into a spectrum of colors and the second reverses the process by combining the spectrum back into white light, Stoytchev explained.
Stoytchev and Sukhoy describe their new algorithm in a paper recently published online by Scientific Reports, a Nature Research journal. Their paper shows that the algorithm matches the computational complexity or speed of its counterpart, that it can be used with exponentially decaying or growing frequency components (unlike the IFFT) and that it has been tested for numerical accuracy.
(Score: 1, Funny) by Anonymous Coward on Saturday October 12 2019, @04:47AM (10 children)
Kudos to Iowa State University for supporting this research.
(Score: 3, Funny) by Coward, Anonymous on Saturday October 12 2019, @05:18AM (9 children)
This sounds very cool, but I have no idea what to use this ICZT algorithm for, let alone the CZT. Can we analyze spiral galaxies? If the reference to Cyclones is for humor, that's quite deep.
(Score: 2) by takyon on Saturday October 12 2019, @06:58AM (3 children)
Sounds like we could get new compression algorithms out of it.
[SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
(Score: 1, Interesting) by Anonymous Coward on Saturday October 12 2019, @07:12AM
I wouldn't be shocked to see a decades-old patent get declassified. This is the sort of thing that would make a huge difference for radar or sonar.
It ought to be useful for medical imaging, music production, and cleaning up noisy signals.
(Score: 3, Interesting) by FatPhil on Saturday October 12 2019, @01:28PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Funny) by driverless on Sunday October 13 2019, @01:51AM
Already been done:
I'm the creator of a similar transform for compression, the Fast Driverless Transform (FDT):
As should be obvious, the FDT achieves truly remarkable compression ratios that will revolutionise the industry. I'm just waiting for someone to develop the IFDT to recover the original data.
(Score: 5, Insightful) by choose another one on Saturday October 12 2019, @08:10AM
Well I've just tried to brush up on CZT and realised how much of this stuff I've forgotten :-(
However, my thoughts are that the CZT hasn't been much use other than academic curiosity _because_ there was no inverse. If the inverse has anywhere near same computational cost (not same as complexity, although same complexity gives hope) as DFT then we could be looking at a whole new class of encoding/decoding compressing/decompressing algorithms which _might_ turn out to be better than what we have today. Just because you have a "cleaner" mathematically more general function does not guarantee you'll have better results though, it may just turn out to be better in some cases and worse in others.
What we can be pretty definite about is that a whole bunch of new research opportunities (for which you can read "research grant application opportunities") just opened up in signal processing.
(Score: 1, Interesting) by Anonymous Coward on Saturday October 12 2019, @08:20AM (3 children)
big deal actually for numerical analysis.
pseudo-spectral algorithms are used routinely because of their accuracy, but relying on FFT means constraints on regularly spaced grids and linear ranges of wavenumbers.
for some problems it may turn out that the sparser representation discussed here is good enough, with the advantage of increased accuracy.
(Score: 4, Informative) by Coward, Anonymous on Saturday October 12 2019, @08:53AM (1 child)
But FFT-based methods also work on irregular grids...
https://journals.aps.org/pre/abstract/10.1103/PhysRevE.53.1217 [aps.org]
https://scholars.huji.ac.il/sites/default/files/ronniekosloff/files/wayat.pdf [huji.ac.il]
(Score: 0) by Anonymous Coward on Saturday October 12 2019, @10:15AM
Thanks, appreciate the links, CA.
(Score: 2) by opinionated_science on Saturday October 12 2019, @12:17PM
my first thought was, a nice new machine learning tool.
my second thought was about electrostatics....
(Score: 4, Interesting) by deadstick on Saturday October 12 2019, @01:32PM
Your EE 3xxx text is now obsolete and there's a new one at the bookstore for $250.
(Score: 4, Interesting) by Rupert Pupnick on Saturday October 12 2019, @02:41PM (3 children)
This is a pretty big deal in my corner of the tech world, and it’s nice to see it reported here in SN. As a quick aside, all of these numerical techniques fall into the larger category of z-transforms which are discrete time/frequency equivalents of the continuous math underlying Fourier Transforms. By making a discrete equivalent, you can realize them in everyday digital systems.
I’m not an expert in the underlying mathematical machinery of FFTs, but they really are used almost everywhere in modern digital electronics from consumer grade to more sophisticated measurement and instrumentation systems. Without it, DSP simply does not exist, and there’s no way you could fit the signal processing that currently exists in modern cellphones into anything even close to what we have today.
As one example, in almost every communications system in existence, it is a bandpass filter function that provides the crucial properties of receiver selectivity and noise immunity. In the pre-digital world, this was implemented in LC (using inductors and capacitors) filters that take up large amounts of space at commonly used IF frequencies in the roughly 10 to 100 MHz range. If you’re an analog nerd, calculate for yourself what inductor value you need to get 50 ohms of reactance at 100 MHz, and then look at the physical dimensions you need to make an inductor of this value. For every two orders of filter characteristic (a measure of “sharpness”) you need one inductor. For the 140 MHz IF systems I worked on way back when, a roughly eighth order filter was about the size of half a pack of cigarettes.
(Score: 2) by opinionated_science on Saturday October 12 2019, @06:47PM
to design using LC components there is the Laplace transform, a close relative of the FFT for which there exist many closed form solutions.
It does however still need some solid mathematics for larger systems....
(Score: 2) by jmichaelhudsondotnet on Sunday October 13 2019, @03:00AM (1 child)
What actual applications will this help with?
Am I right to think this will enable emf based radar, imagining, rangefinding, and triangulation to be more accurate over distance with less power?
(Score: 3, Informative) by Rupert Pupnick on Monday October 14 2019, @07:49PM
Hard for me to say how big the incremental improvements will be to existing systems. One thing is for sure, though, and that is unlike a lot of tech and science stuff you read about, this can actually be deployed right away.