Fourier Transform
Is the quintessential frequency-analysis function which can map continuous time-domain input into frequency-domain within the fourier-series at \(N\) evenly spaced discrete frequencies.
Note: This transformation is [see page 13, lossless]. Note: You can find an intuitive description of fourier, here.
There're several [see page 17, variants] of the general FT algorithm:
| Variant | Description |
|---|---|
| Fourier Transform | Continuous time signals to continuous frequency domain. |
| Discrete Fourier Transform | Transform discrete time signals to the discrete frequency domain. |
| Fast Fourier Transform | An efficient algorithm for DFT (with bit-reversal). |
| Discrete Time Fourier Transform | Transform discrete (sampled) time signals to the continuous frequency domain. |
Frequency Analysis
Fourier transform works by using both cosine and sine correlation. It has been shown that Cosine Correlation and Sine Correlation can both do frequency-analysis except both only work accurately when the target signals are in-phase with their respective waveforms... however a sine-wave and cosine-wave are always \(90^{\textdegree}\) out of phase with each other and the correlation of each of them is proportional to a cosine and sine wave respectively.
Fourier transform takes advantage of this fact and the trig identity: \[ \cos^2(n) + sin^2(n) = 1 \]
We use the derived correlation formulas to find that:
\begin{align*}
cosinecorrelation = \alpha \times \cos(\phi) \
sinecorrelation = \alpha \times \sin(\phi) \
\end{align*}
We find that: \[ ({(\alpha \times \cos(\phi))}^2 + {(\alpha \times \sin(\phi))}^2) = \alpha^2 \]
With this we can derive the amplitude of the current sinusoid component (independent of phase) as \[ \alpha = \sqrt{(\mathrm{cosinecorrelation})^2 + (\mathrm{sinecorrelation})^2} \] We can also find the phase of this component by \[ \phi = \tan^{-1}(\frac{sinecorrelation}{cosinecorrelation}) \]
These two equations [see page 6, define] the Discrete Fourier Transform.
Now we can use essentially the same process as cosine-correlation but use this formula instead to extract the frequencies in a signal.
You can try examples of the DFT [see page 18, here].
Real and Imaginary Parts
The DFT is [see page 8, often] expressed using complex number notation. This is because the formula for the magnitude and phase of complex numbers has the same [see page 7, form] as the above ones for DFT.
The only relevant result of this form is that we can reduce our correlation function from the product of the input signal and some combination of sine and cosine waves etc. to a variant of Eulers Formula.
\[ S_p = \sum^{N-1}_{s(nT) \times e^{-j(\frac{2 \pi np}{N})}}, p = 0,1,\ldots,{N-1} \]
Observations ([see page 9, Spectrum Symmetricity])
- The magnitude spectrum for a DFT transformed signal is symmetric about \(\frac{1}{2T} Hz\).
- The phase spectrum for a DFT transformed signal is anti-symmetric about \(\frac{1}{2T} Hz\).
These observations are taken advantage of by for the more [see page 18, efficient] FFT algorithm.