Engineers solve 50-year-old puzzle in signal processing

October 10, 2019

AMES, Iowa - 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.

Stoytchev said he stumbled on the idea to attempt to formulate the missing algorithm while looking for analogies to help the graduate students in his "Computational Perception" course understand the fast Fourier transform. He read a lot of the signal-processing literature and couldn't find anything about the inverse to the related chirp z-transform.

"I got curious," he said. "Is that because they couldn't explain it, or is it because it doesn't exist? It turned out it didn't exist."

And so he decided to try to find a fast inverse algorithm.

Sukhoy said the inverse algorithm is a harder problem than the original, forward algorithm and so "we needed better precision and more powerful computers to attack it." He also said a key was seeing the algorithm within the mathematical framework of structured matrices.

Even then, there were lots of computer test runs "to show everything was working - we had to convince ourselves that this could be done."

It took courage to keep attacking the problem, said James Oliver, director of Iowa State's Student Innovation Center and former director of the university's Virtual Reality Applications Center. Stoytchev and Sukhoy acknowledge Oliver in their paper "for creating the research environment in which we could pursue this work over the past three years."

Oliver said Stoytchev earned his support for a mathematical and computational challenge that hadn't been solved for 50 years: "Alex has always impressed me with his passion and commitment to take on big research challenges. There is always risk in research and it takes courage to devote years of hard work to a fundamental problem. Alex is a gifted and fearless researcher."
-end-


Iowa State University

Related Cell Phone Articles from Brightsurf:

Cell phone location used to estimate COVID-19 growth rates
Cell phone location data shows that in counties where activity declined at workplaces and increased at home, coronavirus infection rates were lower.

Study: Anonymized cell phone location data can help monitor COVID-19 growth rates
In a new study published in JAMA Internal Medicine, researchers from Mount Auburn Hospital and the University of Pennsylvania analyzed anonymous, county-level cell phone location data and incidence of COVID-19.

To make a good impression, leave cell phone alone during work meetings
New hires especially should keep their cell phones stashed away during business meetings, a new study strongly implies.

Flat-panel technology could transform antennas, wireless and cell phone communications
Researchers at Los Alamos National Laboratory are reinventing the mirror, at least for microwaves, potentially replacing the familiar 3-D dishes and microwave horns we see on rooftops and cell towers with flat panels that are compact, versatile, and better adapted for modern communication technologies.

Cell phone injuries
Cell phones are mainstays of daily life. This observational study analyzed 20 years of data on people who went to emergency departments with head and neck injuries from cell phone use to estimate the number of injuries, learn what types of injuries there were, and understand how the injuries occurred, such as from distracted driving or walking.

Cell phone-based microscope leads to possible strategy for treating river blindness
River blindness, or onchocerciasis, is a disease caused by a parasitic worm (Onchocerca volvulus) found primarily in Africa.

Cell phone data coupled with sewage testing show drug use patterns
The drugs people inhale, inject or ingest ultimately end up in some form down the toilet.

Cell phone use and distracted driving begins in the mind
Even simple cell phone conversations can cause distracted driving. Researchers have found listening on the phone while driving creates a lag in the mind to extract itself from one object before fixing attention on another object.

What motivates parents to protect children from cell phone addiction?
A new study examined the role parental mediation can play in protecting children from the potential negative effects of smartphone use, comparing the perceived risk and different types of mediation and parenting styles.

Catching the IMSI-catchers: SeaGlass brings transparency to cell phone surveillance
University of Washington security researchers have developed a new system called SeaGlass to detect anomalies in the cellular landscape that can indicate where and when IMSI-catchers, cell-site simulators and other devices used in cell phone surveillance are present.

Read More: Cell Phone News and Cell Phone Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.