![]() | 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 |
Hi Are you aware of any possible advancement to the DFT, in discrete-frequency? I am particulartly working on a topic which have reached restrictions on frequencies to become an infinite set of discrete values rather than continuous variable. My problem is to determine a correct inverse to an already derived fourier transform. Any comment in this regard is appreciated.
Frequently many computer modeling people use DFT to calculate the actual Fourier Transform. I think in this page we need a small section on the realtions between the continuous fourier transform, and the discrete fourier transform. This would really help.-- 129.107.47.144 ( talk) 20:44, 24 March 2009 (UTC)
This section could do with a rewrite. The notation is different from the rest of the article - brackets not subscripts. There is no need to refer to the dtft article. It's easy to show straight from the dft definition that it is periodic. Paul Matthews 09:44, 3 October 2006 (UTC). I also find it strange that nowhere does the article say that a DFT is a truncation of the Fourier series - well it does now!
I just removed the whole section in question, because it makes no sense (to me). Here it is in case anyone wants to fix it up, remember it, or explain to me what it's trying to say:
It is shown in the Discrete-time Fourier transform (DTFT) article that the Fourier transform of a discrete time sequence is periodic. A finite length sequence is just a special case. I.e., it is an infinite sequence of zeros containing a region (aka window) in which non-zero values may occur. So , the DTFT of the finite sequence , is periodic. Not surprisingly, the DFT is periodic; e.g. . Less obvious, perhaps, is that the inverse DFT is also periodic; e.g., . It is a periodically extended version of the finite sequence.
The DTFT of the periodically extended sequence is zero-valued except at the discrete set of frequencies sampled by the DFT. I.e., it is effectively identical to the DFT. The DTFT of the finite sequence has other non-zero values, but it is still identical to the DFT at the frequencies sampled by the DFT. So the approximation error of , as an approximation to , lies in the missing non-zero values, not in the coefficients. In terms of the inverse DFT, that approximation error becomes the periodic extension of the finite sequence.
Here's what I don't get: what is meant in the first place by "the Fourier transform of a discrete time sequence"? Sequences don't have Fourier transforms. To get a periodic Fourier transform, aren't they assuming a modulated comb of delta functions? Do we really want that complexity introduced into an article on a simple discrete transform? And then, the periodicity stuff presumed definitions different from what we have in this article. I was looking at a book today in what defined periodic extensions of x and X, which might then give something to say. But what does this article refer to when it says "it" in "It is a periodically extended version of the finite sequence"? It seems to be contradicting the definition that we have for the IDFT. And so on. This is all too fuzzy for me. If anyone can make it sensible, then put it back. Dicklyon 03:35, 5 October 2006 (UTC)
Yes, those might be good ideas for additions to the section.
I found my book: Peled & Liu's Digital Signal Processing: Theory, Design, and Implementation. I misremembered a bit. Their notation is not specific to the periodic extension, but rather "taken to mean the periodic extensions when appropriate". That is they use the same notation for the DFT and its periodic extension, essentially equivalent to treating them as circular, to make it easier to state certain properties, such as even and odd symmetries, reverse directions, shifts, etc. that involve negating or offsetting subscripts, to avoid introducing circularity mid mod N subscripts I suppose.
However, the idea of periodicity arising from uniformly spaced discrete samples gets a lot more complicated. There is nothing in the DFT that cares about uniform spacing, so to tie its periodicity periodicity of spectra of continuous-time signals will take a lot of work, which is already well covered, I think, in DTFT article.
The circular convolution and shift properties are already covered, I believe. You don't need to drag periodicity into the explanation of circular.
Dicklyon 17:41, 5 October 2006 (UTC)
I just took a brief look on this article after a long time. Still only the editors can read it. Fundamental problems remain unsolved from the very beginning of the article. Quote:
The expression is not for a basis but for a vector component, as it contains no information distinguishing component adress and vector adress. The matter was discussed in talk:function (mathematics)#standard notation and it was resolved that the notation for such a basis could be
the k th vector of which is
the nth component of which is
Bo Jacoby 14:52, 7 February 2007 (UTC).
There's another problem too. This article doesn't mention anywhere that the DFT is applicable to any orthogonal basis function, not just . I'd like to see it generalized a bit more, and be less specific in its focus on sinewaves. ~ Amatulić ( talk) 21:25, 21 October 2008 (UTC)
The definition is incomprehensible to the uninitiated reader.
1. It is more important to tell the reader that is a primitive N'th root of unity, than that "e is the base of the natural logarithm, is the imaginary unit (), and π is Pi".
2. A few simple examples might help.
Bo Jacoby 07:42, 8 February 2007 (UTC).
A person with long experience reacts differently than a person who just heard the word 'discrete fourier transform' and is now curious about it. WP ought to be helpful to our young friend. He/she is likely to stop reading at the very first formula. Is it possible to improve with this in mind? What problem is DFT solving? Is there a simple example? Perhaps it should be even simpler.
Bo Jacoby 12:09, 9 February 2007 (UTC).
I don't agree with this sentence "The sequence of N complex numbers x0, ..., xN−1 is transformed into the sequence of N complex numbers X0, ..., XN−1", since DFT doesn't necessary trasform N complex numbers into other N (that is only true for Fast Fourier Transform). I think this definition should be more general giving different cardinalities to the numbers of the 2 different domains (ie: transforming a sequence of N complex numbers into a sequence of K complex numbers).
79.18.198.247 ( talk) 12:42, 25 January 2008 (UTC)
The reader has 3 equivalent expressions to learn
The article becomes easier to read if we get rid of the third one and write DFT rather than like this:
Bo Jacoby 08:03, 8 February 2007 (UTC).
If a reader wants to study an authoritative book, then he will learn the notation from that book, and then he does not need to read the wikipedia article. The purpose of a encyclopedia article is to provide a comprehensible explanation to persons who do not already know the subject matter, and who do not necessarily intend to commence a deeper study. So the article should not be complicated by different ways of expressing the same thing. The big F is used not only for discrete fourier transform, but also for other transforms such as the continuous Fourier transform. Therefore it is easier to get rid of the big F here rather than to get rid of the abbreviation DFT, which specificly means Discrete Fourier Transform. (It would be nice to stop distinguishing between discrete and continuous fourier transform and create a common presentation, but that is quite another story). Bo Jacoby 23:00, 8 February 2007 (UTC).
"Finite Fourier transform" redirected to "Discrete Fourier transform" here at Wiki. But I put up a disambiguation page for the "Finite" term, because alas it is used in a different sense by some people, ee.g.
http://www.dtc.army.mil/navigator/apnd_D03.html
http://library-dspace.larc.nasa.gov/dspace/jsp/bitstream/2002/10966/1/NASA-97-tm110340.pdf
LDH 11:07, 26 February 2007 (UTC)
Is there not an error in the denominator for the forward transform? (Or the compound forward/inverse scaling factor?) I get half result when testing in program and spreadsheet. Apparently for all indices other than 0 and N/2, the scale factor (product) should be 1/(N/2), rather than 1/N. (Could be written 2/N). See link below, and this value makes my program work, I believe.
http://www.dspguide.com/ch8/5.htm
63.76.53.47 17:35, 6 June 2007 (UTC)Gordon Elliott 63.76.53.47 17:35, 6 June 2007 (UTC)
b(x)=8x+2 d=4 d>deg(a(x))+deg(b(x)) 4>3 a={3,9,1,0}//append last zero b={8,2,0,0}//append last zero's
(3x^2+9x+1)*(8x+2)=24x^3+78x^2+26x+2
yet FFT^-1(FFT(a)*FFT(b))={42,78,8,2} which does not equal {24,78,26,2}
because FFT({3,9,1,0})={13,11,-6+i,-6-i} FFT({8,2,0,0})={10,10,6,6} {13,11,-6+i,-6-i}*{10,10,6,6}={130,110,-36+6i,-36-6i} FFT^-1({130,110,-36+6i,-36-6i})={42,78,8,2}!={24,78,26,2}
what am I doing wrong?
-- ANONYMOUS COWARD0xC0DE 20:43, 25 June 2007 (UTC)
Someone removed the {{ technical}} I stuck up there because I didn't leave any comments about what I didn't understand. So, I put it back, and here's what I don't understand: just about all of it. It goes right into high-level mathematics without so much as an explanation of what you're even doing. Wikipedia's here to create en encyclopedia accessible to everyone, not just people who took 4+ years of math in college. So, in short, how about a little simplification? — SheeEttin { T/ C} 02:16, 29 June 2007 (UTC)
Definition
The DFT is a linear algebraic transform that takes as its input a set of numbers that can be thought of as a sampled time-domain signal that repeats, wrapping from the last sample back to the first forever. The transform produces as output a set of just as many numbers, which can be thought of as measurements of the amounts and phases of different frequencies present in the original periodic sequence. The numbers are complex in general; in particular, even if the input numbers are real, the output numbers are still usually complex. Each output number corresponds to a frequency of some number of cycles in the length of the original data; the first, at index represents "DC", or the amount of unchanging signal in the input; the second, at index , represents the amount and phase of a sinusoid of one cycle in the input data (that is, one cycle per repetition in the infinite periodic repetition of the input); similarly, output values for higher index values quantify the amount and phase on sinusoid of that many cycle in the input data. The amount and phase are the magnitude and phase of the output complex numbers, which can also be interpreted as real and imaginary parts specifying the amounts of cosine and sine waves in the input data. Each output value of the DFT is computed by summing the values of the input times samples of a complex exponential of the frequency corresponding to the output index. For the higher index values, above half the number of input points, the high frequencies exceed a half cycle per input sample, and may alternatively be viewed as negative frequencies.
In algebraic notation, the sequence of N complex numbers x0, ..., xN−1 is transformed into the sequence of N complex numbers X0, ..., XN−1 by the DFT according to the formula:
where e is the base of the natural logarithm, is the imaginary unit (), and π is pi. The transform is sometimes denoted by the symbol , as in or or .
The DFT for the case of real inputs can also be defined in terms of sums of purely real sines and cosines, for the real and imaginary part separately:
And so on...
I must say this article is pretty confusing. I've done some research about the DFT to try to understand and apply it in a program, but it looks like there are many variants of this... For example, on [1] it is said:
Each of the four Fourier Transforms can be subdivided into real and complex versions. The real version is the simplest, using ordinary numbers and algebra for the synthesis and decomposition. For instance, Fig. 8-1 is an example of the real DFT. The complex versions of the four Fourier transforms are immensely more complicated, requiring the use of complex numbers. These are numbers such as: 3+4j, where j is equal to sqrt(-1) (electrical engineers use the variable j, while mathematicians use the variable, i). Complex mathematics can quickly become overwhelming, even to those that specialize in DSP. In fact, a primary goal of this book is to present the fundamentals of DSP without the use of complex math, allowing the material to be understood by a wider range of scientists and engineers.
The formula in that article is:
and do not require complex numbers. Also, these formulae yield me N+2 values in the frequency domain (N being the number of samples). The formulae in the Wikipedia article give me 2*N values (N complex numbers). What's the difference between both formulae (if there is any)? Why aren't these versions written in this article? It seems to me that they are easier to use and are sufficient for most purposes. —Preceding unsigned comment added by 87.65.199.96 ( talk • contribs)
I agree that the article is too technical and confusing. One year ago I suggested a more pedagogical approach, See Talk:Discrete Fourier transform/archive 1#Always begin with the simplest example. I gave up because some other editor was opposing rather than cooperating. Now, after a year, the problem still exists, the article is still too technical and confusing. The editor in question has had his chance and blew it. He must give room to other editors. Bo Jacoby 13:31, 27 July 2007 (UTC).
Steven, the idea of writing an encyclopedic article is not to summarize the "standard" approach of the "the popular and time-tested textbooks", but rather to move the topic from the advanced level down to the elementary level. By writing that "some people will find this material hard to follow, but that will be true in any presentation of an advanced-undergraduate-level topic" you indicate that you do not believe that a good encyclopedic article can be written at all. An encyclopedic article should not describe every variation of notation and definition found in litterature, but rather explain the essence of the subject to the uninitiated reader, using the sufficient minimum of notation and definition. For example, the trancendental numbers e and π is no problem on the advanced-undergraduate-level, but they are unnecessary and should be removed, because discrete fourier transform is pure algebra. Explaining a special case helps, when a reader does not understand the general case. From the easy case N = 2 one may proceed to the case N = 3, introducing a complex cube root of unity, then to the general finite case, introducing a complex, primitive Nth root of unity, and then to the limiting cases, namely the fourier series and the fourier integral transform. I do not suggest to stick to the case N = 2. Bo Jacoby 09:35, 28 July 2007 (UTC).
Bob, after 40 years you have no problem with e and π and you have no need to express the discrete fourier transform in terms of simple algebra. So you are not a member of the elementary segment of the reader population. Nor are you a member of the advanced segment, because you do not need the article at all. It tells you nothing new. You are neither complaining that the article is technical and confusing, nor are you praising it for providing you with just the insight you need. We could prefix the article with a note that the reader is supposed to have 40 years of mathematical experience in order to understand it, and in that case he has no benefit from reading it anyway. So we do not need two articles. We need one encyclopedic article! Your suggestions for improving the services of Wikipedia are nice, but besides the point I am trying to make. Bo Jacoby 12:47, 28 July 2007 (UTC).
The article is too technical and confusing. The readers tell you so. How come you don't listen to what is said? Not every article in WP has that problem. You argue that it cannot be helped. I see no entry in this talk page where advanced freshmen testify that they follow most of it. How come you listen to what is not said? Bo Jacoby 16:29, 28 July 2007 (UTC).
Ok. The problem was there one year ago and it is still there today. Lets talk again in another year from now to see whether your established pedagogic approach has solved the problem by then. If any deviation from the approach of the advanced textbooks is considered forbidden original research, then the problem has got no solution. Good luck. Bo Jacoby 18:15, 28 July 2007 (UTC).
In section "Orthogonality" you have mentioned . What is the range of indexes k and k'? Is it possible to add a link to where it comes from? It`s not from article " orthogonal", the only somehow relevant link I can see. Arkadi kagan 13:01, 11 September 2007 (UTC)
16-Oct-2007: When expanding the article with text for general readers, please isolate explanations to limited sections, or else the article will become "too simple" (or "too tedious") for experienced readers. Several readers have complained about articles being "baby-fied" with wording that over-simplifies the technical details they feel are needed. This is just a general concern: avoid making the technical writers afraid to use technical terms or formulae, or afraid to expand advanced concepts in the article.- Wikid77 19:42, 16 October 2007 (UTC)
16-Oct-2007: To handle concerns of "too technical" (or "too simple"), I have expanded the article with a new bottom section, Basic explanation. That section gives a simple explanation of a "discrete Fourier transform" (plus the applications and branches of mathematics used), without cluttering the main text of the article. I think such a bottom section is about the best way to explain many novice issues about the subject, without annoying the more advanced readers about the background basics, such as using "formulas in finite mathematics" and "algebra". At this point, I am removing the "{technical}" tag at the top. - Wikid77 23:42, 16 October 2007 (UTC)
This sections needs LOTS OF IMAGES. —Preceding unsigned comment added by 18.243.2.30 ( talk) 19:31, 14 November 2007 (UTC)
Yes, this and entire Fourier series articles on Wikipedia are too complicated. Here is Wikipedia, not a math courses. I looked over the discussion page and I saw only cheap talk among "specialists" . Please insert sections with basics explanations about Fourier and then you can put whatever complex stuff you want. —Preceding unsigned comment added by 192.35.17.15 ( talk) 12:39, 12 February 2008 (UTC)
Take it from occasional reader, the editors of this page seem to be way too locked up on the way it is always done in math courses. People "who dont know" need broader perspective, e.g. where the hell the core comes from, why it is the way it is (not "just because of its properties", but why it has them in the 1st place), how does it relate to cross-correlation, etc, etc. Oh ya, the signature: 92.112.247.110 ( talk) —Preceding undated comment was added at 15:20, 9 November 2008 (UTC).
It's been noted, apparently for years that this article is too complex (to which I concur in the extreme), but nothing has been done to correct the situation. As far as I can tell, the only people who can understand the article as it is currently written are people who already know the subject matter perfectly. So the current article serves NO ONE. The people who already understand, don't need it, and the people who don't, can't comprehend it. I would dive in a do something myself, but I'm another person coming to this topic for enlightenment, so I'm hardly qualified to rewrite it. I would strongly suggest someone look over Steven W. Smith's "The Scientist and Engineer's Guide to Digital Signal Processing" for some inspiration on how this topic could be explained so that a newcomer has some prayer of understanding what's going on. If no one else steps up in a reasonable time frame, I'll at least toss in a few graphs of what a signal looks like before and after DFT has been applied to it. Also I'll throw in my best guess of a simple description of what DFT is good for. However I won't be too surprised if my edits mostly get tossed, since as I stated above, this subject is far from a strong point for me. I just don't want to sit by and do nothing when it has been pointed out for so long that this article isn't helping anyone. Please note that I'm not suggesting that the complex material be removed, just some simple description added so the mathematically challenged can gain some understanding. —Preceding unsigned comment added by Twikir ( talk • contribs) 13:55, 20 June 2009 (UTC)
I keep moving the sentence in the third paragraph of the introduction to a separate paragraph, and someone else keeps putting it back. I thought I would start some discussion about this small point. The sentence in question is this: "The terminology is further blurred by the synonym finite Fourier transform for the DFT, which apparently predates the term "fast Fourier transform" (Cooley et al., 1969) but has the same initialism." I have no problem with the sentence itself - only its placement. My thinking is that conflating "finite Fourier transform" and "DFT" happens nowhere near as often as conflating "FFT" and "DFT", and that it seems inappropriate to mention what seems to me to be a relatively obscure term ("finite Fourier transform") in such a prominent place in a long article. Also, the paragraph that it's currently in is otherwise about FFTs and the relationship between FFTs and DFTs. It seems to me that the sentence about finite Fourier transforms should either be split into a separate paragraph immediately following, as I had done, or, removed from the introduction and moved elsewhere. The new home for this sentence could be in an existing section of the article, a new section about terminology, or even a new article about DFT- and FFT-related terminology. -- ATBS 30Aug09
By the way, here is an observation: the introduction contains a lot of parentheses. Adding information by tacking on parenthetical remarks may be convenient for the editor, but it often makes sentences harder to read. Perhaps someone would like to take a shot at rewriting the introduction so as to convey the same information without using so many parentheses. - ATBS —Preceding unsigned comment added by ATBS ( talk • contribs) 22:40, 31 August 2009 (UTC)
I recently tried to add the following sentence to the "Spectral Analysis" section: One more problem of spectral analysis by DFT is that the DFT shows different behaviour for deterministic signals and for noise; ... which Oli Filth reverted with the comment Reverted good faith edits by Hanspi ... Thanks for the "good faith" comment, but my edit was due to rather more than just good faith.
I guess you are aware that a sine will (ideally) give a peak in the DFT whose height is the RMS value of the sine, while for white noise it will be the noise integrated over one frequency bin. However, are you also aware that non-white noise -- noise with an autocorrelation function that is not a Dirac impulse -- can behave in quite unexpected ways? E.g., random-walk noise (cumulative sum of white noise) comes out 3dB higher than one would expect from the idea that the DFT just integrates the noise power in a single frequncy bin. If you use, e.g., a Blackman-Harris window on random-walk noise, this will give you good precision at high frequencies but errors as big as 7dB at low frequencies. Read the Paper "BIASES AND VARIANCES OF SEVERAL FFT SPECTRAL ESTIMATORS AS A FUNCTION OF NOISE TYPE AND NUMBER OF SAMPLES" by Walls, Percival and Irelan, 43rd Annual Synposim on Frequency Control, 1989. I can send you Matlab files to play with, if you wish.
So while I think we could discuss whether this kind of information belongs on the Wikipedia -- and I think not, one sentence plus one reference would be enough, ant that's what I did -- I know two things for sure: first, I keep on having to educate engineers and other scientists on how to read a spectrum made with a DFT and read SNR out of it, because so few of them can do it; and second, my edit was not based on "good faith" but on "proficiency in application". Oli, I'd welcome your comments on this. Hanspi ( talk) 18:55, 7 September 2009 (UTC)
Please carefully explain all the terminology--all the variables. For example, explain n and k very carefully. These concepts are not entirely clear to the learner, especially those like myself who are self taught!!!
Thanks. —Preceding unsigned comment added by 74.232.131.125 ( talk) 20:33, 21 February 2010 (UTC)
It seems to be difficult to identify an actual use of the DFT in everyday consumer technology. — Preceding unsigned comment added by Jfgrcar ( talk • contribs) 21:49, 12 December 2010 (UTC)
Could someone add a subsection to the Application section about how the DFT can be used to diagonalize a Toeplitz matrix? Also, is the Toeplitz matrix the most general form of a matrix that the DFT can diagonalize? Bender2k14 ( talk) 01:22, 21 April 2011 (UTC)
From the article currently:
"The eigenvalues of the DFT matrix are simple and well-known, whereas the eigenvectors are complicated, not unique, and are the subject of ongoing research."
Abstract of linked article:
"The eigenvalues and eigenvectors of the nxn unitary matrix of finite Fourier transform whose element is , is determined. In doing so, a multitude of identities, some of which are new, are encountered. A conjecture is advanced."
The eigenvectors are are stated rather plainly on the second column of the first page.
I'm not quite sure who to believe here. Since I recall listening to a lecture by Gilbert Strang stating (back in 200X, whereas this paper was published in the 80's...) that the eigenvectors are currently unknown and undergoing research, and Wikipedia seems to be backing this up. However, the article I linked to seems fairly plausible.
For the moment I'll Be Bold, but leave this comment here in the discussion so someone else can double-check me.
Peter Stalin ( talk) —Preceding undated comment added 13:15, 8 September 2011 (UTC).
It is not clear what the domain of k is in the definition. I suppose integers 0<=k<n -- in fact I am almost certain -- but it is not clear from the onset (which to me is crucial in a definition) — Preceding unsigned comment added by 184.161.209.68 ( talk) 03:41, 30 January 2013 (UTC)
![]() | 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 |
![]() | 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 |
Hi Are you aware of any possible advancement to the DFT, in discrete-frequency? I am particulartly working on a topic which have reached restrictions on frequencies to become an infinite set of discrete values rather than continuous variable. My problem is to determine a correct inverse to an already derived fourier transform. Any comment in this regard is appreciated.
Frequently many computer modeling people use DFT to calculate the actual Fourier Transform. I think in this page we need a small section on the realtions between the continuous fourier transform, and the discrete fourier transform. This would really help.-- 129.107.47.144 ( talk) 20:44, 24 March 2009 (UTC)
This section could do with a rewrite. The notation is different from the rest of the article - brackets not subscripts. There is no need to refer to the dtft article. It's easy to show straight from the dft definition that it is periodic. Paul Matthews 09:44, 3 October 2006 (UTC). I also find it strange that nowhere does the article say that a DFT is a truncation of the Fourier series - well it does now!
I just removed the whole section in question, because it makes no sense (to me). Here it is in case anyone wants to fix it up, remember it, or explain to me what it's trying to say:
It is shown in the Discrete-time Fourier transform (DTFT) article that the Fourier transform of a discrete time sequence is periodic. A finite length sequence is just a special case. I.e., it is an infinite sequence of zeros containing a region (aka window) in which non-zero values may occur. So , the DTFT of the finite sequence , is periodic. Not surprisingly, the DFT is periodic; e.g. . Less obvious, perhaps, is that the inverse DFT is also periodic; e.g., . It is a periodically extended version of the finite sequence.
The DTFT of the periodically extended sequence is zero-valued except at the discrete set of frequencies sampled by the DFT. I.e., it is effectively identical to the DFT. The DTFT of the finite sequence has other non-zero values, but it is still identical to the DFT at the frequencies sampled by the DFT. So the approximation error of , as an approximation to , lies in the missing non-zero values, not in the coefficients. In terms of the inverse DFT, that approximation error becomes the periodic extension of the finite sequence.
Here's what I don't get: what is meant in the first place by "the Fourier transform of a discrete time sequence"? Sequences don't have Fourier transforms. To get a periodic Fourier transform, aren't they assuming a modulated comb of delta functions? Do we really want that complexity introduced into an article on a simple discrete transform? And then, the periodicity stuff presumed definitions different from what we have in this article. I was looking at a book today in what defined periodic extensions of x and X, which might then give something to say. But what does this article refer to when it says "it" in "It is a periodically extended version of the finite sequence"? It seems to be contradicting the definition that we have for the IDFT. And so on. This is all too fuzzy for me. If anyone can make it sensible, then put it back. Dicklyon 03:35, 5 October 2006 (UTC)
Yes, those might be good ideas for additions to the section.
I found my book: Peled & Liu's Digital Signal Processing: Theory, Design, and Implementation. I misremembered a bit. Their notation is not specific to the periodic extension, but rather "taken to mean the periodic extensions when appropriate". That is they use the same notation for the DFT and its periodic extension, essentially equivalent to treating them as circular, to make it easier to state certain properties, such as even and odd symmetries, reverse directions, shifts, etc. that involve negating or offsetting subscripts, to avoid introducing circularity mid mod N subscripts I suppose.
However, the idea of periodicity arising from uniformly spaced discrete samples gets a lot more complicated. There is nothing in the DFT that cares about uniform spacing, so to tie its periodicity periodicity of spectra of continuous-time signals will take a lot of work, which is already well covered, I think, in DTFT article.
The circular convolution and shift properties are already covered, I believe. You don't need to drag periodicity into the explanation of circular.
Dicklyon 17:41, 5 October 2006 (UTC)
I just took a brief look on this article after a long time. Still only the editors can read it. Fundamental problems remain unsolved from the very beginning of the article. Quote:
The expression is not for a basis but for a vector component, as it contains no information distinguishing component adress and vector adress. The matter was discussed in talk:function (mathematics)#standard notation and it was resolved that the notation for such a basis could be
the k th vector of which is
the nth component of which is
Bo Jacoby 14:52, 7 February 2007 (UTC).
There's another problem too. This article doesn't mention anywhere that the DFT is applicable to any orthogonal basis function, not just . I'd like to see it generalized a bit more, and be less specific in its focus on sinewaves. ~ Amatulić ( talk) 21:25, 21 October 2008 (UTC)
The definition is incomprehensible to the uninitiated reader.
1. It is more important to tell the reader that is a primitive N'th root of unity, than that "e is the base of the natural logarithm, is the imaginary unit (), and π is Pi".
2. A few simple examples might help.
Bo Jacoby 07:42, 8 February 2007 (UTC).
A person with long experience reacts differently than a person who just heard the word 'discrete fourier transform' and is now curious about it. WP ought to be helpful to our young friend. He/she is likely to stop reading at the very first formula. Is it possible to improve with this in mind? What problem is DFT solving? Is there a simple example? Perhaps it should be even simpler.
Bo Jacoby 12:09, 9 February 2007 (UTC).
I don't agree with this sentence "The sequence of N complex numbers x0, ..., xN−1 is transformed into the sequence of N complex numbers X0, ..., XN−1", since DFT doesn't necessary trasform N complex numbers into other N (that is only true for Fast Fourier Transform). I think this definition should be more general giving different cardinalities to the numbers of the 2 different domains (ie: transforming a sequence of N complex numbers into a sequence of K complex numbers).
79.18.198.247 ( talk) 12:42, 25 January 2008 (UTC)
The reader has 3 equivalent expressions to learn
The article becomes easier to read if we get rid of the third one and write DFT rather than like this:
Bo Jacoby 08:03, 8 February 2007 (UTC).
If a reader wants to study an authoritative book, then he will learn the notation from that book, and then he does not need to read the wikipedia article. The purpose of a encyclopedia article is to provide a comprehensible explanation to persons who do not already know the subject matter, and who do not necessarily intend to commence a deeper study. So the article should not be complicated by different ways of expressing the same thing. The big F is used not only for discrete fourier transform, but also for other transforms such as the continuous Fourier transform. Therefore it is easier to get rid of the big F here rather than to get rid of the abbreviation DFT, which specificly means Discrete Fourier Transform. (It would be nice to stop distinguishing between discrete and continuous fourier transform and create a common presentation, but that is quite another story). Bo Jacoby 23:00, 8 February 2007 (UTC).
"Finite Fourier transform" redirected to "Discrete Fourier transform" here at Wiki. But I put up a disambiguation page for the "Finite" term, because alas it is used in a different sense by some people, ee.g.
http://www.dtc.army.mil/navigator/apnd_D03.html
http://library-dspace.larc.nasa.gov/dspace/jsp/bitstream/2002/10966/1/NASA-97-tm110340.pdf
LDH 11:07, 26 February 2007 (UTC)
Is there not an error in the denominator for the forward transform? (Or the compound forward/inverse scaling factor?) I get half result when testing in program and spreadsheet. Apparently for all indices other than 0 and N/2, the scale factor (product) should be 1/(N/2), rather than 1/N. (Could be written 2/N). See link below, and this value makes my program work, I believe.
http://www.dspguide.com/ch8/5.htm
63.76.53.47 17:35, 6 June 2007 (UTC)Gordon Elliott 63.76.53.47 17:35, 6 June 2007 (UTC)
b(x)=8x+2 d=4 d>deg(a(x))+deg(b(x)) 4>3 a={3,9,1,0}//append last zero b={8,2,0,0}//append last zero's
(3x^2+9x+1)*(8x+2)=24x^3+78x^2+26x+2
yet FFT^-1(FFT(a)*FFT(b))={42,78,8,2} which does not equal {24,78,26,2}
because FFT({3,9,1,0})={13,11,-6+i,-6-i} FFT({8,2,0,0})={10,10,6,6} {13,11,-6+i,-6-i}*{10,10,6,6}={130,110,-36+6i,-36-6i} FFT^-1({130,110,-36+6i,-36-6i})={42,78,8,2}!={24,78,26,2}
what am I doing wrong?
-- ANONYMOUS COWARD0xC0DE 20:43, 25 June 2007 (UTC)
Someone removed the {{ technical}} I stuck up there because I didn't leave any comments about what I didn't understand. So, I put it back, and here's what I don't understand: just about all of it. It goes right into high-level mathematics without so much as an explanation of what you're even doing. Wikipedia's here to create en encyclopedia accessible to everyone, not just people who took 4+ years of math in college. So, in short, how about a little simplification? — SheeEttin { T/ C} 02:16, 29 June 2007 (UTC)
Definition
The DFT is a linear algebraic transform that takes as its input a set of numbers that can be thought of as a sampled time-domain signal that repeats, wrapping from the last sample back to the first forever. The transform produces as output a set of just as many numbers, which can be thought of as measurements of the amounts and phases of different frequencies present in the original periodic sequence. The numbers are complex in general; in particular, even if the input numbers are real, the output numbers are still usually complex. Each output number corresponds to a frequency of some number of cycles in the length of the original data; the first, at index represents "DC", or the amount of unchanging signal in the input; the second, at index , represents the amount and phase of a sinusoid of one cycle in the input data (that is, one cycle per repetition in the infinite periodic repetition of the input); similarly, output values for higher index values quantify the amount and phase on sinusoid of that many cycle in the input data. The amount and phase are the magnitude and phase of the output complex numbers, which can also be interpreted as real and imaginary parts specifying the amounts of cosine and sine waves in the input data. Each output value of the DFT is computed by summing the values of the input times samples of a complex exponential of the frequency corresponding to the output index. For the higher index values, above half the number of input points, the high frequencies exceed a half cycle per input sample, and may alternatively be viewed as negative frequencies.
In algebraic notation, the sequence of N complex numbers x0, ..., xN−1 is transformed into the sequence of N complex numbers X0, ..., XN−1 by the DFT according to the formula:
where e is the base of the natural logarithm, is the imaginary unit (), and π is pi. The transform is sometimes denoted by the symbol , as in or or .
The DFT for the case of real inputs can also be defined in terms of sums of purely real sines and cosines, for the real and imaginary part separately:
And so on...
I must say this article is pretty confusing. I've done some research about the DFT to try to understand and apply it in a program, but it looks like there are many variants of this... For example, on [1] it is said:
Each of the four Fourier Transforms can be subdivided into real and complex versions. The real version is the simplest, using ordinary numbers and algebra for the synthesis and decomposition. For instance, Fig. 8-1 is an example of the real DFT. The complex versions of the four Fourier transforms are immensely more complicated, requiring the use of complex numbers. These are numbers such as: 3+4j, where j is equal to sqrt(-1) (electrical engineers use the variable j, while mathematicians use the variable, i). Complex mathematics can quickly become overwhelming, even to those that specialize in DSP. In fact, a primary goal of this book is to present the fundamentals of DSP without the use of complex math, allowing the material to be understood by a wider range of scientists and engineers.
The formula in that article is:
and do not require complex numbers. Also, these formulae yield me N+2 values in the frequency domain (N being the number of samples). The formulae in the Wikipedia article give me 2*N values (N complex numbers). What's the difference between both formulae (if there is any)? Why aren't these versions written in this article? It seems to me that they are easier to use and are sufficient for most purposes. —Preceding unsigned comment added by 87.65.199.96 ( talk • contribs)
I agree that the article is too technical and confusing. One year ago I suggested a more pedagogical approach, See Talk:Discrete Fourier transform/archive 1#Always begin with the simplest example. I gave up because some other editor was opposing rather than cooperating. Now, after a year, the problem still exists, the article is still too technical and confusing. The editor in question has had his chance and blew it. He must give room to other editors. Bo Jacoby 13:31, 27 July 2007 (UTC).
Steven, the idea of writing an encyclopedic article is not to summarize the "standard" approach of the "the popular and time-tested textbooks", but rather to move the topic from the advanced level down to the elementary level. By writing that "some people will find this material hard to follow, but that will be true in any presentation of an advanced-undergraduate-level topic" you indicate that you do not believe that a good encyclopedic article can be written at all. An encyclopedic article should not describe every variation of notation and definition found in litterature, but rather explain the essence of the subject to the uninitiated reader, using the sufficient minimum of notation and definition. For example, the trancendental numbers e and π is no problem on the advanced-undergraduate-level, but they are unnecessary and should be removed, because discrete fourier transform is pure algebra. Explaining a special case helps, when a reader does not understand the general case. From the easy case N = 2 one may proceed to the case N = 3, introducing a complex cube root of unity, then to the general finite case, introducing a complex, primitive Nth root of unity, and then to the limiting cases, namely the fourier series and the fourier integral transform. I do not suggest to stick to the case N = 2. Bo Jacoby 09:35, 28 July 2007 (UTC).
Bob, after 40 years you have no problem with e and π and you have no need to express the discrete fourier transform in terms of simple algebra. So you are not a member of the elementary segment of the reader population. Nor are you a member of the advanced segment, because you do not need the article at all. It tells you nothing new. You are neither complaining that the article is technical and confusing, nor are you praising it for providing you with just the insight you need. We could prefix the article with a note that the reader is supposed to have 40 years of mathematical experience in order to understand it, and in that case he has no benefit from reading it anyway. So we do not need two articles. We need one encyclopedic article! Your suggestions for improving the services of Wikipedia are nice, but besides the point I am trying to make. Bo Jacoby 12:47, 28 July 2007 (UTC).
The article is too technical and confusing. The readers tell you so. How come you don't listen to what is said? Not every article in WP has that problem. You argue that it cannot be helped. I see no entry in this talk page where advanced freshmen testify that they follow most of it. How come you listen to what is not said? Bo Jacoby 16:29, 28 July 2007 (UTC).
Ok. The problem was there one year ago and it is still there today. Lets talk again in another year from now to see whether your established pedagogic approach has solved the problem by then. If any deviation from the approach of the advanced textbooks is considered forbidden original research, then the problem has got no solution. Good luck. Bo Jacoby 18:15, 28 July 2007 (UTC).
In section "Orthogonality" you have mentioned . What is the range of indexes k and k'? Is it possible to add a link to where it comes from? It`s not from article " orthogonal", the only somehow relevant link I can see. Arkadi kagan 13:01, 11 September 2007 (UTC)
16-Oct-2007: When expanding the article with text for general readers, please isolate explanations to limited sections, or else the article will become "too simple" (or "too tedious") for experienced readers. Several readers have complained about articles being "baby-fied" with wording that over-simplifies the technical details they feel are needed. This is just a general concern: avoid making the technical writers afraid to use technical terms or formulae, or afraid to expand advanced concepts in the article.- Wikid77 19:42, 16 October 2007 (UTC)
16-Oct-2007: To handle concerns of "too technical" (or "too simple"), I have expanded the article with a new bottom section, Basic explanation. That section gives a simple explanation of a "discrete Fourier transform" (plus the applications and branches of mathematics used), without cluttering the main text of the article. I think such a bottom section is about the best way to explain many novice issues about the subject, without annoying the more advanced readers about the background basics, such as using "formulas in finite mathematics" and "algebra". At this point, I am removing the "{technical}" tag at the top. - Wikid77 23:42, 16 October 2007 (UTC)
This sections needs LOTS OF IMAGES. —Preceding unsigned comment added by 18.243.2.30 ( talk) 19:31, 14 November 2007 (UTC)
Yes, this and entire Fourier series articles on Wikipedia are too complicated. Here is Wikipedia, not a math courses. I looked over the discussion page and I saw only cheap talk among "specialists" . Please insert sections with basics explanations about Fourier and then you can put whatever complex stuff you want. —Preceding unsigned comment added by 192.35.17.15 ( talk) 12:39, 12 February 2008 (UTC)
Take it from occasional reader, the editors of this page seem to be way too locked up on the way it is always done in math courses. People "who dont know" need broader perspective, e.g. where the hell the core comes from, why it is the way it is (not "just because of its properties", but why it has them in the 1st place), how does it relate to cross-correlation, etc, etc. Oh ya, the signature: 92.112.247.110 ( talk) —Preceding undated comment was added at 15:20, 9 November 2008 (UTC).
It's been noted, apparently for years that this article is too complex (to which I concur in the extreme), but nothing has been done to correct the situation. As far as I can tell, the only people who can understand the article as it is currently written are people who already know the subject matter perfectly. So the current article serves NO ONE. The people who already understand, don't need it, and the people who don't, can't comprehend it. I would dive in a do something myself, but I'm another person coming to this topic for enlightenment, so I'm hardly qualified to rewrite it. I would strongly suggest someone look over Steven W. Smith's "The Scientist and Engineer's Guide to Digital Signal Processing" for some inspiration on how this topic could be explained so that a newcomer has some prayer of understanding what's going on. If no one else steps up in a reasonable time frame, I'll at least toss in a few graphs of what a signal looks like before and after DFT has been applied to it. Also I'll throw in my best guess of a simple description of what DFT is good for. However I won't be too surprised if my edits mostly get tossed, since as I stated above, this subject is far from a strong point for me. I just don't want to sit by and do nothing when it has been pointed out for so long that this article isn't helping anyone. Please note that I'm not suggesting that the complex material be removed, just some simple description added so the mathematically challenged can gain some understanding. —Preceding unsigned comment added by Twikir ( talk • contribs) 13:55, 20 June 2009 (UTC)
I keep moving the sentence in the third paragraph of the introduction to a separate paragraph, and someone else keeps putting it back. I thought I would start some discussion about this small point. The sentence in question is this: "The terminology is further blurred by the synonym finite Fourier transform for the DFT, which apparently predates the term "fast Fourier transform" (Cooley et al., 1969) but has the same initialism." I have no problem with the sentence itself - only its placement. My thinking is that conflating "finite Fourier transform" and "DFT" happens nowhere near as often as conflating "FFT" and "DFT", and that it seems inappropriate to mention what seems to me to be a relatively obscure term ("finite Fourier transform") in such a prominent place in a long article. Also, the paragraph that it's currently in is otherwise about FFTs and the relationship between FFTs and DFTs. It seems to me that the sentence about finite Fourier transforms should either be split into a separate paragraph immediately following, as I had done, or, removed from the introduction and moved elsewhere. The new home for this sentence could be in an existing section of the article, a new section about terminology, or even a new article about DFT- and FFT-related terminology. -- ATBS 30Aug09
By the way, here is an observation: the introduction contains a lot of parentheses. Adding information by tacking on parenthetical remarks may be convenient for the editor, but it often makes sentences harder to read. Perhaps someone would like to take a shot at rewriting the introduction so as to convey the same information without using so many parentheses. - ATBS —Preceding unsigned comment added by ATBS ( talk • contribs) 22:40, 31 August 2009 (UTC)
I recently tried to add the following sentence to the "Spectral Analysis" section: One more problem of spectral analysis by DFT is that the DFT shows different behaviour for deterministic signals and for noise; ... which Oli Filth reverted with the comment Reverted good faith edits by Hanspi ... Thanks for the "good faith" comment, but my edit was due to rather more than just good faith.
I guess you are aware that a sine will (ideally) give a peak in the DFT whose height is the RMS value of the sine, while for white noise it will be the noise integrated over one frequency bin. However, are you also aware that non-white noise -- noise with an autocorrelation function that is not a Dirac impulse -- can behave in quite unexpected ways? E.g., random-walk noise (cumulative sum of white noise) comes out 3dB higher than one would expect from the idea that the DFT just integrates the noise power in a single frequncy bin. If you use, e.g., a Blackman-Harris window on random-walk noise, this will give you good precision at high frequencies but errors as big as 7dB at low frequencies. Read the Paper "BIASES AND VARIANCES OF SEVERAL FFT SPECTRAL ESTIMATORS AS A FUNCTION OF NOISE TYPE AND NUMBER OF SAMPLES" by Walls, Percival and Irelan, 43rd Annual Synposim on Frequency Control, 1989. I can send you Matlab files to play with, if you wish.
So while I think we could discuss whether this kind of information belongs on the Wikipedia -- and I think not, one sentence plus one reference would be enough, ant that's what I did -- I know two things for sure: first, I keep on having to educate engineers and other scientists on how to read a spectrum made with a DFT and read SNR out of it, because so few of them can do it; and second, my edit was not based on "good faith" but on "proficiency in application". Oli, I'd welcome your comments on this. Hanspi ( talk) 18:55, 7 September 2009 (UTC)
Please carefully explain all the terminology--all the variables. For example, explain n and k very carefully. These concepts are not entirely clear to the learner, especially those like myself who are self taught!!!
Thanks. —Preceding unsigned comment added by 74.232.131.125 ( talk) 20:33, 21 February 2010 (UTC)
It seems to be difficult to identify an actual use of the DFT in everyday consumer technology. — Preceding unsigned comment added by Jfgrcar ( talk • contribs) 21:49, 12 December 2010 (UTC)
Could someone add a subsection to the Application section about how the DFT can be used to diagonalize a Toeplitz matrix? Also, is the Toeplitz matrix the most general form of a matrix that the DFT can diagonalize? Bender2k14 ( talk) 01:22, 21 April 2011 (UTC)
From the article currently:
"The eigenvalues of the DFT matrix are simple and well-known, whereas the eigenvectors are complicated, not unique, and are the subject of ongoing research."
Abstract of linked article:
"The eigenvalues and eigenvectors of the nxn unitary matrix of finite Fourier transform whose element is , is determined. In doing so, a multitude of identities, some of which are new, are encountered. A conjecture is advanced."
The eigenvectors are are stated rather plainly on the second column of the first page.
I'm not quite sure who to believe here. Since I recall listening to a lecture by Gilbert Strang stating (back in 200X, whereas this paper was published in the 80's...) that the eigenvectors are currently unknown and undergoing research, and Wikipedia seems to be backing this up. However, the article I linked to seems fairly plausible.
For the moment I'll Be Bold, but leave this comment here in the discussion so someone else can double-check me.
Peter Stalin ( talk) —Preceding undated comment added 13:15, 8 September 2011 (UTC).
It is not clear what the domain of k is in the definition. I suppose integers 0<=k<n -- in fact I am almost certain -- but it is not clear from the onset (which to me is crucial in a definition) — Preceding unsigned comment added by 184.161.209.68 ( talk) 03:41, 30 January 2013 (UTC)
![]() | 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 |