Talk:Discrete Fourier transform

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Sine_wave

WikiProject Mathematics (Rated B-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
High Importance
 Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.

Domain of k?[edit]

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)

The N=2 case[edit]

I don't believe this addition to the "Definition", made earlier today, is helpful or relevant (to the definition):

http://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform&diff=527527711&oldid=526485596

--Bob K (talk) 13:38, 11 December 2012 (UTC)

I wouldn't include it in the definition either. However, the connection of the N=2 case to the Hadamard transform should probably be mentioned somewhere in the article. — Steven G. Johnson (talk) 19:37, 11 December 2012 (UTC)

Inverse DFT by reversing inputs, incorrect?[edit]

The article claims that the inverse DFT can be calculated by reversing the input vector, applying DFT, and dividing the result by N. This looks incorrect, I've tried it numerically and it gives the wrong results. The conjugation method however seems to work correctly (computing the DFT and inverse DFT of that yields the original vector). 193.77.101.149 (talk) 19:02, 21 March 2013 (UTC)

You are probably making a mistake in how you reverse the inputs. You need to replace x[n] by x[N-n], where the index is interpreted modulo N. In particular, this means that n=0 goes to N-0=N=0 mod N, so that the 0th element stays at the same place. For example, the inputs (0,1,2,3,4,5) (for N=6) would be reversed to (0,5,4,3,2,1), not to (5,4,3,2,1,0). — Steven G. Johnson (talk) 20:11, 21 March 2013 (UTC)
And it's not hard to derive, if you're interested. When you substitute k=6-L, L=6,1,2,3,4,5 in the IDFT:
the first term becomes:
and the last five terms become:
which is the promised DFT.
--Bob K (talk) 14:34, 22 March 2013 (UTC)

What is this page talking about?[edit]

I must confess to being absolutely baffled as to what this page is talking about. In (moderately) laymans terms, I understand that Fourier's theorem is that a wave form of amplitude Y and time T can be made up of the "harmonics" of the fundamental frequency. i.e.
if Y = f(X) and the period of the waveform is 2 pi then
Y = a1 cos x + b1 sin x +a2 cos 2x + b2 sin 2x + a3 cos 3x + b3 sin 3x (etc) Is this fast fourier transform calculating the values of a1,a2,a3 and b1,b2,b3 from a sample of f(x) or are we talking about something else?

If so then what does the real and imaginary parts of the input and output refer to? Op47 (talk) 22:15, 3 April 2013 (UTC)

It's "something else". The a's and b's you're referring to are the ones at Fourier_series#Fourier's formula for 2π-periodic functions using sines and cosines. And the series index goes from 0 to ∞, as you have said. An alternative series is explained at Fourier_series#Exponential_Fourier_series. Each a,b, pair is replaced by a complex number, and the series index goes from -∞ to ∞. When f(x) is a real-valued function, the calculation:
is equivalent to:
In that case, is just the complex conjugate of
and
simplifies to:
--Bob K (talk) 15:43, 6 April 2013 (UTC)


The DFT implies that your starting point is not "a sample of f(x)", but rather a sample (subsequence) of the infinite sequence of "samples" of f(x). (Or equivalently, "discrete samples of a sample (sub-interval) of f(x)".) If the infinite sequence happens to be periodic, then the DFT is equivalent to a DTFT (see DTFT#Periodic_data). Otherwise, the DTFT is a continuous function, and the best the DFT can do is provide a discrete set of samples of it (see DTFT#Sampling_the_DTFT). But in neither case can we exactly compute the Fourier series coefficients (cn). That requires the continuous f(x) function. The difference is depicted by the two images on the right-hand side of File:Variations_of_the_Fourier_transform.tif.
--Bob K (talk) 17:05, 4 April 2013 (UTC)

Converges rapidly?[edit]

The page currently contains this text:

...yields an eigenvector of the discrete transform:
  • .
A closed form expression for the series is not known, but it converges rapidly.

But I understand as being the set of gaussian integers - complex numbers with integer valued real and imaginary parts. And while this series would converge rapidly if represented regular integers, complex integers mean that will contain arbitrarily large values. In other words, this sum diverges rapidly. Alternatively, if has some other significance this should probably be documented instead of assumed. --Raudelmil (talk) 08:20, 21 April 2014 (UTC)

Amplitudes correct?[edit]

The part saying that amplitude of the -th sinusoid is equal to:
...
Should it not be:
for
for
?

Plancherel and Parseval theorems[edit]

It seems that in this article the Plancherel and Parseval theorems are used interchangeably and inconsitently. In the subsection "The Plancherel theorem and Parseval's theorem" it is stated that the Plancherel theorem is a special case of the Parseval's theorem where y = x and in the subsection on "The unitary DFT" it is stated exactly the other way around where Parseval's theorem is a special case of the Plancherel Theorem (where again y = x). As I understand it, both the Parseval's theorem and Plancherel theorem talk about the "general" case where the inner product <x,y> is preserved under the fourier transformation, the difference being that the Parseval's theorem talks about the summability and unitarity of the Fourier series whereas the the Plancherel theorem more generally talks about the unitarity of any Fourier transform (continuous, multi dimensional etc.).

Doubbleb (talk) 09:29, 18 August 2015 (UTC)

j in definition[edit]

Why there j in definition? Should not there be imaginary unit (i)? — Preceding unsigned comment added by Av life (talkcontribs) 11:28, 24 September 2015 (UTC)

I agree. It is confusing. If I actually knew what j was supposed to be, I'd add it myself. — Preceding unsigned comment added by 137.150.38.16 (talk) 17:04, 20 October 2015 (UTC)

Engineers (and sometimes physicists) often use j instead of i to refer to the imaginary unit. This is to avoid confusion with i meaning electrical current. 96.55.224.124 (talk) 05:02, 3 January 2016 (UTC)

Input length infinite or finite?[edit]

The article opens by saying "the discrete Fourier transform (DFT) converts a infinite list of equally spaced samples of a function into the list of coefficients of a finite combination of complex sinusoids", but then goes on to say "[the DFT] deals with a finite amount of data". These statements are contradictory; it appears to be the first statement which is in error. --96.55.224.124 (talk) 05:05, 3 January 2016 (UTC)

That was this 22 Dec. vandalism. Thanks. Fixed. Dicklyon (talk) 05:48, 3 January 2016 (UTC)

continuous function and its fourier transform[edit]

Fourier transform of a gaussian is a gaussian right? KorgBoy (talk) 23:13, 12 May 2016 (UTC)

Example[edit]

Mr Author,

Please let me express my sincere gratitude for your article, and make a comment: at least one example would be very helpful.

With regards and friendship, Georges Theodosiou, chretienorthodox1@gmail.com88.188.110.51 (talk) 13:22, 27 June 2016 (UTC)

Lots of examples here: Window_function#A_list_of_window_functions. The input functions are the blue-filled graphs, followed by a long sequence of zeros, which improves the resolution of the graphs labelled "Fourier transform", which are the DFT output functions.
--Bob K (talk) 14:06, 29 June 2016 (UTC)

Amplitude is double of the shown[edit]

Mr Author,

Please accept my many thanks for you responded to my request for examples.

Now let me say that Wikipedia's definition for the amplitude of sine wave as function of time is:

  • A = the amplitude, the peak deviation of the function from zero.

Accordingly, amplitude of sinusoid's frequency is (as another commentator has suggested):

for

With regards and friendship, Georges Theodosiou, chretienorthodox1@gmail.com 109.26.246.124 (talk) 15:02, 1 July 2016 (UTC)

What you propose is called "peak-to-peak" deviation. The article has it right.
--Bob K (talk) 02:48, 2 July 2016 (UTC)
Mr Author, please let me express my sincere gratitude for you replied.
I stand on my position because every example in the literature shows it true. For get "peak-to-peak" deviation, one has to multiply by 4.
With regards and friendship, Georges Theodosiou, chretienorthodox1@gmail.com 109.26.246.124 (talk) 09:36, 2 July 2016 (UTC)
Consider the example Then:
And your belief is that its amplitude is . Is that right?
--Bob K (talk) 12:09, 2 July 2016 (UTC)
Mr Author, please let me again express my sincere gratitude for you replied again, and permit me following question:
My dear Teacher (he teaches me through his book "understanding DSP") Mr Lyons, in his example (in section 3.1 UNDERSTANDING THE DFT EQUATION 3.1.1 DFT Example 1) samples and performs an 8-point DFT on a continuous input signal containing components at 1 kHz and 2 kHz, expressed as
x(t) = sin(2π . 1000 . t) + 0.5sin(2π2000 . t + 3π/4).
It is clear, amplitude (from 0 to peak) of first frequency (1 khz) is 1, and of second (2 khz) is 0.5.
Then he calculates X(1) and find Re = 0 and Im = -4. Squared and added yied 0 + (-4)^2 = 0 + 16 = 16. Its positive root is 4 that he calls magnitude. If you divide by number of samples N = 8 you get 0.5 that is half of the amplitude.
Then he calculates X(2) and find Re = 1.414 and Im = 1.414. Squared and added yield 4. Its positive root is 2 that he calls relative amplitude. If you divide by number of samples N = 8 you get 0.25 that is half of the amplitude.
Is that right?
I remain with regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com109.26.246.124 (talk) 13:15, 2 July 2016 (UTC)
Yes, that is correct. Each of the complex amplitudes (e.g. at X(1) at X(7)) that contribute to the sin(2π . 1000 . t) term with amplitude 1 will have half of that amplitude, since sin(2π . 1000 . t) = (exp(i2π . 1000 . t) - sin(-i2π . 1000 . t))/2. Dicklyon (talk) 14:51, 19 July 2016 (UTC)
Mr Dicklyon please let me express my sincere gratitude for your straight answer, and make a comment: X(1) exists in the signal, X(7) does not exist and I could compute X(1) without computing X(7). Then X(1)'s amplitude is
.
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com 85.14.164.161 (talk) 13:55, 27 July 2016 (UTC)
No, that's wrong. Both X(1) and X(7) exist in the signal. They are the positive- and negative-frequency complex exponentials that add up to make the real sinusoidal input. Dicklyon (talk) 00:46, 28 July 2016 (UTC)
It might be helpful to explain that sin(2π n 1/N) is not a basis function of the DFT. And any time that happens, it requires multiple basis functions to represent such a sequence. In this case, the required number is 2. If the input sequence was sin(2π n (1½)/N), all N basis functions would be needed.
Similarly, if the basis functions of a transform were sin(2π n k/N) and cos(2π n k/N), k=0,1,2,...,N-1, it would require only 1 basis function to represent sin(2π n 1/N), and it would require 2 basis functions to represent   It would also take 2 basis functions to represent
--Bob K (talk) 13:08, 28 July 2016 (UTC)
We're getting into some interesting semantics now. The statement that the basis functions    and    "exist" in    really just means that they are not orthogonal functions. Therefore, it can also be said that    "exists" in    and    Do the vectors (1,1) and (1,-1) "exist" in the real number "1"? Or does "1" exist in the vectors? Anyhow, Georges said "I could compute X(1) without computing X(7)." My answer to that would be yes, because you know that the input sequence is real-valued, which makes X(7) redundant. But so what? The amplitude of X(1)/N is still just ½.
--Bob K (talk) 00:36, 29 July 2016 (UTC)

I'm sorry, but this is not a place for discussing your textbook. We're discussing a claim made in the article. I asked you a simple question, meant to be illustrative. But you ignored it. You will learn more by focusing on one question at a time than by changing the subject. Do you understand the question?
--Bob K (talk) 15:54, 2 July 2016 (UTC)

The answer to my question is that the amplitude of is 1, not 2. Every "example in the literature" will verify that. So the formula in the article is correct. Your real question has to do with the interpretation of a DFT coefficient, which is relevant here. A DFT coefficient always multiplies a term of the form , not . In your textbook's example, you could express as , which has two DFT components with amplitudes of ½. Their amplitudes are halved, because there are two of them.

Another question you seem to have is the term "relative amplitude". What your textbook means is that the DFT coefficients .5 and .25 (or 4 and 2) have the same ratio as the amplitudes of and .
--Bob K (talk) 19:02, 2 July 2016 (UTC)

Mr Author, let me express my sincere gratitude for your two answers, my sorrow for my answer's delay, and also my sorrow for I do not understand your question nor your answers. I understand what I have learned from the examples in my Teacher's book and in many University's courses online:
is half of frequency's amplitude.
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com62.160.151.126 (talk) 14:15, 5 July 2016 (UTC)


Please look more closely at this excerpt from the article, especially the expression I colored red:

In this interpretation, each is a complex number that encodes both amplitude and phase of a sinusoidal component    of function The sinusoid's frequency is k cycles per N samples.  Its amplitude is:

Your textbook's meaning of "sinusoid" is the real-valued sine function. And as I said above, it comprises 2 DFT components with amplitudes of ½.
--Bob K (talk) 16:34, 5 July 2016 (UTC)

You should also look ahead in your textbook to Section 3.4, which states: "The 1/N scale factor in Eq. (3-18) makes the amplitudes of X'(m) equal to half the time-domain input sinusoid's peak value." They are not equal, and our article is referring to X'(m).
--Bob K (talk) 13:14, 6 July 2016 (UTC)

Mr Author, please let me again express my sincere gratitude for your answers given that you did not answer same question by Gentleman in "Amplitudes correct?" section. I ignored the beginning of your definition "The sequence of N complex numbers" and regarded them real. When I study later sections in my dear Teacher's book I take into account your suggestions.
With regards and friendship, Georges Theodosiou, the Straw Man, chretienorthodox1@gmail.com82.127.83.8 (talk) 13:12, 13 July 2016 (UTC)

I think you still don't understand. When you sample a real-valued sine function and perform a standard DFT, the input sequence has zero-valued imaginary parts. That produces the DFT of a sine function, not the DFT a "complex sinusoid". You and I and your textbook are all talking about the same thing: the DFT of a real-valued sine function input. Your confusion has to do with the output amplitude. If the input is , the output is a single non-zero DFT component with an amplitude of 1. But if the input is , with zero-valued imaginary parts, the output is two non-zero DFT components and , with amplitudes of ½. In order to deduce the amplitude of the original function from , you have to multiply by 2 (as you have noticed), but the amplitude of remains only ½.
--Bob K (talk) 16:35, 13 July 2016 (UTC)

Mr Author, please let me again express my sincere gratitude for still answer my comments. I understand you mean in the example of my Teacher, the alias frequency 7 khz. Do you mean that?
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com92.140.217.216 (talk) 08:55, 15 July 2016 (UTC)

Yes, that is what I mean. Please note that I am removing my previous comment at this location. You are correct to refer to 7 kHz as an alias frequency, because sin(2π 1000 n/8000) = sin(2π 7000 n/8000 + π).  If the sinusoid was complex-valued, it would not be an alias frequency. I'm sorry if my comment was confusing.
--Bob K (talk) 18:43, 20 July 2016 (UTC)

Mr Author, please let me express my sincere sorrow for I still do not understand you, and say my last word in french: Au revoir!
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com14:31, 19 July 2016 (UTC)193.251.178.42 (talk)
OK, and good luck. Have faith that your textbook and this article are in agreement. But for some reason, you are reading them differently.--Bob K (talk) 21:00, 19 July 2016 (UTC)
Mr Author,
Please let me say reason is difference in expression. Yours is rigorous without arithmetic examples, my Teacher's is easy with arithmetic examples. This difference is critical for someone just learning a subject.
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com 176.189.60.4 (talk) 06:40, 16 August 2016 (UTC)

Bob K has explained the disconnect clearly enough, but it might be good to change a few words in the sentence " is a complex number that encodes both amplitude and phase of a sinusoidal component    of function " to not call the complex exponential a sinusoidal component. Perhaps calling it a "complex sinusoidal component" would go some way toward preventing readers tripping on this? Though it doesn't look like it would have helped this reader much. Dicklyon (talk) 14:51, 19 July 2016 (UTC)

Mr Author, please let me say that at last I understand you after have read your comment by 18:43, 20 July 2016 (UTC). I understand 7 khz and 6 khz frequencies, (in my Teacher's example) are alias because are reflections, according to Teacher nomenclature, of existing frequencies, 1 khz and 2 khz with Nyquist frequency (the mirror) 4 khz. Now I suggest you insert following:
When input signal is real numbers then kth sinusoidal's amplitude is: 2·.
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com 85.14.164.161 (talk) 08:25, 27 July 2016 (UTC)
Sorry, no. You are still alluding to the example in your book, which is not in this article. I.e., you are assuming that the input sequence is the sum of one or more real-valued sinusoids whose frequencies are integer multiples ("harmonics") of 1/N. This article does not discuss that example. What it says is that [for any input sequence] the inverse DFT output sequence (formula Eq.2) is the sum of one or more complex-valued sinusoids whose frequencies are integer multiples of 1/N.
--Bob K (talk) 20:28, 27 July 2016 (UTC)
Mr Author, please let me express my sincere sorrow for the delay in my response, and make a comment. I'm not aware of complex input signals but Equation 2 seems to me, complex Fourier series, and in your Fourier series's definition [[1]], you are referred to real only. It confuses me, although Professors in their courses online teach complex Fourier series.
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com 109.190.1.196 (talk) 13:05, 5 August 2016 (UTC)
That is a good point, and I understand your confusion. What our Fourier series article should mention is that in the formula:
s(x) can be complex, in which case the relationship is no longer generally true.
--Bob K (talk) 15:57, 5 August 2016 (UTC)

Mr Author, please let me say you here, my understanding of half amplitude obtained by Fourier transform, when input is single (real) sinusoid. I consider the simplest input signal (e.g. tuning fork's), , and perform continuous Fourier transform for x = kπ.

1. Input signal multiplied by cos(x) and integrated, yields 0, due to relative phase rad.

2. Input signal multiplied by -sin(x) (input's opposite and imaginary part in testing complex sinusoid) is shortened in wide (as well in length) by half (peak-peak from 2 become 1), and lies just below x axis, as it seen by graphing calculator. Apparently, horizontal line by -0.5, is axis of symmetry, and its integral (surface) is equal to the surface of rectangular -0.5 by x. Its magnitude (absolute value) is 0.5x. Divided by x yields 0.5, half the amplitude.

Reason, apparently, is that, numbers in range [0, 1] multiplied by their opposites move to [-1, 0], and numbers in [-1, 0] multiplied by their opposites remain in this range. So, the opposite sinusoids multiplied lie in [-1, 0] that is half the original wide. However, product is sinusoid shaped, so that horizontal line by its half, is axis of symmetry. So far, this is my research.

With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com 176.189.60.4 (talk) 08:09, 16 August 2016 (UTC)

Apparently we are finished discussing this article. You might not have sufficient prerequisite background to understand the explanations, but there are no contradictions between the article and your textbook. Keep trying, but this talk page is not an appropriate forum for your progress reports. Good luck to you.
--Bob K (talk) 01:05, 17 August 2016 (UTC)
Mr Author, please let me express my sicere gratitude for the discussion, and wish "à ta santé". Au revoir.
With regards and friendship, Georges Theodosiou, The Straw Man, chretienorthodox1@gmail.com
P.S. Because my english are poor and my math elementary (I am Greek secondary school graduate), please let me authorize you edit my messages - especially that one by 08:09, 16 August 2016 (UTC) - as you think. G.T. 176.189.60.4 (talk) 05:48, 17 August 2016 (UTC)