2
$\begingroup$

Studying DSP on my own time on Coursera.

Was given a proof to why the Fourier basis is orthogonal, but I can't figure it out. Here is how it is proof goes.

Consider the Fourier basis $$ \left\lbrace \mathbf w^{(k)} \right\rbrace_{k=0,...,N−1} $$

defined as:

$$ \mathbf w^{(k)}_n = e^{−j\frac{2\pi}{N} nk} $$

Let us compute the inner product, that is

\begin{align} <\mathbf w^{(k)}, \mathbf w^{(h)} > &= \sum_{n=0}^{N-1} \mathbf w^{*(k)}[n] \mathbf w^{(h)}[n]\\ &= \sum_{n=0}^{N-1} e^{j\frac{2\pi}{N} nk} e^{−j\frac{2\pi}{N} nh}\\ & = \sum_{n=0}^{N-1} e^{-j\frac{2\pi}{N} n (h-k)}\\ &= \begin{cases} N & \text{if}\quad k=h\\[2ex] 0 & \text{otherwise} \end{cases} \end{align}

I do understand all of the derivation except the last step. How does one arrive at the conclusion that when $k\neq h$ the inner product is $0$. Would appreciate any help with that.

$\endgroup$
5
$\begingroup$

Just use the formula for the geometric series (I use $l=h-k\neq mN$):

$$\sum_{n=0}^{N-1}e^{-j\frac{2\pi}{N}nl}=\frac{1-e^{-j\frac{2\pi}{N}Nl}}{1-e^{-j\frac{2\pi}{N}l}}=\frac{1-e^{-j2\pi l}}{1-e^{-j\frac{2\pi}{N}l}}=\frac{1-1}{1-e^{-j\frac{2\pi}{N}l}}=0,\quad l\neq mN$$

$\endgroup$
  • $\begingroup$ How does one solve this sum for $l=0$? It looks like it is undefined, $$\sum_{n=0}^{N-1}e^{-j\frac{2\pi}{N}nl}=\frac{1-e^{-j\frac{2\pi}{N}Nl}}{1-e^{-j\frac{2\pi}{N}l}}=\frac{1-e^{-j2\pi l}}{1-e^{-j\frac{2\pi}{N}l}}=\frac{1-1}{1-1}=undefined$$ $\endgroup$ – flashburn Jan 17 '18 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.