††††††††††† This unit introduces the Discrete Fourier Transform as a means for obtaining a frequency based representation of a digital signal.† The special characteristics of the Fast Fourier Transform implementation are described.
††††††††††† When you have worked through this unit you should:
∑ be able to explain what information is represented on a magnitude spectrum and on a phase spectrum of a discrete signal
∑ be able to state the mathematical expression for the Discrete-time discrete-frequency Fourier Transform (DFT)
∑ understand how the direct implementation of the DFT operates
∑ appreciate that the direct implementation of the DFT is very inefficient, and that the Fast discrete-time discrete-frequency Fourier Transform (FFT) provides a more efficient means of its calculation
∑ have a qualitative understanding of the operation of the decimation-in-time form of the FFT
∑ be able to predict how simple sine and cosine signals appear on the DFT in the region from 0 to Fs.
††††††††††† A digital signal of finite duration x[1..N] can be specified in the time domain as a sequence of N scaled impulses occurring at regular sampling instants: each impulse taking on the amplitude of the signal at that instant.† The same signal may also be described as a combination of N complex sinusoidal components X[0..N-1], each of a given frequency and phase, and each being a harmonic of the sampling rate/N.† This representation, called a frequency-domain representation, may be obtained from the time-domain form through the use of the Discrete Fourier Transform or DFT.† The time domain form and the frequency domain form are simply different ways of representing the same digital signal, one is chosen over the other simply in terms of utility for a given purpose.
††††††††††† The Discrete Fourier Transform X(f) of a signal x[1..N] is defined as:
††††††††††† where X[k] is the amplitude of the kth harmonic, where k varies from 0 to N-1 and where k/N represents a fractional frequency value of the sampling rate.† In general X and x can hold complex values, and X will be complex even if x is purely real.
††††††††††† The graph of |X(f)| against frequency is known as the magnitude spectrum.† The graph of arg X(f) against frequency is known as the phase spectrum.
††††††††††† By copying a real digital signal into a complex sequence x[1..N], the DFT has a straightforward algorithmic implementation (shown in ComplexDFT()), using complex multiplication with the complex exponential defined as:
††††††††††† and hence:
††††††††††† We can also define the inverse transform, from the frequency representation X back to the time representation x:
††††††††††† where n varies from 1 to N.† We have chosen to place the scaling factor 1/N in the forward transform, but many authorities place it in the inverse transform.† We choose to place it here because it leads to harmonic amplitudes which are normalised to the sequence length, and hence independent of the amount of signal analysed.† This leads naturally to an equivalence between the energy in the signal and the energy in the spectrum:
††††††††††† The frequency spectrum is often displayed in log magnitude terms in units of decibels (dB), and may be converted using:
††††††††††† From a real signal at a sampling rate Fs, the DFT provides N harmonic amplitudes at frequencies from 0 to .† However the frequencies from 0 to Fs/2 are aliased to the region Fs/2 to Fs, so only the lower N/2 amplitudes are important.
††††††††††† The phase angles may be converted to degrees using:
††††††††††† The Fast Fourier Transform or FFT is simply a particular implementation of the DFT, that gives identical results, but which takes considerably less calculation.† It does this by eliminating a great deal of redundant computation in the DFT in the circumstances when the sequence length N is a power of 2 (i.e. 4, 8, 16, 32, 64, etc).
††††††††††† In a normal DFT, each harmonic amplitude is the result of N complex multiplies with N different complex exponentials - giving a total of N2 multiplies for all N harmonics.† When N is a power of 2, many of these multiplies concern identical numerical multiplicands and many of the complex exponentials are zero or 1.† When redundant computation is removed, the number of multiplies is Nlog2(N) rather than N2 and this represents a very large saving when N is large (e.g. for 1024 samples there is 100 times less calculation).
††††††††††† At the heart of the FFT is a simple algebraic manipulation that takes two input values, performs a multiply operation with a complex exponential and produces two output values.† This basic unit is called a 'butterfly', and for two complex inputs a and b, a frequency W (=2πkn/N), and outputs p and q, the butterfly calculation is
††††††††††† We shall diagram this basic operation as:
††††††††††† This actually represents the DFT of a 2 sample waveform.† Longer waveforms can be processed by combining these butterfly operations with variations on the value of W.† Thus a DFT of an 8 sample waveform x to x can be graphed as:
††††††††††† Where Wj is one of the frequencies in the DFT calculation (=2πj/N). This signal flow graph is the basis of the ComplexFFT() implementation.† To operate the graph, the input signal is shuffled into the spectrum array in an order known as bit-reversed addressing.† Then each column of butterfly operations is performed, so that the signal 'moves' left-to-right through the graph, turning into the DFT spectrum.
††††††††††† A more mathematical explanation of the FFT is also available.
††††††††††† The FFT routines have not been written for maximum efficiency.† Note that the calculation of the bit-reversed addresses and the values of the complex exponentials need only be performed once for a given size of transform.† Since typical use of the FFT is the repeated use of the transform on constant lengths of waveform,† these tables may be pre-calculated and stored.
††††††††††† Meade & Dillon, Signals and Systems, Chapter 7, pp130-144.
††††††††††† Lynn & Fuerst, Introductory Digital Signal Processing, Chapter 7.
††††††††††† Orfanidis, Introductory Signal Processing, Chapter 9.
††††††††††† Algorithm 5.1 Complex to Complex Discrete Fourier Transform
††††††††††† Algorithm 5.2† Complex Fast Fourier Transform
††††††††††† Example 5.1 Complex Discrete Fourier Transform
††††††††††† Example 5.2 Complex Fast Fourier Transform
5.1†††††† The inverse DFT provides a simpler method to synthesize a square wave: set up the spectrum of a square wave and call ComplexIDFT().† Set up a spectrum as follows:
††††††††††††††††††††††† Spectrum(1000,0.05);†††††††† // 0..19,980Hz in 1000 steps
†††† Then put in the odd harmonics of 100Hz with appropriate amplitudes (amplitude of nth harmonic is just 1/n).† That is, put in amplitudes of 1.0 at spectrum position 5, 0.33 at position 15, 0.2 at position 25, etc.† Donít forget to put in the mirror images at positions 995, 985, 975, etc.† Plot your spectrum and the result of the inverse DFT.
††††††††††† How would you change your solution to use an FFT?† Why might you want to?
5.2†††††† Modify Examples 5.1 and 5.2 to explore the differences between an exact DFT of a 40 point test waveform and the FFT of the same waveform suffixed with 24 zeros.† Plot a graph showing the magnitude spectrum and the phase spectrum of the same signal analysed in these two ways.
††††††††††† What differences are there between an FFT of a 64 point waveform and an FFT of the same waveform appended with 64 zeros?