FFT

FFT

FFT is an abbreviation for a Fast Fourier Transform.

The Fourier Transform is a mathematical tool developed and named
after Jean Baptiste Fourier (1768 - 1830) and is commonly used to
convert a signal from the time domain (amplitude-vs-time) to the
frequency domain (amplitude-vs-frequency). A frequency domain plot
is also known as a spectra plot.

The Fast Fourier Transform (FFT) is a computationally efficient
implementation of the Fourier Transform developed by J.W. Cooley and
J.W. Tukey in 1965. The Fast Fourier Transform is limited to block
sizes which are even powers of 2.

For example, if a FFT is performed on a pure sinusoidal signal, the
resulting spectra would be single peak (line). Real world signals
are a composite of many sinusoidal signals; examining the signal's
spectra clearly shows the frequency tones which are present.

What the FFT (or any Fourier transform) really gives you, when applied to a
sample of finite duration (as they all are), is the spectrum corresponding
to the waveform made by _looping_ the sample. So it isn't terribly
meaningful for transient signals. However, if the signal doesn't decay too
fast we can factor out the decay before applying the Fourier Transform. But
we still need to find a place where the waveform at least nearly repeats
(and for FFT, takes 2^n samples). This is relatively easy for timbres with
harmonic partials, but can be nearly impossible for inharmonic timbres.

If we use a sample containing n cycles of the fundamental, with frequency
f, then the frequency resolution of the spectrum is no better than f/n.

Or putting it another way, if the sample is t seconds long, the frequency
resolution is no better than 1/t hertz. e.g. A 2 second sample can't give
you better than 0.5 Hz resolution. So all those big numbers in the ratios
are meaningless. Better to give it as decimal frequency ratios (or cents).

This is the uncertainty principle, as made famous in quantum mechanics.
Time and frequency are complementary. Only a signal of infinite duration
has a line spectrum. A signal of finite duration has a continuous (or
"blurry") spectrum.

For Joe Pehrson,

I shouldn't have said that multiplication in the time domain gives addition
and subtraction in the frequency domain. I realise now that this is only
useful as a mnemonic device (or mantra) when you already know what it
means, but it is simply confusing for a novice because its literal (or most
obvious) interpretation is completely wrong. Sorry. Listen to Paul E.

Regards,

-- Dave Keenan
http://dkeenan.com

i have done extensive explorations with FFT and have generated some
interesting sounds
i used
SMS tools for windows
http://www.iua.upf.es/~sms/sms.html
and CERES for linux

Pat Pagano, Director
South East Just Intonation Society
http://indians.australians.com/meherbaba/
http://www.screwmusicforever.com/SHREESWIFT/
----- Original Message -----
From: David C Keenan <D.KEENAN@UQ.NET.AU>
To: <tuning@egroups.com>
Sent: Monday, November 20, 2000 11:31 PM
Subject: [tuning] FFT

> What the FFT (or any Fourier transform) really gives you, when applied to
a
> sample of finite duration (as they all are), is the spectrum corresponding
> to the waveform made by _looping_ the sample. So it isn't terribly
> meaningful for transient signals. However, if the signal doesn't decay too
> fast we can factor out the decay before applying the Fourier Transform.
But
> we still need to find a place where the waveform at least nearly repeats
> (and for FFT, takes 2^n samples). This is relatively easy for timbres with
> harmonic partials, but can be nearly impossible for inharmonic timbres.
>
> If we use a sample containing n cycles of the fundamental, with frequency
> f, then the frequency resolution of the spectrum is no better than f/n.
>
> Or putting it another way, if the sample is t seconds long, the frequency
> resolution is no better than 1/t hertz. e.g. A 2 second sample can't give
> you better than 0.5 Hz resolution. So all those big numbers in the ratios
> are meaningless. Better to give it as decimal frequency ratios (or cents).
>
> This is the uncertainty principle, as made famous in quantum mechanics.
> Time and frequency are complementary. Only a signal of infinite duration
> has a line spectrum. A signal of finite duration has a continuous (or
> "blurry") spectrum.
>
> For Joe Pehrson,
>
> I shouldn't have said that multiplication in the time domain gives
addition
> and subtraction in the frequency domain. I realise now that this is only
> useful as a mnemonic device (or mantra) when you already know what it
> means, but it is simply confusing for a novice because its literal (or
most
> obvious) interpretation is completely wrong. Sorry. Listen to Paul E.
>
> Regards,
>
> -- Dave Keenan
> http://dkeenan.com
>
>
> You do not need web access to participate. You may subscribe through
> email. Send an empty email to one of these addresses:
> tuning-subscribe@egroups.com - join the tuning group.
> tuning-unsubscribe@egroups.com - unsubscribe from the tuning group.
> tuning-nomail@egroups.com - put your email message delivery on hold for
the tuning group.
> tuning-digest@egroups.com - change your subscription to daily digest
mode.
> tuning-normal@egroups.com - change your subscription to individual
emails.
>
>
>

--- In tuning@egroups.com, David C Keenan <D.KEENAN@U...> wrote:

http://www.egroups.com/message/tuning/15706

> For Joe Pehrson,
>
> I shouldn't have said that multiplication in the time domain gives
addition and subtraction in the frequency domain. I realise now that
this is only useful as a mnemonic device (or mantra) when you already
know what it means, but it is simply confusing for a novice because
its literal (or most obvious) interpretation is completely wrong.
Sorry. Listen to Paul E.
>
> Regards,
>
> -- Dave Keenan
> http://dkeenan.com

Thanks, Dave, for your clarification. I was already a little
confused before you mentioned this, so no real harm was done...

Thanks, also, to everybody for answering some of my questions.

Gee... this stuff is interesting. I will be anxious to hear more of
the kind of music generated with the FFT methods... (and will "check
out" those posted...)

________ ___ __ _ _
Joseph Pehrson

>What the FFT (or any Fourier transform) really gives you, when applied to a
>sample of finite duration (as they all are), is the spectrum corresponding
>to the waveform made by _looping_ the sample. So it isn't terribly
>meaningful for transient signals. However, if the signal doesn't decay too
>fast we can factor out the decay before applying the Fourier Transform.

Has anyone used wavelet analysis instead of FT for this sort
of timbral analysis? It's supposed to capture the development of a
signal's components better, or at least I think it does based on my
limited familiarity with this sort of math.

--
wm

> Has anyone used wavelet analysis instead of FT for this sort
> of timbral analysis? It's supposed to capture the development of a
> signal's components better, or at least I think it does based on my
> limited familiarity with this sort of math.

Yes, there have been wavelet analyses of sound done. I don't remember any
names at the moment, but I'm sure if you give "wavelet" and "sound" to a
search engine you'll find plenty on the web. But the FFT is still the
workhorse of digital signal processing. CSound has two types of sound
analysis built in, phase vocoder analysis and linear predictive coding.
There is also a free program called SNDAN which uses phase vocoder analysis
and something called McAaulay-Quatieri analysis. SNDAN is free for Windows
at

http://www.bath.ac.uk/~masjpf/NCD/software/sndan/sndan.html

The Composers Desktop Project also contains sound analysis capabilities.
Their URL is

http://www.bath.ac.uk/~masjpf/CDP/CDP.htm

In general, given a steady-state signal or a mathematical function in any
number of dimensions, one typically tries to find a parsimonious
representation of it -- a representation with as few terms as possible --
using some form of truncated infinite series. The fewer terms the better,
and both wavelets and Fourier series are possibilities depending on the
nature of what you're trying to analyze. Tschebycheff polynomials are also
good in some circumstances; they are related to discrete cosine transforms
and can usually be computed with a variant of the FFT.

*However*, the complex time-varying signals from natural sounds and music
pretty much rule out a parsimonious representation regardless of what
analytical techniques you choose to apply. None of the techniques work very
well on noise, for example. It is still not possible with reasonably
inexpensive computing technology to play a recording of, say, Shostakovich's
4th symphony, and derive the score from the sound computationally.
--
M. Edward Borasky
mailto:znmeb@teleport.com
http://www.borasky-research.com

Cold leftover pizza: it's not just for breakfast any more!

Hi,

Edward Borasky wrote:

> There is also a free program called SNDAN which uses phase vocoder
> analysis and something called McAaulay-Quatieri analysis.

From the LemurPro documentation, for Mac and Power Mac (a really neat
shareware program):

Lemur is a Macintosh implementation of an extended
McAulay-Quatieri algorithm for sound analysis and synthesis based on
the work of Rob Maher and Jim Beauchamp at the Computer Music
Project of the University of Illinois School of Music. It analyzes AIFF
sample files to produce an intermediate representation (a Lemur analysis
file), and uses these analysis files to synthesize AIFF sample files.
Time scaling, frequency scaling, and frequency shifting, and magnitude
scaling are possible. All may be time-variant, and all but time scaling
may be applied selectively to the different frequency components of the
sound.
Lemur analysis consists of a series of short-time Fourier spectra
from which significant frequency components are selected. Similar
components in successive spectra are linked to form time-varying
partials, called tracks. The number of significant frequency components,
and, thus, the number of tracks may vary over the duration of a sound.
Synthesis is performed by a bank of oscillators, each oscillator
reproducing the frequency and amplitude trajectory of a single track.
Phase accuracy is maintained using cubic phase (parabolic frequency)
interpolation between spectra. The Lemur model allows extensive
modification of the sound using Lemur's built-in editing functions, or
using other customized editors to modify the intermediate analysis file
before resynthesis. The Lemur file format contains only amplitude,
frequency, and linking information for each track, making it easy for
users to write customized Lemur file editors.

Lemur Pro will run on any Macintosh with System 7 and a floating
point math coprocessor (68881 or 68882), AND on any Power
Macintosh. (Lemur Pro is a fat application, containing 68k and
PowerMac native code.)

<http://www.cerlsoundgroup.org/Lemur/>

Clark

>I will be anxious to hear more of
>the kind of music generated with the FFT methods...

One doesn't usually generate _music_ with FFT-based methods, at least not
directly. One typically analyses and synthesises timbres.

I hope it is clear from Ed Borasky's and Clark Panaccione's posts that all
these software tools:
SMS, CERES, SNDAN, CSound, CDP, LemurPro
have to do _WAAAAY_ more than just a Fourier transform in order to analyse
a sound sufficiently to be able to synthesise it convincingly.

The Fourier transform alone (FFT or otherwise) is really only useful for
continuous sounds, particularly harmonic ones. It has no concept of attack,
decay or release.

If anyone finds a good introduction to the wavelet transform (it can assume
an understanding of the Fourier and/or Laplace transforms) please let me
know. I understand it is used in speech recognition. It seems to me it
might be useful for analysing transient timbres too.

Regards,
-- Dave Keenan
http://dkeenan.com

> >I will be anxious to hear more of
> >the kind of music generated with the FFT methods...
>
> One doesn't usually generate _music_ with FFT-based methods, at least not
> directly. One typically analyses and synthesises timbres.

Well, yes and no. Bill Sethares does quite a bit with additive synthesis.
The examples in his book are much closer to pure "FFT music" than some
others. He basically uses windowed FFTs to determine the spectrum of sounds,
then resynthesizes them with an additive synthesizer, after editing the
FFT-generated spectrum to simplify it. One could, assuming small enough
FFTs, synthesize music with them. As long as one doesn't need real-time
sound generation, one can use any technique, and I can think of some
instances where FFT synthesis might be useful as a complement to analysis
that was also done using FFTs.

The converse of this is that you don't need to use FFTs for the analysis
either -- other things like filter banks and maximum entropy spectral
analysis have their uses.
--
M. Edward Borasky
mailto:znmeb@teleport.com
http://www.borasky-research.com

Cold leftover pizza: it's not just for breakfast any more!

Here's a (fairly) gentle introduction to FFTs and phase vocoders from the
CDP project folks. Enjoy!

http://www.bath.ac.uk/~masjpf/CDP/techp/operpvoc.htm

--
M. Edward Borasky
mailto:znmeb@teleport.com
http://www.borasky-research.com

Cold leftover pizza: it's not just for breakfast any more!