Talk:Discrete Fourier transform

From Wikipedia, the free encyclopedia

For older versions of this Talk page, see:

• Talk:Discrete Fourier transform/archive 1

---

Contents 1 Periodicity section 1.1 Periodicity 2 Orthogonality 3 Definition 4 Notation 5 Finite Fourier transform

[edit] Periodicity section

This section could do with a rewrite. The notation is different from the rest of the article - brackets not subscripts. There is no need to refer to the dtft article. It's easy to show straight from the dft definition that it is periodic. Paul Matthews 09:44, 3 October 2006 (UTC). I also find it strange that nowhere does the article say that a DFT is a truncation of the Fourier series - well it does now!

I agree that the DTFT should not be relied on so heavily in discussing periodicity of the spectrum. The point that the author of that section (Bob K, I think) wanted to make was that the periodicity of the spectrum is an inherent consequence of the discrete sampling and doesn't rely on any other property of the DFT, really. But perhaps this point could be made in a different way. —Steven G. Johnson 16:29, 3 October 2006 (UTC)

Thanks for remembering that, and I agree that a rewrite could be helpful. I also hope we don't lose sight of the fact that the DFT can be viewed as samples of the DTFT of a windowed function. --Bob K 18:37, 3 October 2006 (UTC)

I would go farther and say: We shouldn't lose sight of the fact that the DFT can be viewed in many different ways. I'm almost inclined to suggest that there should be a section ("Approaches to the DFT" or something) briefly summarizing the most important starting points from which the DFT can be derived. The question, here, is whether the DTFT viewpoint should be so central to the periodicity section—another possibility would be to point to the DTFT as another, related example of the rule that sampling leads to aliasing (rather than the source of this rule). —Steven G. Johnson 21:48, 3 October 2006 (UTC)

I recommend we consult some books, and pick one or two to motivate a good treatment of this subject, not just make it up as we go along. Do you have an approach or book in mind already? Dicklyon 21:55, 3 October 2006 (UTC)

The trigonometric interpolation section is not the right place to talk about the relation to the Fourier series, I think. First, the truncation is only approximate (due to aliasing), and it's a bit tenuous to say that the interpolation "shows" it. The statement of the relationship to the Fourier series needs to be made more precise, and the level of precision required should go somewhere else. —Steven G. Johnson 16:29, 3 October 2006 (UTC)

That's what I was going too say. Wrong place, and over-simplified. The Fourier series is a function of a continuous-time function, and the DFT of a discrete-time function. Tieing them together requires either a modulating comb of Dirac delta functions or a limit of the Fourier series of nascent delta functions. Nontrivial to get this right, but it might be worth doing to prevent the all-too-frequent attempts that do it wrong. Dicklyon 16:33, 3 October 2006 (UTC)

You don't need Dirac delta functions to tie them together. It is more common, and more useful for most applications (e.g. spectral methods), to simply view the DFT as a trapezoidal rule approximation for the Fourier-series integral. The error in this approximation depends on the smoothness of the function being sampled, and is closely related to aliasing. (Note that, because of periodicity, the endpoints aren't half-weighted unlike the usual trapezoidal rule. If you have a periodic function and no other information, then none of the fancier non-adaptive quadrature methods help you; by translational symmmetry, equally weighted and equally spaced points are optimal.) But still, this introduces a whole new set of topics. —Steven G. Johnson 16:56, 3 October 2006 (UTC)

I'm not sure I follow. You refer to trapezoidal rule, but also to approximation. How does that relate to the claim in question that "a DFT is a truncation of the Fourier series". It is my belief and understanding that that's true only is the continuous-time function that the Fourier series is computed from corresponds to the dirac impulse train, or a version of it filtered with a filter that is exactly flat at 1.0 up to half the sample rate. How does trapezoidal rule fit into that? Dicklyon 21:54, 3 October 2006 (UTC)

Given a function f(x) with period L, the DFT of the sampled function f(nL/N) is precisely a trapezoidal-rule approximation for the integrals giving the first N Fourier series coefficients of f(x). Thus, the DFT is an approximate truncated Fourier series for f(x), in the same way that the DTFT of a non-periodic sampled function f(x) is a trapezoidal-rule approximation for the Fourier transform of the original function. (A better term might be a "collapsed" Fourier series, because the DFT is the sum of the aliased coefficients in the series, but this terminology is nonstandard.)

Note that here I'm talking about "functions" in the classic sense, not distributions. i.e. I'm excluding delta functions and the like, for which numerical integration is impossible (and unnecessary). Yes, it's also true that the Fourier transform of a periodic delta train is a DFT. However, the approximate viewpoint bears a more direct relationship to actual usage of the DFT — in reality, you rarely have trains of delta functions, but you often have samples of a continuous-time function whose Fourier transform/series you want to approximate. (Of course, there is a relationship between the two viewpoints: the DFT of the sampled function f(nL/N) is the Fourier transform of f(x) multiplied by a unit-impulse train.)

As you increase N for a fixed period L (decreasing Δx as L/N), the DFT rapidly approaches the exact Fourier series coefficients. How rapidly depends on the smoothness of f(x). If f(x) is k-times differentiable and the k-th derivative is piecewise continuous, then the error decreases as 1/N^k+1; if f(x) is infinitely differentiable, then the error decreases at least exponentially fast. (Much faster than the trapezoidal rule for smooth non-periodic integrands, which is only 1/N² convergence.)

Clearer, I hope? —Steven G. Johnson 22:26, 3 October 2006 (UTC)

Yes, that's all clear. But that's about approximating a Fourier series by a DFT, which brings up the whole big subject of methods of spectrum estimation, etc. Let's not let it dominate the discussion of what the DFT is, and its properties. As to the original statement in question, there are conditions under which it can be true, but it's complicated. Dicklyon 22:43, 3 October 2006 (UTC)

An energetic discussion. I'm with Steven J (not surprisingly - we both teach spectral methods). I see the DFT as truncated FS. There is no need to talk about delta fn combs or a 'sequence of impulses'. See steve's comments above. And for the IDFT, you just start from the complex FS, f(x) = sum c_n exp(i n pi x/L), (period is 2L) evaluate it at grid points x_j = 2 j L / N and you get f(x_j) = sum c_n exp(2 i j n pi/N) which is the IDFT when you truncate the sum. Sure, this is not very rigorous as you have the aliasing question, but I think this approach gives a much clearer picture of what the DFT is about, which is what an encyclopedia ought to be doing. Obviously there are at least 2 different communities (signal processing and spectral methods) that see things differently. Paul Matthews 09:27, 4 October 2006 (UTC)

I have feet in each community. To me it seems important to be very clear in distinguishing mathematical properties of the DFT that are exact from those properties that make it useful in approximate applications. The truncated Fourier series is then an approximation in your applications, yes? That is, it relates the DFT values of a discrete function only approximately to the FS of a continuous function that those discrete values may be samples of. Under certain conditions the relationship may be exact, but that's a long discussion, which is why we have other articles on such things. So, OK to mention any of this, but as applications, not the core of the DFT exposition itself. Dicklyon 16:35, 4 October 2006 (UTC)

I'm with Dick. I believe I know everything that I need to know about the DFT to use it successfully for spectral analysis. And I have never thought of it as a truncated Fourier series. The clear picture that I think an encyclopedia ought to be giving is this one:

1. Sampling a continuous-time signal changes the spectrum (into a DTFT).

2. Much to the great surprise and delight of most neophytes, the old spectrum is still largely intact, provided the sample-rate is sufficient and one knows where to look.

3. , or if you wish, can only be numerically evaluated exactly if either:

3.1 is non-zero only within a finite interval, or

3.2 is periodic

4. In case 3.1, is continuous, so it can only be evaluated (numerically) at discrete frequencies; i.e. "sampled". The DFT can do that task exactly and with arbitrarily good resolution.

5. In case 3.2, is zero except at a discrete set of frequencies, which the DFT can evaluate exactly.

--Bob K 18:45, 4 October 2006 (UTC)

I'm not so sure you're with me. These things are all about spectra of continuous-time signals, and how to evaluate and approximate them. That's all fine, but the DFT itself has no necessary or explicit connection to anything continuous-time. It is a discrete transform on a finite set of values. All else is applications and approximations, yes? Dicklyon 18:55, 4 October 2006 (UTC)

Sorry. I was focussing (too much) on your statement:

"To me it seems important to be very clear in distinguishing mathematical properties of the DFT that are exact from those properties that make it useful in approximate applications."

I think it is important for encyclopedia readers to understand that under the conditions of 3.1 or 3.2, the approximation error can all be attributed to sampling (i.e. aliasing), and none to the DFT. The samples of the DTFT that it computes are exact. Describing it as a "truncated Fourier series" gives an impression of truncation error, which is misleading, at least in these two cases. If the truncation error we're talking about is the usual leakage that results from windowing an infinite sequence into a finite one (thereby achieving condition 3.1), I don't think that "truncated Fourier series" is the clearest way to describe that to an encyclopedia audience.

--Bob K 21:12, 4 October 2006 (UTC)

Bob, your blinkers are showing: you claim to know everything that [you] need to know about the DFT to use it successfully for spectral analysis, but there's much more to the DFT than signal processing. For example, in spectral methods for PDEs, the boundary conditions may well be a priori periodic, in which case there is zero error due to windowing. In such cases, it is useful to separate the error into two components: first, the difference between the DFT amplitudes and the Fourier-series amplitudes, which is due to aliasing; and second, the error due to the higher-frequency terms you are not computing. There are several reasons it is useful to separate these two errors—perhaps the simplest is that the truncation error is impossible to avoid, while the aliasing error can be avoided if you compute your Fourier series coefficients by an exact integral or quadrature (i.e. a Galerkin method, whereas the DFT corresponds to a collocation method).

In this context, it is also more fruitful to focus on the relationship between the aliasing and truncation error and the convergence rate of the Fourier series (which determines the magnitude of the high-frequency components that are truncated/aliased).

Yet another context in which it is important to view the DFT as an approximate integral is numerical quadrature. Here, the relationship between the integration error and the rate of convergence (via aliasing) is central to methods such as Clenshaw-Curtis quadrature. It also arises in Chebyshev approximation, where again the truncation error is conceptually separate from the error in the expansion coefficients.

I absolutely agree that the DFT is a wonderful beast in its own right that has lots of interesting properties that can be derived without reference to any other transform. However, its applications often (not always) involve some approximation for another transform. For signal processing, these approximations are due to aliasing (from sampling) and leakage (from windowing). For spectral PDE methods, it is more useful to describe the errors as I have above.

All of this has nothing to do with the periodicity section, of course. I agree with Dick that it should go under applications, etc. But don't belittle things you don't understand.

—Steven G. Johnson 00:02, 5 October 2006 (UTC)

I had no intention of belittling, which is why my statement was so carefully worded and narrow in scope. As Paul said, "there are at least 2 different communities (signal processing and spectral methods) that see things differently"... the usual intractable Wikipedia problem. So it shouldn't surprise you that we disagree. My intent was to challenge Paul's assertion that viewing the DFT as a truncated Fourier series "gives a much clearer picture of what the DFT is about". That blanket statement does not apply to all of us, and I seriously doubt that I am a minority of 1 or even a minority at all.

--Bob K 02:55, 5 October 2006 (UTC)

I just removed the whole section in question, because it makes no sense (to me). Here it is in case anyone wants to fix it up, remember it, or explain to me what it's trying to say:

[edit] Periodicity

It is shown in the Discrete-time Fourier transform (DTFT) article that the Fourier transform of a discrete time sequence is periodic. A finite length sequence is just a special case. I.e., it is an infinite sequence of zeros containing a region (aka window) in which non-zero values may occur. So , the DTFT of the finite sequence , is periodic. Not surprisingly, the DFT is periodic; e.g. . Less obvious, perhaps, is that the inverse DFT is also periodic; e.g., . It is a periodically extended version of the finite sequence.

The DTFT of the periodically extended sequence is zero-valued except at the discrete set of frequencies sampled by the DFT. I.e., it is effectively identical to the DFT. The DTFT of the finite sequence has other non-zero values, but it is still identical to the DFT at the frequencies sampled by the DFT. So the approximation error of , as an approximation to , lies in the missing non-zero values, not in the coefficients. In terms of the inverse DFT, that approximation error becomes the periodic extension of the finite sequence.

• Commonly, is a modification of a longer, perhaps infinite, sequence, whose DTFT is only approximated by . In that case, of course, too is only an approximation to [samples of] the original DTFT.

• The shift theorem, above, is also an expression of the implicit periodicity of the inverse DFT, because it shows that the DFT amplitudes are unaffected by a circular (periodic) shift of the inputs, which is simply a choice of origin and therefore only affects the phase. Periodic boundary conditions play an important role in many applications of the DFT. When solving differential equations they allow periodic boundary conditions to be automatically satisfied, and thus can be a useful property. See also the applications section below.

Here's what I don't get: what is meant in the first place by "the Fourier transform of a discrete time sequence"? Sequences don't have Fourier transforms. To get a periodic Fourier transform, aren't they assuming a modulated comb of delta functions? Do we really want that complexity introduced into an article on a simple discrete transform? And then, the periodicity stuff presumed definitions different from what we have in this article. I was looking at a book today in what defined periodic extensions of x and X, which might then give something to say. But what does this article refer to when it says "it" in "It is a periodically extended version of the finite sequence"? It seems to be contradicting the definition that we have for the IDFT. And so on. This is all too fuzzy for me. If anyone can make it sensible, then put it back. Dicklyon 03:35, 5 October 2006 (UTC)

Yes, you've raised a lot of the things that led me to flag this section. Ok, all thats needed I think is the 1-line proof that

This is a simple property that follows directly from the definition so I hope it should not be controversial. I have put that in, please feel free to add to it. I have put it just before the shift theorems because they use periodicity. Periodicity is also very useful for understanding aliasing and the 'common mistake' problem argued about earlier - you cant distinguish between X_N-1 and X_-1, and it makes more sense to call it X_-1. Paul Matthews 10:12, 5 October 2006 (UTC). Again, to me, the periodicity proof shows that the DFT is a form of FS.

I fixed it to talk about periodic extensions, since the DFT and IDFT as defined are finite sequences. This follows a book I have (I'll have to look up which one if anyone cares; it introduces a specific notation for the periodic extensions so that they can be used for certain properties that benefit from the infinite sequence). Dicklyon 15:13, 5 October 2006 (UTC)

I would argue for a broader phrasing, something like:

Although the DFT is ostensibly just a transformation of N numbers into N numbers, it has a number of properties closely associated with the notion that both the input and the output are periodic sequences, with period N. And then give various examples, such as:

• Defining the periodic extension just by evaluating the formula for all k (or n, for the IDFT).
• The notion that periodicity in the transform arises whenever you have uniformly spaced discrete samples. (Relate to the DTFT and Fourier series for periodicity in k and n, respectively.)
• The fact that the DFT can be derived from a Fourier transform of periodic sequences of delta functions (or from the DTFT of a periodic sequence, or...).
• The (circular) shift theorem: under a cyclic shift, only the phase of the output changes, analogous to the usual shift formula for the Fourier transform and DTFT.
• More abstractly, the relation to cyclic groups. (e.g. the DFT can be viewed as the projection operator onto the irreducible representations of the order-N cyclic group.)
• Others...?

—Steven G. Johnson 17:25, 5 October 2006 (UTC)

Yes, those might be good ideas for additions to the section.

I found my book: Peled & Liu's Digital Signal Processing: Theory, Design, and Implementation. I misremembered a bit. Their notation is not specific to the periodic extension, but rather "taken to mean the periodic extensions when appropriate". That is they use the same notation for the DFT and its periodic extension, essentially equivalent to treating them as circular, to make it easier to state certain properties, such as even and odd symmetries, reverse directions, shifts, etc. that involve negating or offsetting subscripts, to avoid introducing circularity mid mod N subscripts I suppose.

However, the idea of periodicity arising from uniformly spaced discrete samples gets a lot more complicated. There is nothing in the DFT that cares about uniform spacing, so to tie its periodicity periodicity of spectra of continuous-time signals will take a lot of work, which is already well covered, I think, in DTFT article.

The circular convolution and shift properties are already covered, I believe. You don't need to drag periodicity into the explanation of circular.

Dicklyon 17:41, 5 October 2006 (UTC)

Well I would prefer to Keep It Simple, especially in the properties section, stick to things that follow straight from the definition, like the periodoc extension. Reference to DTFT and talk of sampling can come later in the applications section (and please, no representation theory here!). Remember, the article is already too long. Paul Matthews 09:03, 6 October 2006 (UTC)

[edit] Orthogonality

I just took a brief look on this article after a long time. Still only the editors can read it. Fundamental problems remain unsolved from the very beginning of the article. Quote:

The vectors form an orthogonal basis over the set of N-dimensional complex vectors

The expression is not for a basis but for a vector component, as it contains no information distinguishing component adress and vector adress. The matter was discussed in talk:function (mathematics)#standard notation and it was resolved that the notation for such a basis could be

the k th vector of which is

the nth component of which is

Bo Jacoby 14:52, 7 February 2007 (UTC).

The statement you have excerpted does not have to stand on its own. My opinion is that the context you have omitted is sufficient. With due respect, if I had to clarify it, I think a more conventional notation is something like:

--Bob K 15:15, 7 February 2007 (UTC)

[edit] Definition

The definition is incomprehensible to the uninitiated reader.

1. It is more important to tell the reader that is a primitive N'th root of unity, than that "e is the base of the natural logarithm, is the imaginary unit (i² = − 1), and π is Pi".

2. A few simple examples might help.

Bo Jacoby 07:42, 8 February 2007 (UTC).

The examples didn't do anything for me, but I agree with you that the excerpt you quoted is too patronizing for my taste. I would also omit "primitive N'th root of unity" for the simple reason that I have been using for 40 years and I have never needed that particular description.

--Bob K 23:17, 8 February 2007 (UTC)

A person with long experience reacts differently than a person who just heard the word 'discrete fourier transform' and is now curious about it. WP ought to be helpful to our young friend. He/she is likely to stop reading at the very first formula. Is it possible to improve with this in mind? What problem is DFT solving? Is there a simple example? Perhaps it should be even simpler.

Bo Jacoby 12:09, 9 February 2007 (UTC).

[edit] Notation

The reader has 3 equivalent expressions to learn

1. The name "Discrete Fourier Transformation"
2. The abbreviation "DFT"
3. The symbol

The article becomes easier to read if we get rid of the third one and write DFT rather than like this:

Bo Jacoby 08:03, 8 February 2007 (UTC).

But the single-symbol transform function with the big F is pretty conventional, isn't it? The reader really ought to learn it. This should probably be argued with respect to how different authoritative books present it. Dicklyon 15:33, 8 February 2007 (UTC)

If a reader wants to study an authoritative book, then he will learn the notation from that book, and then he does not need to read the wikipedia article. The purpose of a encyclopedia article is to provide a comprehensible explanation to persons who do not already know the subject matter, and who do not necessarily intend to commence a deeper study. So the article should not be complicated by different ways of expressing the same thing. The big F is used not only for discrete fourier transform, but also for other transforms such as the continuous Fourier transform. Therefore it is easier to get rid of the big F here rather than to get rid of the abbreviation DFT, which specificly means Discrete Fourier Transform. (It would be nice to stop distinguishing between discrete and continuous fourier transform and create a common presentation, but that is quite another story). Bo Jacoby 23:00, 8 February 2007 (UTC).

I know you are big on unique, unambiguous, standalone, notation, and in my more idealistic years, I might have bought into that. But the place I'm at now is that notation is not enough to handle the complexities and multiple conventions of the real world. E.g., even within Wikipedia we are stuck with two different meanings of sinc() for engineers and physicists. There will always be a need for definition, context, and prose. Both the writers and the readers will need all those communication tools and skills. Having placed that stake in the ground, let me point out both an unmentioned advantage and another disadvantage of keeping here:

1. The advantage is your stated desire to "stop distinguishing between discrete and continuous Fourier transform". Although I don't think the goal is realistic, it seems like a step in that direction is to proliferate the rather than restrict it.
2. The disadvantage is that the does not distinguish between DFT and DTFT. But I'm not really worried about it, because I also have the other clues.

--Bob K 23:51, 8 February 2007 (UTC)

[edit] Finite Fourier transform

"Finite Fourier transform" redirected to "Discrete Fourier transform" here at Wiki. But I put up a disambiguation page for the "Finite" term, because alas it is used in a different sense by some people, ee.g.

http://www.dtc.army.mil/navigator/apnd_D03.html

http://library-dspace.larc.nasa.gov/dspace/jsp/bitstream/2002/10966/1/NASA-97-tm110340.pdf

LDH 11:07, 26 February 2007 (UTC)

I see you "fixed" it. I have disputed your fix; see talk:Finite Fourier transform. Dicklyon 21:08, 26 February 2007 (UTC)

And I'm disputing your dispute. =) I don't see anything wrong with LDH's fix...the references for those definitions seem easy to find. However, some of the references you point out give a third definition (grrr), in which "finite Fourier transform" is a synonym for the Fourier-series coefficients. —Steven G. Johnson 06:41, 27 February 2007 (UTC)

Thanks for adding refs and the other meaning, and getting a little closer to typical usage on the last one; I don't believe it's typically limited to x of finite support, though. I'll look for a good ref (such as the first one LDH gave above, maybe). Dicklyon 07:39, 27 February 2007 (UTC)

The difference seems to be just a matter of interpretation—does x(t) have compact support, or do we just happen to restrict the Fourier integral to compact region? It's just a question of whether you are looking at the function before or after windowing. (In any case, it would be nice to have a more authoritative reference; I hate to rely on web pages and technical reports.) —Steven G. Johnson 07:46, 27 February 2007 (UTC)