Nav: Home

Solving a 50-year-old puzzle in signal processing, part two:

March 25, 2020

AMES, Iowa - Iowa State University's Alexander Stoytchev says it's one of the "most popular and useful" algorithms around - even though most of us have never heard of it.

But, if you've used a cell phone, browsed the internet or needed a medical image, you've benefitted from the fast Fourier transform (FFT).

The transform and its inverse (known as the IFFT) have been in use since 1965. For example, in your cell phone the FFT is used to analyze the signal received from the base station (or cell tower). The IFFT solves the inverse problem: it synthesizes the signal that your phone sends to the base station.

In 1969, researchers developed a more useful, generalized version of the FFT known as the chirp z-transform (CZT). But nobody had come up with a generalized version of the IFFT. It was a 50-year-old puzzle in signal processing.

That is, until last fall when two Iowa State engineers - Stoytchev and Vladimir Sukhoy - announced in a research paper they had come up with a closed-form solution for the inverse chirp z-transform (ICZT) and a fast algorithm for computing it. (The paper sparked a lot of interest in the signal-processing community, tallying more than 26,000 accesses since October.)

Now Stoytchev - an associate professor of electrical and computer engineering who's also affiliated with the university's Virtual Reality Applications Center - and Sukhoy - a lecturer in electrical and computer engineering - report new research results about their algorithm.

In a paper just published online by Scientific Reports, a Nature Research journal, the two show how their algorithm functions "on the unit circle," which refers to a special case of its parameters. (Their previous paper only highlighted operations "off the unit circle.")

The paper details how the algorithm can work with frequency components that are generated by sample points from the unit circle in the complex plane. These points form a contour that is known as the chirp contour. Unlike the IFFT, which can only work with equispaced sampling points that fully cover the unit circle, the ICZT algorithm can work with contours that cover only a fraction of the unit circle. It can also work with contours that wrap around and perform multiple revolutions over the circle. This enables the use of certain (non-orthogonal) frequency components, which lifts one of the main restrictions of the IFFT and could lead to better spectrum utilization.

The paper identifies the parameter values for which the algorithm is numerically accurate and for which it isn't, and describes how to estimate its accuracy as a function of the parameters. (Technical note: It shows that the singularities of the ICZT of size n are related to the elements of the Farey sequence of order n-1. This is an interesting connection because Farey sequences often appear in number theory.)

The paper demonstrates that, on the unit circle, the ICZT algorithm achieves high accuracy with only 64-bit floating-point numbers and does not require additional numerical precision, making it easier to implement. It reports the algorithm can pair well with the existing CZT algorithm to do back-to-back signal analysis and signal synthesis. And it shows that the algorithm is fast (it operates in what's known as O(n log n) time).

"This algorithm is more general than the IFFT, but maintains the same speed," Stoytchev said.

That's good news for the engineers working to solve all kinds of signal-processing challenges:

"Application domains that could benefit from this," the Iowa State engineers wrote in the paper, "include signal processing, electronics, medical imaging, radar, sonar, wireless communications, and others."

Iowa State University

Related Cell Phone Articles:

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.
Implantable sensor relays real-time personal health data to a cell phone
Personalized medicine is one step closer thanks to tiny, implantable sensors that can send data to a computer or cell phone to give early warning of a person's developing health problems.
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.
Astronomers propose a cell phone search for galactic fast radio bursts
Fast radio bursts seem to come from distant galaxies, but there is no obvious reason that, every once in a while, an FRB wouldn't occur in our own Milky Way galaxy too.
Your cell phone could curb the intensity of your workout
Talking or texting on a cell phone during exercise will lower the intensity of a workout and also affect balance.
Counting molecules with an ordinary cell phone
The new visual readout method to count individual nucleic acid molecules within a sample can be performed by any cell-phone camera.
More Cell Phone News and Cell Phone Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

There's so much we've yet to explore–from outer space to the deep ocean to our own brains. This hour, Manoush goes on a journey through those uncharted places, led by TED Science Curator David Biello.
Now Playing: Science for the People

#555 Coronavirus
It's everywhere, and it felt disingenuous for us here at Science for the People to avoid it, so here is our episode on Coronavirus. It's ok to give this one a skip if this isn't what you want to listen to right now. Check out the links below for other great podcasts mentioned in the intro. Host Rachelle Saunders gets us up to date on what the Coronavirus is, how it spreads, and what we know and don't know with Dr Jason Kindrachuk, Assistant Professor in the Department of Medical Microbiology and infectious diseases at the University of Manitoba. And...
Now Playing: Radiolab

Dispatch 1: Numbers
In a recent Radiolab group huddle, with coronavirus unraveling around us, the team found themselves grappling with all the numbers connected to COVID-19. Our new found 6 foot bubbles of personal space. Three percent mortality rate (or 1, or 2, or 4). 7,000 cases (now, much much more). So in the wake of that meeting, we reflect on the onslaught of numbers - what they reveal, and what they hide.  Support Radiolab today at