3
$\begingroup$

If $x[n] = \left\{\frac 14, \frac 14, \frac 14, \frac 14\right\}$ and the resulting DTFT is $$ \frac 12\exp\left(\frac 32\omega\right)\left(\cos\left(\frac 32\omega\right)+\cos\left(\frac 12\omega\right)\right)\tag{1} $$

I'm looking for a general, computational method for obtaining the general DTFT formula, that works in almost all cases, that doesn't involve doing anything by hand. Is there enough information in a FFT magnitude and phase result, assuming there were enough bins used and appropriate zero-padding was done, to work out the DTFT?

To reiterate, pretend like all you have is the graph below. I'm asking if you can somehow derive the formula equation $(1)$ without doing anything else but looking at that graph. I'm asking if that is possible using just FFT information.

enter image description here

Improve this question
$\endgroup$
  • $\begingroup$ How exactly DTFT is different than FFT? Isn't FFT a certain case of DTFT? What exactly you look for - non power of 2 number of samples for the DTFT? $\endgroup$ – Moti Dec 5 '16 at 18:47
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – msm Dec 5 '16 at 21:29
  • $\begingroup$ @moti Pretend like all you have is that graph. Now, derive the formula 1/2*exp(3/2*w)*(cos(3/2*w)+cos(1/2*w)) without doing anything else but looking at that graph. I'm asking if that is possible using just FFT information. $\endgroup$ – user2514676 Dec 6 '16 at 2:06
  • $\begingroup$ @msm, the reference is okay, i guess, but has atrocious notational convention. $\endgroup$ – robert bristow-johnson Dec 6 '16 at 4:21
  • $\begingroup$ @robertbristow-johnson I have a similar impression from most wiki pages. They are probably most sensible for people from science background. $\endgroup$ – msm Dec 6 '16 at 7:07
1
$\begingroup$

Your question is a bit difficult to comprehend. It seems that you are requesting a closed form solution to the DTFT given the DFT of a sequence. This is of course possible. If there is no time-domain nor frequency-domain aliasing, then we can simply apply the formula for the IDFT on the samples (or equivalently perform the IFFT). Following this, we can apply the formula for DTFT on the time-domain samples. This may not be an answer in the simplified form you want, but it is a closed form expression for the DTFT and can be evaluated at any point. Furthermore, a very good computer algebra system (e.g., Maple, Mathematica, etc.) may be able to reduce it to the form that you have requested (meeting your requirement for no computation by hand).

The DFT is a frequency-domain sampled version of the DTFT. The FFT computes the DFT. Because of this, you could simply apply the Shannon-Nyquist Sampling Theorem and interpolate the points of the DFT using sinc functions,

$$\DeclareMathOperator{\sinc}{sinc} \begin{align} X_{DTFT}(f) &= \sum_{k=-\infty}^{\infty} X_{DFT}[k] \sinc(f - k) \\ &= \sum_{k=0}^{N-1} X_{DFT}[k] \frac{\sin(\pi(f-k))}{N \sin\left(\tfrac{\pi}{N}(f-k)\right)} \end{align}$$

where $\sinc(x) = \frac{\sin(\pi x)}{\pi x}$. This expression is equal to your simplified expression (i.e., it evaluates to the same value at every point). This expression assumes a unit length sampling interval (i.e., $T = 1$). This at least suggests a method for interpolating the DTFT from the DFT samples.

Looking for an exact simplified expression is difficult because different schools of thought will simplify it in different ways. Who is to say that your expression involving trigonometric functions is any better than one involving complex exponentials? For example, isn't the expression $$ X_{DTFT}(f) = \frac{1}{4} + \frac{1}{4} \exp(-j 2 \pi f) + \frac{1}{4} \exp(-j 4 \pi f) + \frac{1}{4} \exp(-j 8 \pi f)$$ exactly what you are after? This is exactly what we would get if we used the approach in the first paragraph. Take the IFFT of the DFT, and then apply the formula for the DTFT. A computer program could do all of this and could evaluate this expression at any point $f$, requiring no computations by hand.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ hey hops, welcome. and thanks for showing me a new $\LaTeX$ operator \DeclareMathOperator{\sinc}{sinc}. i knew about \operatorname{} before. anyway you will get no complaint from me with: $$ X_{DTFT}(f) = \sum_{k=-\infty}^{\infty} X_{DFT}[k] \operatorname{sinc}(f - k),$$ but some folks might find it challenging that the DFT $X[k]$ is defined for $k<0$ or $k \ge N$. but i am fully in agreement with you that the input and output of the DFT is a periodic sequence. but you also need to worry a little about the scaling applied to $f$. are you defining $f=1$ to be the sampling frequency? $\endgroup$ – robert bristow-johnson Dec 30 '16 at 0:34
  • $\begingroup$ and then, you might want to look up the Dirichlet kernel. that's how you deal with this thing with a finite number of $k$. $\endgroup$ – robert bristow-johnson Dec 30 '16 at 0:43
  • $\begingroup$ Thanks for the comment, @robertbristow-johnson. This is my first attempt at an answer. I would love to improve it, so I welcome suggestions. Thanks. After writing, I realized the scaling would come up. I should have been more explicit in my assumption that T = 1 is the sampling period. I'll fix that. Thanks for the suggestion for further reading on the Dirichlet kernel, I'll take a look and see if I can improve the interpolation expression. $\endgroup$ – hops Dec 30 '16 at 6:28
  • $\begingroup$ that Wikipedia article is crap. i can't seem to find a good online reference. $\endgroup$ – robert bristow-johnson Dec 30 '16 at 6:53
  • 1
    $\begingroup$ The new line that you added with the Dirichlet kernel can't be correct, because it is independent of $f$, but the whole point is to define the interpolated version as a function of $f$. I'll look into it a little and see if I can fix it. $\endgroup$ – hops Jan 3 '17 at 2:47
0
$\begingroup$

Depends on how strict you want to be with "almost all cases". If you can make some simplifying assumptions on the form of the DTFT formula, then you could use lsqnonlin() in matlab, or similar curve fitting algorithms, to fit the function to the data. e.g. if you have an N point FFT, and if you know that DTFT must take the form $ \sum_{i=1}^M a_i e^{w_i}$, and if N >> M, then lsqnonlin() could probably solve for the unknown $a_i$ and $w_i$. In the example shown, you have 64 known data points (32 point complex FFT) and would be solving for 8 unknowns (2 terms, each having a complex amplitude and a complex phase), so it would probably work. If N could be on the same order as M, or if the form of the DTFT was totally arbitrary, then probably not.

Improve this answer
$\endgroup$
  • $\begingroup$ How would you know there were two terms you were solving for though? Why not 3 terms or one term? $\endgroup$ – user2514676 Dec 6 '16 at 3:44
  • $\begingroup$ Well, let's say that you asked your non-linear curve fitter to solve for 3 terms when there were really only 2 terms. If it is a good solver, and if you have a sufficiently large data set, it will come back and tell you that that the 3rd term is zero. But that's not totally foolproof. It might come back and tell you that it's some small value. Like I said, you have to be able to make some simplifying assumptions for this to work. it will not work for a completely arbitrary case. $\endgroup$ – Daniel K Dec 6 '16 at 23:02

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.