Sunday, 15 March 2015

proof - struggling to understand why Fourier basis is orthogonal


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.



Answer



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$$


No comments:

Post a Comment

readings - Appending 内 to a company name is read ない or うち?

For example, if I say マイクロソフト内のパートナーシップは強いです, is the 内 here read as うち or ない? Answer 「内」 in the form: 「Proper Noun + 内」 is always read 「ない...