# Explained: The Discrete Fourier Transform

##### Nov 25, 2009 by Larry Hardesty

(PhysOrg.com) -- In 1811, Joseph Fourier, the 43-year-old prefect of the French district of Isčre, entered a competition in heat research sponsored by the French Academy of Sciences. The paper he submitted described a novel analytical technique that we today call the Fourier transform, and it won the competition; but the prize jury declined to publish it, criticizing the sloppiness of Fourier’s reasoning. According to Jean-Pierre Kahane, a French mathematician and current member of the academy, as late as the early 1970s, Fourier’s name still didn’t turn up in the major French encyclopedia the Encyclopædia Universalis.

Now, however, his name is everywhere. The Fourier transform is a way to decompose a signal into its constituent frequencies, and versions of it are used to generate and filter cell-phone and Wi-Fi transmissions, to compress audio, image, and video files so that they take up less bandwidth, and to solve differential equations, among other things. It’s so ubiquitous that “you don’t really study the Fourier transform for what it is,” says Laurent Demanet, an assistant professor of applied mathematics at MIT. “You take a class in signal processing, and there it is. You don’t have any choice.”

The Fourier transform comes in three varieties: the plain old Fourier transform, the Fourier series, and the discrete Fourier transform. But it’s the discrete Fourier transform, or DFT, that accounts for the Fourier revival. In 1965, the computer scientists James Cooley and John Tukey described an algorithm called the fast Fourier transform, which made it much easier to calculate DFTs on a computer. All of a sudden, the DFT became a practical way to process .

To get a sense of what the DFT does, consider an MP3 player plugged into a loudspeaker. The MP3 player sends the speaker audio information as fluctuations in the voltage of an electrical signal. Those fluctuations cause the speaker drum to vibrate, which in turn causes air particles to move, producing sound.

An audio signal’s fluctuations over time can be depicted as a graph: the x-axis is time, and the y-axis is the voltage of the electrical signal, or perhaps the movement of the speaker drum or air particles. Either way, the signal ends up looking like an erratic wavelike squiggle. But when you listen to the sound produced from that squiggle, you can clearly distinguish all the instruments in a symphony orchestra, playing discrete notes at the same time.

That’s because the erratic squiggle is, effectively, the sum of a number of much more regular squiggles, which represent different frequencies of sound. “” just means the rate at which air molecules go back and forth, or a voltage fluctuates, and it can be represented as the rate at which a regular squiggle goes up and down. When you add two frequencies together, the resulting squiggle goes up where both the component frequencies go up, goes down where they both go down, and does something in between where they’re going in different directions.

The DFT does mathematically what the human ear does physically: decompose a signal into its component frequencies. Unlike the analog signal from, say, a record player, the digital signal from an MP3 player is just a series of numbers, representing very short samples of a real-world sound: CD-quality digital audio recording, for instance, collects 44,100 samples a second. If you extract some number of consecutive values from a digital signal — 8, or 128, or 1,000 — the DFT represents them as the weighted sum of an equivalent number of frequencies. (“Weighted” just means that some of the frequencies count more than others toward the total.)

The application of the DFT to wireless technologies is fairly straightforward: the ability to break a signal into its constituent frequencies lets cell-phone towers, for instance, disentangle transmissions from different users, allowing more of them to share the air.

The application to data compression is less intuitive. But if you extract an eight-by-eight block of pixels from an image, each row or column is simply a sequence of eight numbers — like a digital signal with eight samples. The whole block can thus be represented as the weighted sum of 64 frequencies. If there’s little variation in color across the block, the weights of most of those frequencies will be zero or near zero. Throwing out the frequencies with low weights allows the block to be represented with fewer bits but little loss of fidelity.

Demanet points out that the DFT has plenty of other applications, in areas like spectroscopy, magnetic resonance imaging, and quantum computing. But ultimately, he says, “It’s hard to explain what sort of impact Fourier’s had,” because the Fourier transform is such a fundamental concept that by now, “it’s part of the language.”

Provided by Massachusetts Institute of Technology (news : web)

Explore further: Strong teams attract crowds for international cricket

## Related Stories

#### The not-so-digital future of digital signal processing

Apr 07, 2008

Fungi processing audio signals. E. Coli storing images. DNA acting as logic circuits. It’s possible, and in some cases, it’s already happened. In any event, performing digital signal processing using organic and chemical ...

#### Sony's Major Strategic Shift: MP3 Format Support

Sep 23, 2004

Sony Corp., an electronics giant, said on Thursday that in future some of its new MP3 player models will feature direct support for MP3 format in addition to its own proprietary ATRAC (Adaptive Transform Acous ...

#### Femtogram-level chemical measurements now possible

Mar 27, 2008

Finding a simple and convenient technique that combines nanoscale structural measurements and chemical identification has been an elusive goal. With current analytical instruments, spatial resolution is too low, signal-to-noise ...

#### New method reveals all you need to know about 'waveforms'

Oct 07, 2009

The National Institute of Standards and Technology has unveiled a method for calibrating entire waveforms -- graphical shapes showing how electrical signals vary over time -- rather than just parts of waveforms as is current ...

#### Researchers develop world's fastest bar code reader

Sep 30, 2008

(PhysOrg.com) -- Building on a series of recent breakthroughs in ultrafast analog-to-digital conversion, UCLA engineers have designed a bar code reader that is nearly a thousand times faster than any device currently in use.

#### Improving our ability to peek inside molecules

Sep 16, 2008

(PhysOrg.com) -- It's not easy to see a single molecule inside a living cell. Nevertheless, researchers at Lawrence Livermore National Laboratory are helping to develop a new technique that will enable them ...

## Recommended for you

#### Optimising the future with mathematics

6 hours ago

How will science address the challenges of the future? In collaboration with Australia's chief scientist Ian Chubb, we're asking how each science discipline will contribute to Australia now and in the fu ...

#### Strong teams attract crowds for international cricket

Mar 06, 2014

The strength of the team—not the promise of a close contest—is the biggest draw to crowds in international cricket, new research has found.

#### Improving radiation therapies for cancer mathematically

Mar 05, 2014

In a paper published in December in the SIAM Journal on Scientific Computing, authors Li-Tien Cheng, Bin Dong, Chunhua Men, Xun Jia, and Steve Jiang propose a method to optimize radiation therapy treatments in cancer patien ...

#### Computational study finds maximum packing density of 55,000 different shapes

Mar 05, 2014

A team of researchers at the University of Michigan has used computational and analytical analysis to find the maximum packing density of 55,000 uniquely shaped particles. In their paper published in the ...

#### Secret to the perfect pancake is discovered

Mar 04, 2014

In a collaboration with Meadowhall Shopping Centre, students from the University's Maths Society (SUMS) developed, trialled and tested a formula which enables pancake-lovers across the world to rustle-up ...

##### Bob_Kob
5 / 5 (6) Nov 25, 2009
No, I like articles like this. Probably because ive just done a course on signals and systems that used a lot of Fourier transforms in it.
##### El_Nose
not rated yet Nov 25, 2009
I agree this is not news, it is an article put out by MIT every week to explain a random topic --
##### frajo
3 / 5 (2) Nov 25, 2009
I agree this is not news, it is an article put out by MIT every week to explain a random topic --

It's a nice kind of widening one's knowledge into topics one is not acquainted with. Today mathematics, tomorrow perhaps genetics - nobody knows it all. Aerobics for the brain.
##### codesuidae
not rated yet Nov 25, 2009
I enjoyed the article. Wouldn't mind seeing a deeper dive into how DFT algorithms work, their limitations and some practical issues about how one goes about using them (e.g., the utility of applying an envelope function to a block of stream data before the DFT, the impact this has on the result, etc).
##### mattytheory
5 / 5 (1) Nov 25, 2009
"Demanet points out that the DFT has plenty of other applications, in areas like spectroscopy, magnetic resonance imaging, and quantum computing."

I wonder if the weighted sum concept applies to spectroscopy in the context of galactic redshift? DIBBS!
##### physpuppy
5 / 5 (1) Nov 25, 2009
The Fourier transform is so amazing - just think about it: without the work of this 19th century mathematician, MRI would not be possible. Structural analysis of chemicals and materials would be much more difficult and results more error prone (synthesis of new drugs). The fast Fourier transform fits amazingly well in digital computers - base 2 - if you saw the code for the calculation you would be astounded at its elegance. The basic code (when written in assembly code) can fit into less than 4k of memory (I used it on a PDP-8 computer back in the 70's)

##### physpuppy
not rated yet Nov 25, 2009
I've liked this explanation of FT:

You have a bunch of bells, each plays a different tone. Your task is to find out which bells are a little out of tune. But you have many bells to test and you have to leave early because you have a hot date.

So without Fourier, the obvious way to do this is to go to each bell, ring it, and use some device to measure the frequency and compare.

With Fourier, you get a stick, hit them all at once, take your measurement, the FFTs separate the individual frequencies out, you compare to the correct frequency and you're done- much faster.

Okay, so what use unless you're a musician ?

This can be applied to anything with waves!
electromagnetism = waves, the FT spectrometer attempts to stimulate all frequencies at once, you record the result and FFT deconvolutes the frequencies. In the time it would take to measure each individual frequency, you can sum up many FT scans and get far better signal/noise and to do all sorts of new types of analysis
##### tkjtkj
5 / 5 (1) Dec 01, 2009
the article was not designed for those of you who actually use FT's .. it was clearly meant for those of us who do not. It was well-written, clear, concise, and informative. I enjoyed it.
##### channie
not rated yet Jan 22, 2010
this article has been well written in way which disentangles the complexity and difficulty associated with the FT especially for beginners. more importantly, it states the application of FT, where it can be used & in some examples how it can be used.

## More news stories

#### Study shows men and women both biased against women's math abilities

(Phys.org) —A study conducted by business and economic researchers Ernesto Reuben, Paola Sapienza, and Luigi Zingales, has found that both men and women hold biases against women's math abilities. In their ...

#### Study finds investors prefer good-looking male backed entrepreneurial ventures

(Phys.org) —A study conducted by a team of researchers from Harvard, Wharton and MIT has revealed that venture capitalists prefer to back entrepreneurial opportunities when pitched by a man and that they ...

When it comes to shopping for gifts, we try to select things we think people both want and need. According to a new study in the Journal of Consumer Research, focusing too much on the gift recipient can lead to giving the gi ...

#### What's the upside of feeling too sad for chocolate?

The instant gratification and the pleasure derived from consuming excessive chocolate and deep-fried foods can lead way to a double-edged sword of negative consequences ranging from weight gain to feelings of low self-esteem. ...

#### New analyses verify the use of fire by Peking Man

Zhoukoudian Locality 1 in northern China has been widely known for the discovery of the Middle Pleistocene human ancestor Homo erectus pekinensis ( known as Peking Man ) since the 1920s. By 1931, the suggestion ...

#### Diets high in animal protein may help prevent functional decline in elderly individuals

A diet high in protein, particularly animal protein, may help elderly individuals function at higher levels physically, psychologically, and socially, according to a study published in the Journal of the American Geriatrics So ...

#### Dynamic stressing of a global system of faults results in rare seismic silence

In the global aftershock zone that followed the major April 2012 Indian Ocean earthquake, seismologists noticed an unusual pattern – a dynamic "stress shadow," or period of seismic silence when some faults near failure ...

#### Patients prefer specific info from docs for prostate cancer

(HealthDay)—Although patients with prostate cancer endorse multiple sources of information, they report greatest satisfaction with information from the treating physician about patient outcomes, according ...

#### Empathy chimpanzees offer is key to understanding human engagement

In their latest study about empathy, Yerkes National Primate Research Center researchers Matthew Campbell, PhD, and Frans de Waal, PhD, have shown chimpanzees exhibit flexibility in their empathy, just as ...

#### USPSTF: Evidence lacking for drug use interventions

(HealthDay)—The U.S. Preventive Services Task Force (USPSTF) has found that there is currently insufficient evidence to recommend primary care interventions to prevent or reduce illicit drug use or nonmedical ...