# 2d dft

1. Jun 5, 2013

### Number2Pencil

1. The problem statement, all variables and given/known data

Calculate, by hand, the DFT of cos(2*pi(fx*m + fy*n)). It should simplify to something simple. It should NOT be left as a summation.

2. Relevant equations

2D DFT Formula:
$$\tilde{s(k,l)} = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} s(m,n) e^{-j 2 \pi (\frac{1}{M}mk + \frac{1}{N}ln)}$$

3. The attempt at a solution

$$\tilde{s(k,l)} = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} cos(2 \pi (f_x m + f_y n)) e^{-j 2 \pi (\frac{1}{M}mk + \frac{1}{N}ln)}$$

One of Euler's Formulas:

$$cos(u+v) = \frac{1}{2}(e^{ju + jv} + e^{-ju -jv})$$

After much algebra crunching, I wound up with this:

$$\tilde{s(k,l)} = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} \left[ \frac{1}{2}e^{-j2 \pi \frac {-f_x m M N + m k N + l n M - f_y n M N} {MN} } + \frac{1}{2} e^{-j2 \pi \frac {f_x m M N + f_y n M N + m k N + l n M} {MN}} \right]$$

I am really not sure how to simplify this double geometric sum. Does it look recognizable? Was there an earlier simplification I could take?

2. Jun 5, 2013

### haruspex

Consider just one of the two added terms. As a function of n, it's of the form exp(An+B) = exp(A)nexp(B). So isn't it just the sum of a geometric series?

3. Jun 5, 2013

### Number2Pencil

So if e^{An+B} = e^{An} e^{B}, then e^{B} simply acts as a constant for the internal geometric sum?

[(1-A^M)/(1-A)] e^{B} ???

And then I can take the geometric sum again?

The original cosine function is not separable...is it?

4. Jun 5, 2013

### haruspex

Looks ok to me.