This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 |
I would like to do a spectral analasys, but I have NC on how to interpret the results I get after the transformation. Can anyone explain it please? -- Marco 17:54, 18 February 2006 (UTC)
I can't see the character ℱ, even when I select Unicode encoding from the "view" menu of explorer (unless it's supposed to be an empty box). - rs2 21:25, 24 Mar 2004 (UTC)
This is wrong. The discrete fourier transform is given by
The inverse DFT is given by
In both equations, N is the total number of sampling points.
Hello Steven - about the reason for the 1 and 1/n convention - I see your point that it avoids a multiplication for the DFT but I don't think that an actual algorithm would put the 1/n inside the summation and multiply all n times. It would just perform the summation and then multiply by 1/n. Shouldn't we say that its a combination of avoiding a multiplication for the DFT, AND not having to spend the time calculating the square root? Paul Reiser 18:58, 25 Jan 2005 (UTC)
Ok, I get it about the n times thing. I think we are coming at this thing from two different directions. Your idea of "best" normalization seems to be from an algorithmic point of view, mine is from a mathematical point of view. Casting the DFT as a unitary operator is absolutely the best thing to do from my point of view. All of physics is based on things that are invariant under some transformation or other. When the DFT is a unitary transformation, the dot product, the angle between two vectors, the length of a vector, all are preserved. Viewing the DFT as a unitary operator is like saying it is a simple rigid rotation in space. With the 1,1/n normalization, it is like saying its a rigid rotation plus converting from meters to inches. Its klugy from a mathematical point of view. Ok, thats my rant. I agree that using the η symbols is not the best thing for a new reader to see, and we have to come to a compromise here. How about we do it in 1,1/n normalization, and I put in a section about the unitary normalization and how neat it is. I was about to say I needed to correct some things, but I see you are editing the page as I am writing this so I will check it tomorrow. Paul Reiser 02:51, 26 Jan 2005 (UTC)
Hello Steven - I put the unitary material into one section, I think it works, but I took the matrix out of the orthogonality section. I'm not sure if you thought it was serving a purpose there, I couldn't see one, but I did see a purpose for the unitary section, in pointing out that it is a unitary matrix (with the proper normalization). Paul Reiser 11:58, 27 Jan 2005 (UTC)
Should this article be merged with discrete-time Fourier transform? Michael Hardy 01:34, 2 Jun 2005 (UTC)
I have an online book about the DFT that is aimed at the beginning undergraduate level: Mathematics of the Discrete Fourier Transform ( http://ccrma.stanford.edu/~jos/mdft/) I am looking into splitting out some of the material into articles for the Wikipedia. However, since there is already a fine DFT article at the Wikipedia, I would merely recommend the book as an external reference, especially for "beginners". -- Julius
Also, it would be nice to have pointers to "live" Fourier transform software, perhaps:
... is there a good place on Wikipedia or Wikibooks to put public-domain source code?
Hi StevenJ. You reverted my changes because you liked your own better. Well, I don't. Shall we discuss the matter and collaborate to improve instead of reverting each others changes ?
Hi Steven. The article is terrible: confusing, inconsistent, incomprehensible and far too long. Even if it is not mathematically wrong to change notations and definitions in the middle of an article, it is no good to the reader. I'd like very much to help in cleaning it up, but when you just revoke everything I do, you cannot be helped. I'm really sorry. Bo Jacoby 07:29, 29 September 2005 (UTC)
Thank you for your suggestion, PAR. I'll pick out one particular correction. It is certainly not the biggest in my mind, for that would be the union of all the changes that I have in mind, but it is the first one that I stumble on while reading. It was stated that the word 'sequence' would be used in the meaning of 'vector'. Then the reader could have the burden to remember this and translate 'sequence' into 'vector' while reading. I think this suggests the simple edit of changing 'sequence' to 'vector', taking the burden from the shoulders of the reader. Let me know if anyone disagrees. Bo Jacoby 07:55, 30 September 2005 (UTC)
Bo - Before I revert some of your edits, let me explain myself. A sequence is an ordered set of numbers, and that's about it. A vector is a mathematical object which has associated operators etc. and by a logical process it can be deduced that if you define a set of basis vectors (a coordinate system), you can represent a vector in terms of this basis set by a sequence. The sequence is not the vector, at least from a mathematicians or a physicists point of view. It is from a computer programmers point of view, I think, but this is a mathematical article. That means the statement:
is not correct, "vector" should read "sequence". There is no such thing as a "vector of complex numbers", only a sequence of complex numbers that may or may not represent a vector, depending on whether a coordinate system and all the vector operators have been defined. The bottom line is that the DFT operates on sequences. It is often very helpful (and interesting) to assume that the sequences are representative of vectors. The DFT then can be thought of as a linear vector operator, etc. etc. The article is a bit sloppy in this regard and needs to be fixed. PAR 10:38, 30 September 2005 (UTC)
I agree, that distinction should be made more clear. However, I still say that the DFT fundamentally operates on sequences which may or may not be sequences of vector components. I don't need to know whether a sequence of complex numbers represents a vector in order to perform a DFT on that sequence. A sequence of complex numbers is not necessarily PAR 14:38, 30 September 2005 (UTC)
Ok, I see your point, once you have the transform, you've implicitly defined the operators that make the sequence a vector space. It still grates my sensibilities, I mean there are so many properties of the DFT that aren't of a vector nature, like the shift property. Should we be using "vector" in this instance? I don't think so. Should we only use vector when its a property of a vector space or some higher-ordered space (eg metric) and use sequence otherwise? The previous wording mixed it up, but was there a method to it? PAR 21:08, 30 September 2005 (UTC)
Ok, see your point. Its between you and Bo, then, but if I have to break a tie, I would say the old way was good, except a little longer note than "sequence and vector are used interchangeably" would be needed. PAR 14:27, 1 October 2005 (UTC)
I agree with Steven that the discrete fourier transform operations are vector operations. Any finite dimensional vector space over the field of complex numbers can be subject to the discrete fourier transform by chosing a basis, so PAR's feeling that the discrete fourier transform applies to sequencies rather that to abstract vectors is incorrect. Though I generally agree with Orwell about synonyms, the connection between concepts and words is more precise in mathematics than in everyday language. I agree with Steven that one concept is logically sufficient, but we disagree about using two words. To me using two words for one mathematical concept is an unnecessary complication, and this very discussion confirms that it does introduce misunderstanding. Bo Jacoby 08:14, 3 October 2005 (UTC)
A second suggestion. Why not simply write: and instead of: if then and ? The f is unnecessary. Bo Jacoby 09:02, 3 October 2005 (UTC)
Different readers look differently on things. I just see the f as a useless complication which the author should have eliminated himself instead of leaving it to the reader. Bo Jacoby 09:27, 4 October 2005 (UTC)
This section introduces a 4th notation for the fourier transform : The primed index: . Why not reuse one of the 3: , , . Further cleanup may reduce the number even more, hopefully to one. Bo Jacoby 09:25, 3 October 2005 (UTC)
Any linear bijection defines a change of coordinate system. That is an important point. It should be explained somewhere in WP, but not necessarily here. Bo Jacoby 09:39, 4 October 2005 (UTC)
Says: "The only important thing is that the DFT and IDFT have opposite-sign exponents, and that the product of their normalization factors be 1/n." The words "The only important thing" indicate that only one thing is important. The explanation gives two things. It is depressing to the reader to accept the fact that the author has difficulties in counting to two.
The opposite-sign exponent thing is not important, because the involutary DFT has DFT=IDFT, with equal exponents. Bo Jacoby 11:52, 3 October 2005 (UTC)
Consider the important special case of a sequence of real numbers x being transformed according to the formula How is this formula generalized to a sequence of complex numbers x ? There are two options : and Both formulae generalize the real case. They are not that different. The lazy mathematician choses the first one because then he dosn't need to modify the formula. The careful mathematician is guided by algebraic simplicity: Because the second one is involutary and the first one is not, the second one must be chosen and the first one sacrificed on the altar of Occam. PS. Note that I resisted the temptation to write :-) Bo Jacoby 08:42, 4 October 2005 (UTC)
"Early muddled thinking being carved in stone" it is. I love your poetry! The better generalization of the concept of a linear operator on a real vector space is that of an antilinear operator on a complex vector space. The antilinearity gives precisely what you need. (The name 'antilinear' is ill chosen, however, because it seems to imply that it is the opposite of linear, which it is not.) Bo Jacoby 13:28, 4 October 2005 (UTC)
Steven, after studying No original research I think you are completely wrong. I quote: Research that consists of collecting and organizing information from existing primary and/or secondary sources is strongly encouraged... "No original research" does not mean that experts on a specific topic cannot contribute to Wikipedia. Indeed, Wikipedia welcomes experts and academics. This means that a new calculation or a new notation or an alternative definition is not considered 'original research' in this context. It does not rely on information which is inaccessible to you or to anybody else. I am very flattered that you consider the involutary fourier transform to be original research. If I claim that I have made an invention, I expect everybody to object against it saying that it has been done before, or that it is trivial, so I should not consider myself an original scientist. Now the situation is up-side down. I personally don't believe that the involutary fourier transform is original research on my part. I consider it fairly trivial. I merely point out a minor error in one of your definitions of the fourier transform: one missing asterisk. It can easily be corrected. It is no big deal. I don't consider this to be original research. But you do ! Thank you very much, I'm honored and pleased. Bo Jacoby 08:07, 5 October 2005 (UTC)
PAR, what you need is expanding the expression T(ax+by). In the real case it is aT(x)+bT(y). In the complex case it can be either aT(x)+bT(y) or a*T(x)+b*T(y). In both cases T(ax+by) is evaluated, and that is what is needed. Bo Jacoby 08:07, 5 October 2005 (UTC)
The introduction should give a short answer to the short question: "What is the discrete fourier transform?". Smalltalk should be avoided here. Using the involutary DFT as the definition will do this, and also save the The Plancherel theorem from being mentioned twice in the article. Bo Jacoby 11:52, 3 October 2005 (UTC)
If your programmer wants to spare his computer from computing the square root, by all means, let him code a fast fourier transform subroutine called SQRT_FFT computing √N*DFT(X). It is no excuse for the mathematician to make non-unitarian or non-involutarian definitions. The unitarity and involutarity is appealing to every user, who neither wants to remember two versions of the Plancherel theorem, nor to bother about the difference between DFT and IDFT. Bo Jacoby 12:57, 4 October 2005 (UTC)
Actually I do have FFT-experience. I completely agree on your PS that the time for taking the square root is epsilon. But the time for the 2N real multiplications is neglectible too because the inner loop of the FFT requires Nlog(N)/log(2) complex multiplications, so this inner loop is more timecomsuming when N is a large number. When N is not a large number everything is fast, so nothing matters. Of cause you know all that. The convolution theorem asserts that the transform of a convolution is the product of the transforms, so the convolution is the transform of the product of the transforms. Can that really be simplified? Please show me. I don't think that unitarity is the only convenient property. Involutarity is nice too, because it is timeconsuming to debug the error of having chosen the wrong one of IDFT and DFT. Not having this to worry about makes programming safer. Bo Jacoby 08:39, 5 October 2005 (UTC)
I was mistaken. Thank you for telling me. Bo Jacoby 11:54, 6 October 2005 (UTC)
Implement any variation of the discrete fourier transform to suit your needs of saving computer time, but stick to one definition and explain your subroutine in terms of that. Bo Jacoby 11:54, 6 October 2005 (UTC)
Yes. Here the symmetry is broken. The coefficients of the fourier series are integrals. Yet my point is the same as before: define one discrete fourier transform and express everything else in terms of that, instead of confusing the reader regarding the meaning of the word. My 'crusade' is for simplicity and clarity, and you are not my opponent in that respect. Bo Jacoby 11:54, 6 October 2005 (UTC)
My next suggestion for improvement of the article. Some people consider the discrete transform to be a special case of the continuous transform, when generalized to distributions like the dirac delta 'function'. I think it is better to consider the continuous transformations as limiting cases of the discrete transformation, because then the reader doesn't need to know about integration but can just consider a large value of n. Consider the ring of integers , the ideal of multipla of n , and the quotient ring . The vector space in question is The indexes can be represented by integers from 0 to n-1, or from 1 to n. The indexes can be represented by integers from -n to n-1. Substituting into gives the limit Bo Jacoby 12:04, 5 October 2005 (UTC)
For the continuous transform, choose the dimension to be an even square number: . Substituting
into
gives the limit
Note that does not appear in this expression for the unitary involutary continuous fourier transform. (The asterisk signifies complex conjugation). Bo Jacoby 12:46, 6 October 2005 (UTC)
1. In the context of discrete fourier transform it is interesting to compute a finite sum approximately by means of a known integral. That is uncomplicated. 2. In the context of integration theory, the integral is defined as a limit of a sequence of finite sums. That is where all the complication belong. 3. Regarding : You are not expected to change your mind, but the mathematicians following you may not feel the same way as you do. Today's nonstandard original reseach may be tomorrow's standard notation. When contempleting your life's net value to humanity you may count your battle against progress as a negative contribution, but while there is death, there is hope. 4. Surely the usual branch cut is redefined. That was no holy cow. is multivalued, and that cannot be helped in general. The usual branch cut leaves unpleasant and unnatural discontinuities. The conventional choice that is nonnegative real for nonnegative real z is natural when working with real numbers. The conventional choice that is utterly unimportant. It is not used in practice. Why write instead of 1 ? The notation is free to be redefined to something useful. The expression is repeated endlessly in technical and mathematical litterature, and a many readers get confused. Where did and and come from ? Because , then is a natural and useful convention. Bo Jacoby 11:27, 7 October 2005 (UTC)
to Steven. The discrete fourier transform of x(t)=1 is , (using Iverson bracket), while the continuous fourier transform of 1 requires a definitional extention of the concept of a function. The indicator function of the rationals, , does not appear as a limit of discrete functions. The complications of definition belong to the article Distribution (mathematics). The complications of integration theory belong to the article Lebesgue integration. No such complication belong to discrete fourier transform. Bo Jacoby 10:27, 10 October 2005 (UTC)
to PAR.
I should practice what I preach, so I redid the unitary section to get rid of the primed indices. The problem is, I replaced it with primed vector symbols, and this is still not in conformity with previous use of capitals as transformed quantities. I want to emphasize with the notation as much as possible the idea of having a constant vector object, and its components are the only things that change, the DFT being simply a coordinate transformation. That was the idea of the primed coordinate indices rather than the primed vector symbols. However, to express the unitary stuff using capital letters would further obscure this idea. Is there any objection to changing the capital letters to primed letters in the rest of the article? PAR 15:56, 8 October 2005 (UTC)
For those who think of the Fourier transform as a time-frequency pair, yes, you want to emphasize the distinction. For those who think of it as a coordinate transformation between the momentum and space representations of a quantum wave function, you want to emphasize the lack of distinction. We should not favor the time-frequency POV. PAR 18:54, 8 October 2005 (UTC)
' Ok, I'm focusing on the concept and not the particular calculation technique. You know that the study of invariants under linear transformations is fundamental in physics. Also, you know I agree we don't need any unsual notation. But Parsevals and Plancherel's theorems are just so much mathematical gobbledygook to a beginner, and I am trying to convey an intuitive understanding of these theorems. Will you help me do that ? PAR 23:30, 8 October 2005 (UTC)
I separated the involutions from the tricks. Is the Hartley transformation really an involution ? Shouldn't the divisor '2' be under the square root sign ? Shouldn't the formula be found in the Discrete Hartley transform article ? Bo Jacoby 13:13, 13 October 2005 (UTC)
Dear friend. The Discrete Hartley transform says: Its main distinction from the DFT is that it transforms real inputs to real outputs, with no intrinsic involvement of complex numbers, in variance your statement: taking the real part is necessary to get the Hartley transform (even for the real inputs, the outputs of H(x) are complex). Please make up your mind. That the involution form is basically an aside; it does not merit its own section is your opinion, but not your decision. You know that the matter is controversial. Nobody prevents you from expressing your view based on your experience, nor should you prevent others from expressing their view based on their experience. My experience-based view is that this involution has the simpler algebraic properties. Please restore my edit and stop acting like a censor of the spanish inquisition. Bo Jacoby 08:56, 14 October 2005 (UTC)
You claimed that the notation is considered 'original research' and I didn't pursue it. The involutary fourier transform was accepted by you. Nobody called it 'original research' until now. I just changed the division into sections. I trusted PAR that you would not remove my edits, but you did. Spanish Inquisition refer to your actions, not to your person. You remove anything that you personally don't like, as herecy. This is getting ridiculous. I must give up my attempt to clean up your messy article on discrete fourier transform, because you are working against it. Yes, you may delete it entirely. You are on your own. Good bye. Bo Jacoby 11:26, 17 October 2005 (UTC)
What does this have to do with the DFT? Aliasing is caused by periodic sampling. We don't need a DFT to see that and are indistinguishable. -- Bob K 04:14, 13 December 2005 (UTC)
What purpose is served by the word finite in the sentence?: "and it means that in a finite discrete signal one cannot distinguish between frequencies j that differ by n". -- Bob K 04:14, 13 December 2005 (UTC)
What is the point of this?: "If one simply evaluates the DFT formula at then one finds that ," I.e., it appears that we are assuming the sequence is periodic in order to "prove" that the DFT thinks it is periodic. -- Bob K 04:14, 13 December 2005 (UTC)
Hi Bob, your basic issue seems to be that aliasing "has nothing to do with the DFT". Although aliasing can also be derived in other circumstances and in other ways, I can't agree with you entirely. Aliasing is still implicit in the definition of the DFT, and the implied periodicities are an intrinsic consideration in almost any application of the transform; it would be remiss not to mention it here.
I don't think you can avoid using the DFT definition in deriving the aliasing in this case, moreover, because the DFT definition defines what you mean by "samples" and "frequency" in this context. Because this corresponds to the usual definition for uniformly spaced samples, you don't even think about it, but it is there. For example, you could certainly apply the DFT to a sequence of numbers corresponding to non-uniformly spaced samples of some signal — the resulting DFT would not correspond to amplitudes of "frequencies" of the original signal in the usual sense, but would still have an aliasing property of a different sort. In general, the aliasing property can arise in contexts that have nothing to do with signals and sampling, e.g. many FFT algorithms exploit the implicit periodicity. Abstractly, there is also a close relation between the DFT and representation theory for the irreducible representations of the cyclic group (which would be a nice connection to mention in the article, although currently the representation theory articles in Wikipedia are painful to read).
You can quibble about the precise way in which the property is proved, I suppose, but any sufficiently short and clear proof seems fine to me. I'm not sure where you think the current article skips a step. —Steven G. Johnson 17:25, 13 December 2005 (UTC)
Would you be happy if the article stated something like, "More generally, aliasing phenomena also occur whenever one is analyzing the frequency components of a discrete signal (or discrete samples of a continuous signal), such as in the discrete-time Fourier transform." I have no problem with this. —Steven G. Johnson 23:14, 14 December 2005 (UTC)
I like the stacked version better than the unstacked version. IMO, that's the whole point of having a cool math editor. -- Bob K 21:11, 15 December 2005 (UTC)
A major point of having a cool math editor is versatility: you can make it do what you want it to. "Stacked" is appropriate in some cases, but seldom within superscripts. Bob K, did you think I was saying "stacked" should never be used? If so, go back and read what I wrote, since you missed it entirely. Michael Hardy 21:53, 15 December 2005 (UTC)
Stacked notation does not work well for inline formulae. Using stacked for display and unstacked for inline places an extra burden on the reader. For a fraction with both numerator and denominator complicated, stacked display can be a great help to clarity; here, the benefit seems small. Outside of TeX, k/n can be marked up to appear as k⁄n; but that's of little help in this case, partly because of Wikipedia's LaTeX limitations. Finally, stacking causes shrinking in an already-small superscript, cancelling some of the benefit of stacking in general. -- KSmrq T 01:57, 16 December 2005 (UTC)
Michael, in general I agree with you about stacking in superscripts. However, in this particular case, the stacking serves a useful purpose: to clearly separate the 2πi/n from the jk index product. If you don't do this, the ijk is somewhat confusing because all of the letters look similar. —Steven G. Johnson 04:31, 16 December 2005 (UTC)
hi guys, i've only recently started taking an interest in all of the Fourier/Laplace/Z transform pages and had no idea that there was such recent activity on this one.
i want to suggest something (that i am willing to do the grunt work) that i feel really strongly about. while the Laplace Transform, Fourier transform, Continuous Fourier transform, and Fourier series articles will have much broader interest and readership, i really believe that the discrete-time transforms, DTFT, DFT, Z, have much more narrow interest and constituency. while i do not claim that only electrical engineers doing signal processing are the only persons interested in or using these concepts, techniques, or algorithms, i do believe that it is principally people doing signal processing having such an interest. in that there is already a widely accepted notational convention for these discrete-time or discrete-frequency signals (that is and ) in the textbooks (i still consider Oppenheim and Schafer Discrete-Time Signal Processing to be the standard, but i s'pose we could argue about that) and lit, i really believe that we should adhere to that convention here. there are some of us agitating to revamp a bunch of EE electronics, control systems, communications systems, filtering, and general signal processing articles and we really should have notational consistency, and i really think that all of the discrete-time linear transforms (DTFT, DFT, Z) fall mostly in the EE and signal processing discipline.
may i change that notational convention from to and to (spending some considerable time) without someone reverting all of my effort away? FYI, there are two reasons i know of for why the EE discipline and lit has changed the notation. the main reason is that it is not uncommon to be processing a signal vector. in continuous time it looks like and, if sampled it would be . but, if we need to refer to the individual components of the signal vector, it would be and . do you see how it gets ugly if we have to say instead? also is harder to do by hand than . r b-j 02:59, 16 December 2005 (UTC)
The DFT is used by a wide audience, and so it is important to use as universal a notation as possible. If you use subscripts, everyone knows what you mean, but I think brackets are a bit too overloaded as far as notation goes. The Wikipedia articles aren't using a vector signal so that argument is moot. (I admit I don't have terribly strong feelings about this. I'll point out, however, that most of the literature on FFT algorithms uses subscripts as far as I can tell.) Moreover, you'll have to change literally dozens of Wikipedia articles that use the subscript notation. —Steven G. Johnson 04:38, 16 December 2005 (UTC)
I don't know if you realize, but is by definition identical to . It is purely an issue of notation, not of meaning. I think artices dealing with the DTFT, the DFT, and the ZT should use the bracketed notation rather than the subscript notation, for all of the reasons mentioned above. It does not need to create any confusion if you simply note, near the beginning of each article, that the article will be using the convention that
and then explain briefly the rationale (common convention in signal processing, indicative of vector/matrix notation, etc) for using this notation. It should not be a big deal for non-EE's to understand, and it would be a big help for EE's. Why are non-EE's so afraid of trying something different? There are good reasons why EE's have chosen these newer conventions, and they actually can help in other disciplines as well. It's helpful if you drop the not invented here paradigm. -- Metacomet 22:06, 16 December 2005 (UTC)
One other point: I believe that the bracketed notation is actually older than the subscript notation. Back in the old days, before WYSIWIG computers, people used to use typewriters or text-based computers. Yes, I know it is hard to believe, but these antique devices did not provide the capability of creating sub-scripts or super-scripts the way we can today in our modern word processing applications or with LaTeX. So the way that people used to indicate sub-scripts was to place the sub-scripted character inside of square brackets, as in, for a one-dimensional vector or even for a two-dimensional matrix.
It's only half-speculative, because I am pretty sure about it. And I preceded my comments with the words "I believe that...". -- Metacomet 00:25, 17 December 2005 (UTC)
I never said that subscripts and superscripts were not also used. Obviously, in handwriting or typesetting, or with an advanced enough typewriter, you can do subscripts. What I did say was that brackets were also used, when you had a typewriter that could not handle subscripts, and people had no trouble understanding what they meant. --
Metacomet 00:23, 17 December 2005 (UTC)
I am not suggesting that we should abandon WYSIWIG and go back to using square brackets in all situations. What I am saying, however, is that this convention existed long before EE's adopted it as notation for describing discrete-time signals, and I believe that it is a perfectly acceptable convention for vector and matrix notation. -- Metacomet 22:20, 16 December 2005 (UTC)
I agree 100 percent on your notation changes. We should not use i or j as index variables, since either one can represent the imaginary unit. -- Metacomet 00:15, 17 December 2005 (UTC)
As far as a mass conversion is concerned, I would say that we should only change articles where it makes sense to do so (not to state the obvious) – mainly articles related to discrete-time signals, discrete-time systems, discrete transforms, and image processing. -- Metacomet 00:15, 17 December 2005 (UTC)
Okay, I am sorry for getting in the middle of this discussion. I lost my head for a while. It is very difficult to get a consensus with such a diverse group of people coming from so many different points of view.
I just took another look at the article itself, and regardless of where you stand on the issue of brackets versus subscripts, it is really clear that the current notation in the article is really problematic. Again, I cannot speak for everyone, but it seems to me that no one should be happy with the current situation.
So if my assumption is correct, then maybe we shoud see if we can find at least some common ground.
I would make the following recommentaions:
Can we all agree on at least these initial steps to help move forward? Please comment.
-- Metacomet 03:28, 17 December 2005 (UTC)
Even though I agree with changing from subscript to brackets, I would recommend that you hold off on that idea for now. If we can get consensus on the few items I listed above, and the one item I listed below, then maybe we can at least accomplish something in the short run.
In the meantime, we can continue to discuss the subscripts versus brackets issue and maybe try to find a solution. -- Metacomet 03:46, 17 December 2005 (UTC)
Another recommendation:
-- Metacomet 03:44, 17 December 2005 (UTC)
I just wanted to give a few things a bit of a test drive. There is no harm done, things can always be reverted if they don't work out. I will leave it alone for now though. I am going to sleep now anyway. I will take a look at it tomorrow. Good luck.
In addition to the changes you just mentioned, I would replace j with m and leave k alone for now. Or use n and k if you want to do the extra work. -- Metacomet 04:45, 17 December 2005 (UTC)
Actually, I do not agree with putting the nk on top of the fraction. Believe it or not, I think it makes sense to put the i in front of the fraction, the 2 π on top of N for the fraction, and then the nk after the fraction. The reason is that you can attach in important interpretation to the 2 π/N as representing the discrete angular frequency increment (in radians per sample) that is very useful in understanding the DFT and more importantly, in implementing the frequency domain in a computer simulation. If you don't know what I mean, I will try to explain later. It's a bit complicated. -- Metacomet 04:49, 17 December 2005 (UTC)
Although we will likely never agree on all aspects of the change, it looks like we can probably agree on some set of changes to make. However, it is important to list them all here before making them, since if we are going to change several things it will be much easier to change them all at once than piecemeal. Second, there is no huge rush — this is an article that lots of people have contributed to, and it is reasonable to wait for comments for a t least a couple of days before instituting major, wholesale changes across dozens and dozens of articles. —Steven G. Johnson 06:24, 17 December 2005 (UTC)
Just as an idea of what I am talking about, I collected all the articles in Category:Digital signal processing including sub-categories and listed them on the above page. I also put a menu in listing notational changes, and we can check them off as needed. I assume the k,n,N changes are acceptable to everyone, so I listed that first. I didn't spend a lot of time alphabetizing or elaborating in case this idea doesn't fly. PAR 20:04, 17 December 2005 (UTC)
If nobody objects, I am going to start working on a very modest plan to start changing the notation. I am going to work on this article only and on only one change at a time. The plan is as follows:
1. n becomes N: Change all instances of the symbol n to the new symbol N to represent the length of the sequences in both the time and frequency domains.
2. k becomes n: Change all instances of the symbol k to the new symbol n to represent the index variable for the time domain sequence.
3. j becomes k: Change all instances of the symbol j to the new symbol k to represent the index variable for the frequency domain sequence.
I am going to make one change at a time, and I am not going to proceed with one step until I have completed the prior step.
We have been discussing these changes for many weeks, and from what I can see, nobody has objected to these three changes, and many have expressed support for them. So I believe there is a consensus at least on these changes. If there are any objections, please speak up now. I will start working very soon.
-- Metacomet 02:00, 27 December 2005 (UTC)
To make all three at once would require changing all of the notation in the whole article in one shot. I don't have time to do that, unless I can figure out a way to do it with a global search and replace algorithm. I could possibly do that in Microsoft Word, but I am not sure it will work. Otherwise, I need to make the changes as an evolution over several days, and because of the nature of the changes, they must be done in the order that I have suggested.
If you have any better ideas, I am all ears (or eyes...)
Out of curiosity, why are you suggesting to do all the changes at once? The method I have propsed should not create any confusion during the transition.
-- Metacomet 19:52, 27 December 2005 (UTC)
Are you suggesting that you don't think I have a lot of common sense? -- Metacomet 02:23, 28 December 2005 (UTC)
Actually, don't answer that. I think I already know the answer.
There are good reasons for making the changes one-at-a-time, if you think about it for more than 3 seconds. The reasons are related to concepts from manufacturing like error proofing and single piece flow. Although it is not at all obvious, it turns out that it will actually take less time to make one change at a time than it would to make all three changes together, and more importantly, it will be much less likely to make an error.
BTW, with a little bit of clever scheming, it is not all that difficult to figure out a way for a global-search-and-replace to distinguish between "n" in an equation and "n" that is part of a word. Again, it just requires a little bit of thinking and planning.
-- Metacomet 02:56, 28 December 2005 (UTC)
Also, I would appreciate it if you would avoid snide put-downs. Please see No personal attacks and Civility. Thanks. -- Metacomet 05:25, 28 December 2005 (UTC)
Sorry, RBJ, it's just too difficult to get anything done. I have other fish to fry. It would be nice to see the notation changed to something more standard, but ultimately, it is not all that important to me. Good luck. -- Metacomet 18:42, 28 December 2005 (UTC)
Another problem, while we're at it, is the unnecessary use of two different symbols for the same thing: and . is probably more conventional, given that the time sequence is . And for what it's worth, it avoids potential confusion with the in
http://en.wikipedia.org/math/7/7/5/7757e67d47b0ba3f1f7e3628c813bd2d.png
--
Bob K 20:48, 2 January 2006 (UTC)
I have started converting the notation in Discrete cosine transform to match the changes that we have agreed to on this article. The four changes are:
1. n becomes N: Change all instances of the symbol n to the new symbol N to represent the length of the sequences in both the time and frequency domains.
2. k becomes n: Change all instances of the symbol k to the new symbol n to represent the index variable for the time domain sequence.
3. j becomes k: Change all instances of the symbol j to the new symbol k to represent the index variable for the frequency domain sequence.
4. f becomes X: Change all instances of the symbol f to the new symobl X to represent the transformation of the data sequence in the frequency domain.
Once I have finished the DCT article, I will start working on Discrete sine transform.
If others would like to help, please review the List of Fourier-related transforms for articles to work on (discrete versions only).
-- Metacomet 16:00, 6 January 2006 (UTC)
The section on Completeness states: "for any N ≥ 0, any N-dimensional complex vector has a DFT and an IDFT which are in turn N-dimensional complex vectors."
The case N=0 is unimportant, and all the formulas having N in the denominator ceases to make sense. It should be changed to "for any N > 0, any N-dimensional complex vector has a DFT and an IDFT which are in turn N-dimensional complex vectors."
Bo Jacoby 07:46, 5 January 2006 (UTC)
Here we go again... As you know, I think this section needs a little work. My new gripe is with the last paragraph:
-- Bob K 03:11, 7 January 2006 (UTC)
Since this article is basically totally incomprehensible to those who do not know higher math, perhaps we could include a visual representation of a DFT so the reader may at least get a vague idea of what it means/does. How about a nmr or ftir spectrum?-- Deglr6328 08:09, 12 April 2006 (UTC)
My sentiments exactly. I was really surprised at the detailed math of this. Good math, maybe, dry article. So now begins the...:
The Finite Fourier Transform is an experiment you really can do at home; your spreadsheet is all you need.
---A WORK IN PROGRESS--
All "real-world" waveforms can be described by a summation of sines and cosines with constant coefficients (amplitudes): Why do we care?
Why do we care? Answer this: Why does a bird chirp sound different than a cricket chirp? What frequency (pitch) was that crow's caw? Why does my voice sound different than yours? How do we make this awful picture of Aunt Millie sharper? Most scientists mathematicians, and engineers use the various processes called "the Fourier transform" to answer these and similar questions. They want to learn more about the waveforms of the signals-- the "waveform" is "the shape" of "the signal" (that comes for example, from their microphone).
Why not just look the waveform on an oscilloscope or a computer screen? Because it will be just a jumble of up-and-down "waves" with littler wavey wiggles in them -- like ocean waves, big waves with little waves riding on top. There is nothing we can use there.
The discrete Fourier transform freezes in time facts about a waveform's "pitch" (its frequency, its tone high or low as in A-440 cycles per second versus middle C-512 [?]) that we can look at as long as we'd like. And, given this transform, we can recover our original waveform.
When waveforms have been "transformed" to this stationary form we can do all kinds of neat things to them. Such as: use Adobe Photoshop to sharpen the digital photos of Aunt Millie.
Discrete signal recording:
Before the mid-1980's sound recording was done first (i) mechanically by phonograph, then later (ii) electro-optically on film (motion picture sound track), or tape (magnetically). Sound engineers used these "analog" (continuous as opposed to discrete) methods and looked at their signals on "analog" oscilloscopes.
But today the computer "sound card" takes the signal that comes from the scientist's microphone and "samples" it (40,000 times per second, or 44,000 per second, or 176,000 per second, etc). What the sound card produces and sends to the computer are streams of "bits and bytes" -- 16 bits, 24 bits, 32 bits -- that represent the signal but are no longer "the signal" itself; the sound is gone across the meadow into the hills, the signal from the microphone is converted to heat and lost forever. All that exists finally are "the bits and bytes" that the scientist's computer has recorded on her hard drive or her flash-card.
This type of "signal-processing" is called "analog-to-digital" (A-to-D) conversion and is done by special circuitry. In all cases the conversion involves (i) sampling the waveform, (2) A-to-D conversion at a fixed interval (such as 44,000 conversions per second, or 176,000 conversions per second for "high resolution" recordings). Quite often the processs involves more steps: (i) smooth the signal with a "low-pass filter", (ii)"hold" the signal steady for a moment while (iii) the A-to-D converter samples the held signal, (iv) actually A-to-D convert the sampled signal. We will see below why these extra steps are required.
Sampling is easy:
To sample a waveform just multiply it by 1 to take the sample; the rest of the time, multiply by 0. (The briefer the sample, the better). In our example, the waveform we are sampling changes from -10 to +10 (usually the waveforms are much smaller, this is just an example). Whenever our "sampler" takes a sample, it -- in effect -- multiplies the waveform at that instant by 1.
Our resulting string of numbers-as-samples looks like this:
Notice something interesting: our waveform is compressed into just a few samples, now stored in space on a computer disk (or whereever). Is it really possible that we can recover our original waveform from this squished stuff? YES!
An aside: Quantization:
A crude A-to-D converter might change our analog number between -15 and +15 into 31 levels of "quantization" equivalent to steps (quanta) of 1. These "levels" will come out as bits and bytes. For example, +5 might be 00100, -5 might be 10101, etc. Fancy A-to-D converters convert to 32 bits or about 4 billion levels. Common audio conversion in a computer is to 16 bits, about 65,000 levels.
The role of the discrete Fourier transform is not fret about issues surrounding "quantization". The transform's role is to convert our waveform from a time-based event into frequencies that we can stare at forever, if we want to. The only job quantization has to do is to give the computer (or us) numbers that it (we) can crunch.
Analog samples would work just fine if we had a bunch of analog multipliers and adders to do the transform.
But what about the transform? Show me the transform!
All in good time. First we need to describe how we get the waveform back:
Discrete signal playback:
When the scientist plays back the sound on her computer, the computer delivers the saved bytes to the sound-card.
> [usually beforehand the scientist selects a "slice" to look at and transform... Sound Forge example? hence the sampling window]
The card uses a reverse process called Digital-to-Analog (D-to-A) to convert the bytes and bits back into a waveform. But the output from the D-to-A converter will again have discrete steps in it. If we were to look at the Sony Sound Forge reproduction of the "signal's waveform" we find it is represented by points (the discrete samples) connected by lines (interpolations so the result may look like triangles). After D-to-A conversion the sound card smoothes out the steps (or triangles) with a low-pass filter. The sound card amplifies this smoothed now-analog signal; it is now in a form our scientist can hear on her speakers [Is this correct re sigma-delta conversion?]
A question appears: Why do we believe we can trust our tools?:
In brief: we can't until we "calibrate them" -- test them against known good results. We wonder: will a reproduction be faithful to its original? Maybe yes, maybe no. Even if our crow-caw microphone introduces "junk" (wind noise is typical), a poorly-designed sound card may introduce unexpected junk into our scientist's reproduced waveform (growls, whistles, whines). If this is the case, she (hopefully) will find it when she looks at "the spectrum" of the waveform. With the use of the discrete Fourier transform she can do just that -- look at the "frequency spectrum" of her bird and insect sounds, present them on a sonogram that plots frequency on the Y axis, time on the X axis, and colors the intensity of the sound. Perhaps from what she expects and from applying known waveforms to her sampler, she can learn to "trust her tools".
sines and cosines:
Why do we need to discuss "sines" and "cosines"? It just turns out that any snippet of waveform can be approximated by a bunch of them added together. The why and the proof of this is not so simple, however. [see Why it Works].
Most people think of sines and cosines in terms of trigonometry, but the words themselves do not contain those ideas. Rather, the word "sine" comes from Latin sinus meaning "curve": we speak of Marilyn Monroe as a "sinuous woman", for example. And "cosine" comes from Latin cosinus, co- (with, together) +sinus "curve" (Websters New Collegiate). The sine and cosine are close associates.
The pendulum is commonly used as the example of a repeating "cosinusoidal" motion (cf Cannon p. 171ff). Pull it to the right R, then let it go. The pendulum comes back to center C, swings to the left L, then back to center C:
A "full cycle" is the motion R, C, L, C. Apply numbers to the symbols R, C, L; choose R = +1, C = 0, L= -1. Now record the motion -- at one-second snap-shots -- of a really slow pendulum -- our pendulum takes 8 seconds to make its complete cycle . We see that our pendulum seems to "dwell" longer at the extremes L = -1 and R = +1, and move faster in the center C = 0. Our records, in fact, show the pendulum's positions to be as follows:
The waveform in the first picture is a cosine. In the picture of its reconstruction the reconstruced waveform is "almost a sine" -- if it were to start at zero it would be a sine (ignoring the wiggles riding on it). Its shift to the right repreents a delay and is called its phase shift; the "hold" and the "filter" are responsible for this.
Observe what we have just done: we have sampled the motion of the pendulum. And we will soon use these same numbers to extract the Discrete Fourier Transform from our snippet of waveform!
We say the pendulum's (and hence its cosine's) frequency is how long in seconds the pendulum requires to make one full cycle. Our slow pendulum takes 8 seconds to move in one full cycle, so we say that its frequency is 1/8 Hz (Hz = Hertz = cycles per second).
If we plot the times on an X axis and the pendulum's position on a Y axis and draw a smooth curve through the points, the cosine is just this smooth curve. A sine curve is of identical shape, just shifted right so that it starts at 0 rather than 1. [footnote: derivative of sine is cosine and vice versa; easy to see with difference equations]. If we were to put a felt-tip pen on the bottom of our pendulum and, at a steady rate, pull a piece of paper beneath the pendulum, the motion of the pen would trace out the cosine (or sine). The shapes of the two waves -- sine and cosine -- are identical; they just start at different values.
Sampling Window:
Only rarely is a signal sampled for a long period of time and then have a discrete Fourier Transform applied to it. Usually we do this for just an interesting piece of the waveform. If we are recording a crow's caw we just "snip" the "caw" and discard the uninteresting road noise and lawn-mower sounds. The time-duration of the "snippet" (or length of the snippet if we are looking at the waveform on our computer screen) is called "the window".
For more about what can go wrong with windows and what we do about it, see "What can go wrong" below.
Fundamental frequency, Harmonics, frequency components, amplitudes, :
Anyone who plays a musical instrument knows what an "octave" is: it is just the next lower or higher register. For example: middle C is the note C just below the treble staff, the first octave above middle C is the C on the staff. The next octave higher puts C above the staff. A higher octaves represents doubling frequency. A harmonic is similar, but it represents an integer multiple of (usually positive with 0 a special case i.e. 1, 2, 3, 4, ...), rather than a doubling of, a base frequency called "the fundamental:"
Another name for the harmonics is the frequency components. The harmonics/frequency components together with the fundamental make up the spectrum of the waveform.
As it turns out we will need to find both cosine and sine harmonics. Neither a collection of sine harmonics nor a collection of cosine harmonics is sufficient (adequate) to reconstruct our waveform -- we need both sets. Why? Because the cosine always starts from 1, if we encounter a wave that starts from 0 we will need the sine harmonics too. More likely than not we will need both sets.
The fundamental is fundamental
So just who or what determines "the fundamental"?
Hamming (p. 508) provides us with a wonderful analogy: think about our "snippet" of waveform as if it were wrapped around a cylinder with a circumference the same length as the snippet. [The following may be O.R. [?]: a perhaps even better analogy is an early precursor to the motion-picture, the Mutoscope -- a cylinder with sampling slits in it, around the inside of which a sequence of images is wrapped. The viewer cranks a handle and watchs the scene move. Problem is, the scene repeats every rotation. But this is exactly like Hamming's analogy.]
The discrete Fourier transform treats our waveform as if it were "a snippet" wrapped around in a cyclider that is spinning. It is the circumference of the cylinder -- or "(time-)duration" of the cylinder to make one full roation-cycle -- that determines the so-called "wavelength of the fundamental", or in time, the longest duration and lowest frequency that the transform can deliver back to us.
All the other frequencies that the transform delivers/produces will be integer multiples of this fundamental. Why would this be? An obscure answer is: the average value of the "area under the curve" of sine or cosine curve is 0. If we were to use a non-integer (0.5 cycles or 1.5 cycles) this would not be the case.
But rather than this obscure answer, what we are going to do is show firstly that a cosine fundamental can "pluck out" of a waveform a cosine of the same (fundamental) frequency, but not a sine. Secondly we will show that a cosine with double the frequency does not pluck out either a cosine nor a cosine of the fundamental frequency. This will be true for every harmonic, not just the first with double the frequency.
We will "transform" our sampled pendulum's cosine waveform with itself, and see what we get. What we do is write down one cycle of our pendulum -- sampled at the 8 1-second intervals -- and multiply each sample by itself. We add up the numbers, and divide by 4 to get what is called "(double) the weighted average".
The sum of the individual products is 4 and the average is 1.
We will "transform" our pendulum's motion with a sine pendulum's motion -- same slow speed -- and see what we get. We add up the numbers, and divide by 4 to get "the weighted average".
time in seconds.........: { 0,.... 1, ...2,... 3,... 4,... 5,....6,....7 } position of cosine pendulum..: { +1.0, +0.7, +0.0, -0.7, -1.0, -0.7, +0.0, +0.7 } position of sine pendulum....: { +0.0, +0.7, +1.0, +0.7, +0.0, -0.7, -1.0, -0.7, } products.....................: { +0.0, +0.5, +0.0, -0.5, +0.0, +0.5, +0.0, -0.5 } running sum of products......: { +0.0, +0.5, +0.5, +0.0, +0.0, +0.5, +0.5, +0.0 } The sum of the products is 0 and the average is 0.
We will "transform" our pendulum's motion with a faster pendulum's motion -- three as fast -- and see what we get. What we do is put down three cycles of our fast pendulum -- sampled at the same 8 1-second intervals -- and multiply each slow sample by the fast sample. We add up the numbers, and divide by 4 to get "the weighted average".
The sum of the products is 0 and the average is 0.
This time we multiply our slow pendulum's motion by by the three-times-as-fast sine waveform:
The sum of the products is 0 and their average is 0.
So how many integer-multiples of this sort can we get? Unfortunately, not as many as we'd like: Just the number of samples in fundamental's cycle divided by 2 -- in other words 4 for the cosine collection and 4 for the sine collection. Why is this? The answer is not so simple. See Nyquist Rate below.
Our conclusions from the above examples:
1. Our sampled waveform: : { 1, 1, 1, 1, 0, 0, 0, 0 }
2. The fundamental frequency is 1/8 seconds
3. The integer sample size is 8
4. The various integer multiples of the fundamental will be
5. The various integer frequencies of the sines and cosines will be
6. The sampled cosine fundamental and its harmonics:
7. The sampled sine fundamental and its harmonics:
To create our transform we simply multiply the counterparts (thus we have to do this 8 times, and we see that 2 of these yield 0 so they are trivial). here is an example of n=3 for the numbers of the sampled sine:
We add these and divide by 4 to get 0.25. This is the amplitude (height, value) of this "component" n=3. If one were to write cosine equation for this harmonic "wave" it would be:
We can get a better feeling of what is going on if we go to larger sample sizes. Our original waveform shown here is the following:
{ -0.5, -0.5, -0.5, 1, 1, 1, -1, -1, -1, -1, -1, 0.5, 0.5, 0.5, 0.5, 0.5 }
The graphing together of sine and cosine amplitudes is somewhat difficult to look at, so we will plot the information in a different way -- in the more common presentation of "a spectrum". The "spectrum" has facinating quality of being position invariant -- unlike the varying sine-cosine harmonics that change depending on where we "start" our waveform on the cylinder, the spectrum remains the same.
A spectrum does not show the amplitudes of the individual sines and cosines, but rather it combines the two into a single number for each harmonic (for more about the trigonometry behind this see Why it Works):
The square root is usually taken in the positive and represents a directionless quantity: (the length of a line but not its direction). This composite amplitude V, however, contains only has half the information. The rest is contained in "the phase" φ:
An "arc-tangent" is "the angle whose tangent is ...". On an Excel spreadsheet the ATAN function "appears" in the form of radians, where a "radian" is defined as 2π of these puppies in one circle. If we want to convert "radians" to "degrees" (360 degrees in a circle), a radian is 360 degrees/(2π) = 57.29577951 degrees, a convenient-and-easy to remember number.
To do a reconstruction, then, either both the composite amplitudes Vn and the phases φn are required for each component n, or both the sines' and cosines' amplitudes an and bn are required for each component. Nothing comes for free.
Our original waveform shown here is the following, the same as appears on the cylinder above:
The original waveform is shown in black. Just below the X-axis (labelled 0.00) is the "d.c." (abbreviation for "Direct Current") or steady-state value that comes from the 0th cosine component. Our reconstruction sums this d.c. value and all the other sine and cosine terms for each component, then sums up the resulting waves into a partial reconstruction. Not all the partial-reconstruction sums are shown because the picture gets cluttered.
The odd wiggles on the final reconstruction (bold red line) is typical. See more at Gibb's phenomenon below.
---A WORK IN PROGRESS--
Nyquist frequency: the maximum frequency in our "transform" = 1/2 the sampling frequency
Observe an interesting fact: when m=4, the sine is 0 all the way down the column, but when n=4, the cosine alternates:
These numbers represent the cosine's maximum and minimum values. If our "waveform" contains a cosine or sine that is "faster" than this, our sampling will make an error. This is related to what is called the Nyquist frequency. Our maximum sampling frequency should be less than or equal to (at worst) one-half of our sample rate. Aliasing occurs when we don't to this problem (for more see Aliasing below).
Sometimes (for sound purposes) folks plot these as a 'sonogram' where frequency is on the Y axis, time is on the X-axis, and intensity is the color or the "brilliance" of a point in the plane.
Repeatitive numbers in the sine and cosine samples
Observe that only the following numbers appeared in the 8-sample transform when we sample the sines and cosines:
This lucky find means that if we are doing this with a microcontroller we don't have to compute vast numbers of sines and cosines, we can just store the necessary numbers in a table. It happens because our sines and cosines are periodic and related to one another by integers. This observation will be of use if we want to proceed to a "fast Fourier Transform" (see below).
But, we do have to be clever in our choice of sample size. An example (not shown) of 10 samples creates 5 harmonics for the sine and five for the cosine. But the numbers are not so fortunate and there are lots more of them. If you were to work this out on a spread-sheet you would observe the numbers below:
Hamming seems fond of the number "12" (cf Hamming p. 543ff).
Prelude to the 'Fast Fourier Transform' The "FFT" is just a computing trick that depends on the fact noted above: that all the values of sine and cosines in the table are similar (cf. Chapter 33 "The Fast Fourier Transform" in Hamming, p. 539ff). The FFT has become a highly-developed art since Hamming. See Discrete cosine transform for nice examples.
---A WORK IN PROGRESS--
Hamming describes the many issues that can arise with the discrete Fourier Transform:
The origin of "beat frequencies" (in sound recordings: unexpected groans, whistles, whines, throbbing pulsations; in photos: weird Moire patterns) and their role in aliasing can be found in some trigonometric identities that show what happens when we multiply sines by sines, or cosines by cosines. (We can easily derive these identities if we express sine and cosine in their complex (i.e. e^ix) forms). We use the following:
From the above we simply derive the equations below. These show that if we multiply two sines or cosines, we get the sum frequency (x+y) and the difference frequency (x - y) and there is nothing we can do about it:
Because any Fourier transform multiplies cos x*cosy and sin x*sin y we will always get "beats". Whether or not the "beats" have any affect on what we are doing depends on how cautious we are with respect to our sample rate and our waveform that we are sampling.
Suppose we sample our wave at 4 per second (t occuring at an interval of 0.125 second), a sine waveform with a frequency of 6 per second. In other words, we have not sampled at a high enough frquency. Sampling can be thought of as multiplying our 6 Hz waveform by "the sampler" occurring at 4 per second. Let's use the simplest sampler we can: a sinewave "lifted up" so that its peak occurs at 1 and its minimum at zero:
Our sampling thus multiplies our 6 Hz sinewave by the "sampler"
And we have seen that this process of multiplication introduces "beats". The right-most term yields the "beats" at 2 and 10 Hz:
So our sampling has produced the following new waveform:
Observe that we have just picked up 2 Hz and 10 Hz in addition to the original 6 Hz.
Now, what happens when we do our transform? We create more beats! We can see this if we use the 4 Hz sine or cosine of the transform:
The first term creates 2 and 10, the second term creates 2 and 6, and the third term creates 6 and 14!
The process of sampling and processing with discrete Fourier transforms is like making an infinitely long paper doll: we fold our infinitely-long paper, cut one shape and unfold it to reveal the repeating pattern, ad infinitum (cf drawing on pag 514 of Hamming, and his explanation p.513). If we cut too far our shape "overlaps" into the shapes beside it. This is called "folding".
Harmonic 6 is equivalent to 2. 6 has "folded back" to become 2, and the "2" shouldn't be there. 10 also folds back to 2.
Note that we could have done this in reverse order: multiplied, in the continuous domain, our waveform by the sine, then sampled it. The results would be the same.
The aperture (cf Carlson p. 285, Bracewell, p. 276ff) is the time e.g. 0.001 second for a slow sampler) during which a "snap-shot" of the waveform is taken and either held constant (while an A-to-D conversion occurs, in the above audio example) or allowed to change while either the sample or (if no "hold") the conversion is occurring). Thus we see two sources of error during the instant the sample is taken: (i) the waveform may be changing during "the sample", (ii) an A-to-D error may occur. But there is a third intrinsic error which is related to "windows".
As mentioned above, the fact that we have introduced a "window "of finite time-duration during which we take our samples itself introduces more "junk.
Our analogy points to a source of problems: we may "cut" our waveform at an inopportune place and make the splice to another inopportune place, and thereby create a "discontinuity." And such discontinuities create something called 'the Gibbs phenomenon' (see more below).
[need reference here e.g. Sound Forge uses various methods:] What to do about this? Engineers have devised ways of "smoothing" the signal -- multiplying the window by a "weighting factor" so that the discontinuity is not so odious. [Blackmun, Hamming, etc. windows]
>(cf Hamming p. 532ff, Bracewell p. 209). [Is this Hamming's "leakage?]
Some examples produce tidy results -- the reverse DFT reproduces its waveform perfectly. But if we had picked the following waveform we would not be able to reproduce it exactly. In the little picture, the original is in blue and the red is the reproduced. this problem is either caused by (i) Gibbs phonomenon or by (ii) too-high frequency content for the sample rate:
It appears to have "ripples" in the waveform that we cannot get rid of [etc: is this Gibbs or is this the effect of aliasing -- too much high-freq crap in the original waveform?]
---A WORK IN PROGRESS--
> In the final analysis, can we can convince ourselves that a waveform of a given length/duration can be expressed as "the finite sum of a integral sines and cosines with various amplitudes"?
> An important observation: weighted average: If we plot one cycle of our fundamental sine and consider the area under the curve of "the upper half" (above the X-axis) to be positive area, and the "lower half" to be negative, then we see that the area below cancels out the area above. This is also true for the cosine, since they have the same shape.
This happens always when there are an integral number of cycles of the sine or cosine, but never when the number of cycles is not integral.
If we multiply our waveform by our "reference" sine or cosine, the total positive- and negative- areas under the resulting curve (the curve that represents the product of our waveform x sine, or waveform * cosine) may not be (and probably won't be) 0. The "residual" area gives us a clue about how much of that particular "component/harmonic" is "in the waveform".
>Why is "the component" that results from the transform just the simple average of the area? If we were to plot the "residual" area as a little rectangle, it will have either a positive-area or a negative-area) stretched over the extent of our "snippet window" = "length/duration of fundamental". Thus our rectangle's length is the "length" of the fundamental and its "height" is the area divided by the length. [Aren't things are off by a factor of 2? Why?]
> Then the notion of "plucking out" the amplitudes by use of the "unit harmonics" may be straight-forward (if you're willing to do some algebra). It is the assertion that "a finite waveform can be expressed as the finite sum...." that is hard to swallow.
To pluck out third cosine harmonic, multiply W(t) by unit cosine 1*sin2Π*3*t/8. This generates a slew of harmonics, in essence doubling the number of terms on the right:
> concept #1: to locate a point on the plane we need two values, its "X-coordinate" and the "Y-coordinate". This is, ultimately, where the need for both the sine and the cosine waveforms comes from. If our X- and Y-axes are at right angles, we say that they are "orthogonal", a word used interchangeably with 'perpendicular':
> concept #2: the ultimate value of a*sine X + b*cos Y is "Z" in the third dimension. If we are to keep the cylinder analogy we really have to think about this in 3-D. The waveform is printed on the treads of a tire, the tire is mounted on a wheel on an axle that spins at the same rate as the fundamental sine and cosine. The 1st harmonic spins twice as fast. Etc.
> concept #3 requires a bit of trigonometry: the Pythagorean theorem. Given that our "X" and "Y-axes" are perpendicular/orthogonal, and the values for "X" and "Y" are the coordinates (location) of the point in the plane, the diagonal V-- measured from the origin to the point -- has the following length:
An example: On a stairs the "run" is the length of the "tread" and the rise is the (perpendicular) height of the step. The diagonal is, well ... the diagonal.
If this length-of-line V is given together with its "direction" we call it a "a vector". But how do we specify its "direction?"
> concept #4 requires a bit of trigonometry. A common way of describing a vector's "direction" (remember: a "vector" is the line drawn from the origin to a point on our waveform) is to give the angle, measured counter-clockwise, that it makes withthe X-axis. If our vector-line lies flat on the X-axis and points to the right, it has an angle of 0° (always described with respect to the X-axis). Straight up it has an angle of 90, straight left it has an angle of 270, straight down it has an angle of 360.
> concept #5 requires a bit of trigonometry. The definition of "the cosine of an angle" is "run" divided by the diagonal. the definition of "the sine of an angle" is the "rise" divided by the diagonal. The two concepts can be compressed into a third definition called "the tangent": "rise"/"run".
Basis vectors:
What is the angle between the X-axis and Y-axis? We might start this way: we draw a line and call it "the X-axis". Somewhere on it we put a point; this we call "the origin". Then off the line somewhere we put a point, say to the upper right an inch or so. If we were to draw a line from the origin through this point it would form an angle. Now move the point directly above the origin so that the X-axis and the line are perpendicular (orthogonal). The angle of our perpendicular line is 90 degrees. What is its cosine? 0.
> This is the mathematical definition of orthogonal: cosine between two lines-as-vectors is 0.
>[So what is the point? Why does the reader want to care about this?: that for any point in an X-Y plane we can use two orthogonal vectors to locate it? these are "the basis vectors". In the "X-Y" plane we need only two: the (unit) X-leg and Y-leg of the (unit) triangle; any point in the plane can be located with the help of these two: 3*X + 4*Y locates a point at x=3, y=4. The length of "the vector" (measured from origin to the point) is sqrt(3^2 + 4^2) = 5, the angle is arctan(4/3) = 53 degrees. Given these two values L=5, angle=53 degrees, how do we locate our point? (x=5*cos(53°), Y=5*sin(53°)). But why not skip the X, Y step and go to a unit sine and unit cosine as a basis? How and why do "the harmonics" come into this?
> Here's an important observation: the product of two "vectors", i.e. a sine as "a vector" and a cosine as "a vector" times our waveform which is a bunch of vectors:
What will be the sum of these two points? the simplest way would be to just add everything together in a mish-mash. But We would loos our vector. Vectors add "component ax" to component cx, "component by to component dy". The resulting vectors (a+c)x and (b+d)y are considered 'independent' and are not intermingled:
What will the product of these two points, a product that we need for our transform? We will just do our multiplication in the "normal way" -- term by term and see what it looks like:
We would expect that, like most things multiplicative, x*x = x, ditto for y*y = y
But what about y*x and x*y? Because they are at right angles to one another, both products are 0. [and why is that?]
Given that we accept the sentence above, our product leaves us with something simple: we see that we haven't "gained" any extra terms, so if we needed to we could do this again, and again (we don't need to):
>[We have to move, in an intuitive manner, from a point to a sequence of points that trace out a curve and show without handwaving . Each point can be described by a single vector (length) and an angle with respect to the X-axis, or as two perpendicular vectors. for a circle we can see this easily, and the sines and cosines for the fundamental -- the circumference of the unit circle -- . But just how do the harmonics come into this? The Harmonics spin around the Z axis-as-axle twice as fast, three times as fast, four times as fast, etc.
>We have to show the reader how this stuff works. We have cylinders or disks spinning at the "fundamental rate" of 1 revolution per 8 seconds, twice as fast 2 revolutions per 8 seconds, three times as fast (3 revolutions per 8 seconds), 4 revolutions per 8 seconds.
Here, m and n are integers that will represent "the harmonics" as described below. They either positive or negative values. Usually they are just considered positive: For continuous sine and cosine wavesforms:
For discrete sine and cosine waveforms the following become summations over the number of samples S (e.g. S=8):
---A WORK IN PROGRESS--
wvbailey Wvbailey 18:50, 16 June 2006 (UTC)
The simplest non-trivial example is N = 2 .
This table shows (−1)jk.
... k=-1 k=0 k=1 k=2 ... ... ... ... ... ... ... ... j=-1 ... -1 +1 -1 +1 ... j=0 ... +1 +1 +1 +1 ... j=1 ... -1 +1 -1 +1 ... j=2 ... +1 +1 +1 +1 ... ... ... ... ... ... ... ...
The rows and columns of the table are periodic with period 2. So the following tiny table is sufficient.
k=0 k=1 j=0 +1 +1 j=1 +1 -1
A pair of real numbers x = (x0, x1) is transformed into a pair of numbers Fx = ((Fx)0, (Fx)1) defined by
This F is the discrete fourier transformation.
These special cases follow from the definition:
so does the proof that it is a linear transformation:
and the fact that the transformation is an involution
So, any periodic sequence, of period N = 2, can be written as a linear combination of powers of (−1). If the variable j is interpreted as a point of time, and xj is the corresponding sample of a signal, then the variable k is interpreted as a frequency, and (Fx)k is the corresponding amplitude. The amplitude (Fx)0, corresponding to the frequency k = 0, is called the DC amplitude, for Direct Current, and the maximum frequency, k = 1, is called the Nyquist frequency.
The next case to consider is N = 4 .
(This case is simpler than the case N = 3 because the square root of minus one, i, is logically prior to the primitive cube root of unity, (−1+i×31/2)/2. In both cases it is necessary to consider complex numbers.)
One possible generalization is:
However, this definition loses the involutary property.
The following alternative generalization:
where the asterisk * signifies the complex conjugate: (a+ib)* = a−ib, makes F an involutary and antilinear map.
The latter choice is logically preferable but not always chosen in the literature.
Note that this theory of fourier transform doesn't need the geometrical and analytical concepts of cos, sin, e, and π, which scare the beginner. It is pure algebra. Bo Jacoby 12:45, 16 June 2006 (UTC)
Can you cite a reference? I need the reference. I haven't seen any FT's done without a consideration of sines and cosines first. N.O.R. even if its good and to the point.
The idea of a non-harmonic "basis" would be okay but I believe the true FT is always with sines and cosines...correct me if I'm wrong.
(It would be interesting to see Fourier's original work and see exactly what he was up to).
If so, Somewhere these ugly dudes will have to creep in.
They are not that bad if you can see them. Before i launched into this I did consider a simpler case. The problem is we don't get to see "the harmonics". And it's no fun (and pointless) unless you can see the harmonics.
As you see I got some pretty nasty feedback when I started into my little effort. The folks sneered at the tables in general.
So I cut out another table completely. Really what we need is, together with the tables, a picture or two of a simple "waveform" fitted with sines and cosines, or the point values, or whatever. Together with the harmonics. I don't know enough about wiki's esoteric importing to be able to get them out of Excel.
Imaginary numbers = fear and loathing.
Matrices, forget it. "Orthogonality" will throw folks. So will "basis vectors" or anything like that. These concepts need to go way at the end (or just disappear as "a given", "proven in linear algebra"). Like I wrote, behind the fourier transform is 50 pages of dense linear algebra, enough to choke anybody but a determined math or engineering major. And that is just in the reals, not even including the complex domain.
Here's my goal: to write (some of) this for a high-school kid good in math. Like my 9th-grade nephew -- he was exposed to fractals in 8th grade, loved them. I showed him the wiki page and he loved it. I had some books that I loaned him, got him all excited. Ditto for my son when he was that age, he loved the idea of a picture that you travel through -- I found a program (referenced on that page). As a post-doc he's had to use sonograms and FTs in Sound Forge extensively in his work. He uses them as a tool, not as an esoteric math concept. But if he wanted to know more, why the f*** should he have to slog through a bunch of equations if someone can present the ideas in a kindler, gentler way? The trick is to find the way. Wvbailey 13:45, 16 June 2006 (UTC)
The primitive roots of unity are purely algebraic concepts. Fourier (to the best of my knowledge) didn't use complex numbers, so he had to rely on the more complicated analytical properties of the real-valued trigonometric functions. The immensely powerful concept of involution is not used for the fourier transforms in the article, and the readers suffer. Bo Jacoby 15:54, 19 June 2006 (UTC)
The unsatisfactory section of the article could be replaced by this.
The eigenvalues of the involutary discrete fourier transform, F, are +1 and −1, because F satisfies the equation F2 = 1 and so any eigenvalue k satisfies k2 = 1.
The operators P = 2−1(1+F) and Q = 2−1(1−F) are idempotent :
If x is any vector, then Px is a eigenvector with eigenvalue +1, and Qx is a eigenvector with eigenvalue −1, because
Any vector x is a sum of an eigenvector with eigenvalue +1 and an eigenvector with eigenvalue −1:
because
and the involutary fourier transform of this vector is
because
Bo Jacoby 15:03, 19 June 2006 (UTC)
As the eigenvalue-multiplicities for λ=+i and λ=−i must be equal, the table in the article not correct. Bo Jacoby 10:52, 21 June 2006 (UTC)
size N | λ = +1 | λ = −1 | λ = +i | λ = −i |
---|---|---|---|---|
4m | m + 1 | m | m | m − 1 |
4m + 1 | m + 1 | m | m | m |
4m + 2 | m + 1 | m + 1 | m | m |
4m + 3 | m + 1 | m + 1 | m + 1 | m |
I took it out after finding DFT linked from the aliasing page. Since the DFT has no relationship to continuous-time signals or aliasing, I took it out. Only afterward did I check here and see the long-running dispute about it between Bob and Stephen. I must say I agree with Bob. Furthermore, the concept of aliasing is very well described in other articles where it is relevant. See aliasing, Nyquist–Shannon sampling theorem, Nyquist–Shannon interpolation formula, Nyquist rate, Nyquist frequency, etc. I'd be interesting in knowing if any textbooks discuss aliasing with respect to the DFT. Dicklyon 06:10, 23 June 2006 (UTC)
This is my first major Wikipedia submission; please bear with me. I have written a quick reference to how to use the DFT in MATLAB which I would like to offer for inclusion. What say you all? -- Cxw 19:33, 18 July 2006 (UTC)
Dear Wikipedians, "I would lean against including it" is much gentler than saying "Shut up". But where I come from, the proper etiquette is to not only be gentle in telling someone that something is off-topic here, but also to tell them where that something is on-topic (or at least more on-topic than it is here).
In this particular case, I suspect http://en.wikibooks.org/wiki/MATLAB_Programming would be a good place for that quick reference.
-- DavidCary -- 65.70.89.241 15:36, 8 August 2006 (UTC)
We are told that
and
are different forms of the same function. They are not. Different functions must have different names. Bo Jacoby 11:20, 9 August 2006 (UTC)
I think the phrase "different forms" was intended in the sense of "different functional forms" (e.g. a*sin(x) + b*x has a different functional form than a*x^2 + b) rather than "different forms of the same function" which was obviously not meant here. I edited it slightly to emphasize this difference, although perhaps more substantial rephrasing would clarify things further. Definitely, a more complete discussion should go in trigonometric interpolation polynomial but I think there's a good argument for putting at least the minimal-slope interpolations here as a summary, since those interpolation polynomials, and their non-uniqueness, are critical for a lot of applications of the DFT (e.g. for spectral methods). —Steven G. Johnson 04:44, 11 August 2006 (UTC)
'Sinusoid' is a new word in the context. It might be confusing to some readers. I changed it to 'wave' in accordance with the explanation given in the article sinusoid but it was changed back. The terms in the trigonometric polynomial as written are exponentials, not explicite trigonometrics. Perhaps this is the place to show a real-function expression of trigonometric polynomials involving the sine and cosine functions explicitely? If the reader has seen such an expression in some book it is nice if he recognizes it in wikipedia so that he doesn't think that the article here is about something quite different. Bo Jacoby 06:35, 16 August 2006 (UTC)
The sinusoid is complex, not the frequency. You can do better! Bo Jacoby 08:06, 16 August 2006 (UTC)
"In contrast, the most obvious trigonometric interpolation polynomial is the one in which the frequencies range from 0 to N − 1 (instead of roughly − N / 2 to + N / 2 as above), similar to the inverse DFT formula. This interpolation does not minimize the slope, and is not generally real-valued for real xn; its use is a common mistake."
Dear Steven, the fact that you made this mistake yourself does not make it common. You do not have to document your mistakes in WP. :-) Bo Jacoby 06:44, 16 August 2006 (UTC)
I am talking about that the history of this subsection is that you first mentioned the frequency range from 0 to N−1 rather than from −(2·N−1+(−1)N) / 4 to (2·N−3−(−1)N) / 4. Accept reader's comments constructively, especially as you are not letting anybody but yourself edit 'your' article. The subsection does not explain what you explained here. Errors made by students may be caused by errors in teaching, so your students make a biased sample. Still, WP is not the place for documenting errors, common or not. Bo Jacoby 10:19, 17 August 2006 (UTC)
As for WP not being the place for "documenting errors," I don't think you're being reasonable. From a pedagogical perspective it can be almost as valuable to explain what not to do, if there is a common pitfall, as to explain what to do. Moreover, the non-uniqueness of trigonometric interpolation is a fundamental concept that needs to be understood in order to properly apply the DFT/DTFT for everything from PDEs to the sampling theorem. What better way to explain it than to briefly mention an example of an inequivalent interpolation? —Steven G. Johnson
Hi Steven. I made my point. A pitfall is avoided by building a road that circumvents the pitfall, rather than by placing a warning sign at the end of the road that leads to the pitfall. You might introduce the balanced frequency range early, rather than to use an unbalanced frequency range for theoretical work, thus leading the reader to use it also for interpolation, giving bad results. If I make an edit, will you promise to leave it unremoved for a week? You do have a long history of removing my WP contributions, you remember. Be nice to people and they will be nice to you. Show respect, and respect will be shown to you. I am your mirror, my friend. Bo Jacoby 09:24, 18 August 2006 (UTC)
I am referring to correcting your errors such as including n=0 in the definition of the discrete fourier transform. I stopped editing because of your vandalism, not because you are right. Can you see a constructive aspect of my comment or are you just permanently offended by my implying that you are not perfect? Bo Jacoby 14:41, 20 August 2006 (UTC)
This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 |
I would like to do a spectral analasys, but I have NC on how to interpret the results I get after the transformation. Can anyone explain it please? -- Marco 17:54, 18 February 2006 (UTC)
I can't see the character ℱ, even when I select Unicode encoding from the "view" menu of explorer (unless it's supposed to be an empty box). - rs2 21:25, 24 Mar 2004 (UTC)
This is wrong. The discrete fourier transform is given by
The inverse DFT is given by
In both equations, N is the total number of sampling points.
Hello Steven - about the reason for the 1 and 1/n convention - I see your point that it avoids a multiplication for the DFT but I don't think that an actual algorithm would put the 1/n inside the summation and multiply all n times. It would just perform the summation and then multiply by 1/n. Shouldn't we say that its a combination of avoiding a multiplication for the DFT, AND not having to spend the time calculating the square root? Paul Reiser 18:58, 25 Jan 2005 (UTC)
Ok, I get it about the n times thing. I think we are coming at this thing from two different directions. Your idea of "best" normalization seems to be from an algorithmic point of view, mine is from a mathematical point of view. Casting the DFT as a unitary operator is absolutely the best thing to do from my point of view. All of physics is based on things that are invariant under some transformation or other. When the DFT is a unitary transformation, the dot product, the angle between two vectors, the length of a vector, all are preserved. Viewing the DFT as a unitary operator is like saying it is a simple rigid rotation in space. With the 1,1/n normalization, it is like saying its a rigid rotation plus converting from meters to inches. Its klugy from a mathematical point of view. Ok, thats my rant. I agree that using the η symbols is not the best thing for a new reader to see, and we have to come to a compromise here. How about we do it in 1,1/n normalization, and I put in a section about the unitary normalization and how neat it is. I was about to say I needed to correct some things, but I see you are editing the page as I am writing this so I will check it tomorrow. Paul Reiser 02:51, 26 Jan 2005 (UTC)
Hello Steven - I put the unitary material into one section, I think it works, but I took the matrix out of the orthogonality section. I'm not sure if you thought it was serving a purpose there, I couldn't see one, but I did see a purpose for the unitary section, in pointing out that it is a unitary matrix (with the proper normalization). Paul Reiser 11:58, 27 Jan 2005 (UTC)
Should this article be merged with discrete-time Fourier transform? Michael Hardy 01:34, 2 Jun 2005 (UTC)
I have an online book about the DFT that is aimed at the beginning undergraduate level: Mathematics of the Discrete Fourier Transform ( http://ccrma.stanford.edu/~jos/mdft/) I am looking into splitting out some of the material into articles for the Wikipedia. However, since there is already a fine DFT article at the Wikipedia, I would merely recommend the book as an external reference, especially for "beginners". -- Julius
Also, it would be nice to have pointers to "live" Fourier transform software, perhaps:
... is there a good place on Wikipedia or Wikibooks to put public-domain source code?
Hi StevenJ. You reverted my changes because you liked your own better. Well, I don't. Shall we discuss the matter and collaborate to improve instead of reverting each others changes ?
Hi Steven. The article is terrible: confusing, inconsistent, incomprehensible and far too long. Even if it is not mathematically wrong to change notations and definitions in the middle of an article, it is no good to the reader. I'd like very much to help in cleaning it up, but when you just revoke everything I do, you cannot be helped. I'm really sorry. Bo Jacoby 07:29, 29 September 2005 (UTC)
Thank you for your suggestion, PAR. I'll pick out one particular correction. It is certainly not the biggest in my mind, for that would be the union of all the changes that I have in mind, but it is the first one that I stumble on while reading. It was stated that the word 'sequence' would be used in the meaning of 'vector'. Then the reader could have the burden to remember this and translate 'sequence' into 'vector' while reading. I think this suggests the simple edit of changing 'sequence' to 'vector', taking the burden from the shoulders of the reader. Let me know if anyone disagrees. Bo Jacoby 07:55, 30 September 2005 (UTC)
Bo - Before I revert some of your edits, let me explain myself. A sequence is an ordered set of numbers, and that's about it. A vector is a mathematical object which has associated operators etc. and by a logical process it can be deduced that if you define a set of basis vectors (a coordinate system), you can represent a vector in terms of this basis set by a sequence. The sequence is not the vector, at least from a mathematicians or a physicists point of view. It is from a computer programmers point of view, I think, but this is a mathematical article. That means the statement:
is not correct, "vector" should read "sequence". There is no such thing as a "vector of complex numbers", only a sequence of complex numbers that may or may not represent a vector, depending on whether a coordinate system and all the vector operators have been defined. The bottom line is that the DFT operates on sequences. It is often very helpful (and interesting) to assume that the sequences are representative of vectors. The DFT then can be thought of as a linear vector operator, etc. etc. The article is a bit sloppy in this regard and needs to be fixed. PAR 10:38, 30 September 2005 (UTC)
I agree, that distinction should be made more clear. However, I still say that the DFT fundamentally operates on sequences which may or may not be sequences of vector components. I don't need to know whether a sequence of complex numbers represents a vector in order to perform a DFT on that sequence. A sequence of complex numbers is not necessarily PAR 14:38, 30 September 2005 (UTC)
Ok, I see your point, once you have the transform, you've implicitly defined the operators that make the sequence a vector space. It still grates my sensibilities, I mean there are so many properties of the DFT that aren't of a vector nature, like the shift property. Should we be using "vector" in this instance? I don't think so. Should we only use vector when its a property of a vector space or some higher-ordered space (eg metric) and use sequence otherwise? The previous wording mixed it up, but was there a method to it? PAR 21:08, 30 September 2005 (UTC)
Ok, see your point. Its between you and Bo, then, but if I have to break a tie, I would say the old way was good, except a little longer note than "sequence and vector are used interchangeably" would be needed. PAR 14:27, 1 October 2005 (UTC)
I agree with Steven that the discrete fourier transform operations are vector operations. Any finite dimensional vector space over the field of complex numbers can be subject to the discrete fourier transform by chosing a basis, so PAR's feeling that the discrete fourier transform applies to sequencies rather that to abstract vectors is incorrect. Though I generally agree with Orwell about synonyms, the connection between concepts and words is more precise in mathematics than in everyday language. I agree with Steven that one concept is logically sufficient, but we disagree about using two words. To me using two words for one mathematical concept is an unnecessary complication, and this very discussion confirms that it does introduce misunderstanding. Bo Jacoby 08:14, 3 October 2005 (UTC)
A second suggestion. Why not simply write: and instead of: if then and ? The f is unnecessary. Bo Jacoby 09:02, 3 October 2005 (UTC)
Different readers look differently on things. I just see the f as a useless complication which the author should have eliminated himself instead of leaving it to the reader. Bo Jacoby 09:27, 4 October 2005 (UTC)
This section introduces a 4th notation for the fourier transform : The primed index: . Why not reuse one of the 3: , , . Further cleanup may reduce the number even more, hopefully to one. Bo Jacoby 09:25, 3 October 2005 (UTC)
Any linear bijection defines a change of coordinate system. That is an important point. It should be explained somewhere in WP, but not necessarily here. Bo Jacoby 09:39, 4 October 2005 (UTC)
Says: "The only important thing is that the DFT and IDFT have opposite-sign exponents, and that the product of their normalization factors be 1/n." The words "The only important thing" indicate that only one thing is important. The explanation gives two things. It is depressing to the reader to accept the fact that the author has difficulties in counting to two.
The opposite-sign exponent thing is not important, because the involutary DFT has DFT=IDFT, with equal exponents. Bo Jacoby 11:52, 3 October 2005 (UTC)
Consider the important special case of a sequence of real numbers x being transformed according to the formula How is this formula generalized to a sequence of complex numbers x ? There are two options : and Both formulae generalize the real case. They are not that different. The lazy mathematician choses the first one because then he dosn't need to modify the formula. The careful mathematician is guided by algebraic simplicity: Because the second one is involutary and the first one is not, the second one must be chosen and the first one sacrificed on the altar of Occam. PS. Note that I resisted the temptation to write :-) Bo Jacoby 08:42, 4 October 2005 (UTC)
"Early muddled thinking being carved in stone" it is. I love your poetry! The better generalization of the concept of a linear operator on a real vector space is that of an antilinear operator on a complex vector space. The antilinearity gives precisely what you need. (The name 'antilinear' is ill chosen, however, because it seems to imply that it is the opposite of linear, which it is not.) Bo Jacoby 13:28, 4 October 2005 (UTC)
Steven, after studying No original research I think you are completely wrong. I quote: Research that consists of collecting and organizing information from existing primary and/or secondary sources is strongly encouraged... "No original research" does not mean that experts on a specific topic cannot contribute to Wikipedia. Indeed, Wikipedia welcomes experts and academics. This means that a new calculation or a new notation or an alternative definition is not considered 'original research' in this context. It does not rely on information which is inaccessible to you or to anybody else. I am very flattered that you consider the involutary fourier transform to be original research. If I claim that I have made an invention, I expect everybody to object against it saying that it has been done before, or that it is trivial, so I should not consider myself an original scientist. Now the situation is up-side down. I personally don't believe that the involutary fourier transform is original research on my part. I consider it fairly trivial. I merely point out a minor error in one of your definitions of the fourier transform: one missing asterisk. It can easily be corrected. It is no big deal. I don't consider this to be original research. But you do ! Thank you very much, I'm honored and pleased. Bo Jacoby 08:07, 5 October 2005 (UTC)
PAR, what you need is expanding the expression T(ax+by). In the real case it is aT(x)+bT(y). In the complex case it can be either aT(x)+bT(y) or a*T(x)+b*T(y). In both cases T(ax+by) is evaluated, and that is what is needed. Bo Jacoby 08:07, 5 October 2005 (UTC)
The introduction should give a short answer to the short question: "What is the discrete fourier transform?". Smalltalk should be avoided here. Using the involutary DFT as the definition will do this, and also save the The Plancherel theorem from being mentioned twice in the article. Bo Jacoby 11:52, 3 October 2005 (UTC)
If your programmer wants to spare his computer from computing the square root, by all means, let him code a fast fourier transform subroutine called SQRT_FFT computing √N*DFT(X). It is no excuse for the mathematician to make non-unitarian or non-involutarian definitions. The unitarity and involutarity is appealing to every user, who neither wants to remember two versions of the Plancherel theorem, nor to bother about the difference between DFT and IDFT. Bo Jacoby 12:57, 4 October 2005 (UTC)
Actually I do have FFT-experience. I completely agree on your PS that the time for taking the square root is epsilon. But the time for the 2N real multiplications is neglectible too because the inner loop of the FFT requires Nlog(N)/log(2) complex multiplications, so this inner loop is more timecomsuming when N is a large number. When N is not a large number everything is fast, so nothing matters. Of cause you know all that. The convolution theorem asserts that the transform of a convolution is the product of the transforms, so the convolution is the transform of the product of the transforms. Can that really be simplified? Please show me. I don't think that unitarity is the only convenient property. Involutarity is nice too, because it is timeconsuming to debug the error of having chosen the wrong one of IDFT and DFT. Not having this to worry about makes programming safer. Bo Jacoby 08:39, 5 October 2005 (UTC)
I was mistaken. Thank you for telling me. Bo Jacoby 11:54, 6 October 2005 (UTC)
Implement any variation of the discrete fourier transform to suit your needs of saving computer time, but stick to one definition and explain your subroutine in terms of that. Bo Jacoby 11:54, 6 October 2005 (UTC)
Yes. Here the symmetry is broken. The coefficients of the fourier series are integrals. Yet my point is the same as before: define one discrete fourier transform and express everything else in terms of that, instead of confusing the reader regarding the meaning of the word. My 'crusade' is for simplicity and clarity, and you are not my opponent in that respect. Bo Jacoby 11:54, 6 October 2005 (UTC)
My next suggestion for improvement of the article. Some people consider the discrete transform to be a special case of the continuous transform, when generalized to distributions like the dirac delta 'function'. I think it is better to consider the continuous transformations as limiting cases of the discrete transformation, because then the reader doesn't need to know about integration but can just consider a large value of n. Consider the ring of integers , the ideal of multipla of n , and the quotient ring . The vector space in question is The indexes can be represented by integers from 0 to n-1, or from 1 to n. The indexes can be represented by integers from -n to n-1. Substituting into gives the limit Bo Jacoby 12:04, 5 October 2005 (UTC)
For the continuous transform, choose the dimension to be an even square number: . Substituting
into
gives the limit
Note that does not appear in this expression for the unitary involutary continuous fourier transform. (The asterisk signifies complex conjugation). Bo Jacoby 12:46, 6 October 2005 (UTC)
1. In the context of discrete fourier transform it is interesting to compute a finite sum approximately by means of a known integral. That is uncomplicated. 2. In the context of integration theory, the integral is defined as a limit of a sequence of finite sums. That is where all the complication belong. 3. Regarding : You are not expected to change your mind, but the mathematicians following you may not feel the same way as you do. Today's nonstandard original reseach may be tomorrow's standard notation. When contempleting your life's net value to humanity you may count your battle against progress as a negative contribution, but while there is death, there is hope. 4. Surely the usual branch cut is redefined. That was no holy cow. is multivalued, and that cannot be helped in general. The usual branch cut leaves unpleasant and unnatural discontinuities. The conventional choice that is nonnegative real for nonnegative real z is natural when working with real numbers. The conventional choice that is utterly unimportant. It is not used in practice. Why write instead of 1 ? The notation is free to be redefined to something useful. The expression is repeated endlessly in technical and mathematical litterature, and a many readers get confused. Where did and and come from ? Because , then is a natural and useful convention. Bo Jacoby 11:27, 7 October 2005 (UTC)
to Steven. The discrete fourier transform of x(t)=1 is , (using Iverson bracket), while the continuous fourier transform of 1 requires a definitional extention of the concept of a function. The indicator function of the rationals, , does not appear as a limit of discrete functions. The complications of definition belong to the article Distribution (mathematics). The complications of integration theory belong to the article Lebesgue integration. No such complication belong to discrete fourier transform. Bo Jacoby 10:27, 10 October 2005 (UTC)
to PAR.
I should practice what I preach, so I redid the unitary section to get rid of the primed indices. The problem is, I replaced it with primed vector symbols, and this is still not in conformity with previous use of capitals as transformed quantities. I want to emphasize with the notation as much as possible the idea of having a constant vector object, and its components are the only things that change, the DFT being simply a coordinate transformation. That was the idea of the primed coordinate indices rather than the primed vector symbols. However, to express the unitary stuff using capital letters would further obscure this idea. Is there any objection to changing the capital letters to primed letters in the rest of the article? PAR 15:56, 8 October 2005 (UTC)
For those who think of the Fourier transform as a time-frequency pair, yes, you want to emphasize the distinction. For those who think of it as a coordinate transformation between the momentum and space representations of a quantum wave function, you want to emphasize the lack of distinction. We should not favor the time-frequency POV. PAR 18:54, 8 October 2005 (UTC)
' Ok, I'm focusing on the concept and not the particular calculation technique. You know that the study of invariants under linear transformations is fundamental in physics. Also, you know I agree we don't need any unsual notation. But Parsevals and Plancherel's theorems are just so much mathematical gobbledygook to a beginner, and I am trying to convey an intuitive understanding of these theorems. Will you help me do that ? PAR 23:30, 8 October 2005 (UTC)
I separated the involutions from the tricks. Is the Hartley transformation really an involution ? Shouldn't the divisor '2' be under the square root sign ? Shouldn't the formula be found in the Discrete Hartley transform article ? Bo Jacoby 13:13, 13 October 2005 (UTC)
Dear friend. The Discrete Hartley transform says: Its main distinction from the DFT is that it transforms real inputs to real outputs, with no intrinsic involvement of complex numbers, in variance your statement: taking the real part is necessary to get the Hartley transform (even for the real inputs, the outputs of H(x) are complex). Please make up your mind. That the involution form is basically an aside; it does not merit its own section is your opinion, but not your decision. You know that the matter is controversial. Nobody prevents you from expressing your view based on your experience, nor should you prevent others from expressing their view based on their experience. My experience-based view is that this involution has the simpler algebraic properties. Please restore my edit and stop acting like a censor of the spanish inquisition. Bo Jacoby 08:56, 14 October 2005 (UTC)
You claimed that the notation is considered 'original research' and I didn't pursue it. The involutary fourier transform was accepted by you. Nobody called it 'original research' until now. I just changed the division into sections. I trusted PAR that you would not remove my edits, but you did. Spanish Inquisition refer to your actions, not to your person. You remove anything that you personally don't like, as herecy. This is getting ridiculous. I must give up my attempt to clean up your messy article on discrete fourier transform, because you are working against it. Yes, you may delete it entirely. You are on your own. Good bye. Bo Jacoby 11:26, 17 October 2005 (UTC)
What does this have to do with the DFT? Aliasing is caused by periodic sampling. We don't need a DFT to see that and are indistinguishable. -- Bob K 04:14, 13 December 2005 (UTC)
What purpose is served by the word finite in the sentence?: "and it means that in a finite discrete signal one cannot distinguish between frequencies j that differ by n". -- Bob K 04:14, 13 December 2005 (UTC)
What is the point of this?: "If one simply evaluates the DFT formula at then one finds that ," I.e., it appears that we are assuming the sequence is periodic in order to "prove" that the DFT thinks it is periodic. -- Bob K 04:14, 13 December 2005 (UTC)
Hi Bob, your basic issue seems to be that aliasing "has nothing to do with the DFT". Although aliasing can also be derived in other circumstances and in other ways, I can't agree with you entirely. Aliasing is still implicit in the definition of the DFT, and the implied periodicities are an intrinsic consideration in almost any application of the transform; it would be remiss not to mention it here.
I don't think you can avoid using the DFT definition in deriving the aliasing in this case, moreover, because the DFT definition defines what you mean by "samples" and "frequency" in this context. Because this corresponds to the usual definition for uniformly spaced samples, you don't even think about it, but it is there. For example, you could certainly apply the DFT to a sequence of numbers corresponding to non-uniformly spaced samples of some signal — the resulting DFT would not correspond to amplitudes of "frequencies" of the original signal in the usual sense, but would still have an aliasing property of a different sort. In general, the aliasing property can arise in contexts that have nothing to do with signals and sampling, e.g. many FFT algorithms exploit the implicit periodicity. Abstractly, there is also a close relation between the DFT and representation theory for the irreducible representations of the cyclic group (which would be a nice connection to mention in the article, although currently the representation theory articles in Wikipedia are painful to read).
You can quibble about the precise way in which the property is proved, I suppose, but any sufficiently short and clear proof seems fine to me. I'm not sure where you think the current article skips a step. —Steven G. Johnson 17:25, 13 December 2005 (UTC)
Would you be happy if the article stated something like, "More generally, aliasing phenomena also occur whenever one is analyzing the frequency components of a discrete signal (or discrete samples of a continuous signal), such as in the discrete-time Fourier transform." I have no problem with this. —Steven G. Johnson 23:14, 14 December 2005 (UTC)
I like the stacked version better than the unstacked version. IMO, that's the whole point of having a cool math editor. -- Bob K 21:11, 15 December 2005 (UTC)
A major point of having a cool math editor is versatility: you can make it do what you want it to. "Stacked" is appropriate in some cases, but seldom within superscripts. Bob K, did you think I was saying "stacked" should never be used? If so, go back and read what I wrote, since you missed it entirely. Michael Hardy 21:53, 15 December 2005 (UTC)
Stacked notation does not work well for inline formulae. Using stacked for display and unstacked for inline places an extra burden on the reader. For a fraction with both numerator and denominator complicated, stacked display can be a great help to clarity; here, the benefit seems small. Outside of TeX, k/n can be marked up to appear as k⁄n; but that's of little help in this case, partly because of Wikipedia's LaTeX limitations. Finally, stacking causes shrinking in an already-small superscript, cancelling some of the benefit of stacking in general. -- KSmrq T 01:57, 16 December 2005 (UTC)
Michael, in general I agree with you about stacking in superscripts. However, in this particular case, the stacking serves a useful purpose: to clearly separate the 2πi/n from the jk index product. If you don't do this, the ijk is somewhat confusing because all of the letters look similar. —Steven G. Johnson 04:31, 16 December 2005 (UTC)
hi guys, i've only recently started taking an interest in all of the Fourier/Laplace/Z transform pages and had no idea that there was such recent activity on this one.
i want to suggest something (that i am willing to do the grunt work) that i feel really strongly about. while the Laplace Transform, Fourier transform, Continuous Fourier transform, and Fourier series articles will have much broader interest and readership, i really believe that the discrete-time transforms, DTFT, DFT, Z, have much more narrow interest and constituency. while i do not claim that only electrical engineers doing signal processing are the only persons interested in or using these concepts, techniques, or algorithms, i do believe that it is principally people doing signal processing having such an interest. in that there is already a widely accepted notational convention for these discrete-time or discrete-frequency signals (that is and ) in the textbooks (i still consider Oppenheim and Schafer Discrete-Time Signal Processing to be the standard, but i s'pose we could argue about that) and lit, i really believe that we should adhere to that convention here. there are some of us agitating to revamp a bunch of EE electronics, control systems, communications systems, filtering, and general signal processing articles and we really should have notational consistency, and i really think that all of the discrete-time linear transforms (DTFT, DFT, Z) fall mostly in the EE and signal processing discipline.
may i change that notational convention from to and to (spending some considerable time) without someone reverting all of my effort away? FYI, there are two reasons i know of for why the EE discipline and lit has changed the notation. the main reason is that it is not uncommon to be processing a signal vector. in continuous time it looks like and, if sampled it would be . but, if we need to refer to the individual components of the signal vector, it would be and . do you see how it gets ugly if we have to say instead? also is harder to do by hand than . r b-j 02:59, 16 December 2005 (UTC)
The DFT is used by a wide audience, and so it is important to use as universal a notation as possible. If you use subscripts, everyone knows what you mean, but I think brackets are a bit too overloaded as far as notation goes. The Wikipedia articles aren't using a vector signal so that argument is moot. (I admit I don't have terribly strong feelings about this. I'll point out, however, that most of the literature on FFT algorithms uses subscripts as far as I can tell.) Moreover, you'll have to change literally dozens of Wikipedia articles that use the subscript notation. —Steven G. Johnson 04:38, 16 December 2005 (UTC)
I don't know if you realize, but is by definition identical to . It is purely an issue of notation, not of meaning. I think artices dealing with the DTFT, the DFT, and the ZT should use the bracketed notation rather than the subscript notation, for all of the reasons mentioned above. It does not need to create any confusion if you simply note, near the beginning of each article, that the article will be using the convention that
and then explain briefly the rationale (common convention in signal processing, indicative of vector/matrix notation, etc) for using this notation. It should not be a big deal for non-EE's to understand, and it would be a big help for EE's. Why are non-EE's so afraid of trying something different? There are good reasons why EE's have chosen these newer conventions, and they actually can help in other disciplines as well. It's helpful if you drop the not invented here paradigm. -- Metacomet 22:06, 16 December 2005 (UTC)
One other point: I believe that the bracketed notation is actually older than the subscript notation. Back in the old days, before WYSIWIG computers, people used to use typewriters or text-based computers. Yes, I know it is hard to believe, but these antique devices did not provide the capability of creating sub-scripts or super-scripts the way we can today in our modern word processing applications or with LaTeX. So the way that people used to indicate sub-scripts was to place the sub-scripted character inside of square brackets, as in, for a one-dimensional vector or even for a two-dimensional matrix.
It's only half-speculative, because I am pretty sure about it. And I preceded my comments with the words "I believe that...". -- Metacomet 00:25, 17 December 2005 (UTC)
I never said that subscripts and superscripts were not also used. Obviously, in handwriting or typesetting, or with an advanced enough typewriter, you can do subscripts. What I did say was that brackets were also used, when you had a typewriter that could not handle subscripts, and people had no trouble understanding what they meant. --
Metacomet 00:23, 17 December 2005 (UTC)
I am not suggesting that we should abandon WYSIWIG and go back to using square brackets in all situations. What I am saying, however, is that this convention existed long before EE's adopted it as notation for describing discrete-time signals, and I believe that it is a perfectly acceptable convention for vector and matrix notation. -- Metacomet 22:20, 16 December 2005 (UTC)
I agree 100 percent on your notation changes. We should not use i or j as index variables, since either one can represent the imaginary unit. -- Metacomet 00:15, 17 December 2005 (UTC)
As far as a mass conversion is concerned, I would say that we should only change articles where it makes sense to do so (not to state the obvious) – mainly articles related to discrete-time signals, discrete-time systems, discrete transforms, and image processing. -- Metacomet 00:15, 17 December 2005 (UTC)
Okay, I am sorry for getting in the middle of this discussion. I lost my head for a while. It is very difficult to get a consensus with such a diverse group of people coming from so many different points of view.
I just took another look at the article itself, and regardless of where you stand on the issue of brackets versus subscripts, it is really clear that the current notation in the article is really problematic. Again, I cannot speak for everyone, but it seems to me that no one should be happy with the current situation.
So if my assumption is correct, then maybe we shoud see if we can find at least some common ground.
I would make the following recommentaions:
Can we all agree on at least these initial steps to help move forward? Please comment.
-- Metacomet 03:28, 17 December 2005 (UTC)
Even though I agree with changing from subscript to brackets, I would recommend that you hold off on that idea for now. If we can get consensus on the few items I listed above, and the one item I listed below, then maybe we can at least accomplish something in the short run.
In the meantime, we can continue to discuss the subscripts versus brackets issue and maybe try to find a solution. -- Metacomet 03:46, 17 December 2005 (UTC)
Another recommendation:
-- Metacomet 03:44, 17 December 2005 (UTC)
I just wanted to give a few things a bit of a test drive. There is no harm done, things can always be reverted if they don't work out. I will leave it alone for now though. I am going to sleep now anyway. I will take a look at it tomorrow. Good luck.
In addition to the changes you just mentioned, I would replace j with m and leave k alone for now. Or use n and k if you want to do the extra work. -- Metacomet 04:45, 17 December 2005 (UTC)
Actually, I do not agree with putting the nk on top of the fraction. Believe it or not, I think it makes sense to put the i in front of the fraction, the 2 π on top of N for the fraction, and then the nk after the fraction. The reason is that you can attach in important interpretation to the 2 π/N as representing the discrete angular frequency increment (in radians per sample) that is very useful in understanding the DFT and more importantly, in implementing the frequency domain in a computer simulation. If you don't know what I mean, I will try to explain later. It's a bit complicated. -- Metacomet 04:49, 17 December 2005 (UTC)
Although we will likely never agree on all aspects of the change, it looks like we can probably agree on some set of changes to make. However, it is important to list them all here before making them, since if we are going to change several things it will be much easier to change them all at once than piecemeal. Second, there is no huge rush — this is an article that lots of people have contributed to, and it is reasonable to wait for comments for a t least a couple of days before instituting major, wholesale changes across dozens and dozens of articles. —Steven G. Johnson 06:24, 17 December 2005 (UTC)
Just as an idea of what I am talking about, I collected all the articles in Category:Digital signal processing including sub-categories and listed them on the above page. I also put a menu in listing notational changes, and we can check them off as needed. I assume the k,n,N changes are acceptable to everyone, so I listed that first. I didn't spend a lot of time alphabetizing or elaborating in case this idea doesn't fly. PAR 20:04, 17 December 2005 (UTC)
If nobody objects, I am going to start working on a very modest plan to start changing the notation. I am going to work on this article only and on only one change at a time. The plan is as follows:
1. n becomes N: Change all instances of the symbol n to the new symbol N to represent the length of the sequences in both the time and frequency domains.
2. k becomes n: Change all instances of the symbol k to the new symbol n to represent the index variable for the time domain sequence.
3. j becomes k: Change all instances of the symbol j to the new symbol k to represent the index variable for the frequency domain sequence.
I am going to make one change at a time, and I am not going to proceed with one step until I have completed the prior step.
We have been discussing these changes for many weeks, and from what I can see, nobody has objected to these three changes, and many have expressed support for them. So I believe there is a consensus at least on these changes. If there are any objections, please speak up now. I will start working very soon.
-- Metacomet 02:00, 27 December 2005 (UTC)
To make all three at once would require changing all of the notation in the whole article in one shot. I don't have time to do that, unless I can figure out a way to do it with a global search and replace algorithm. I could possibly do that in Microsoft Word, but I am not sure it will work. Otherwise, I need to make the changes as an evolution over several days, and because of the nature of the changes, they must be done in the order that I have suggested.
If you have any better ideas, I am all ears (or eyes...)
Out of curiosity, why are you suggesting to do all the changes at once? The method I have propsed should not create any confusion during the transition.
-- Metacomet 19:52, 27 December 2005 (UTC)
Are you suggesting that you don't think I have a lot of common sense? -- Metacomet 02:23, 28 December 2005 (UTC)
Actually, don't answer that. I think I already know the answer.
There are good reasons for making the changes one-at-a-time, if you think about it for more than 3 seconds. The reasons are related to concepts from manufacturing like error proofing and single piece flow. Although it is not at all obvious, it turns out that it will actually take less time to make one change at a time than it would to make all three changes together, and more importantly, it will be much less likely to make an error.
BTW, with a little bit of clever scheming, it is not all that difficult to figure out a way for a global-search-and-replace to distinguish between "n" in an equation and "n" that is part of a word. Again, it just requires a little bit of thinking and planning.
-- Metacomet 02:56, 28 December 2005 (UTC)
Also, I would appreciate it if you would avoid snide put-downs. Please see No personal attacks and Civility. Thanks. -- Metacomet 05:25, 28 December 2005 (UTC)
Sorry, RBJ, it's just too difficult to get anything done. I have other fish to fry. It would be nice to see the notation changed to something more standard, but ultimately, it is not all that important to me. Good luck. -- Metacomet 18:42, 28 December 2005 (UTC)
Another problem, while we're at it, is the unnecessary use of two different symbols for the same thing: and . is probably more conventional, given that the time sequence is . And for what it's worth, it avoids potential confusion with the in
http://en.wikipedia.org/math/7/7/5/7757e67d47b0ba3f1f7e3628c813bd2d.png
--
Bob K 20:48, 2 January 2006 (UTC)
I have started converting the notation in Discrete cosine transform to match the changes that we have agreed to on this article. The four changes are:
1. n becomes N: Change all instances of the symbol n to the new symbol N to represent the length of the sequences in both the time and frequency domains.
2. k becomes n: Change all instances of the symbol k to the new symbol n to represent the index variable for the time domain sequence.
3. j becomes k: Change all instances of the symbol j to the new symbol k to represent the index variable for the frequency domain sequence.
4. f becomes X: Change all instances of the symbol f to the new symobl X to represent the transformation of the data sequence in the frequency domain.
Once I have finished the DCT article, I will start working on Discrete sine transform.
If others would like to help, please review the List of Fourier-related transforms for articles to work on (discrete versions only).
-- Metacomet 16:00, 6 January 2006 (UTC)
The section on Completeness states: "for any N ≥ 0, any N-dimensional complex vector has a DFT and an IDFT which are in turn N-dimensional complex vectors."
The case N=0 is unimportant, and all the formulas having N in the denominator ceases to make sense. It should be changed to "for any N > 0, any N-dimensional complex vector has a DFT and an IDFT which are in turn N-dimensional complex vectors."
Bo Jacoby 07:46, 5 January 2006 (UTC)
Here we go again... As you know, I think this section needs a little work. My new gripe is with the last paragraph:
-- Bob K 03:11, 7 January 2006 (UTC)
Since this article is basically totally incomprehensible to those who do not know higher math, perhaps we could include a visual representation of a DFT so the reader may at least get a vague idea of what it means/does. How about a nmr or ftir spectrum?-- Deglr6328 08:09, 12 April 2006 (UTC)
My sentiments exactly. I was really surprised at the detailed math of this. Good math, maybe, dry article. So now begins the...:
The Finite Fourier Transform is an experiment you really can do at home; your spreadsheet is all you need.
---A WORK IN PROGRESS--
All "real-world" waveforms can be described by a summation of sines and cosines with constant coefficients (amplitudes): Why do we care?
Why do we care? Answer this: Why does a bird chirp sound different than a cricket chirp? What frequency (pitch) was that crow's caw? Why does my voice sound different than yours? How do we make this awful picture of Aunt Millie sharper? Most scientists mathematicians, and engineers use the various processes called "the Fourier transform" to answer these and similar questions. They want to learn more about the waveforms of the signals-- the "waveform" is "the shape" of "the signal" (that comes for example, from their microphone).
Why not just look the waveform on an oscilloscope or a computer screen? Because it will be just a jumble of up-and-down "waves" with littler wavey wiggles in them -- like ocean waves, big waves with little waves riding on top. There is nothing we can use there.
The discrete Fourier transform freezes in time facts about a waveform's "pitch" (its frequency, its tone high or low as in A-440 cycles per second versus middle C-512 [?]) that we can look at as long as we'd like. And, given this transform, we can recover our original waveform.
When waveforms have been "transformed" to this stationary form we can do all kinds of neat things to them. Such as: use Adobe Photoshop to sharpen the digital photos of Aunt Millie.
Discrete signal recording:
Before the mid-1980's sound recording was done first (i) mechanically by phonograph, then later (ii) electro-optically on film (motion picture sound track), or tape (magnetically). Sound engineers used these "analog" (continuous as opposed to discrete) methods and looked at their signals on "analog" oscilloscopes.
But today the computer "sound card" takes the signal that comes from the scientist's microphone and "samples" it (40,000 times per second, or 44,000 per second, or 176,000 per second, etc). What the sound card produces and sends to the computer are streams of "bits and bytes" -- 16 bits, 24 bits, 32 bits -- that represent the signal but are no longer "the signal" itself; the sound is gone across the meadow into the hills, the signal from the microphone is converted to heat and lost forever. All that exists finally are "the bits and bytes" that the scientist's computer has recorded on her hard drive or her flash-card.
This type of "signal-processing" is called "analog-to-digital" (A-to-D) conversion and is done by special circuitry. In all cases the conversion involves (i) sampling the waveform, (2) A-to-D conversion at a fixed interval (such as 44,000 conversions per second, or 176,000 conversions per second for "high resolution" recordings). Quite often the processs involves more steps: (i) smooth the signal with a "low-pass filter", (ii)"hold" the signal steady for a moment while (iii) the A-to-D converter samples the held signal, (iv) actually A-to-D convert the sampled signal. We will see below why these extra steps are required.
Sampling is easy:
To sample a waveform just multiply it by 1 to take the sample; the rest of the time, multiply by 0. (The briefer the sample, the better). In our example, the waveform we are sampling changes from -10 to +10 (usually the waveforms are much smaller, this is just an example). Whenever our "sampler" takes a sample, it -- in effect -- multiplies the waveform at that instant by 1.
Our resulting string of numbers-as-samples looks like this:
Notice something interesting: our waveform is compressed into just a few samples, now stored in space on a computer disk (or whereever). Is it really possible that we can recover our original waveform from this squished stuff? YES!
An aside: Quantization:
A crude A-to-D converter might change our analog number between -15 and +15 into 31 levels of "quantization" equivalent to steps (quanta) of 1. These "levels" will come out as bits and bytes. For example, +5 might be 00100, -5 might be 10101, etc. Fancy A-to-D converters convert to 32 bits or about 4 billion levels. Common audio conversion in a computer is to 16 bits, about 65,000 levels.
The role of the discrete Fourier transform is not fret about issues surrounding "quantization". The transform's role is to convert our waveform from a time-based event into frequencies that we can stare at forever, if we want to. The only job quantization has to do is to give the computer (or us) numbers that it (we) can crunch.
Analog samples would work just fine if we had a bunch of analog multipliers and adders to do the transform.
But what about the transform? Show me the transform!
All in good time. First we need to describe how we get the waveform back:
Discrete signal playback:
When the scientist plays back the sound on her computer, the computer delivers the saved bytes to the sound-card.
> [usually beforehand the scientist selects a "slice" to look at and transform... Sound Forge example? hence the sampling window]
The card uses a reverse process called Digital-to-Analog (D-to-A) to convert the bytes and bits back into a waveform. But the output from the D-to-A converter will again have discrete steps in it. If we were to look at the Sony Sound Forge reproduction of the "signal's waveform" we find it is represented by points (the discrete samples) connected by lines (interpolations so the result may look like triangles). After D-to-A conversion the sound card smoothes out the steps (or triangles) with a low-pass filter. The sound card amplifies this smoothed now-analog signal; it is now in a form our scientist can hear on her speakers [Is this correct re sigma-delta conversion?]
A question appears: Why do we believe we can trust our tools?:
In brief: we can't until we "calibrate them" -- test them against known good results. We wonder: will a reproduction be faithful to its original? Maybe yes, maybe no. Even if our crow-caw microphone introduces "junk" (wind noise is typical), a poorly-designed sound card may introduce unexpected junk into our scientist's reproduced waveform (growls, whistles, whines). If this is the case, she (hopefully) will find it when she looks at "the spectrum" of the waveform. With the use of the discrete Fourier transform she can do just that -- look at the "frequency spectrum" of her bird and insect sounds, present them on a sonogram that plots frequency on the Y axis, time on the X axis, and colors the intensity of the sound. Perhaps from what she expects and from applying known waveforms to her sampler, she can learn to "trust her tools".
sines and cosines:
Why do we need to discuss "sines" and "cosines"? It just turns out that any snippet of waveform can be approximated by a bunch of them added together. The why and the proof of this is not so simple, however. [see Why it Works].
Most people think of sines and cosines in terms of trigonometry, but the words themselves do not contain those ideas. Rather, the word "sine" comes from Latin sinus meaning "curve": we speak of Marilyn Monroe as a "sinuous woman", for example. And "cosine" comes from Latin cosinus, co- (with, together) +sinus "curve" (Websters New Collegiate). The sine and cosine are close associates.
The pendulum is commonly used as the example of a repeating "cosinusoidal" motion (cf Cannon p. 171ff). Pull it to the right R, then let it go. The pendulum comes back to center C, swings to the left L, then back to center C:
A "full cycle" is the motion R, C, L, C. Apply numbers to the symbols R, C, L; choose R = +1, C = 0, L= -1. Now record the motion -- at one-second snap-shots -- of a really slow pendulum -- our pendulum takes 8 seconds to make its complete cycle . We see that our pendulum seems to "dwell" longer at the extremes L = -1 and R = +1, and move faster in the center C = 0. Our records, in fact, show the pendulum's positions to be as follows:
The waveform in the first picture is a cosine. In the picture of its reconstruction the reconstruced waveform is "almost a sine" -- if it were to start at zero it would be a sine (ignoring the wiggles riding on it). Its shift to the right repreents a delay and is called its phase shift; the "hold" and the "filter" are responsible for this.
Observe what we have just done: we have sampled the motion of the pendulum. And we will soon use these same numbers to extract the Discrete Fourier Transform from our snippet of waveform!
We say the pendulum's (and hence its cosine's) frequency is how long in seconds the pendulum requires to make one full cycle. Our slow pendulum takes 8 seconds to move in one full cycle, so we say that its frequency is 1/8 Hz (Hz = Hertz = cycles per second).
If we plot the times on an X axis and the pendulum's position on a Y axis and draw a smooth curve through the points, the cosine is just this smooth curve. A sine curve is of identical shape, just shifted right so that it starts at 0 rather than 1. [footnote: derivative of sine is cosine and vice versa; easy to see with difference equations]. If we were to put a felt-tip pen on the bottom of our pendulum and, at a steady rate, pull a piece of paper beneath the pendulum, the motion of the pen would trace out the cosine (or sine). The shapes of the two waves -- sine and cosine -- are identical; they just start at different values.
Sampling Window:
Only rarely is a signal sampled for a long period of time and then have a discrete Fourier Transform applied to it. Usually we do this for just an interesting piece of the waveform. If we are recording a crow's caw we just "snip" the "caw" and discard the uninteresting road noise and lawn-mower sounds. The time-duration of the "snippet" (or length of the snippet if we are looking at the waveform on our computer screen) is called "the window".
For more about what can go wrong with windows and what we do about it, see "What can go wrong" below.
Fundamental frequency, Harmonics, frequency components, amplitudes, :
Anyone who plays a musical instrument knows what an "octave" is: it is just the next lower or higher register. For example: middle C is the note C just below the treble staff, the first octave above middle C is the C on the staff. The next octave higher puts C above the staff. A higher octaves represents doubling frequency. A harmonic is similar, but it represents an integer multiple of (usually positive with 0 a special case i.e. 1, 2, 3, 4, ...), rather than a doubling of, a base frequency called "the fundamental:"
Another name for the harmonics is the frequency components. The harmonics/frequency components together with the fundamental make up the spectrum of the waveform.
As it turns out we will need to find both cosine and sine harmonics. Neither a collection of sine harmonics nor a collection of cosine harmonics is sufficient (adequate) to reconstruct our waveform -- we need both sets. Why? Because the cosine always starts from 1, if we encounter a wave that starts from 0 we will need the sine harmonics too. More likely than not we will need both sets.
The fundamental is fundamental
So just who or what determines "the fundamental"?
Hamming (p. 508) provides us with a wonderful analogy: think about our "snippet" of waveform as if it were wrapped around a cylinder with a circumference the same length as the snippet. [The following may be O.R. [?]: a perhaps even better analogy is an early precursor to the motion-picture, the Mutoscope -- a cylinder with sampling slits in it, around the inside of which a sequence of images is wrapped. The viewer cranks a handle and watchs the scene move. Problem is, the scene repeats every rotation. But this is exactly like Hamming's analogy.]
The discrete Fourier transform treats our waveform as if it were "a snippet" wrapped around in a cyclider that is spinning. It is the circumference of the cylinder -- or "(time-)duration" of the cylinder to make one full roation-cycle -- that determines the so-called "wavelength of the fundamental", or in time, the longest duration and lowest frequency that the transform can deliver back to us.
All the other frequencies that the transform delivers/produces will be integer multiples of this fundamental. Why would this be? An obscure answer is: the average value of the "area under the curve" of sine or cosine curve is 0. If we were to use a non-integer (0.5 cycles or 1.5 cycles) this would not be the case.
But rather than this obscure answer, what we are going to do is show firstly that a cosine fundamental can "pluck out" of a waveform a cosine of the same (fundamental) frequency, but not a sine. Secondly we will show that a cosine with double the frequency does not pluck out either a cosine nor a cosine of the fundamental frequency. This will be true for every harmonic, not just the first with double the frequency.
We will "transform" our sampled pendulum's cosine waveform with itself, and see what we get. What we do is write down one cycle of our pendulum -- sampled at the 8 1-second intervals -- and multiply each sample by itself. We add up the numbers, and divide by 4 to get what is called "(double) the weighted average".
The sum of the individual products is 4 and the average is 1.
We will "transform" our pendulum's motion with a sine pendulum's motion -- same slow speed -- and see what we get. We add up the numbers, and divide by 4 to get "the weighted average".
time in seconds.........: { 0,.... 1, ...2,... 3,... 4,... 5,....6,....7 } position of cosine pendulum..: { +1.0, +0.7, +0.0, -0.7, -1.0, -0.7, +0.0, +0.7 } position of sine pendulum....: { +0.0, +0.7, +1.0, +0.7, +0.0, -0.7, -1.0, -0.7, } products.....................: { +0.0, +0.5, +0.0, -0.5, +0.0, +0.5, +0.0, -0.5 } running sum of products......: { +0.0, +0.5, +0.5, +0.0, +0.0, +0.5, +0.5, +0.0 } The sum of the products is 0 and the average is 0.
We will "transform" our pendulum's motion with a faster pendulum's motion -- three as fast -- and see what we get. What we do is put down three cycles of our fast pendulum -- sampled at the same 8 1-second intervals -- and multiply each slow sample by the fast sample. We add up the numbers, and divide by 4 to get "the weighted average".
The sum of the products is 0 and the average is 0.
This time we multiply our slow pendulum's motion by by the three-times-as-fast sine waveform:
The sum of the products is 0 and their average is 0.
So how many integer-multiples of this sort can we get? Unfortunately, not as many as we'd like: Just the number of samples in fundamental's cycle divided by 2 -- in other words 4 for the cosine collection and 4 for the sine collection. Why is this? The answer is not so simple. See Nyquist Rate below.
Our conclusions from the above examples:
1. Our sampled waveform: : { 1, 1, 1, 1, 0, 0, 0, 0 }
2. The fundamental frequency is 1/8 seconds
3. The integer sample size is 8
4. The various integer multiples of the fundamental will be
5. The various integer frequencies of the sines and cosines will be
6. The sampled cosine fundamental and its harmonics:
7. The sampled sine fundamental and its harmonics:
To create our transform we simply multiply the counterparts (thus we have to do this 8 times, and we see that 2 of these yield 0 so they are trivial). here is an example of n=3 for the numbers of the sampled sine:
We add these and divide by 4 to get 0.25. This is the amplitude (height, value) of this "component" n=3. If one were to write cosine equation for this harmonic "wave" it would be:
We can get a better feeling of what is going on if we go to larger sample sizes. Our original waveform shown here is the following:
{ -0.5, -0.5, -0.5, 1, 1, 1, -1, -1, -1, -1, -1, 0.5, 0.5, 0.5, 0.5, 0.5 }
The graphing together of sine and cosine amplitudes is somewhat difficult to look at, so we will plot the information in a different way -- in the more common presentation of "a spectrum". The "spectrum" has facinating quality of being position invariant -- unlike the varying sine-cosine harmonics that change depending on where we "start" our waveform on the cylinder, the spectrum remains the same.
A spectrum does not show the amplitudes of the individual sines and cosines, but rather it combines the two into a single number for each harmonic (for more about the trigonometry behind this see Why it Works):
The square root is usually taken in the positive and represents a directionless quantity: (the length of a line but not its direction). This composite amplitude V, however, contains only has half the information. The rest is contained in "the phase" φ:
An "arc-tangent" is "the angle whose tangent is ...". On an Excel spreadsheet the ATAN function "appears" in the form of radians, where a "radian" is defined as 2π of these puppies in one circle. If we want to convert "radians" to "degrees" (360 degrees in a circle), a radian is 360 degrees/(2π) = 57.29577951 degrees, a convenient-and-easy to remember number.
To do a reconstruction, then, either both the composite amplitudes Vn and the phases φn are required for each component n, or both the sines' and cosines' amplitudes an and bn are required for each component. Nothing comes for free.
Our original waveform shown here is the following, the same as appears on the cylinder above:
The original waveform is shown in black. Just below the X-axis (labelled 0.00) is the "d.c." (abbreviation for "Direct Current") or steady-state value that comes from the 0th cosine component. Our reconstruction sums this d.c. value and all the other sine and cosine terms for each component, then sums up the resulting waves into a partial reconstruction. Not all the partial-reconstruction sums are shown because the picture gets cluttered.
The odd wiggles on the final reconstruction (bold red line) is typical. See more at Gibb's phenomenon below.
---A WORK IN PROGRESS--
Nyquist frequency: the maximum frequency in our "transform" = 1/2 the sampling frequency
Observe an interesting fact: when m=4, the sine is 0 all the way down the column, but when n=4, the cosine alternates:
These numbers represent the cosine's maximum and minimum values. If our "waveform" contains a cosine or sine that is "faster" than this, our sampling will make an error. This is related to what is called the Nyquist frequency. Our maximum sampling frequency should be less than or equal to (at worst) one-half of our sample rate. Aliasing occurs when we don't to this problem (for more see Aliasing below).
Sometimes (for sound purposes) folks plot these as a 'sonogram' where frequency is on the Y axis, time is on the X-axis, and intensity is the color or the "brilliance" of a point in the plane.
Repeatitive numbers in the sine and cosine samples
Observe that only the following numbers appeared in the 8-sample transform when we sample the sines and cosines:
This lucky find means that if we are doing this with a microcontroller we don't have to compute vast numbers of sines and cosines, we can just store the necessary numbers in a table. It happens because our sines and cosines are periodic and related to one another by integers. This observation will be of use if we want to proceed to a "fast Fourier Transform" (see below).
But, we do have to be clever in our choice of sample size. An example (not shown) of 10 samples creates 5 harmonics for the sine and five for the cosine. But the numbers are not so fortunate and there are lots more of them. If you were to work this out on a spread-sheet you would observe the numbers below:
Hamming seems fond of the number "12" (cf Hamming p. 543ff).
Prelude to the 'Fast Fourier Transform' The "FFT" is just a computing trick that depends on the fact noted above: that all the values of sine and cosines in the table are similar (cf. Chapter 33 "The Fast Fourier Transform" in Hamming, p. 539ff). The FFT has become a highly-developed art since Hamming. See Discrete cosine transform for nice examples.
---A WORK IN PROGRESS--
Hamming describes the many issues that can arise with the discrete Fourier Transform:
The origin of "beat frequencies" (in sound recordings: unexpected groans, whistles, whines, throbbing pulsations; in photos: weird Moire patterns) and their role in aliasing can be found in some trigonometric identities that show what happens when we multiply sines by sines, or cosines by cosines. (We can easily derive these identities if we express sine and cosine in their complex (i.e. e^ix) forms). We use the following:
From the above we simply derive the equations below. These show that if we multiply two sines or cosines, we get the sum frequency (x+y) and the difference frequency (x - y) and there is nothing we can do about it:
Because any Fourier transform multiplies cos x*cosy and sin x*sin y we will always get "beats". Whether or not the "beats" have any affect on what we are doing depends on how cautious we are with respect to our sample rate and our waveform that we are sampling.
Suppose we sample our wave at 4 per second (t occuring at an interval of 0.125 second), a sine waveform with a frequency of 6 per second. In other words, we have not sampled at a high enough frquency. Sampling can be thought of as multiplying our 6 Hz waveform by "the sampler" occurring at 4 per second. Let's use the simplest sampler we can: a sinewave "lifted up" so that its peak occurs at 1 and its minimum at zero:
Our sampling thus multiplies our 6 Hz sinewave by the "sampler"
And we have seen that this process of multiplication introduces "beats". The right-most term yields the "beats" at 2 and 10 Hz:
So our sampling has produced the following new waveform:
Observe that we have just picked up 2 Hz and 10 Hz in addition to the original 6 Hz.
Now, what happens when we do our transform? We create more beats! We can see this if we use the 4 Hz sine or cosine of the transform:
The first term creates 2 and 10, the second term creates 2 and 6, and the third term creates 6 and 14!
The process of sampling and processing with discrete Fourier transforms is like making an infinitely long paper doll: we fold our infinitely-long paper, cut one shape and unfold it to reveal the repeating pattern, ad infinitum (cf drawing on pag 514 of Hamming, and his explanation p.513). If we cut too far our shape "overlaps" into the shapes beside it. This is called "folding".
Harmonic 6 is equivalent to 2. 6 has "folded back" to become 2, and the "2" shouldn't be there. 10 also folds back to 2.
Note that we could have done this in reverse order: multiplied, in the continuous domain, our waveform by the sine, then sampled it. The results would be the same.
The aperture (cf Carlson p. 285, Bracewell, p. 276ff) is the time e.g. 0.001 second for a slow sampler) during which a "snap-shot" of the waveform is taken and either held constant (while an A-to-D conversion occurs, in the above audio example) or allowed to change while either the sample or (if no "hold") the conversion is occurring). Thus we see two sources of error during the instant the sample is taken: (i) the waveform may be changing during "the sample", (ii) an A-to-D error may occur. But there is a third intrinsic error which is related to "windows".
As mentioned above, the fact that we have introduced a "window "of finite time-duration during which we take our samples itself introduces more "junk.
Our analogy points to a source of problems: we may "cut" our waveform at an inopportune place and make the splice to another inopportune place, and thereby create a "discontinuity." And such discontinuities create something called 'the Gibbs phenomenon' (see more below).
[need reference here e.g. Sound Forge uses various methods:] What to do about this? Engineers have devised ways of "smoothing" the signal -- multiplying the window by a "weighting factor" so that the discontinuity is not so odious. [Blackmun, Hamming, etc. windows]
>(cf Hamming p. 532ff, Bracewell p. 209). [Is this Hamming's "leakage?]
Some examples produce tidy results -- the reverse DFT reproduces its waveform perfectly. But if we had picked the following waveform we would not be able to reproduce it exactly. In the little picture, the original is in blue and the red is the reproduced. this problem is either caused by (i) Gibbs phonomenon or by (ii) too-high frequency content for the sample rate:
It appears to have "ripples" in the waveform that we cannot get rid of [etc: is this Gibbs or is this the effect of aliasing -- too much high-freq crap in the original waveform?]
---A WORK IN PROGRESS--
> In the final analysis, can we can convince ourselves that a waveform of a given length/duration can be expressed as "the finite sum of a integral sines and cosines with various amplitudes"?
> An important observation: weighted average: If we plot one cycle of our fundamental sine and consider the area under the curve of "the upper half" (above the X-axis) to be positive area, and the "lower half" to be negative, then we see that the area below cancels out the area above. This is also true for the cosine, since they have the same shape.
This happens always when there are an integral number of cycles of the sine or cosine, but never when the number of cycles is not integral.
If we multiply our waveform by our "reference" sine or cosine, the total positive- and negative- areas under the resulting curve (the curve that represents the product of our waveform x sine, or waveform * cosine) may not be (and probably won't be) 0. The "residual" area gives us a clue about how much of that particular "component/harmonic" is "in the waveform".
>Why is "the component" that results from the transform just the simple average of the area? If we were to plot the "residual" area as a little rectangle, it will have either a positive-area or a negative-area) stretched over the extent of our "snippet window" = "length/duration of fundamental". Thus our rectangle's length is the "length" of the fundamental and its "height" is the area divided by the length. [Aren't things are off by a factor of 2? Why?]
> Then the notion of "plucking out" the amplitudes by use of the "unit harmonics" may be straight-forward (if you're willing to do some algebra). It is the assertion that "a finite waveform can be expressed as the finite sum...." that is hard to swallow.
To pluck out third cosine harmonic, multiply W(t) by unit cosine 1*sin2Π*3*t/8. This generates a slew of harmonics, in essence doubling the number of terms on the right:
> concept #1: to locate a point on the plane we need two values, its "X-coordinate" and the "Y-coordinate". This is, ultimately, where the need for both the sine and the cosine waveforms comes from. If our X- and Y-axes are at right angles, we say that they are "orthogonal", a word used interchangeably with 'perpendicular':
> concept #2: the ultimate value of a*sine X + b*cos Y is "Z" in the third dimension. If we are to keep the cylinder analogy we really have to think about this in 3-D. The waveform is printed on the treads of a tire, the tire is mounted on a wheel on an axle that spins at the same rate as the fundamental sine and cosine. The 1st harmonic spins twice as fast. Etc.
> concept #3 requires a bit of trigonometry: the Pythagorean theorem. Given that our "X" and "Y-axes" are perpendicular/orthogonal, and the values for "X" and "Y" are the coordinates (location) of the point in the plane, the diagonal V-- measured from the origin to the point -- has the following length:
An example: On a stairs the "run" is the length of the "tread" and the rise is the (perpendicular) height of the step. The diagonal is, well ... the diagonal.
If this length-of-line V is given together with its "direction" we call it a "a vector". But how do we specify its "direction?"
> concept #4 requires a bit of trigonometry. A common way of describing a vector's "direction" (remember: a "vector" is the line drawn from the origin to a point on our waveform) is to give the angle, measured counter-clockwise, that it makes withthe X-axis. If our vector-line lies flat on the X-axis and points to the right, it has an angle of 0° (always described with respect to the X-axis). Straight up it has an angle of 90, straight left it has an angle of 270, straight down it has an angle of 360.
> concept #5 requires a bit of trigonometry. The definition of "the cosine of an angle" is "run" divided by the diagonal. the definition of "the sine of an angle" is the "rise" divided by the diagonal. The two concepts can be compressed into a third definition called "the tangent": "rise"/"run".
Basis vectors:
What is the angle between the X-axis and Y-axis? We might start this way: we draw a line and call it "the X-axis". Somewhere on it we put a point; this we call "the origin". Then off the line somewhere we put a point, say to the upper right an inch or so. If we were to draw a line from the origin through this point it would form an angle. Now move the point directly above the origin so that the X-axis and the line are perpendicular (orthogonal). The angle of our perpendicular line is 90 degrees. What is its cosine? 0.
> This is the mathematical definition of orthogonal: cosine between two lines-as-vectors is 0.
>[So what is the point? Why does the reader want to care about this?: that for any point in an X-Y plane we can use two orthogonal vectors to locate it? these are "the basis vectors". In the "X-Y" plane we need only two: the (unit) X-leg and Y-leg of the (unit) triangle; any point in the plane can be located with the help of these two: 3*X + 4*Y locates a point at x=3, y=4. The length of "the vector" (measured from origin to the point) is sqrt(3^2 + 4^2) = 5, the angle is arctan(4/3) = 53 degrees. Given these two values L=5, angle=53 degrees, how do we locate our point? (x=5*cos(53°), Y=5*sin(53°)). But why not skip the X, Y step and go to a unit sine and unit cosine as a basis? How and why do "the harmonics" come into this?
> Here's an important observation: the product of two "vectors", i.e. a sine as "a vector" and a cosine as "a vector" times our waveform which is a bunch of vectors:
What will be the sum of these two points? the simplest way would be to just add everything together in a mish-mash. But We would loos our vector. Vectors add "component ax" to component cx, "component by to component dy". The resulting vectors (a+c)x and (b+d)y are considered 'independent' and are not intermingled:
What will the product of these two points, a product that we need for our transform? We will just do our multiplication in the "normal way" -- term by term and see what it looks like:
We would expect that, like most things multiplicative, x*x = x, ditto for y*y = y
But what about y*x and x*y? Because they are at right angles to one another, both products are 0. [and why is that?]
Given that we accept the sentence above, our product leaves us with something simple: we see that we haven't "gained" any extra terms, so if we needed to we could do this again, and again (we don't need to):
>[We have to move, in an intuitive manner, from a point to a sequence of points that trace out a curve and show without handwaving . Each point can be described by a single vector (length) and an angle with respect to the X-axis, or as two perpendicular vectors. for a circle we can see this easily, and the sines and cosines for the fundamental -- the circumference of the unit circle -- . But just how do the harmonics come into this? The Harmonics spin around the Z axis-as-axle twice as fast, three times as fast, four times as fast, etc.
>We have to show the reader how this stuff works. We have cylinders or disks spinning at the "fundamental rate" of 1 revolution per 8 seconds, twice as fast 2 revolutions per 8 seconds, three times as fast (3 revolutions per 8 seconds), 4 revolutions per 8 seconds.
Here, m and n are integers that will represent "the harmonics" as described below. They either positive or negative values. Usually they are just considered positive: For continuous sine and cosine wavesforms:
For discrete sine and cosine waveforms the following become summations over the number of samples S (e.g. S=8):
---A WORK IN PROGRESS--
wvbailey Wvbailey 18:50, 16 June 2006 (UTC)
The simplest non-trivial example is N = 2 .
This table shows (−1)jk.
... k=-1 k=0 k=1 k=2 ... ... ... ... ... ... ... ... j=-1 ... -1 +1 -1 +1 ... j=0 ... +1 +1 +1 +1 ... j=1 ... -1 +1 -1 +1 ... j=2 ... +1 +1 +1 +1 ... ... ... ... ... ... ... ...
The rows and columns of the table are periodic with period 2. So the following tiny table is sufficient.
k=0 k=1 j=0 +1 +1 j=1 +1 -1
A pair of real numbers x = (x0, x1) is transformed into a pair of numbers Fx = ((Fx)0, (Fx)1) defined by
This F is the discrete fourier transformation.
These special cases follow from the definition:
so does the proof that it is a linear transformation:
and the fact that the transformation is an involution
So, any periodic sequence, of period N = 2, can be written as a linear combination of powers of (−1). If the variable j is interpreted as a point of time, and xj is the corresponding sample of a signal, then the variable k is interpreted as a frequency, and (Fx)k is the corresponding amplitude. The amplitude (Fx)0, corresponding to the frequency k = 0, is called the DC amplitude, for Direct Current, and the maximum frequency, k = 1, is called the Nyquist frequency.
The next case to consider is N = 4 .
(This case is simpler than the case N = 3 because the square root of minus one, i, is logically prior to the primitive cube root of unity, (−1+i×31/2)/2. In both cases it is necessary to consider complex numbers.)
One possible generalization is:
However, this definition loses the involutary property.
The following alternative generalization:
where the asterisk * signifies the complex conjugate: (a+ib)* = a−ib, makes F an involutary and antilinear map.
The latter choice is logically preferable but not always chosen in the literature.
Note that this theory of fourier transform doesn't need the geometrical and analytical concepts of cos, sin, e, and π, which scare the beginner. It is pure algebra. Bo Jacoby 12:45, 16 June 2006 (UTC)
Can you cite a reference? I need the reference. I haven't seen any FT's done without a consideration of sines and cosines first. N.O.R. even if its good and to the point.
The idea of a non-harmonic "basis" would be okay but I believe the true FT is always with sines and cosines...correct me if I'm wrong.
(It would be interesting to see Fourier's original work and see exactly what he was up to).
If so, Somewhere these ugly dudes will have to creep in.
They are not that bad if you can see them. Before i launched into this I did consider a simpler case. The problem is we don't get to see "the harmonics". And it's no fun (and pointless) unless you can see the harmonics.
As you see I got some pretty nasty feedback when I started into my little effort. The folks sneered at the tables in general.
So I cut out another table completely. Really what we need is, together with the tables, a picture or two of a simple "waveform" fitted with sines and cosines, or the point values, or whatever. Together with the harmonics. I don't know enough about wiki's esoteric importing to be able to get them out of Excel.
Imaginary numbers = fear and loathing.
Matrices, forget it. "Orthogonality" will throw folks. So will "basis vectors" or anything like that. These concepts need to go way at the end (or just disappear as "a given", "proven in linear algebra"). Like I wrote, behind the fourier transform is 50 pages of dense linear algebra, enough to choke anybody but a determined math or engineering major. And that is just in the reals, not even including the complex domain.
Here's my goal: to write (some of) this for a high-school kid good in math. Like my 9th-grade nephew -- he was exposed to fractals in 8th grade, loved them. I showed him the wiki page and he loved it. I had some books that I loaned him, got him all excited. Ditto for my son when he was that age, he loved the idea of a picture that you travel through -- I found a program (referenced on that page). As a post-doc he's had to use sonograms and FTs in Sound Forge extensively in his work. He uses them as a tool, not as an esoteric math concept. But if he wanted to know more, why the f*** should he have to slog through a bunch of equations if someone can present the ideas in a kindler, gentler way? The trick is to find the way. Wvbailey 13:45, 16 June 2006 (UTC)
The primitive roots of unity are purely algebraic concepts. Fourier (to the best of my knowledge) didn't use complex numbers, so he had to rely on the more complicated analytical properties of the real-valued trigonometric functions. The immensely powerful concept of involution is not used for the fourier transforms in the article, and the readers suffer. Bo Jacoby 15:54, 19 June 2006 (UTC)
The unsatisfactory section of the article could be replaced by this.
The eigenvalues of the involutary discrete fourier transform, F, are +1 and −1, because F satisfies the equation F2 = 1 and so any eigenvalue k satisfies k2 = 1.
The operators P = 2−1(1+F) and Q = 2−1(1−F) are idempotent :
If x is any vector, then Px is a eigenvector with eigenvalue +1, and Qx is a eigenvector with eigenvalue −1, because
Any vector x is a sum of an eigenvector with eigenvalue +1 and an eigenvector with eigenvalue −1:
because
and the involutary fourier transform of this vector is
because
Bo Jacoby 15:03, 19 June 2006 (UTC)
As the eigenvalue-multiplicities for λ=+i and λ=−i must be equal, the table in the article not correct. Bo Jacoby 10:52, 21 June 2006 (UTC)
size N | λ = +1 | λ = −1 | λ = +i | λ = −i |
---|---|---|---|---|
4m | m + 1 | m | m | m − 1 |
4m + 1 | m + 1 | m | m | m |
4m + 2 | m + 1 | m + 1 | m | m |
4m + 3 | m + 1 | m + 1 | m + 1 | m |
I took it out after finding DFT linked from the aliasing page. Since the DFT has no relationship to continuous-time signals or aliasing, I took it out. Only afterward did I check here and see the long-running dispute about it between Bob and Stephen. I must say I agree with Bob. Furthermore, the concept of aliasing is very well described in other articles where it is relevant. See aliasing, Nyquist–Shannon sampling theorem, Nyquist–Shannon interpolation formula, Nyquist rate, Nyquist frequency, etc. I'd be interesting in knowing if any textbooks discuss aliasing with respect to the DFT. Dicklyon 06:10, 23 June 2006 (UTC)
This is my first major Wikipedia submission; please bear with me. I have written a quick reference to how to use the DFT in MATLAB which I would like to offer for inclusion. What say you all? -- Cxw 19:33, 18 July 2006 (UTC)
Dear Wikipedians, "I would lean against including it" is much gentler than saying "Shut up". But where I come from, the proper etiquette is to not only be gentle in telling someone that something is off-topic here, but also to tell them where that something is on-topic (or at least more on-topic than it is here).
In this particular case, I suspect http://en.wikibooks.org/wiki/MATLAB_Programming would be a good place for that quick reference.
-- DavidCary -- 65.70.89.241 15:36, 8 August 2006 (UTC)
We are told that
and
are different forms of the same function. They are not. Different functions must have different names. Bo Jacoby 11:20, 9 August 2006 (UTC)
I think the phrase "different forms" was intended in the sense of "different functional forms" (e.g. a*sin(x) + b*x has a different functional form than a*x^2 + b) rather than "different forms of the same function" which was obviously not meant here. I edited it slightly to emphasize this difference, although perhaps more substantial rephrasing would clarify things further. Definitely, a more complete discussion should go in trigonometric interpolation polynomial but I think there's a good argument for putting at least the minimal-slope interpolations here as a summary, since those interpolation polynomials, and their non-uniqueness, are critical for a lot of applications of the DFT (e.g. for spectral methods). —Steven G. Johnson 04:44, 11 August 2006 (UTC)
'Sinusoid' is a new word in the context. It might be confusing to some readers. I changed it to 'wave' in accordance with the explanation given in the article sinusoid but it was changed back. The terms in the trigonometric polynomial as written are exponentials, not explicite trigonometrics. Perhaps this is the place to show a real-function expression of trigonometric polynomials involving the sine and cosine functions explicitely? If the reader has seen such an expression in some book it is nice if he recognizes it in wikipedia so that he doesn't think that the article here is about something quite different. Bo Jacoby 06:35, 16 August 2006 (UTC)
The sinusoid is complex, not the frequency. You can do better! Bo Jacoby 08:06, 16 August 2006 (UTC)
"In contrast, the most obvious trigonometric interpolation polynomial is the one in which the frequencies range from 0 to N − 1 (instead of roughly − N / 2 to + N / 2 as above), similar to the inverse DFT formula. This interpolation does not minimize the slope, and is not generally real-valued for real xn; its use is a common mistake."
Dear Steven, the fact that you made this mistake yourself does not make it common. You do not have to document your mistakes in WP. :-) Bo Jacoby 06:44, 16 August 2006 (UTC)
I am talking about that the history of this subsection is that you first mentioned the frequency range from 0 to N−1 rather than from −(2·N−1+(−1)N) / 4 to (2·N−3−(−1)N) / 4. Accept reader's comments constructively, especially as you are not letting anybody but yourself edit 'your' article. The subsection does not explain what you explained here. Errors made by students may be caused by errors in teaching, so your students make a biased sample. Still, WP is not the place for documenting errors, common or not. Bo Jacoby 10:19, 17 August 2006 (UTC)
As for WP not being the place for "documenting errors," I don't think you're being reasonable. From a pedagogical perspective it can be almost as valuable to explain what not to do, if there is a common pitfall, as to explain what to do. Moreover, the non-uniqueness of trigonometric interpolation is a fundamental concept that needs to be understood in order to properly apply the DFT/DTFT for everything from PDEs to the sampling theorem. What better way to explain it than to briefly mention an example of an inequivalent interpolation? —Steven G. Johnson
Hi Steven. I made my point. A pitfall is avoided by building a road that circumvents the pitfall, rather than by placing a warning sign at the end of the road that leads to the pitfall. You might introduce the balanced frequency range early, rather than to use an unbalanced frequency range for theoretical work, thus leading the reader to use it also for interpolation, giving bad results. If I make an edit, will you promise to leave it unremoved for a week? You do have a long history of removing my WP contributions, you remember. Be nice to people and they will be nice to you. Show respect, and respect will be shown to you. I am your mirror, my friend. Bo Jacoby 09:24, 18 August 2006 (UTC)
I am referring to correcting your errors such as including n=0 in the definition of the discrete fourier transform. I stopped editing because of your vandalism, not because you are right. Can you see a constructive aspect of my comment or are you just permanently offended by my implying that you are not perfect? Bo Jacoby 14:41, 20 August 2006 (UTC)
This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |