Sin( x y ) Image Border.

FAST FOURIER TRANSFORM IN C++


Overview

The Fast Fourier Transform (FFT) is a fast method for evaluating the discrete Fourier transform (DFT) defined to be the complex exponential sum, $$ \hat{x}_k = {1 \over \sqrt{N}} \sum_{j=0}^{N-1} x_j W^{j k} \quad n = 0 \ldots N-1 $$ on the sequence $\{ x_k, \quad k = 0 \ldots N-1 \}$ where $W = e^{-2 \pi i / N}$ is an nth root of unity, and i denotes $\sqrt {-1}$

The FFT performs $O(n \: lg \: N)$ operations when N is a power of 2.

Here's C++ software which implements a power of two FFT. We create it as a derived class of the STL vector type.

Features

Download

Source code and executables are distributed under the terms of the GNU General Public License. Current version is 1.0

FFT.cpp FFT implementation. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
FFT.h Header file containing the class definitions. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
testFFT.cpp Main unit test or demo program. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
makefile Makefile Eye icon for source code viewing. View     Compact disk icon for source code download. Download
fftIn.txt Input test file. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
fftOut.txt Output test file. Eye icon for source code viewing. View     Compact disk icon for source code download. Download

Install and Run

On Mac OS X, I use the Xcode IDE; on a Windows platforms, I use the GNU Cygwin toolset for command line compiling and debugging; and on Unix systems, including Mac OS X, I use the built-in gcc compiler and gdb debugger. For online C++ language tutorials, books and references, see links to C++ documentation.

DFT on a Discretized Sine Wave, Sampling Theorem, and Windowing

The discrete Fourier transform (DFT) is a discrete time approximation to the Fourier integral over a finite domain. It assumes the data in the domain is periodic. If it is not, any discontinuity at the beginning and end will generate artificial high frequencies which mix in with the power spectrum, called spectral leakage. To avoid that, people apply windowing functions to the data before applying the FFT.

Here's an example of a DFT on a single frequency and how to use windowing to reduce spectral leakage,

References


Copyright © 2005-2017 by Sean Erik O'Connor. All Rights Reserved.     last updated 01 Jan 17.