FFT Class

FFT Class

FFT functions.

Inheritance Hierarchy

SystemObject
Imsl.MathFFT

Namespace: Imsl.Math
Assembly: ImslCS (in ImslCS.dll) Version: 6.5.2.0

Syntax

C++

Copy

[SerializableAttribute]
public class FFT

<SerializableAttribute>
Public Class FFT

[SerializableAttribute]
public ref class FFT

[<SerializableAttribute>]
type FFT =  class end

The FFT type exposes the following members.

Constructors

	Name	Description
	FFT	Constructs an FFT object.

Top

Methods

	Name	Description
	Backward	Compute the real periodic sequence from its Fourier coefficients.
	Equals	Determines whether the specified object is equal to the current object. (Inherited from Object.)
	Finalize	Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection. (Inherited from Object.)
	Forward	Compute the Fourier coefficients of a real periodic sequence.
	GetHashCode	Serves as a hash function for a particular type. (Inherited from Object.)
	GetType	Gets the Type of the current instance. (Inherited from Object.)
	MemberwiseClone	Creates a shallow copy of the current Object. (Inherited from Object.)
	ToString	Returns a string that represents the current object. (Inherited from Object.)

Top

Remarks

Class FFT computes the discrete Fourier transform of a real vector of size n. The method used is a variant of the Cooley-Tukey algorithm, which is most efficient when n is a product of small prime factors. If n satisfies this condition, then the computational effort is proportional to n log n.

The Forward method computes the forward transform. If n is even, then the forward transform is

$q_{2m - 1} = \sum\limits_{k = 0}^{n - 1} {p_k } \cos \frac{{2\pi km}}{n} \,\,\,\, m = 1,\; \ldots ,\;n/2$

$q_{2m - 2} = - \sum\limits_{k = 0}^{n - 1} {p_k } \sin \frac{{2\pi km}}{n} \,\,\,\, m = 1,\; \ldots ,\;n/2 - 1$

$q_0 = \sum\limits_{k = 0}^{n - 1} {p_k }$

If n is odd, is defined as above for m from 1 to (n - 1)/2.

Let f be a real valued function of time. Suppose we sample f at n equally spaced time intervals of length $\delta$ seconds starting at time . That is, we have

$p_i : = f\left( {t_0 + i\Delta } \right)\, i = 0,\,1, \ldots ,\,n - 1$

We will assume that n is odd for the remainder of this discussion. The class FFT treats this sequence as if it were periodic of period n. In particular, it assumes that $f\left( {t_0 } \right) = f\left( {t_0 + n\Delta } \right)$ . Hence, the period of the function is assumed to be $T = n\Delta$ . We can invert the above transform for p as follows:

$p_m = {1 \over n}\left[ {q_0 + 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\quad q_{2k + 1} } \cos {{2\pi (k+1)m} \over n} - 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\quad q_{2k + 2} } \sin {{2\pi (k+1)m} \over n}} \right]$

This formula is very revealing. It can be interpreted in the following manner. The coefficients q produced by FFT determine an interpolating trigonometric polynomial to the data. That is, if we define

$g\left( t \right) = {1 \over n}\left[{q_0 + 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\quad q_{2k + 1} } \cos {{2\pi (k+1)\left( {t - t_0 } \right)} \over {n\Delta }} - 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\quad q_{2k + 2} } \sin {{2\pi (k+1)\left( {t - t_0 } \right)} \over {n\Delta }}} \right]$

$= {1 \over n}\left[ {q_0 + 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\quad q_{2k + 1} } \cos {{2\pi (k+1)\left( {t - t_0 } \right)} \over T} - 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\quad q_{2k + 2} } \sin {{2\pi (k+1)\left( {t - t_0 } \right)} \over T}} \right]$

then we have

$f\left( {{\rm{t}}_{\rm{0}} + \left( {i - 1} \right)\Delta } \right) = g\left( {{\rm{t}}_{\rm{0}} + \left( {i - 1} \right)} \right)\Delta$

Now suppose we want to discover the dominant frequencies, forming the vector P of length (n + 1)/2 as follows:

$P_0: = \left| {q_0 } \right|$

$P_k: = \sqrt {q_{2k - 2}^2 + q_{2k - 1}^2 } \,\,\,\, k = 1,\;2,\; \ldots ,\;\left( {n - 1} \right)/2$

These numbers correspond to the energy in the spectrum of the signal. In particular, corresponds to the energy level at frequency

${k \over T} = {k \over {n\Delta }} \,\,\,\,\,\,\,\, k = 0,\;1,\; \ldots ,\;{{n - 1} \over 2}$

Furthermore, note that there are only $(n + 1)/2 \approx T/(2\Delta)$ resolvable frequencies when n observations are taken. This is related to the Nyquist phenomenon, which is induced by discrete sampling of a continuous signal. Similar relations hold for the case when n is even.

If the Backward method is used, then the backward transform is computed. If n is even, then the backward transform is

$q_m = p_0 + \left( { - 1} \right)^m p_{n - 1} + 2\sum\limits_{k = 0}^{n/2 - 1} {p_{2k + 1} } \cos \frac{{2\pi (k+1)m}}{n} - 2\sum\limits_{k = 0}^{n/2 - 2} {p_{2k + 2} } \sin \frac{{2\pi (k+1)m}}{n}$

If n is odd,

$q_m = p_0 + 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\;p_{2k + 1} } \cos {{2\pi (k+1)m} \over n} - 2\sum\limits_{k = 0}^{\left( {n - 3} \right)/2} {\;p_{2k + 2} } \sin {{2\pi (k+1)m} \over n}$

The backward Fourier transform is the unnormalized inverse of the forward Fourier transform.

FFT is based on the real FFT in FFTPACK, which was developed by Paul Swarztrauber at the National Center for Atmospheric Research.

Reference

Imsl.Math Namespace

Other Resources

Example