Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

The DFT

For a length $ N$ complex sequence $ x(n)$ , $ n=0,1,2,\ldots,N-1$ , the discrete Fourier transform (DFT) is defined by

$\displaystyle X(\omega_k) \isdef \sum_{n=0}^{N-1}x(n) e^{-j\omega_k t_n} = \sum_{n=0}^{N-1}x(n) e^{-j 2\pi kn/N},
\quad k=0,1,2,\ldots N-1
$

\begin{eqnarray*}
t_n &\isdef & nT = \mbox{$n$th sampling instant (sec)} \\
\omega_k &\isdef & k\Omega = \mbox{$k$th frequency sample (rad/sec)} \\
T &\isdef & 1/f_s = \mbox{time sampling interval (sec)} \\
\Omega &\isdef & 2\pi f_s/N = \mbox{frequency sampling interval (rad/sec)}
\end{eqnarray*}

We are now in a position to have a full understanding of the transform kernel:

$\displaystyle e^{-j\omega_k t_n} = \cos(\omega_k t_n) - j \sin(\omega_k t_n)
$

The kernel consists of samples of a complex sinusoid at $ N$ discrete frequencies $ \omega_k$ uniformly spaced between 0 and the sampling rate $ \omega_s \isdeftext 2\pi f_s$ . All that remains is to understand the purpose and function of the summation over $ n$ of the pointwise product of $ x(n)$ times each complex sinusoid. We will learn that this can be interpreted as an inner product operation which computes the coefficient of projection of the signal $ x$ onto the complex sinusoid $ \cos(\omega_k t_n) + j \sin(\omega_k t_n)$ . As such, $ X(\omega_k)$ , the DFT at frequency $ \omega_k$ , is a measure of the amplitude and phase of the complex sinusoid which is present in the input signal $ x$ at that frequency. This is the basic function of all linear transform summations (in discrete time) and integrals (in continuous time) and their kernels.


Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications --- Second Edition'', by Julius O. Smith III, W3K Publishing, 2007, ISBN 978-0-9745607-4-8.
Copyright © 2014-04-06 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA