Talk:Discrete-time Fourier transform

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] Should articles be merged

Should this article be merged with discrete Fourier transform? Michael Hardy 01:34, 2 Jun 2005 (UTC)

No, but I do not see anything wrong with merging discrete-time Fourier transform with Fourier series since the forward discrete-time Fourier transform is just the reverse Fourier series.
I don't think any of the Fourier transform articles should be merged. I think it is important to make it absolutely clear that there are four separate and distinct types of FT's:
  • Continuous-time Fourier Transform (CTFT)
  • Discrete-time Fourier Transform (DTFT)
  • Discrete Fourier Transform (DFT)
  • Fourier series
Obviously, there are relationships between all four of these types of FT, but each one is different from the others, and each serves its own purpose. -- Metacomet 06:02, 24 December 2005 (UTC)
I agree with Meta. In a world without hyperlinks, I might feel differently. But fortunately we no longer live there. --Bob K 14:04, 19 March 2006 (UTC)

[edit] Plots and resolution

The plots used to show the increase of resolution actually show something else. They show the effect of the DFT on a frequency that is between the frequency it samples. A clearer example could be produced by transforming a smooth function of frequency instead of the Dirac delta that that example uses.

[edit] DTFT vs. DFT (moved from User talk:Stevenj)

At http://en.wikipedia.org/w/index.php?title=Discrete-time_Fourier_transform&diff=32124402&oldid=32123635 I don't think you quite grasped the significance of "DFT". There is one underlying DTFT, which contains an infinite number of non-zero values. Since we cannot compute all of them, we choose a DFT size (N) to sample the DTFT. Different choices produce different DFT's (i.e. different resolution). So "DFT" is really what I meant to say. --Bob K 18:11, 20 December 2005 (UTC)

It's not a DFT if you have N < L, for example. Anyway, please use the Talk page of the article. —Steven G. Johnson 18:16, 20 December 2005 (UTC)
Okay, I read that paragraph through again and I see that you were specifically referring to the zero-padded case of N > L, where it is a DFT. I've rephrased it to distinguish these two cases more clearly at that point. (Note, by the way, that there are pruned FFT algorithms that can potentially exploit zeros in the input, although the savings in practice are not generally very great.) —Steven G. Johnson 18:26, 20 December 2005 (UTC)

[edit] Relationship between discrete and continuous

The article does not provide any connection between the use of \omega \,, in radians per sample, to represent the spectrum of a discrete-time signal, and the use of \omega \,, in radians per second, to represent the spectrum of a continuous-time signal. The two are related by the sampling rate, f_s \, in samples per second:

\mathrm{radians \ per \ sample} = \mathrm{ radians \ per \ second \over samples \ per \ second }

It is difficult to show this relationship explicitly because it is common practice to use a single symbol, \omega \,, to represent two very different concepts, angular frequency per unit time and angular frequency per sample.

-- Metacomet 05:38, 24 December 2005 (UTC)

The relationship is not at all difficult to show. But I disagree with the original author(s), who [apparently] deemed it obvious (i.e. too easy). Rather it is the source of much confusion and misunderstanding, so I have added it to the article. radians per sample is an abstraction called normalized frequency. It is primarily useful when making a point (as in a textbook) that does not depend on the actual sample-rate. But the DTFT can be written in terms of angular or ordinary frequency ( as I have done), when the sample-rate is actually important (as when using the DTFT for a frequency measurement).
--Bob K 16:56, 20 March 2006 (UTC)

[edit] Why introduce both f and ω in the introduction?

Is it necessary to include the discussion, in the introduction, relating frequency f in cycles per sample (which is not even correct) to angular frequency ω in radians per sample? I do not think it serves any purpose, particularly in the introduciton, to open the whole can of worms about these two different ways of representing frequency. IMO, it would be simpler, more concise, and less confusing simply to define the DTFT using angular frequency (in radians per sample) right at the beginning, and to avoid any mention of frequency at all, which is completely unnecessary. -- Metacomet 05:47, 24 December 2005 (UTC)

Notice that the definition contains no mention of sample-rate, or equivalently the time-interval between samples. That means f\, is a normalized frequency, which is the actual frequency (cycles per second) divided by the sample rate (samples per second). And therefore its units are indeed cycles per sample.
In my opinion, this article (and others) should introduce concepts in terms of real-world units so that beginners can immediately see the relevance. The notational simplifications afforded by normalized units should also be explained. But many readers will not need that information, so we should not force it on them by putting it at the beginning.
--Bob K 20:45, 17 March 2006 (UTC)

[edit] Notation for rect and tri functions

What is with this notation for the rect and tri funcitions with the 2-delta subscripts? Is that a common way of representing these functions? Why not simply introduce a scaling factor to the argument, such as:

\mathrm{rect} \left( { n \over N } \right)

or

\mathrm{rect} \left( { \omega \over W } \right)

This approach seems a lot simpler and more intuitve than using the subscripted delta notation.


I would propose changing the definitions to the following, which I believe are far more standard and far simpler to use:

  • Rectangle function
\operatorname{rect} (\lambda) = \begin{cases} 1 & -{1 \over 2} \leq \lambda \leq { 1 \over 2 } \\ 0 & \mbox{otherwise} \end{cases}
i think that we will run into problems later (involving the sign function, step function, analytic signal, hilbert, at least in the continuous domain) unless we adjust that definition to be:
  • Rectangle function
\operatorname{rect} (\lambda) = \begin{cases} 1 & |\lambda| < \frac{1}{2} \\ \frac{1}{2} & |\lambda| = \frac{1}{2} \\ 0 & \mbox{otherwise} \end{cases}


and

  • Triangle function
\operatorname{tri} ( \lambda ) = \begin{cases} 1 + 2 \lambda ; & - {1 \over 2 }\leq \lambda \leq 0 \\ 1 - 2 \lambda ; & 0 < \lambda \leq {1 \over 2 } \\ 0 & \mbox{otherwise} \end{cases}


where, for example,

\lambda = { n \over N } \,

or

\lambda = { \omega \over W } \,


-- Metacomet 07:40, 24 December 2005 (UTC)

there are several different notations, and they all have their own good points. The one I used, with the 2Δ as subscript, is the one I have found in several DSP-related books. On the other hand, I found the one you suggest in physics-related books. According to me, the best thing to do would be to start a proper article about the rect and tri functions, choosing only one notation (the one you suggest is more consistent) and link to that, just like we did for the unit step and the sinc. Alessio Damato 09:37, 24 December 2005 (UTC)

I just did a quick search on Wikipedia, and I found an article for the rectangle function but nothing for the triangle function. The notation and definition in the rectangle article are similar if not identical to what I have proposed. As you suggest, it may make sense to create a similar article for the triangle function. -- Metacomet 15:29, 24 December 2005 (UTC)

I am not a big fan of using the symbol Δ to represent a number, since Δ is, as you know, very often used as an operator to represent, for example, the change in or difference between two numbers:

\Delta x = x_2 - x_1 \,

Alternatively, it is sometimes used to represent the Laplace operator.

The other drawback to using Δ in the context of physics or engineering is that it is not at all clear what dimensions or units of measure are associated with this symbol. If you use a variable such as T to scale the time domain t, or W to scale the frequency domain ω, then it is generally clear that the units of measure are seconds in the one case, and radians per second or radians per sample in the other case. -- Metacomet 15:29, 24 December 2005 (UTC)

I have created a new article called triangular function as a mathematics-related stub. Please check it out, and expand if you like. Thanks. -- Metacomet 18:51, 28 December 2005 (UTC)

[edit] Change in DTFT for Unit Step?

I placed a negative in the exponential for the DTFT of the unit step function u[n]. Can anyone verify that this is correct? This is what my textbook had.

First off, you're definitely right (I just did it out by hand, and checked in some tables). Also, for some reason 130.63.96.199 decided to flip the frequency domain entry in the table for the unit step with the one below it. I flipped them back. I'm not too sure about the others, though (for example, the DTFT Transform table on Wikibooks [1] has exp(-an) in the fourth row where this has exp(-jan)... pretty sure the other one is at fault here, though) --Dirk Gently 03:54, 6 December 2006 (UTC)

[edit] Is the transform for sinc correct?

I am certainly no expert in this area, but it seems that the transform listed for (W/pi)*sinc(W*n) to rect(w/W)*e^(jaw) is incorrect. If rect is 1 from -(1/2) to (1/2) then the transform should have a (1/2) in it. ie. rect(w/(2W), otherwise it won't work correctly.

I've found another table which seems to support this. However I'm not sure so I don't want to make a change.

I agree, and I added the condition: 0 < W \le \pi
From row 12 of Table of important Fourier transforms:
\mathrm{sinc}(W t) \quad \Longleftrightarrow \quad \frac{\pi}{W}\cdot \mathrm{rect}\left(\frac{\pi}{W} f \right)
And from row 23:
\sum_{n=-\infty}^{\infty} \delta(t - n) \quad \Longleftrightarrow \quad \sum_{k=-\infty}^{\infty} \delta \left( f - k \right) \quad
From which this Fourier transform (DTFT) follows:
\mathrm{sinc}(W n) \quad \Longleftrightarrow \quad \sum_{k=-\infty}^{\infty} \frac{\pi}{W}\cdot \mathrm{rect}\left(\frac{\pi}{W} (f-k) \right) = \sum_{k=-\infty}^{\infty} \frac{\pi}{W}\cdot \mathrm{rect}\left(\frac{\omega -2\pi k}{2W} \right)
The width of the \mathrm{rect}()\, is 2W\,. And the spacing of \mathrm{rect}()'s\, is 2\pi\,. So when 2W \le 2\pi\,, the -\pi < \omega < \pi \, region of the DTFT comprises just the k=0\, term of the summation:
\frac{\pi}{W}\cdot \mathrm{rect}\left(\frac{\omega}{2W} \right)
--Bob K 23:56, 16 March 2006 (UTC)


[edit] Notation for X()

The notation: X(e^{i \omega})\, does not make sense for 9 of the 13 entries in Table 1 . X(\omega)\, works for all 13 entries, and it is also the notation used in Table 2.
--Bob K 18:47, 17 March 2006 (UTC)

[edit] The X(eiω) notation

This article uses the notation X(eiω) for the resulting function, already in the definition of the transform, without providing a rationale. I know that this notation is in common use, in particular in the signal processing community. But as far as I can see, it is not a necessary concept in the defintion of the transform. I would rather see an defintion like

X'(\omega) = \sum_{n=-\infty}^{\infty} x[n] \,e^{-i \omega n}\,

which, after providing the rationale, later is rephrased as

X(e^{i \omega}) = \sum_{n=-\infty}^{\infty} x[n] \,e^{-i \omega n}\,

and pointing out that X and X' are two related, but different, functions.

This distinction between X and X' (as they are defined here) is very important. For example, in the relation

x[n] \cdot y[n] \, \Leftrightarrow \frac{1}{2 \pi} X(e^{i \omega}) * Y(e^{i \omega})

it is important to realize that the convolution operation should be made on the X' and Y' functions rather than on the X and Y functions. This is not obviously clear from the current notation used in these formulas. --KYN 21:00, 31 August 2006 (UTC)

The rationale can be found at Discrete-time_Fourier_transform#Periodicity. But I am a member of the signal processing community who never liked the X(e^{i \omega})\, notation. The X_T(f)\, notation, used in the article, is better, because it can represent both sides of the equality:
\sum_{k = -\infty}^{\infty} X(f - {k f_s}) = \sum_{n=-\infty}^{\infty} T\cdot x(nT) \cdot e^{- i 2\pi f n T}\,
Therefore I would lean toward defining the DTFT in terms of f\, or \omega\, and save the X(e^{i \omega})\, notation for the Z-transform intro.
--Bob K 00:26, 1 September 2006 (UTC)
I would lean towards X(ω) myself as well. Note that this has the added benefit of being more similar to the other Fourier transform articles. —Steven G. Johnson 04:14, 1 September 2006 (UTC)
That's an obvious but very important point. I believe that the X(e^{i \omega})\, notation obscures the fact that it's just a normal Fourier transform of x_T(t)\,. I believe it's because of that confusion that Rbj insists that the DTFT is subsequent to a proof of the sampling/reconstruction theorem. But as we all know, one can sample a signal and do a DTFT with the samples without ever proving the sampling theorem. And having done that, the sampling theorem becomes rather obvious and trivial to prove, compared to the bloated proof now offered by Wikipedia. --Bob K 14:41, 1 September 2006 (UTC)

In Discrete-time_Fourier_transform#Periodicity we learn that the resulting function of the transform is periodic, but I don't see that as a sufficient rationale for writing X(eiω). There must be something more than this? Why else has this rather peculiar notation become so widespread? It can't be just to constantly remind the user about the periodicity of X? --KYN 11:17, 2 September 2006 (UTC)

We also learn that it "emphasizes the relationship to the Z-transform". The symbol X\, is overloaded, thus ambiguous. At various times, it can represent any of these functions:
X_1(\omega) = \mathcal{F}\{x(t)\}\,
X_2(\omega) = \mathcal{F}\{x_T(t)\}\,
X_3(z) = \sum_{n=-\infty}^{\infty} x[n] \,z^{-n}
We can remove one of the ambiguities by noting that:
X_2(\omega) = X_3(e^{i \omega})\,
X_2\, is a special case of X_3\,, so we simply dispense with the 2nd definition. Many narrowly focussed DSP articles have no use for X_1(\omega)\, either, leaving no ambiguity at all. I believe that is the rationale. However, a coherent sequence of encyclopedia articles has to build from the ground up. So I don't believe that rationale is appropriate for us. We could avoid overloading if we really wanted to, just as I have done above with subscripts, but that would be non-standard. So we have to rely on context and prose to make our articles unambiguous. That is the standard, as far as I can tell.
--Bob K 15:21, 2 September 2006 (UTC)
I guess another possible rationale, depending on your feelings about the existence of \mathcal{F}\{x_T(t)\}\,, is that X(e^{i \omega})\, seems to circumvent the whole debate over use of the Dirac comb function. But if that is the rationale, I would attribute it to the mathematical community, not the signal processing community. --Bob K 15:36, 2 September 2006 (UTC)
I think the definition with exp(i omega) is really a z transform, and we should just not use it except for that. Go back to X(omega) throughout. At present we have an incompatible mixture, so something must be done. Dicklyon 04:11, 6 December 2006 (UTC)

[edit] And the table...

The table uses X(omega), not the form defined in the lead. And some of the entries have periodic DTFTs while some do not. That is, the ones with exp(i omega) in them are obviously periodic, but the the ones like delta(omega+a) are not; they seem to just be copied from regular Fourier transforms. These need to be fixed. Dicklyon 04:09, 6 December 2006 (UTC)

Oh, I missed this hack:

  • \omega \! is a real number in (-\pi,\ \pi), representing continuous angular frequency (in radians per sample).
    • The remainder of the transform (|\omega| > \pi \,) is defined by: X(\omega + 2\pi k) = X(\omega)\,

Is this enough to make the table always correct? Or are there some entries where an infinite sum is really needed? Probably the sinc-squared needs to be patched up at least, or W limited to 1, otherwise there's overlap that needs to be summed up. And what about a general exp(an) for complex a? Dicklyon 04:33, 6 December 2006 (UTC)

The table is still very screwed up and inconsistent. For example, the factors in front of the delta functions for the exp and cos are not consistent. One just got changed, but it didn't bring them any closer to agreement. Anyone want to take this on? And maybe the section on sampling should be made consistent with the X(omega) definition instead of its own X(f)? Dicklyon 19:32, 14 December 2006 (UTC) OK, I made some changes. Someone should check me. Dicklyon 05:03, 18 December 2006 (UTC)

Alejo2083, thanks for checking me; you may be right that the one I deleted as absurd is not; I missed the n in the denominator. Anyway, I searched back and found that you're the source of the table, so I'd appreciate your comments on the rest of the changes, and also a source please, since I don't want to have to do the math to check all these. Dicklyon 00:27, 19 December 2006 (UTC) I checked a few in Matlab to see how they look, which is where it became clear that the sinc-square and sinc both needed a factor of 1; and I noticed the W condition for the one I thought was absurd, which is fine. Dicklyon 01:15, 19 December 2006 (UTC)

no problem :-) I added that line in the table because I made an exam about Z-transform and I had to use such a transform several times, but it was not in any table. So I calculated it in general, using generic parameters, and I published it on wikipedia, hoping it could be useful for somebody else. If you think the table is growing too big, we might consider moving it to its own page, keeping on this page just the main transforms such as sine and cosine, sinc, and a few more. Alessio Damato 12:41, 19 December 2006 (UTC)


[edit] Symmetry Properties

The new table entries have errors. For instance this equality:

X_R(e^{i \omega}) = Re\{x[n]\}\!

One side is time domain and the other is frequency domain.

And this:

\angle X(e^{i \omega}) = \angle X(e^{-i \omega}) \!

For instance, consider x[n] = \delta [n - k] \! and X(e^{i \omega}) = e^{-i k \omega} \!  :

\angle X(e^{i \omega}) = -k\omega \!
\angle X(e^{-i \omega}) = k\omega \!

So:   -k\omega \ \stackrel{\mathrm{???}}{=}\ \ k\omega\!

I haven't checked everything. Those just leaped out at me.


--Bob K 04:17, 22 February 2007 (UTC)

[edit] notation

In DTFT the frequency variable is commonly symbolized by \Omega \! and not \omega \!. \omega \! is used in continuous Fourier Transform. 132.69.231.117 19:10, 26 February 2007 (UTC)

So are you saying that
  1. \Omega \! is most common (Google appears to disagree with that), or
  2. \Omega \! should be mentioned as another commonly used notation?


--Bob K 13:44, 27 February 2007 (UTC)
Retrieved from "http://en.wikipedia.org../../../d/i/s/Talk%7EDiscrete-time_Fourier_transform_1522.html"