Talk:Discrete Fourier transform

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 (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):

--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). (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:
x_n = \frac{1}{6} \sum_{k=0}^{6-1} X_k \cdot e^{i 2 \pi k n / 6},
the first term becomes:
X_0 \cdot \underbrace{e^{i 2 \pi 0 n / 6}}_{e^{-i 2 \pi 0 n / 6}},
and the last five terms become:
X_{6-L} \cdot \underbrace{e^{i 2 \pi (6-L) n / 6}}_{e^{-i 2 \pi L n / 6}},
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:
c_n = \frac{1}{2\pi}\int_{-\pi}^{\pi} f(x) e^{-inx}\, dx.
is equivalent to:

c_n &= \underbrace{\operatorname{Real}(c_n)}_{\text{real part of output}} + i \underbrace{\operatorname{Imag}(c_n)}_{\text{imag part of output}} = \frac{1}{2\pi}\int_{-\pi}^{\pi} [\underbrace{f(x)}_{\text{real part of input}}+i\underbrace{0}_{\text{imag part of input}}]\cdot e^{-inx}\, dx\\
&= \frac{1}{2\pi}\underbrace{\int_{-\pi}^{\pi} f(x)\cdot \cos(nx) dx}_{\pi a_n} - i\cdot \frac{1}{2\pi}\underbrace{\int_{-\pi}^{\pi} f(x)\cdot \sin(nx) dx}_{\pi b_n}
In that case, c_{-n} is just the complex conjugate of c_{n},
f(x) = \sum_{n=-\infty}^ \infty c_n e^{inx}
simplifies to:

f(x) &= c_0 + \sum_{n=1}^{\infty} [\underbrace{c_n e^{inx} + (c_n e^{inx})^*}_{2\cdot \operatorname{Real}(c_n e^{inx}) }]\\
&= c_0 + \sum_{n=1}^{\infty} 2\cdot[\operatorname{Real}(c_n)\cdot cos(nx)-\operatorname{Imag}(c_n)\cdot sin(nx)]
--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:
  • F(m) = \sum_{k\in\mathbb{Z}} \exp\left(-\frac{\pi\cdot(m+N\cdot k)^2}{N}\right).
A closed form expression for the series is not known, but it converges rapidly.

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