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:

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

Listen Again: Meditations on Loneliness
Original broadcast date: April 24, 2020. We're a social species now living in isolation. But loneliness was a problem well before this era of social distancing. This hour, TED speakers explore how we can live and make peace with loneliness. Guests on the show include author and illustrator Jonny Sun, psychologist Susan Pinker, architect Grace Kim, and writer Suleika Jaouad.
Now Playing: Science for the People

#565 The Great Wide Indoors
We're all spending a bit more time indoors this summer than we probably figured. But did you ever stop to think about why the places we live and work as designed the way they are? And how they could be designed better? We're talking with Emily Anthes about her new book "The Great Indoors: The Surprising Science of how Buildings Shape our Behavior, Health and Happiness".
Now Playing: Radiolab

The Third. A TED Talk.
Jad gives a TED talk about his life as a journalist and how Radiolab has evolved over the years. Here's how TED described it:How do you end a story? Host of Radiolab Jad Abumrad tells how his search for an answer led him home to the mountains of Tennessee, where he met an unexpected teacher: Dolly Parton.Jad Nicholas Abumrad is a Lebanese-American radio host, composer and producer. He is the founder of the syndicated public radio program Radiolab, which is broadcast on over 600 radio stations nationwide and is downloaded more than 120 million times a year as a podcast. He also created More Perfect, a podcast that tells the stories behind the Supreme Court's most famous decisions. And most recently, Dolly Parton's America, a nine-episode podcast exploring the life and times of the iconic country music star. Abumrad has received three Peabody Awards and was named a MacArthur Fellow in 2011.