3 ms·

This was a reasonable explanation of the Fourier Transform, but sadly, not the Fast Fourier Transform. To me the easy part has always been understanding that m

by sireat 16y ago

This was a reasonable explanation of the Fourier Transform, but sadly, not the Fast Fourier Transform. To me the easy part has always been understanding that many sines(and cosines) of different frequencies can make up pretty much any periodic signal and that time and frequency domains map back and forth without losing information. What I still do not fully understand is how exactly FFT algorithm works. Article does not explain it and even this excellent guide: http://www.dspguide.com/ch12/2.htm http://www.dspguide.com/ch12/2.htm skips over it, saying it is too complex(pun intended). My very rough understanding is as follows: Discrete time signal is taken, (optionally padded with 0s to next power of 2) Real representation is decomposed to complex (numbers not difficulty) representation, as far as I understand this is done via interpolating signals and then further dividing signal in half. Why? Not sure. Next part is even more mysterious. Magic algorithm here to find frequencies? Signal is now in frequency domain, just need to show it in as real numbers not complex. So what is the magic step?

jacquesm 16y ago
The magic, as far as I understand it, and it has been many years since I last looked at Fourier transformation is that there is no step. That's why it is called a transform. The 'mapping' of the frequency domain is simply a function of the original sample rate. So if you know your sample rate you'll know the center frequency of each 'bucket'.
- gjm11 16y ago
  I think you've misunderstood the question; it was "step" in the sense of "operation" or "inference in a proof", not in the sense of "difference between successive values". sireat wants to know why the FFT works, not what the relationship is between sample spacings in the input and the output.
  - jacquesm 16y ago
    Ah ok, I see. I got thrown off by the use of the words 'magic algorithm here to find frequencies', I thought that implied he was searching for what absolute frequency was tied to which bucket. Sorry. Also, the 'imaginary' bit contains the phase information, if you are only interested in the frequency domain you could discard this, but if you ever want to reconstruct the original (or if you want to construct a changed signal, such as after filtering) then you'll need that phase information. So you'll need to keep the data in its 'complex' form if you want to do anything more than naive analysis.
    - gjm11 16y ago
      Nonono, don't discard the imaginary part! If you don't care about phase information, use sqrt(real^2+imag^2) to give you the magnitude of each component.
    - iskander 16y ago
      Uhh...if I remember correctly then the Fourier transform is: F(w) = <f(x), cos(2 pi w x)> + i <f(x), sin (2 pi w x) > (where <_, _> is the inner product between functions, x is a time and w is a frequency). So the imaginary component is not the phase but how much of your function is explained by a sine wave. To get the phase you should take the angle of each complex number (and to get the amplitude you take the magnitude).
yummyfajitas 16y ago
The "magic step" is simply an algebraic observation. I'll use python/scipy notation, since HN has no latex. Let f = [ f1, f2, ..., fN] be the sequence you want to take the DFT of (has size N = power of 2). Let x = arange(0,N) = [0,1,...,N]. More numpy notation: exp(x) = [exp(0), exp(1), ..., exp(N)], and x * y = [x1 * y1, x2 * y2, ..., xN * yN]. The DFT of f can be written as: F[k] = sum( exp(2 pi i k x /N) * f) = sum( exp(2 pi i k x /N)[0::2] * f[::2]) + sum( exp(2 pi i k x /N)[1::2] * f[1::2]) I.e., all I did was break up the sum into a sum over the odd indices and the even indices. The second sum can be rewritten as exp(2 pi i / N) sum(exp(2 pi i k x /N)[0::2] * f[1::2]) . So we've now written F[k] as a sum of two DFT's: the DFT over the odd indices and the DFT over the even indices. Each of these DFT's has size N/2. That's the divide step, now you just conquer by working down recursively.
deleted 16y ago
[deleted]

by sireat 16y ago

jacquesm 16y ago

The magic, as far as I understand it, and it has been many years since I last looked at Fourier transformation is that there is no step. That's why it is called a transform. The 'mapping' of the frequency domain is simply a function of the original sample rate. So if you know your sample rate you'll know the center frequency of each 'bucket'.

gjm11 16y ago
I think you've misunderstood the question; it was "step" in the sense of "operation" or "inference in a proof", not in the sense of "difference between successive values". sireat wants to know why the FFT works, not what the relationship is between sample spacings in the input and the output.
- jacquesm 16y ago
  Ah ok, I see. I got thrown off by the use of the words 'magic algorithm here to find frequencies', I thought that implied he was searching for what absolute frequency was tied to which bucket. Sorry. Also, the 'imaginary' bit contains the phase information, if you are only interested in the frequency domain you could discard this, but if you ever want to reconstruct the original (or if you want to construct a changed signal, such as after filtering) then you'll need that phase information. So you'll need to keep the data in its 'complex' form if you want to do anything more than naive analysis.
  - gjm11 16y ago
    Nonono, don't discard the imaginary part! If you don't care about phase information, use sqrt(real^2+imag^2) to give you the magnitude of each component.
  - iskander 16y ago
    Uhh...if I remember correctly then the Fourier transform is: F(w) = <f(x), cos(2 pi w x)> + i <f(x), sin (2 pi w x) > (where <_, _> is the inner product between functions, x is a time and w is a frequency). So the imaginary component is not the phase but how much of your function is explained by a sine wave. To get the phase you should take the angle of each complex number (and to get the amplitude you take the magnitude).

yummyfajitas 16y ago

The "magic step" is simply an algebraic observation. I'll use python/scipy notation, since HN has no latex. Let f = [ f1, f2, ..., fN] be the sequence you want to take the DFT of (has size N = power of 2). Let x = arange(0,N) = [0,1,...,N]. More numpy notation: exp(x) = [exp(0), exp(1), ..., exp(N)], and x * y = [x1 * y1, x2 * y2, ..., xN * yN]. The DFT of f can be written as: F[k] = sum( exp(2 pi i k x /N) * f) = sum( exp(2 pi i k x /N)[0::2] * f[::2]) + sum( exp(2 pi i k x /N)[1::2] * f[1::2]) I.e., all I did was break up the sum into a sum over the odd indices and the even indices. The second sum can be rewritten as exp(2 pi i / N) sum(exp(2 pi i k x /N)[0::2] * f[1::2]) . So we've now written F[k] as a sum of two DFT's: the DFT over the odd indices and the DFT over the even indices. Each of these DFT's has size N/2. That's the divide step, now you just conquer by working down recursively.

deleted 16y ago

[deleted]