Forums

N-point DFt of cosine and sine

Started by AlwaysLearning 7 months ago7 replieslatest reply 7 months ago167 views

Hello,

I have been reading this interesting Article and I have a question about it: https://www.dsprelated.com/showarticle/607.php

My goal is to compute the N point DFT of a cosine signal and a sine signal. Looking at the article, I understand up to equation (4)


And I understand how to use the geometric series to solve this series and I get:

x(m) = (A/2)*(  [1- exp(-j*2*pi*(m-k)) ] / [1- exp(-j*2*pi*(m-k)/N) ]   + [1- exp(-j*2*pi*(m+k)) ] / [1- exp(-j*2*pi*(m+k)/N) ] )

(correct me if I am wrong) but it looks like this equation only has an interesting value at m=k. So taking L'Hospital (to handle the 0/0) and evaluating at k=m (a lot of things nicely cancel out)

(A/2) * [ 1/(1/N) + 1/( (1/N) * exp(-j*2*pi*(k+k)/N) ) ]

= (A/2) * [N + N * exp(-j*4*pi*k/N)]


Thus x(m)  = .5*A*N*[1 + exp(-j*4*pi*k/N)]

Does that look right so far? My problem is that when I take the IDFT of the above x(m), I don't get the original x(n) = A*cos(...) signal. This makes me think that I am messing the math up somewhere. Can you help show me what I am missing?


Thank you



[ - ]
Reply by CedronApril 3, 2020

This blog article of mine completes what you started.

DFT Bin Value Formulas for Pure Real Tones

Note: The simplification assumption done with equation (20) is extremely significant.


[ - ]
Reply by kazApril 3, 2020

without diving in math equations what happened to variable (n) that appears in first equations but disappears in the final equation:

x(m)  = .5*A*N*[1 + exp(-j*4*pi*k/N)]

N is resolution, k is for bin frequency. 

surely you need to account for input sequence samples per frame and all bins.

[ - ]
Reply by AlwaysLearningApril 3, 2020

Hi Kraz,

Thanks for your reply. There is no 'n' because I have transition from x(n) -> DFT -> x(m), when I solve the series it eliminates the n variable. Does that make sense?  I am just following https://www.dsprelated.com/showarticle/771.php steps (14) through (17).

[ - ]
Reply by vladorApril 3, 2020

Hi,

The second sum in (4) is zero when m=k, because in that case exp(-j*2*pi*(m+k))=1. You don't need L'Hospital for that, look in the article that you linked. Therefore X(k)=A*N/2. The second sum is non-zero only for m=N-k, and X(N-k)=A*N/2. All other X(m)=0.


Stay safe!

V

[ - ]
Reply by AlwaysLearningApril 3, 2020

Hi Vlador,

Thank you for your post.

What you said makes sense to me. So basically, my equation:

(eq1):

x(m) = (A/2)*(  [1- exp(-j*2*pi*(m-k)) ] / [1- exp(-j*2*pi*(m-k)/N) ]   + [1- exp(-j*2*pi*(m+k)) ] / [1- exp(-j*2*pi*(m+k)/N) ] )

becomes a piecewise definition as follows:

x(m) = .5*A*N, m=k

x(m) = .5*A*N,m=N-k

x(m) = 0 otherwise.

To me, this means that we should be able to write x(m) as follows:

(eq2)

x(m) = .5*A*N*[δ(m-k)+δ(m-(N-k))]

If this is true, I should be able to take the IDFT of x(m) and get A*cos(2*pi*n*k/N). Let's check it:

(eq3)

x(n) = (1/N)*∑m=0 to N-1 of .5*A*N*[δ(m-k)+δ(m-(N-k))]*e^(j*2*pi*n*m/N)

(eq4)

x(n)=.5*A*(δ(m-k)*e^(j*2*pi*n*m/N) + δ(m-(N-k))*e^(j*2*pi*n*m/N))

(eq5)

x(n)=.5*A*(e^(j*2*pi*n*k/N)+e^(j*2*pi*n*(N-k)/N))

note, (eq6)

e^(j*2*pi*n*(N-k)/N)

= e^(j*2*pi*n*(N/N-k/N))

= e^(j*2*pi*n*1)*e^(j*2*pi*n*(-k)/N) = 1*e^(-j*2*pi*n*k/N)

Thus (eq5) becomes (eq7) below

x(n)=.5*A*(e^(j*2*pi*n*k/N)+e^(-j*2*pi*n*k/N))

and finally using Euler's equation,

x(n)=.5*A*cos(2*pi*n*k/N)

Does this look right to you?

I am going to attempt the same process but with sin(...) to ensure that I have the concept down. Thank you so much for your help.


You stay safe as well. I wonder if people will be reading these posts a year from now and realize that we are talking about the virus. Let's hope this all goes away quickly.



[ - ]
Reply by vladorApril 4, 2020

AlwaysLearning,

You got it. Except that there's no .5 term in the last equation, it is used for transition from exp to cos.

Interestingly, there's finally this one thing that managed to unite most of the world!


[ - ]
Reply by CedronApril 5, 2020
I regard to: "(correct me if I am wrong) but it looks like this equation only has an interesting value at m=k."

The equations of mine I referred you to earlier are degenerate at integer frequencies as the article explains, and the integer solution is well known.  For values very near integers, the equations are a bit numerically unstable.  This article gives an alternative form of the solution in those cases:

An Alternative Form of the Pure Real Tone DFT Bin Value Formula

In essence, the 0/0 gets factored out.  I would argue that is a tad more interesting.

Indeed, stay safe.