<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE> Fast Fourier Transform functions</TITLE>
<META NAME="GENERATOR" CONTENT="DOC++ 3.4.6">
</HEAD>
<body bgcolor="#ffffff" link="#0000ff"
vlink="#dd0000" text="#000088" alink="9000ff">
<A HREF = "http://www.cstr.ed.ac.uk/">
<IMG align=left BORDER=0 SRC = "cstr.gif"></A>
<A HREF="http://www.cstr.ed.ac.uk/projects/speech_tools.html">
<IMG BORDER=0 ALIGN=right SRC="est.jpg" width=150 height=93></A>
<br>
<br clear=left>
<p align=right>
<TABLE BORDER=0><TR>
<TD VALIGN=TOP><H2> <A HREF="#DOC.DOCU">Fast Fourier Transform functions</A></H2></TD></H2></TD></TR></TABLE>
<TABLE>
<TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="slowFFT"></A>
<A HREF=slowFFT.html><B>slowFFT</B></A></TD><TD><BR>
<I>Basic in-place FFT.</I>
</TD></TR><TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="FFT"></A>
<A HREF=FFT.html><B>FFT</B></A></TD><TD><BR>
<I>Alternate name for slowFFT</I>
</TD></TR><TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="slowIFFT"></A>
<A HREF=slowIFFT.html><B>slowIFFT</B></A></TD><TD><BR>
<I>Basic inverse in-place FFT int slowFFT</I>
</TD></TR><TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="IFFT"></A>
<A HREF=IFFT.html><B>IFFT</B></A></TD><TD><BR>
<I>Alternate name for slowIFFT</I>
</TD></TR><TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="power_spectrum"></A>
<A HREF=power_spectrum.html><B>power_spectrum</B></A></TD><TD><BR>
<I>Power spectrum using the fastFFT function.</I>
</TD></TR><TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="power_spectrum_slow"></A>
<A HREF=power_spectrum_slow.html><B>power_spectrum_slow</B></A></TD><TD><BR>
<I>Power spectrum using the slowFFT function</I>
</TD></TR><TR><TD VALIGN=TOP>
<IMG ALT="o" BORDER=0 SRC=icon1.gif><A NAME="fastFFT"></A>
<A HREF=fastFFT.html><B>fastFFT</B></A></TD><TD><BR>
<I>Fast FFT An optimised implementation by Tony Robinson to be used in preference to slowFFT</I>
</TD></TR>
</TABLE>
<A NAME="DOC.DOCU"></A>
<BLOCKQUOTE>
<para>
These are the low level functions where the actual FFT is
performed. Both slow and fast implementations are available for
historical reasons. They have identical functionality. At this time,
vectors of complex numbers are handled as pairs of vectors of real and
imaginary numbers.
</para>
<P><formalpara> <title>What is a Fourier Transform ?</title>
<P><para>
The Fourier transform of a signal gives us a frequency-domain
representation of a time-domain signal. In discrete time, the Fourier
Transform is called a Discrete Fourier Transform (DFT) and is given
by:
<P><BR><CENTER><IMG BORDER=0 SRC=g000024.gif><BR></CENTER>
<P>where \(y = (y_0,y_1,... y_{n-1})\) is the DFT (of order \(n\) ) of the
signal \(x = (x_0,x_1,... x_{n-1})\), where
\(\omega_{n}^{0},\omega_{n}^{1},... \omega_{n}^{n-1}\) are the n
complex nth roots of 1.
</para>
<P><para>
The Fast Fourier Transform (FFT) is a very efficient implementation of
a Discrete Fourier Transform. See, for example "Algorithms" by Thomas
H. Cormen, Charles E. Leiserson and Ronald L. Rivest (pub. MIT Press),
or any signal processing textbook.
</para>
<P></formalpara>
</BLOCKQUOTE>
<DL><DT><DD></DL><P><P><I><A HREF="index.html">Alphabetic index</A></I> <I><A HREF="HIER.html">Hierarchy of classes</A></I></P><HR>
<A HREF = "http://www.ed.ac.uk/">
<IMG align=right BORDER=0 SRC = "edcrest.gif"></A>
<P Align=left><I>This page is part of the
<A HREF="http://www.cstr.ed.ac.uk/projects/speech_tools.html">
Edinburgh Speech Tools Library</A> documentation
<br>
Copyright <A HREF="http://www.ed.ac.uk"> University of Edinburgh</A> 1997
<br>
Contact: <A HREF="mailto:speech_toolss@cstr.ed.ac.uk">
speech_tools@cstr.ed.ac.uk </a>
</P>
<br clear=right>
