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 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 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