Stories
Slash Boxes
Comments

SoylentNews is people

posted by janrinok on Saturday October 12 2019, @03:41AM   Printer-friendly
from the lots-of-numbers dept.

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.


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by takyon on Saturday October 12 2019, @06:58AM (3 children)

    by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Saturday October 12 2019, @06:58AM (#906253) Journal

    Sounds like we could get new compression algorithms out of it.

    --
    [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2  
  • (Score: 1, Interesting) by Anonymous Coward on Saturday October 12 2019, @07:12AM

    by Anonymous Coward on Saturday October 12 2019, @07:12AM (#906254)

    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

    by FatPhil (863) <reversethis-{if.fdsa} {ta} {tnelyos-cp}> on Saturday October 12 2019, @01:28PM (#906313) Homepage
    Compression algorithms that use FFT-like transforms generally use them over such short lengths that O(n.lg(n)) isn't vastly different from O(n^2), once the constant factor's fixed.
    --
    I know I'm God, because every time I pray to him, I find I'm talking to myself.
  • (Score: 3, Funny) by driverless on Sunday October 13 2019, @01:51AM

    by driverless (4770) on Sunday October 13 2019, @01:51AM (#906489)

    Already been done:

    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.

    I'm the creator of a similar transform for compression, the Fast Driverless Transform (FDT):

    FDT( data ) = ∅

    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.