Talk:Discrete Fourier transform

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	High Priority	Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 23:36, 16 June 2007 (UTC)

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 6 Division by 2 error? 7 DFT polynomial multiplication algorithm 8 Too technical 9 Confusing 10 Section "Orthogonality" 11 Too simple 12 Added basic explanation 13 Needs images 14 To complicated

[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).

I don't agree with this sentence "The sequence of N complex numbers x0, ..., xN−1 is transformed into the sequence of N complex numbers X0, ..., XN−1", since DFT doesn't necessary trasform N complex numbers into other N (that is only true for Fast Fourier Transform). I think this definition should be more general giving different cardinalities to the numbers of the 2 different domains (ie: transforming a sequence of N complex numbers into a sequence of K complex numbers).

79.18.198.247 (talk) 12:42, 25 January 2008 (UTC)

I have not seen any definitions of your form--DFT is always N to N. What are you using for a source? Dicklyon (talk) 17:07, 25 January 2008 (UTC)

Rabiner and Gold, Theory and Application of Digital Signal Processing, 1975, p51. They don't exactly commit to either position, and it is not necessary to, in my opinion. Both definitions are useful and valid. We don't all agree on the definition of Fourier transform either. Anyhow, they give the formula:

and say, "it has been called the discrete Fourier transform (DFT)". And they also say, "it is clear that X(k) is periodic with period N samples".

--Bob K (talk) 18:46, 25 January 2008 (UTC)

I don't deny that it's sometimes useful to compute fewer than all N values of a DFT, but I don't think Larry and Ben meant to define it that way by omitting a specific mention of the range of values. I can't find my copy of that one right now, but in the Oppenheim and Schafer of the same year, they also don't seem to have a firm definition. But they do talk about various properties, as we do in this article, that only work if you take DFT to mean all N values. If we define it otherwise, we won't be able to claim invertibility, circular convolution, etc. Dicklyon (talk) 01:29, 26 January 2008 (UTC)

I'm not sure why you say "fewer than all N values of a DFT". I think the issue here is whether the transform domain is [0,N-1] (like an FFT) or unbounded. Larry and Ben certainly acknowledge the latter possibility by mentioning "X(k) is periodic with period N samples".

It's really just a specific form of the issue that arises with the DTFT:

Is the domain (-π, π] or [0, 2π) or unbounded? It can be any of those, depending on the point you are trying to make. All are valid. That is why Oppenheim and Schafer are reluctant to settle on just one.

The unbounded viewpoint, by the way, is particularly useful for insight into the nature of and mitigation strategies for aliasing. When we draw pictures like this one, we are depicting the unbounded DTFT.

When the input to a DTFT is periodic, the DFT can be used to compute the coefficients of the DTFT's modulated Dirac comb output, using just one period of the input. The coefficients are actually a Fourier series, which everyone seems to agree (hooray) is an unbounded number, even if the series is periodic.

--Bob K (talk) 13:36, 26 January 2008 (UTC)

I suppose I may have misinterpreted the idea behind the question above about computing K values from N. You're right that the DFT can be viewed as either N values or as an infinite periodic sequence of N, but since there are still only N distinct values there, I hadn't thought that was what he was asking about. And since the inverse transform is written in term of using only N values, you know... Dicklyon (talk) 17:06, 26 January 2008 (UTC)

Confession: I too may have misunderstood. I did not take "K of N" literally. I guess what he is actually talking about is this formula:

    (from DTFT#Finite-length_sequences),

where L is the actual sequence length. When N > L, it can be computed directly from that "DFT" formula, whereas an FFT requires zero-padding. I guess that is his point. The question is whether or not we want to call that formula a "DFT". It's OK with me, but you might have a hard time finding that definition in a textbook.

--Bob K (talk) 20:59, 26 January 2008 (UTC)

I'd say not OK unless we find it in a textbook. Dicklyon (talk) 21:13, 26 January 2008 (UTC)

According to Oppenheim-Schafer, they don't actually use a strict definition on the cardinalities; they actually point out that for the representation of a finite sequence of length N or of a periodic repetition of a sequence of length N, it is enough to use N coefficients to represent them with a DFT without losing information. Anyway the basical concept behind DFT is actually a transformation between 2 discrete domains (bounded or unbounded is inessential) and I think it should be more general than a "N-to-N transformation"; that's why both Oppenheim-Schafer and Rabiner-Gold don't settle this argument when they give the very first definition. (By the way, I'm the same person of the first message) 79.33.154.55 (talk) 17:51, 27 January 2008 (UTC)

It might be OK to mention that some sources use a more general definition. But you need to be careful and at least state a definition that makes the claimed properties true. Most sources (as far as I can see) do use a strict N-to-N definition; for example this one, this one, this one, etc. Dicklyon (talk) 18:01, 27 January 2008 (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)

[edit] Division by 2 error?

Is there not an error in the denominator for the forward transform? (Or the compound forward/inverse scaling factor?) I get half result when testing in program and spreadsheet. Apparently for all indices other than 0 and N/2, the scale factor (product) should be 1/(N/2), rather than 1/N. (Could be written 2/N). See link below, and this value makes my program work, I believe.

http://www.dspguide.com/ch8/5.htm

63.76.53.47 17:35, 6 June 2007 (UTC)Gordon Elliott63.76.53.47 17:35, 6 June 2007 (UTC)

The sums on that dspguide page only go to N/2. The standard form (which works more generally, not just for real signals with symmetric transforms) shouldn't need the hacked factor. Dicklyon 18:00, 6 June 2007 (UTC)

There is no error that you asked about. Real-valued signals have symmetrical transforms. Since the information is redundant, you can do an inverse transform with just the positive frequency components, but then you have to compensate for the energy that you did not include in the reconstruction. And of course it is exactly half the total, thus the factor of 2.

--Bob K 18:34, 6 June 2007 (UTC)

[edit] DFT polynomial multiplication algorithm

--ANONYMOUS COWARD0xC0DE 20:43, 25 June 2007 (UTC)

That's easy: you're treating a wikipedia article's talk page as a forum. Dicklyon 21:21, 25 June 2007 (UTC)

--Bob K 20:39, 26 June 2007 (UTC)

[edit] Too technical

Someone removed the {{technical}} I stuck up there because I didn't leave any comments about what I didn't understand. So, I put it back, and here's what I don't understand: just about all of it. It goes right into high-level mathematics without so much as an explanation of what you're even doing. Wikipedia's here to create en encyclopedia accessible to everyone, not just people who took 4+ years of math in college. So, in short, how about a little simplification? — SheeEttin {T/C} 02:16, 29 June 2007 (UTC)

• Also see below: Too simple. -Wikid77 19:42, 16 October 2007 (UTC)

OK, let's start with the lead. Is it understandable? If not, what words or phrases throw you? Next, in the definition, since it's a mathematical transform defined by a summation, do you want that spelled out more in words? Or description of what that summation is doing? And is there any hope of presenting something that will make a reader happy if the reader doesn't have the background to understand the material? I'm willing to help, but it's not so easy for those of us who understand to understand what to do to satisfy those who don't. Help us out. Try this as an definition:

Definition

The DFT is a linear algebraic transform that takes as its input a set of numbers that can be thought of as a sampled time-domain signal that repeats, wrapping from the last sample back to the first forever. The transform produces as output a set of just as many numbers, which can be thought of as measurements of the amounts and phases of different frequencies present in the original periodic sequence. The numbers are complex in general; in particular, even if the input numbers are real, the output numbers are still usually complex. Each output number corresponds to a frequency of some number of cycles in the length of the original data; the first, at index k = 0 represents "DC", or the amount of unchanging signal in the input; the second, at index k = 1, represents the amount and phase of a sinusoid of one cycle in the input data (that is, one cycle per repetition in the infinite periodic repetition of the input); similarly, output values for higher index values quantify the amount and phase on sinusoid of that many cycle in the input data. The amount and phase are the magnitude and phase of the output complex numbers, which can also be interpreted as real and imaginary parts specifying the amounts of cosine and sine waves in the input data. Each output value of the DFT is computed by summing the values of the input times samples of a complex exponential of the frequency corresponding to the output index. For the higher index values, above half the number of input points, the high frequencies exceed a half cycle per input sample, and may alternatively be viewed as negative frequencies.

In algebraic notation, the sequence of N complex numbers x₀, ..., x_N−1 is transformed into the sequence of N complex numbers X₀, ..., X_N−1 by the DFT according to the formula:

where e is the base of the natural logarithm, is the imaginary unit (i² = − 1), and π is pi. The transform is sometimes denoted by the symbol , as in or or .

The DFT for the case of real inputs can also be defined in terms of sums of purely real sines and cosines, for the real and imaginary part separately:

And so on...

This may be pretty unpalatable to someone who would prefer to use mathematical notation, but tell me if it helps with your request. It's not less technical, just a different notation for what is inherently a very technical topic.

Dicklyon 04:49, 29 June 2007 (UTC)

Hmm, I'm not entirely happy with your rephrasing. The input and outputs are not merely "sets" of numbers. How does adding the unexplained acronym "DC" help a completely nontechnical reader? And you can't interpret the real and imaginary parts as the amount of cosine and sine in general (not for complex inputs). For real data, it makes much more sense to write the outputs in polar form re^iφ and express the inputs as a sum of sinusoids of the form rcos(ωt + φ), rather than a sum of sine and cosine (since it is not completely obvious that a sum of sine and cosine is just a sinusoid of the same frequency with different phase). Any of the frequency components may be viewed as negative frequencies, not just the upper half; aliasing applies to every component.

—Steven G. Johnson 20:10, 30 June 2007 (UTC)

Yes, I should have said ordered sets, or sequences, or something like that. And yes some of what I said only makes sense for real inputs. And you're right that any of the frequencies can be treated as any of their aliases; maybe this is best left out, but sometimes the "primary" frequency of interest is the one with lowest absolute value, which is what I was getting at. Feel free to work it over, but I don't think polar expressions with complex exponentials is likely to be a part of the solution of making it intelligible to the less technical readers. Dicklyon 22:05, 30 June 2007 (UTC)

I don't think we should try to write out the whole equation in English anyway; if one's mathematical background is too weak to make head or tails of the equation, writing it out "longhand" is very unlikely to be useful or illuminating either. For non-technical readers, I think it is sufficient to (a) have one sentence saying that the DFT, the discrete analogue of the Fourier transform, takes a finite sequence of numbers and expresses it as a sum of sinusoidal components and (b) after the equation, mention that the exp(2pi i nk/N) are the sinusoidal components and the X_k are the complex amplitudes which (in polar form) directly represent both the amplitude and phase of these components, and link Euler's identity. It is unreasonable to attempt to further explain the equation in detail without expecting the reader to know complex arithmetic and Euler's identity. This is not the article in which we should be explaining the relationship between complex arithmetic and trigonometry...the reader should go elsewhere for that. —Steven G. Johnson 06:04, 1 July 2007 (UTC)

I'm good with that approach. You want to take a stab at it? Dicklyon 16:50, 1 July 2007 (UTC)

Okay, will do. —Steven G. Johnson 23:08, 1 July 2007 (UTC)

Guess I should've checked back sooner. Anyway, it still makes no sense to me, but it's written much better. — SheeEttin {T/C} 14:50, 3 July 2007 (UTC)

[edit] Confusing

Also see below: Too simple. -Wikid77 19:42, 16 October 2007 (UTC)

I must say this article is pretty confusing. I've done some research about the DFT to try to understand and apply it in a program, but it looks like there are many variants of this... For example, on [1] it is said:

Each of the four Fourier Transforms can be subdivided into real and complex versions. The real version is the simplest, using ordinary numbers and algebra for the synthesis and decomposition. For instance, Fig. 8-1 is an example of the real DFT. The complex versions of the four Fourier transforms are immensely more complicated, requiring the use of complex numbers. These are numbers such as: 3+4j, where j is equal to sqrt(-1) (electrical engineers use the variable j, while mathematicians use the variable, i). Complex mathematics can quickly become overwhelming, even to those that specialize in DSP. In fact, a primary goal of this book is to present the fundamentals of DSP without the use of complex math, allowing the material to be understood by a wider range of scientists and engineers.

The formula in that article is:

and do not require complex numbers. Also, these formulae yield me N+2 values in the frequency domain (N being the number of samples). The formulae in the Wikipedia article give me 2*N values (N complex numbers). What's the difference between both formulae (if there is any)? Why aren't these versions written in this article? It seems to me that they are easier to use and are sufficient for most purposes. —Preceding unsigned comment added by 87.65.199.96 (talk • contribs)

Those are like the ones I proposed immediately above here as part of an attempt to make it more "simple" to understand. They are however limited to the case of real x; they can be expanded to work for complex x, but look more complicated then. These do NOT avoid complex numbers, just compute complex numbers with real and imag parts separately. It's not clear to me why you're confused, but it's clear that you are, as you've misstated the number of points that these yield. Dicklyon 14:27, 6 July 2007 (UTC)

I agree that the article is too technical and confusing. One year ago I suggested a more pedagogical approach, See Talk:Discrete Fourier transform/archive 1#Always begin with the simplest example. I gave up because some other editor was opposing rather than cooperating. Now, after a year, the problem still exists, the article is still too technical and confusing. The editor in question has had his chance and blew it. He must give room to other editors. Bo Jacoby 13:31, 27 July 2007 (UTC).

If the article is too technical and confusing, we should be looking for a standard pedagogical approach that helps to clarify it. I just reviewed what you proposed a year or so ago, and I think I agree with Stevenj that it was a bit too "original" for wikipedia, not to mention long-winded and probably really not that easy for someone to follow if they can't follow formulas with summations and exponentials. And I would argue that starting off with a representation of periodic extension of the bases, the form of an infinite matrix, is quite beside the point, since the transform in question is explicitly finite. Perhaps something in a section on "elementary introduction" or something like that, but not in the main line lead or intro that's better targeted at people who actually have to capacity to appreciate the material that's on topic. Dicklyon 15:21, 27 July 2007 (UTC)

Bo, if I recall correctly your basic suggestion was to start with the N=2 case (equivalent to a Hadamard transform). Although the N=2 case is easy to understand, it is a very special case that sheds very little light on the properties and applications of the general-N case, unfortunately. Almost all of the practical applications of the DFT follow from its properties in the limit where N is large. There is no question that some people will find this material hard to follow, but that will be true in any presentation of an advanced-undergraduate-level topic; it doesn't necessarily indicate a fundamental failure of the current structure (although improvements can undoubtedly be made), and indeed the current structure is quite standard pedagogically if you compare to any of the popular and time-tested textbooks. —Steven G. Johnson 16:28, 27 July 2007 (UTC)

Steven, the idea of writing an encyclopedic article is not to summarize the "standard" approach of the "the popular and time-tested textbooks", but rather to move the topic from the advanced level down to the elementary level. By writing that "some people will find this material hard to follow, but that will be true in any presentation of an advanced-undergraduate-level topic" you indicate that you do not believe that a good encyclopedic article can be written at all. An encyclopedic article should not describe every variation of notation and definition found in litterature, but rather explain the essence of the subject to the uninitiated reader, using the sufficient minimum of notation and definition. For example, the trancendental numbers e and π is no problem on the advanced-undergraduate-level, but they are unnecessary and should be removed, because discrete fourier transform is pure algebra. Explaining a special case helps, when a reader does not understand the general case. From the easy case N = 2 one may proceed to the case N = 3, introducing a complex cube root of unity, then to the general finite case, introducing a complex, primitive N^th root of unity, and then to the limiting cases, namely the fourier series and the fourier integral transform. I do not suggest to stick to the case N = 2. Bo Jacoby 09:35, 28 July 2007 (UTC).

I prefer the undergrad level, including e and π, FWIW. But what I really want to add here is the question: Why do these things have to be mutually exclusive? The advantage Wikipedia has over a conventional encyclopedia is seemingly unlimited space. Why not create 2 articles, aimed at different segments of the reader population? Why not let the readers pick the article they want to read? The "pure algebra" point-of-view does nothing for me. I have gotten along fine without it for 40 years. But if other folks want to think about it that way, why should I care? To take it a step farther, I would like to see Wikipedia add a way for readers to rate the usefulness of the articles, as many other web pages do. A counter of times visited would also be interesting, if not useful.

--Bob K 11:09, 28 July 2007 (UTC)

Bob, after 40 years you have no problem with e and π and you have no need to express the discrete fourier transform in terms of simple algebra. So you are not a member of the elementary segment of the reader population. Nor are you a member of the advanced segment, because you do not need the article at all. It tells you nothing new. You are neither complaining that the article is technical and confusing, nor are you praising it for providing you with just the insight you need. We could prefix the article with a note that the reader is supposed to have 40 years of mathematical experience in order to understand it, and in that case he has no benefit from reading it anyway. So we do not need two articles. We need one encyclopedic article! Your suggestions for improving the services of Wikipedia are nice, but besides the point I am trying to make. Bo Jacoby 12:47, 28 July 2007 (UTC).

First, an encyclopedia article on the DFT is not an axiomatic textbook, starting from the elementary definitions of real numbers and arithmetic. Nor can every encyclopedia article stand completely on its own. This is not the article in which to introduce complex arithmetic and complex roots of unity to the reader for the first time; we have other articles for that if need be. Even if in principle one can introduce roots of unity without mentioning π, pedagogically it is unreasonable since virtually no English-speaking students will encounter general complex roots of unity before encountering π, and roots of unity are much simpler in polar coordinates. The first rule of technical writing is to know your audience. (And this is why following approaches in standard introductory textbooks is helpful: popular textbooks have been tested against many audiences for the material in question.)

Second, hyperbole will get you nowhere—you don't need 40 years of experience to follow this article; many advanced freshmen would follow most of it, and in a few more years will have progressed well beyond it. On the other hand, there are aspects of DFTs (like many other math subjects) that require years of study to fully appreciate, including aspects (like the choice of eigenvectors) that even professional researchers do not understand completely. A good encyclopedia article should cover the spectrum, from a one-paragraph overview for a general audience, to an introduction to the basics assuming an appropriate background, to at least a hint of more advanced material that may inform even people who are quite familiar with DFTs (and which can eventually be expanded in additional articles on subtopics).

Third, it's simply a fact of life that not every article will be completely understood, from top to bottom, by every reader. This does not mean that the article is a failure, just that the reader does not have sufficient background to fully appreciate the topic, and a single article cannot compensate for the lack of years of study. As mentioned above, encyclopedia articles are not axiomatic textbooks, and do not exist in a vacuum independent of the rest of education or the encyclopedia. Of course, every article should begin with a brief introduction that conveys at least the gist of the subject to as broad an audience as possible. But demanding that we completely rewrite the article every time a single reader doesn't understand everything is absurd—the article will never converge, nor will rewrites for the benefit of one reader (especially a hypothetical reader who understands complex roots of unity but not π) necessarily improve the article for other readers.

—Steven G. Johnson 16:07, 28 July 2007 (UTC)

The article is too technical and confusing. The readers tell you so. How come you don't listen to what is said? Not every article in WP has that problem. You argue that it cannot be helped. I see no entry in this talk page where advanced freshmen testify that they follow most of it. How come you listen to what is not said? Bo Jacoby 16:29, 28 July 2007 (UTC).

I don't think either of has argued that it cannot be helped. We did express the opinion, however, that your particular exposition might not be a great one, and that it smacks more of original research than of an established pedagogic approach. I do appreciate your attempt to help, but you also need to listen to the reactions of other editors. It's just us here. Dicklyon 16:56, 28 July 2007 (UTC)

Ok. The problem was there one year ago and it is still there today. Lets talk again in another year from now to see whether your established pedagogic approach has solved the problem by then. If any deviation from the approach of the advanced textbooks is considered forbidden original research, then the problem has got no solution. Good luck. Bo Jacoby 18:15, 28 July 2007 (UTC).

I have never suggested that the article could not be improved; in fact, I explicitly stated the opposite (although I doubt that a solution which will satisfy every reader exists). What I said is that your specific suggestions were unlikely to be improvements, and I explained why. Your argument is based on a logical fallacy: you seem to think that if some reader has a problem understanding the material covered by the article, a completely different approach is automatically an improvement. —Steven G. Johnson 23:29, 29 July 2007 (UTC)

• See below: Added basic explanation. -Wikid77 23:42, 16 October 2007 (UTC)

[edit] Section "Orthogonality"

In section "Orthogonality" you have mentioned δ_kk'. What is the range of indexes k and k'? Is it possible to add a link to where it comes from? It`s not from article "orthogonal", the only somehow relevant link I can see. Arkadi kagan 13:01, 11 September 2007 (UTC)

[edit] Too simple

16-Oct-2007: When expanding the article with text for general readers, please isolate explanations to limited sections, or else the article will become "too simple" (or "too tedious") for experienced readers. Several readers have complained about articles being "baby-fied" with wording that over-simplifies the technical details they feel are needed. This is just a general concern: avoid making the technical writers afraid to use technical terms or formulae, or afraid to expand advanced concepts in the article.-Wikid77 19:42, 16 October 2007 (UTC)

• Done. See below: Added basic explanation. -Wikid77 23:42, 16 October 2007 (UTC)

[edit] Added basic explanation

16-Oct-2007: To handle concerns of "too technical" (or "too simple"), I have expanded the article with a new bottom section, Basic explanation. That section gives a simple explanation of a "discrete Fourier transform" (plus the applications and branches of mathematics used), without cluttering the main text of the article. I think such a bottom section is about the best way to explain many novice issues about the subject, without annoying the more advanced readers about the background basics, such as using "formulas in finite mathematics" and "algebra". At this point, I am removing the "{technical}" tag at the top. -Wikid77 23:42, 16 October 2007 (UTC)

I don't agree with the explanation of DFT in terms of numerical integration.

--Bob K 15:49, 17 October 2007 (UTC)

25-Oct-2007: In explaining the DFT formula, I am using several analogies, but I'm afraid that the overall article has been so complicated that almost no one understands it. If I didn't have degrees in both mathematics and computer science, I don't think I would have attempted an explanation. Whenever a formula is summing terms of the form "x * e^k" it is summing rectangular areas, although each is being skewed by an exponential factor, based on the counter/index value k. However, I have omitted the discussion of complex numbers to simplify the explanation. Numerical integration can produce similar formulas, as an approximation to an equation in integral calculus, by restricting the counter to discrete values, whereas in a calculus integral formula, the summation involves all possible values of the "counter" variable, usually x, as it ranges from low value to high, during the integration. For that reason, the formula for the DFT summation is similar to numerical integration. However, to reserve some differences of meaning, I have added the term "skewed curve" to the explanation, to not oversimplify the effect of the exponential terms in the DFT formula. Are there some other phrases that might be better to include in the explanation? -Wikid77 11:24, 25 October 2007 (UTC)

I'm with Bob here (which is why I removed that). The DFT has no relation to numerical integration. It is a discrete transform. If it can also be viewed as an approximation to a Fourier series of a continuous periodic function, that's fine, and can be discussed, but it's not what it is. Dicklyon 15:13, 25 October 2007 (UTC)

If the goal is to make DFT understandable/accessible to more people, I don't think it helps to describe the product of a function with an exponential basis function as a "skewed curve". What they really need to understand is that it works like a matched filter. The sinusoidal component of the function that matches the basis function (in shape, not amplitude) is effectively squared, every sample contributing a positive value to the summation. Or in complex (vector) terms, the sinusoidal component of the function that matches the basis function contributes vectors that all point in the same direction. The components that do not match the basis function, contribute values that alternate in sign or vectors that rotate in direction and tend to cancel out of the summation. The final value is therefore dominated by the component that matches the basis function.

Another problem is that you appear to be saying that the summation is a DFT. I don't think you make it clear that it is just one point on a whole function. The DFT is the whole function, not the point.

--Bob K 22:29, 25 October 2007 (UTC)

I edited it to be more nearly correct. Please feel free to work on it more. Dicklyon 23:49, 25 October 2007 (UTC)

[edit] Needs images

This sections needs LOTS OF IMAGES. —Preceding unsigned comment added by 18.243.2.30 (talk) 19:31, 14 November 2007 (UTC)

Why? What kind of images do you have in mind? Dicklyon 20:40, 14 November 2007 (UTC)

I just came here thinking there should be a new page devoted to Fourier transforms of images. Perhaps that's what Anonymous had in mind? I may start Fourier transform of images. I worry it verges on how-to, but there are particulars about it that aren't covered elsewhere right now. There's a lot of encyclopedic "what is it?" information that could be added on the topic. —Ben FrantzDale (talk) 01:50, 18 January 2008 (UTC)

[edit] To complicated

Yes, this and entire Fourier series articles on Wikipedia are too complicated. Here is Wikipedia, not a math courses. I looked over the discussion page and I saw only cheap talk among "specialists" . Please insert sections with basics explanations about Fourier and then you can put whatever complex stuff you want. —Preceding unsigned comment added by 192.35.17.15 (talk) 12:39, 12 February 2008 (UTC)

I tend to agree. A layman's introduction to the Fourier transform would be useful. Integral transforms can seem complicated and unintuitive when they are really fairly simple and are elegant, powerful generalizations of a change of basis in finite-dimensional linear algebra. In an Introduction to Fourier analysis page, I would start with relating it to a change of basis, then show the basis in pictures, and discuss some intuition behind it. For example, that "high-frequency information" means something very specific that can be different from a human intuition for frequency. For example, that a square wave with a given frequency has more than just that frequency component in the Fourier domain. Such a page might also mention the convolution theorem as an important application. —Ben FrantzDale (talk) 12:05, 13 February 2008 (UTC)

I don't think anyone would disagree with more good-quality, well-organized information, since we are not space limited. At the risk of stating the obvious, I think the only "problem" is that formulas are easier/faster to create than pictures, once you get the hang of it. And of course they are more generally useful.

--Bob K (talk) 14:39, 13 February 2008 (UTC)