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


Orthogonality of the DFT Sinusoids

We now show mathematically that the DFT sinusoids are exactly orthogonal. Let

$\displaystyle s_k(n) \isdef e^{j\omega_k nT} = e^{j2\pi k n /N} = \left[W_N^k\right]^n,
\quad n=0,1,2,\ldots,N-1,
$

denote the $ k$ th DFT complex-sinusoid, for $ k=0:N-1$ . Then

\begin{eqnarray*}
\left<s_k,s_l\right> &\isdef & \sum_{n=0}^{N-1}s_k(n) \overline{s_l(n)}
= \sum_{n=0}^{N-1}e^{j2\pi k n /N} e^{-j2\pi l n /N} \\
&=& \sum_{n=0}^{N-1}e^{j2\pi (k-l) n /N}
= \frac{1 - e^{j2\pi (k-l)}}{1-e^{j2\pi (k-l)/N}}
\end{eqnarray*}

where the last step made use of the closed-form expression for the sum of a geometric series6.1). If $ k\neq l$ , the denominator is nonzero while the numerator is zero. This proves

$\displaystyle \zbox {s_k \perp s_l, \quad k \neq l.}
$

While we only looked at unit amplitude, zero-phase complex sinusoids, as used by the DFT, it is readily verified that the (nonzero) amplitude and phase have no effect on orthogonality.


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-21 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA