Orthogonality in Discrete Fourier Transforms

  • Thread starter bdforbes
  • Start date
  • #1
152
0
My professor stated that the following orthogonality condition holds:

[tex]\sum_{n=0}^N cos(2\pi mn/N)cos(2\pi kn/N)=0[/tex]

where m != k, and 0<= m,k < N.

I couldn't prove this, so I plugged in specific values: N=4, m=1, k=3. I found that the sum equals 2. Likewise for other situations where m+k=N, it comes out non-zero.

Is the condition incorrect?
 

Answers and Replies

  • #2
152
0
I'm absolutely sure that my calculations are correct. This seems similar to resonance; at a particular frequency the components resonate and reinforce each other, whereas for other frequencies there is no resonance and they cancel to zero. It seems like this then implies there are only N/2 mutually orthogonal cos() basis functions and N/2 mutually orthogonal sin() basis functions. This is strange though because there are 2N mutually orthogonal complex exponentials which have the following orthogonality condition:

[tex]\sum_{n=0}^{N-1}
\left(e^{ \frac{2\pi i}{N} kn}\right)
\left(e^{-\frac{2\pi i}{N} k'n}\right)
=N~\delta_{kk'}[/tex]

where k,k' range between -(N-1) and +(N-1)
 
  • #3
matt grime
Science Advisor
Homework Helper
9,395
3
There are only N linearly independent exponentials:

exp(2ki\pi/N)

as k goes from 0 to N-1 (or 1 to N).

Notice that there are actually 2N-1 integers in the range -N+1 to N-1, anyway.
 
  • #4
152
0
Hmm. So DFTs only have positive exponentials but FTs have positive AND negative?

In any case, it still appears that the given orthogonality condition for the cosines is incorrect, right?
 
  • #5
matt grime
Science Advisor
Homework Helper
9,395
3
Well, the DFT is explained as being over the complex numbers, and FT over the reals, usually. So a 2N dimensional real space is N complex dimensional, and you see everything is consistent.

If you think about attempting to extract cos or sin from the exponential version using only *real* coefficients, then you need both the +ve and -ve exponents.


I'm being reticent on the original question, not because you're wrong, but because I haven't figured out what your professor was attempting to say: you should speak to him, it would be better all round.
 
  • #6
152
0
That makes sense now. In FTs we have the time domain and frequency domain, both of which are in the reals, whereas in DFTs, we pull coefficients from the complex numbers. So that part is solved, we still have the same number of mutually orthogonal basis functions.

I'll ask my professor today about the original problem. The bottom line is that we need a condition that allows us to pull the coefficients a_m and b_m out of this sum:

[tex]\frac{a_0}{2}+\sum_{m=1}^{N-1}\left[a_m cos(2\pi mn/N)+b_m sin(2\pi mn/N)\right][/tex]

With continuous time we would just multiply by a cos or sin, and integrate over all time, but in the discrete case, we have to sum with respect to the N samples in time we are taking.
The sum above really appears to have non-orthogonal components. Wouldn't it be equivalent to just have the sum

[tex]\sum_{m=1}^{\left\lfloor \frac{N+1}{2}\right\rfloor[/tex]

since this sums over a maximal set of mutually orthogonal functions?
 

Related Threads on Orthogonality in Discrete Fourier Transforms

  • Last Post
Replies
2
Views
3K
Replies
1
Views
2K
Replies
1
Views
1K
  • Last Post
Replies
15
Views
2K
Replies
8
Views
3K
Replies
8
Views
4K
Replies
10
Views
2K
Replies
2
Views
1K
Replies
2
Views
4K
Replies
1
Views
3K
Top