Discrete Fourier Transform

In Mathematics , the discrete Fourier transform (DFT), sometimes called the '''finite Fourier transform''', is a Fourier Transform widely employed in Signal Processing and related fields to analyze the frequencies contained in a sampled Signal , solve Partial Differential Equations , and to perform other operations such as Convolution s. The DFT can be computed efficiently in practice using a Fast Fourier Transform (FFT) algorithm. The sequence of ''N'' complex numbers ''x''₀, ..., ''x''_''N''−1 are transformed into the sequence of ''N'' complex numbers ''X''₀, ..., ''X''_''N''−1 by the DFT according to the formula: : $X_k = \sum_{n=0}^{N-1} x_n e^{-rac{2 \pi i}{N} k n} \quad \quad k = 0, \dots, N-1$ where ''e'' is the Base Of The Natural Logarithm , ''i'' is the Imaginary Unit ( $i^2=-1$ ), and π is Pi . The transform is sometimes denoted by the symbol $\mathcal{F}$ , as in $\mathbf{X} = \mathcal{F}(\mathbf{x})$ or $\mathcal{F} \mathbf{x}$ . The inverse discrete Fourier transform (IDFT) is given by : $x_n = rac{1}{N} \sum_{k=0}^{N-1} X_k e^{rac{2\pi i}{N} k n} \quad \quad n = 0,\dots,N-1.$ Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/''N'') and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/''N''. A normalization of $1/\sqrt{N}$ for both the DFT and IDFT makes the transforms Unitary , which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways). (The convention of a negative sign in the exponent is often convenient because it means that $X_k$ is the amplitude of a "positive frequency" $2\pi k/N$ . Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.) In the following discussion the terms "sequence" and "vector" will be considered interchangeable. PROPERTIES Completeness The discrete Fourier transform is an invertible, Linear Transformation : $\mathcal{F}:\mathbf{C}^N o \mathbf{C}^N$ with C denoting the set of Complex Numbers . In other words, for any ''N'' > 0, an ''N''-dimensional complex vector has a DFT and an IDFT which are in turn ''N''-dimensional complex vectors. Orthogonality The vectors exp(2π''i kn/N'') form an Orthogonal basis over the set of ''N''-dimensional complex vectors: : $\sum_{n=0}^{N-1} \left(e^{ rac{2\pi i}{N} kn} ight) \left(e^{-rac{2\pi i}{N} k'n} ight) =N~\delta_{kk'}$ where δ_''kn'' is the Kronecker Delta . The Plancherel theorem and Parseval's theorem If ''X''_''k'' and ''Y''_''k'' are the DFTs of ''x''_''n'' and ''y''_''n'' respectively then we have the Plancherel Theorem : _n = rac{1}{N} \sum_{k=0}^{N-1} X_k Y^---_k where the star denotes complex conjugation. Parseval's Theorem is a special case of the Plancherel theorem and states:
	The Shift Theorem, Above, Is Also An Expression Of The Implicit Periodicity Of The Inverse DFT, Because It Shows That The DFT Amplitudes <math>X	"k" class="copylinks" target="_blank">{Link without Title} \,</math> are unaffected by a circular (periodic) shift of the inputs, which is simply a choice of Origin and therefore only affects the phase Periodic boundary conditions play an important role in many applications of the DFT When solving Differential Equation s they allow periodic boundary conditions to be automatically satisfied, and thus can be a useful property See also the ''applications'' section below

whose coefficients ''f''_''k'' /''N'' are given by the DFT of ''x''_''n'', above, is called the Trigonometric Interpolation Polynomial of degree ''N'' − 1. It is the unique function of this form that satisfies the property: ''p''(2π''n''/''N'') = ''x''_''n'' for ''n'' = 0, ..., ''N'' − 1.

Because of aliasing, however, the ''form'' of the trigonometric interpolation polynomial is not unique, in that any of the frequencies can be shifted by any multiple of ''N'' while maintaining the property ''p''(2π''n''/''N'') = ''x''_''n'' . In particular, the following form is often preferred:

:

p(t) = rac{f_0}{N} + rac{f_1}{N} e^{it} + \cdots + rac{f_{N/2}}{N} \cos(Nt/2) + rac{f_{N/2+1}}{N} e^{(-N/2+1)it} + \cdots + rac{f_{N-1}}{N} e^{-it}

for Even

N

(where the Nyquist Amplitude

f_{N/2}

should be handled specially) or, for odd

N

:

:

p(t) = rac{f_0}{N} + rac{f_1}{N} e^{it} + \cdots + rac{f_{\lfloor N/2 
floor}}{N} e^{\lfloor N/2 
floor it} + rac{f_{\lfloor N/2 
floor+1}}{N} e^{(-\lceil N/2 
ceil+1)it} + \cdots + rac{f_{N-1}}{N} e^{-it}

:<math>\sum {n 0}^{N-1}x_n^2 = \sum_{k=0}^{N-1}X_k^2</math>
{ Border "1" cellpadding="5" cellspacing="0" align="center"

	CATEGORIES ABOUT DISCRETE FOURIER TRANSFORM

	fourier analysis

	digital signal processing

	numerical analysis

	transforms

	unitary operators

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Discrete Fourier Transform