16-05-2013, 04:41 PM
The Discrete Fourier Transform: Notes
The Discrete Fourier.pdf (Size: 126.18 KB / Downloads: 35)
Definition
The Discrete Fourier Transform is derived from the normal definition of the Fourier Transform of a series (see the introductory text on the Fourier Transform). Suppose that we are given a (time) series with running from , then such a series can be considered 'embedded' in an infinite series running from 0, just by padding it with zeros, and the normal Fourier Transform of a unilateral series can be taken. The result is a continuous function of the 'angular frequency ', called the 'continuous spectrum of the series' and we have replaced a finite series with a continuous function on the unit circle. This would be hardly efficient! However, taking N samples of that complex function at regular intervals along the unit circle of the complex plane converts it again to an -dimensional vector. Remark that a real sequence now becomes complex, some additional reduction is possible - see further. We call the DFT the 'discrete spectrum' of the series . ]
Matrix-vector form
Once the discretization is done, we have obtained a transformation of an N-dimensional (complex) vector into another one. This transformation is linear, and hence can be represented as a matrix-vector product. Check that the matrix-vector multiplication corresponds indeed to the Discrete Fourier Transform defined in the previous sheet!
Central property of NF
The Discrete Fourier Transform involves the Fourier Transformation Matrix shown on the transparancy. This is a square complex matrix with special properties! One central property is that the product of this matrix with its Hermitian Conjugate evaluates to N times a unit matrix. Put differently, the matrixNF*NFNFN1 is said to be 'unitary', which means that each row (or column) has unit square norm and is orthogonal on any other row (respect. column). The inverse of a unitary matrix is particularly simple, it is equal to its Hermitian Conjugate. See the Mathematical Introduction for further information on basic mathematical properties of matrices! The evaluation of the row-column products in amounts to the summation of a geometric series with 'ratio' W.
Symmetries
We saw already that the DFT is somewhat redundant when a real time vector is used since it has the same number of samples but is complex. We find the redundancy back in the Fourier domain by showing that the spectrum of a real vector is (conjugate) symmetric around the midpoint, or to put it more precisely