Read long2.PDF text version
HUNT ENGINEERING Chestnut Court, Burton Row, Brent Knoll, Somerset, TA9 4BP, UK Tel: (+44) (0)1278 760188, Fax: (+44) (0)1278 760199, Email: [email protected] URL: http://www.hunteng.co.uk
Fourier Transforms
Abstract
A Fourier Transform is a mathematical tool that provides a means of transforming information from the time domain to the frequency domain, and vice versa. It is a frequent requirement in signal processing, for the detection and analysis of frequency components that are of interest, even when accompanied by unwanted stronger frequency components. A Fast Fourier Transform is only one of the many available algorithms and techniques for achieving the transformation with a considerably smaller amount of mathematical operations and hence is much faster than the direct implementation. The applications for FFTs are numerous and diverse.
THE BASICS ........................................................................................................................................................ 3 THE FOURIER SERIES .......................................................................................................................................... 3 THE FOURIER TRANSFORM ................................................................................................................................. 3 THE DISCRETE FOURIER TRANSFORM ................................................................................................................ 3 THE FAST FOURIER TRANSFORM............................................................................................................... 5 FFTS OF REALVALUED SEQUENCES.................................................................................................................. 5 Two independent RealValued Sequences of length N .................................................................................. 6 RealValued Sequence of length 2N .............................................................................................................. 6 WINDOWING ....................................................................................................................................................... 7 THE SLIDING FFT ............................................................................................................................................... 8 BENCHMARKS ................................................................................................................................................... 9 SUMMARY......................................................................................................................................................... 10 APPENDIX 1. DERIVATION OF DISCRETE FOURIER TRANSFORM ................................................. 11 APPENDIX 2. DERIVATION OF RADIX 2, INPLACE FFTS ................................................................... 12 THE RADIX 2, INPLACE, DISPLACEMENTINTIME FFT ................................................................................... 12 Example of 8point, Radix2, DIT FFT. ....................................................................................................... 13 THE RADIX 2, INPLACE, DISPLACEMENTINFREQUENCY FFT........................................................................ 15 APPENDIX 3. DERIVATION OF FFT OF TWO REAL SEQUENCES ..................................................... 16 APPENDIX 4. DERIVATION OF FFT OF ONE REAL SEQUENCE OF LENGTH 2N .......................... 17 APPENDIX 5. DERIVATION OF THE SLIDING FFT................................................................................. 18
2
Fourier Transforms V1.0 0899
The Basics
The Fourier Series
Any periodic signal, f(t), maybe expressed as a summation of simple sines and cosines of frequencies that are integer multiples of the fundamental frequency of f(t).
n=
f(t) =
n = 
F(n) e
jnw0t
where 0 = 2f0 = 2/T, T being the period of the signal f(t), and j = (1). It can be shown that the frequency coefficients F(n) can be found from the following integral:
T/2
F(n) = 1/T
f(t) e jnw0t dt
T/2
A trivial example would be the case of a square wave of magnitude 1 and frequency 1 radian/sec. This becomes f(t) = (4/)[ sin(t)  1/3 sin(3t) + 1/5 sin(5t)  1/7 sin(7t) ... ] The equation for F(n) giving: F(n) = (2/n) (1)
((n1) /2)
for odd n,
F(n) = 0 for even n, giving us discrete frequency spectra for the timecontinuous input.
The Fourier Transform
Where a continuous frequency spectrum is required, the progression from Fourier Series analysis to the Fourier Transform is made. This is achieved by letting the period T become progressively larger, so that the discrete frequency results become closer together until they merge into one frequencycontinuous result. For the general case, this is found from the following integral:
F(w) =
f(t) e jwt dt

The Discrete Fourier Transform
In the world of digital signal processing, the time domain information is not available in continuous form; it is sampled. That is, the information is presented as a stream of discrete samples taken at regular intervals in time. For example, a 40MHz A/D generates a sample of the analogue input signal every 25nS. What the signal does in between samples, is completely unknown. Furthermore, it is impossible to capture information from t =  to t = +. By making the assumption that the time domain information eventually repeats itself, i.e. it is periodic, the Fourier Transform degenerates to a sum of discrete frequency components as derived in Appendix 1.
3
Fourier Transforms V1.0 0899
n = N1
F(k) =
n=0
f(n) WN
nk
where WN = e
j2/N
where N is the number of samples within one fundamental period. N = T0/Ts This is the Npoint Discrete Fourier Transform. It takes N discrete timedomain samples, (a noninfinite number of them), and generates a spectra of N discrete frequency values. The FFT is derived from this. As a simple example, consider frequency bin 3 of the 8point DFT, [F(0), F(1),...F(7)], of the 8 input samples [f(0), f(1),...f(7)]. F(3) = f(0) + f(1) W8 + f(2) W8 + f(2) W8 + f(4) W8 + f(5) W8
2
3 6 9 12 15
+ f(6) W8
18
+ f(7) W8
21
It can be seen that to calculate all N frequency outputs of an Npoint DFT requires N multiplications, and (N  N) complex additions.
2
complex
4
Fourier Transforms V1.0 0899
The Fast Fourier Transform
FFTs perform exactly the same task as the DFT, but are able to dramatically reduce the amount of complex arithmetic required to do so, by taking advantage of some of the symmetries, repetitions and redundancies within the transform. There are many different forms of FFT algorithms, all with their advantages and disadvantages. The RADIX of the transform is the number of samples grouped together when performing the next calculations. The radix is normally a small power of two, e.g. 2 or 4. A larger radix transform has the advantage of a slightly smaller number of calculations required, but as the total number of points of the transform must be a power of the radix, the disadvantage is that transforms of certain sizes may not be possible. E.g. radix4 transforms can be 4point, 16point, 64point, 256point, 1024point, etc. A 512point transform for example, must be radix2. An inplace FFT algorithm is one that overwrites its input samples with the results that it generates at each stage or pass. This has the disadvantage that the original data is lost, but has the advantage of needing less memory space. This is important if the calculations are to be carried out on data in the fast internal memory, and is the reason that inplace algorithms are the most popular. Inplace FFT algorithms work with either the input samples (in the case of decimationintime FFT's), or the output samples (in the case of decimationinfrequency FFT's), jumbled into bitreversed order. I.e. decimationintime transforms need their input samples to be swapped into bitreversed order prior to the transform which gives normalorder results, and decimationinfrequency transforms use normal ordered input samples and generate their output samples in bitreversed order. However, this overhead is insignificant when compared to the transform itself. The derivations of most of the standard FFTs, see Appendix 2, start with the basic form:
n = N1
Fk =
n=0 th
x(n) W N
nk
where Fk is the k frequency output (or bin) that is to be calculated, x(n) is the n input sample, N is the size of the transform, and W N = e
th
j2/N
It can be seen in the derivation of both the DIT and DIF Radix 2 FFTs, that there are N/2 complex multiplies and N complex additions in each pass. Therefore the total number of complex multiplies is N/2 log2 N, and the total number of complex additions is N log2 N. For a 1024point FFT this makes 5120 complex multiplies and 10240 complex additions, a significant saving in processing over the DFT which would take 1048576 complex multiplies and 1047552 complex additions to get the same results. Over 200 times less multiplies, and over 100 times less additions!
FFTs of RealValued Sequences
All Fast Fourier transforms involve complex arithmetic in their operation. The coefficients, or "twiddle factors" as they are known, are complex, resulting in complex results at each pass of the transform. It is therefore natural that `standard' transforms assume complex input samples also. For many applications, this is just what is needed. A radar set, for example, will typically present I and Q channels for processing. However, for other applications, complex inputs are unnecessary, as the input samples that are presented to the system are purely real. This is not to say that the standard transforms cannot be used; they can. The simplest approach would be to assume that the input sequence is complex instead of real, and ensure that the imaginary component of all input samples is zero. This approach gives perfectly valid results and, as it can directly employ one of the optimised `standard' transforms, is usually fast enough. There are though more elegant techniques that can take advantage of there being no imaginary input component.
5
Fourier Transforms V1.0 0899
Two independent RealValued Sequences of length N It is possible to evaluate the transforms of two unrelated real sequences of timedomain samples with a single transform. This is done by combining the two real Nlength sequences into one complex Nlength sequence, performing one Npoint complex FFT, and then splitting the single complex output into the two desired frequency sequences. Performing just one Npoint transform instead of two saves time; the combination and splitting processes take only a small fraction of time compared to the transform itself. If the two real Nlength sequences x1(n) and x2(n) are combined into one Nlength complex, x(n), it can be shown that the transforms of the two sequences can be extracted as follows: X1(k) = ½ (X(k) + X(Nk)*) X2(k) = 1/(2j) (X(k)  X(Nk)*) where X(k) is the transform of x(n), and * denotes complex conjugacy.
After the transform is applied, it would appear that the extraction requires one complex addition and one complex dividebytwo for each complex frequency bin of the required sequences. However, more savings can be made since it is known that the input sequences are purely real, and it is therefore only necessary to calculate up to k=N/2. So, if x1(n) and x2(n) are of length N, the additional processing that is required for each transform is only N/2 complex additions and N/2 complex divideby twos. This is significantly better than the extra N/2 log2N complex multiplies and Nlog2N complex additions, of another separate Npoint transform. For the derivation, see Appendix 3. RealValued Sequence of length 2N Similarly, it is possible to evaluate the transform of a data sequence of 2N real timedomain samples with a single transform Npoint complex transform. This is done by combining the even and odd elements of the input into one complex Nlength sequence, performing one Npoint complex FFT, and then again exploiting some of the properties of the transform to extract the 2N transform of the original 2N sequence. If the 2N real sequence g(n) is split into even and odd sequences x1(n) and x2(n), and combined into one complex sequence x(n) of length N, x(n) = x1(n) + jx2(n) it can be shown that the transform G(k) of g(n) can be expressed in terms of X(k), the transform of x(n). G(k) = ½ [(1  jW2N ) X(k)
k
+ (1 + jW2N ) X(Nk)*]
k
See Appendix 4 for derivation. Again, since g(n) is real, it is only necessary to calculate the first half of the frequency bins. I.e. up to bin N 1. (There are 2N bins). For each frequency bin, the additional processing required after applying the FFT, is three complex multiplies and one complex addition. For the N outputs of interest, this amounts to 3N multiplies and N additions. What is saved is the difference in performing an Npoint FFT instead of a 2Npoint FFT. I.e. N/2 log2N complex multiplies instead of N (1+log2N), and Nlog2N complex additions instead of 2N(1+log2N).
6
Fourier Transforms V1.0 0899
Windowing
Looking back at "The Basics", we can see that there is a bit of a problem. It is that we need to assume that the input sequence is periodic. I.e. it repeats itself over and over again. This assumption is necessary if the input signal is to be shown to be comprised of frequency components that are integer multiples of the periodic. In the real world, this never happens, and the FFT, if applied directly, can give false results in the form of spectral leakage. Windowing is simply a means of reducing the spectral leakage effects that occur when the transform's requirements for a periodic input cannot be met. For example, if a signal is sampled 1024 times over a period of 10mS, a 1024point FFT can be made of the sequence, resulting in 1024 frequency bins. These frequency bins are all integer multiples of 100Hz. I.e. DC, 100Hz, 200Hz, 300Hz...102.2kHz, 102.3kHz. Any frequency component of the input signal that is NOT an exact multiple of 100Hz will reduce the accuracy of the transform because it will contribute to ALL frequency bins. By considering the phase of the complex products of the data sample and the `twiddle factor' for a particular frequency bin, this can easily be seen. If a frequency component is an exact multiple of the fundamental, the summation of the complex products will do one of two things. They will either all have the same phase and add up to a large value for the correct frequency bin, as in (a), or they will all have different, equally spaced phases that rotate an integer number of times about the complex origin, cancelling each other out to give zero, as in (b).
(a)
(b)
When a frequency component is an NOT exact multiple of the fundamental, the summation of the complex products will always be nonzero because the phases, although equally spaced apart, will not rotate around the complex origin an integer number of times. This is demonstrated below with the complex products for frequency bin 3 of an 8point transform, where the input signal contains a frequency component that is 0.5 times the fundamental. I.e. a component that lies in between bin 0 and bin 1.
x2W82
x6W 86
x5W85
x3W83 Summation is equal to: x0W 80
x1W81 x4W84
x7W 87
There is an appreciably large result, about 16dB, in frequency bin 3 , despite there being no components of this frequency in the input signal. If there were some small component of this frequency in the signal, it would be hidden by the large false result. This is true of all other frequency bins for the transform. This is the phenomenon of spectral leakage, and more often than not, some means of controlling it is required. This is what windowing can do. Windowing involves applying a weighting factor to each time domain data sample, before the transform is applied. Without this technique, the data is still being windowed because all samples being included in the transform effectively have a weighting factor of unity, and all other time samples assume a weighting
Fourier Transforms V1.0 0899
7
factor of zero. I.e. the window is rectangular. The rectangular window however is what gives rise to the spectral leakage because of the discontinuities at both ends of the window that produce the broad range of frequencies. To reduce the effect of the discontinuities, a different shape of window is chosen so that samples in the middle of the window have greater influence on the transform and samples near the beginning and end of the window have much less influence. I.e. the weighting factors are low at each end and increase to higher values towards the middle of the window. Naturally, if the transform being used is of the decimationintime type, the weighting factors are applied before any bitreversed addressing is employed. There are many different shapes of window that can be applied, and they all have their advantages and disadvantages in terms of resolution, processing loss and dynamic range. Some of the more wellknown window families that are used include the Bartlett window, the raised cosine or Hanning window, the Welch window, the Hamming window, and the DolphChebychev window. The Bartlett window for example is simply a linear ramp of weighting factors rising from 0 at the beginning of the window to unity at sample N/2, then ramping back to zero at the end of the window. In our trivial 8point example, the sequence of factors would be [0, 0.25, 0,5, 0,75, 1.0, 0.75, 0.5, 0.25]. When these factors are applied to the same timedomain samples, before performing the FFT, the spectral leakage is improved. Frequency bin 3 for example is now only 32.9dB, a reduction in spectral leakage of 16.9dB. The reductions in spectral leakage that are achieved with windowing are more pronounced with more practical, higher order transforms. Figures of 50dB or more are achievable, depending again on the transform size and the windowing function that is chosen. Whichever windowing function is used, it involves an extra N multiplies prior to applying the transform.
The Sliding FFT
An interesting abstraction of the Fourier Transform, the sliding FFT can offer significant savings in processing time in cases where only particular frequency bins are needed. As the name suggests, the sliding FFT calculates valid results every sample period instead of every N samples. This material is taken from a document written by Keith Larson of Texas Instruments. Instead of calculating results from every N samples and then starting from scratch with the next N samples, the sliding FFT is able to use the very next single input sample with the previous N frequency results for updating its output. The rectangular sampling window in the time domain effectively slides along in time by one sample period. The advantages of this approach are that: (a) Frequency domain results are updated every sample period, (b) Only those frequency bins that are of interest need be calculated. This approach can therefore be very fast when there are only a few frequency bins to calculate. (c) The time to process each frequency bin is independent of N. It is possible therefore for N to be unusually large. The disadvantages of this approach are that: (a) Unlike convention FFT methods, the sliding FFT has a dependency on previous results. If there is a discontinuity in the time domain samples, the transform becomes invalid, and remains invalid for many samples until the discontinuity has been `worked out'. (b) All processing must be completed in one sample period to avoid the discontinuity problems discussed in (a). This often dictates that only a small number of frequency bins can be calculated. (c) The transform relies on precise values for the coefficients or `twiddle factors'. Integer arithmetic is unlikely to give satisfactory results and may even cause instability. (d) Windowing in the time domain cannot be applied. (e) Despite only using one new sample at a time, a circular buffer of the previous N samples must be maintained. For derivation, see Appendix 5.
8
Fourier Transforms V1.0 0899
Benchmarks
n point FFT Complex, r2 Complex, r4 Real, radix2 Real, radix4 16 bit short integer data, C code (in cycles) ((12*n)+48)*log(n)+8*n+43 ((89*n/4)+98)*log(n)/2+3*n+47 ((6*n)+48)*log(n/2)+13*n+125 ((89*n/8)+98)*log(n/2)/2+8*n+129 16 bit short integer data, assembly (in cycles) ((2*n)+7)*log(n)+n/4+43 ((10*n/4)+33)*log(n)/2+n/4+47 (n+7)*log(n/2)+22*n/4+125 ((5*n/4)+33)*log(n/2)/2+22*n/4+129 32 bit floatingpoint data, assembly (in cycles) ((2*n)+23)*log(n)+n/2+33 ((14*n/4)+23)*log(n)/2+46 (not yet available) (not yet available)
Figure 1. Performance of several different implementations of the FFT algorithm, as measured on `C6201 silicon (the two short integer benchmarks) and `C6701 silicon (the floatingpoint benchmark). To calculate the number of cycles for a complex 256 point radix2 FFT (where both real and imaginary parts are 16 bit short integer data): the number of cycles is (2*256+7)*log(256)+256/4+43=519*8+64+43= 4259 cycles. For a 200 MHz `C6201 the FFT would thus consume (4259*5ns=) 21 us.
Figure 2. Graphical representation of the data in the table in Figure 1. Note 1: the logarithm as shown in the table is of base 2. E.g. log(4)=2, log(8)=3, log(16)=4, and so on. Note 2: the real FFT is implemented as a complex FFT of length n/2, plus some pre and postprocessing. This extra processing is identical for all real FFT implementations. Note 3: the n/2 term in the floating point complex radix2 calculation comes from memory bank conflicts. At the time of writing we were not able yet to run this FFT without incurring the bank conflicts. Note 4: these values are valid only if both code and data are placed in onchip memory. If code or data is placed in external memory, performance will be much lower.
9
Fourier Transforms V1.0 0899
Summary
This document is only intended as a brief introduction to FFTs. The most popular of these, the Radix2, in place FFTs have been discussed, along with some practical techniques for reducing the calculation times further still when dealing with realvalued inputs. The important function of windowing has also been introduced. For brevity's sake, details of the inverse transforms have been omitted, as have discussions on transforms of another radix, mixedradix transforms, 2D transforms, etc. There are many excellent texts that can be referred to for further reading.
10
Fourier Transforms V1.0 0899
Appendix 1. Derivation of Discrete Fourier Transform
The integral for the Fourier Transform degenerates into a sum of discrete frequency components.
F(kw0) =
f(t) e jkw t dt
0 
where w0 is the fundamental frequency of repetition in rad/sec., and k is integer. It is easy to prove that if f(t) is periodic, integrating from t =  to t = + is no longer necessary. The integration can give the same results over the time span t = T0/2 to t = +T0/2.
T0/2
F(kw0) =
f(t) e jkw t dt
0 T0/2
where T0 is the repetition period. The sampled nature of the time domain information is now taken into account. f(t) is replaced with f(nTS) where TS is the time between the discrete samples. f(nTS) = f(t)
n
(tnTS)
where is the Diracdelta function: 1 at 0, 0 at all other times.
The transform becomes
T0/2 n = +
F(kw0) =
f(t)
T0/2
(tnTS) e
jkw0t
dt
n = 
This integral degenerates into another discrete summation.
n = N1
F(kw0) =
n=0
f(nTS) e
j2nk/N
where N is the number of samples within one fundamental period. N = T0/Ts The complex factor e
th
j2/N
is central to understanding the DFT and FFT. It is the fundamental complex
N root of 1 and for clarity is written WN . E.g. W8 = e
j2/8
= cos(/4) j sin(/4).
11
Fourier Transforms V1.0 0899
Appendix 2. Derivation of Radix 2, inplace FFTs
The Radix 2, inplace, DisplacementinTime FFT
Split the single Npoint summation of the DFT into two summations of N/2 points, one using the even input samples, and the other using the odd input samples. Note that it is now assumed that N is even.
n = N1
n = N1
Fk =
x(n) W N
nk
+
x(n) W N
nk
n = 0 even n
n = 0 odd n
In the even summation, where n is [0,2,4,....N2], replace n with 2m, letting m be [0,1,2...(N/2 1)]. In the odd summation, where n is [1,3,5,....N1], replace n with (2m+1), again allowing m to go from 0 to (N/2 1).
m = N/2  1 m = N/2  1
Fk =
m=0
x(2m) WN
2mk
+
x(2m+1) WN
(2m+1)k
m=0
Now, with the input data referred to xeven and xodd, and recognising that WN express the original Npoint transform as the sum of two N/2 point transforms.
m = N/2  1 m = N/2  1
2
= WN/2 it is possible to
Fk =
m=0
xeven(m) WN/2
mk
+
xodd(m) WN/2
m=0
mk
WN
k
= X1(k) + W N X2(k) This process of splitting the transform into a pair of transforms of half the size, is crucial in realising the advantages of the FFT, in this case the radix2, DisplacementInTime FFT. The process is repeated over and over, until a simple 2point transform remains. This is why the number of points in a radix 2 algorithm must be a power of two. The 2point transform is easy because the complex factors have been reduced to W 2 and W 2 . I.e. 1 and 1, so: F(0) = f(0) + f(1) F(1) = f(0) f(1).
k
0
1
12
Fourier Transforms V1.0 0899
Example of 8point, Radix2, DIT FFT. The number of passes in an Npoint radix 2 transform log2 N. For example, an 8point transform has three stages or passes, as shown below. First split into X into two 4point transforms. X1 is the 4point transform of [f(0),f(2),f(4),f(6)], (even elements) X2 is the 4point transform of [f(1),f(3),f(5),f(7)]. (odd elements) Since the process of splitting is working backwards, i.e. from the frequency domain results to the time domain samples, this is the last pass of calculations. X(0) = X1(0) + W8 X2(0) X(1) = X1(1) + W8 X2(1) X(2) = X1(2) + W8 X2(2) X(3) = X1(3) + W8 X2(3) X(4) = X1(0) + W8 X2(0) = X1(0)  W8 X2(0) X(5) = X1(1) + W8 X2(1) = X1(1)  W8 X2(1) X(6) = X1(2) + W8 X2(2) = X1(2)  W8 X2(2) X(7) = X1(3) + W8 X2(3) = X1(3)  W8 X2(3) Then split X1 and X2 are each split into two 2point transforms.
7 3 6 2 5 1 4 0 3 2 1 0
A1 is the 2point transform of [f(0),f(4)], (even:even elements ) A2 is the 2point transform of [f(2),f(6)], (odd:even elements ) B1 is the 2point transform of [f(1),f(5)], (even:odd elements ) B2 is the 2point transform of [f(3),f(7)]. (odd:odd elements ) This is the second pass of calculations.
0
X1(0) = A1(0) + W4 A2(0) X1(1) = A1(1) + W4 A2(1) X1(2) = A1(0) + W4 A2(0) = A1(0)  W4 A2(0) X1(3) = A1(1) + W4 A2(1) = A1(1)  W4 A2(1) X2(0) = B1(0) + W4 B2(0) X2(1) = B1(1) + W4 B2(1) X2(2) = B1(0) + W4 B2(0) = B1(0)  W4 B2(0) X2(3) = B1(1) + W4 B2(1) = B1(1)  W4 B2(1) Having reached 2point transforms, no more splits are necessary. This then is the first pass of calculations to be carried out.
0 3 1 2 0 1 0 3 1 2 0 1
A1(0) = f(0) + W2 f(4) = f(0) + f(4) A1(1) = f(0) + W2 f(4) = f(0)  f(4) A2(0) = f(2) + W2 f(6) = f(2) + f(6)
Fourier Transforms V1.0 0899
0 1
13
A2(1) = f(2) + W2 f(6) = f(2)  f(6) B1(0) = f(1) + W2 f(5) = f(1) + f(5) B1(1) = f(1) + W2 f(5) = f(1)  f(5) B2(0) = f(3) + W2 f(7) = f(3) + f(7) B2(1) = f(3) + W2 f(7) = f(3)  f(7)
1 0 1 0
1
It can be seen that there are N/2 complex multiplies and N complex additions in each pass, so the total number of complex multiplies is N/2 log2 N, and the total number of complex additions is N log2 N. For a 1024point FFT this makes 5120 complex multiplies and 10240 complex additions, a significant saving in processing over the DFT which would take 1048576 complex multiplies and 1047552 complex additions to get the same results.
14
Fourier Transforms V1.0 0899
The Radix 2, inplace, DisplacementinFrequency FFT
Split the single Npoint summation of the DFT into two summations of N/2 points, one for the even output samples, and the other for the odd output samples. Note that it is again assumed that N is even.
n = N1
Fk =
n=0
x(n) W N
nk
Treating k as a binary value, it can be written (k1,k0), where k0 is the LSB and k1 is the remainder of the binary pattern of k, shifted right by one bit.
n = N1
Fk =
n=0 n = N1
x(n) W N
n(2k1+k0)
n = N1
Fk(even) =
x(n) W N
n(2k1)
=
n=0
x(n) WN/2
n(k1)
n=0
n = N1
n = N1
Fk(odd) =
x(n) W N
n(2k1)
WN
n
=
n=0
x(n) W N/2
n(k1)
WN
n
n=0
Each of these two summations produces N/2 frequency results because k1 varies from 0 to N/2 1. This splitting is repeated. I.e. both summations are split into summations for even and odd values of k1. This process is continued until the trivial twoelement summation is reached.
15
Fourier Transforms V1.0 0899
Appendix 3. Derivation of FFT of two real sequences
Some important properties of Fourier Transforms are exploited in deriving this technique. Firstly, if a data sequence xn is purely real, its Npoint transform Fn obeys the following symmetry. FNn = (Fn)* where * denotes complex conjugation.
E.g. in a 1024point transform of a real sequence, frequency bin 1016 will be the complex conjugate of frequency bin 8. Secondly, if a data sequence xn is purely imaginary, its Npoint transform Fn obeys the following symmetry. FNn = (Fn)* E.g. in a 1024point transform of an imaginary sequence, frequency bin 1016 will be the negation of the complex conjugate of frequency bin 8. Thirdly, the transform itself is a linear operation. I.e. the transform of a sum of sequences is the same as the sum of the individual transforms of each sequence. The first step of the procedure is to combine the two real sequences, x1(n) and x2(n), into one complex sequence, x(n). This is done by assigning one of the real sequences to be the real part of the complex sequence, and the other real sequence to be the imaginary part of the complex sequence. I.e. x(n) = x1(n) + jx2(n) Observing the linearity of the Fourier Transform, the transform of x(n) can be expressed as the sum of the transform of x1(n) and the transform of jx2(n), where x1(n) is a purely real sequence, and jx2(n) is a purely imaginary sequence. X(k) = X1(k) + X2(k). X1(k) is the transform of a real sequence, so X1(Nk) = X1(k)*, and X2(k) is the transform of an imaginary sequence, so X2(Nk) = X2(k)*. Therefore,
X(Nk) = X1(k)*  X2(k)* It then follows that and
or, X(Nk)* = X1(k)  X2(k).
X1(k) = ½ (X(k) + X(Nk)*) X2(k) = 1/(2j) (X(k)  X(Nk)*)
The two transforms are now separated.
16
Fourier Transforms V1.0 0899
Appendix 4. Derivation of FFT of one real sequence of length 2N
First, combine the 2Nlength real sequence into an Nlength complex sequence, x(n). If g(n) is the 2N input, where n takes values from 0 to 2N1, make: x1(n) = g(2n) and x2(n) = g(2n+1) where n takes values from 0 to N1. x(n) = x1(n) + jx2(n) where x1(n) is the sequence of even elements of the original 2N inputs, and x2(n) is the sequence of odd elements. Transform and extract as before to give: X1(k) = ½ (X(k) + X(Nk)*) X2(k) = 1/(2j) (X(k)  X(Nk)*) The transform of the original real sequence can be expressed as the sum of two transforms; the transform of the even elements plus the transform of the odd elements. F{g(n)} = F{g(2n)} + F{g(2n+1)}
n=N1 n=N1
Fk =
n=0
g(2n) W2N
2nk
+
g(2n+1) W2N
(2n+1)k
n=0
Now, with the input data referred to geven and godd, and recognising that W2N express the original 2Npoint transform as the sum of two N point transforms.
n=N1 n=N1
2
= WN, it is possible to
Fk =
n=0
geven(n) W N
nk
+
W 2N
k
n=0
godd(m) W N
nk
= X1(k) + W2N X2(k) Using our previously equations for X1(k) and X2(k), Fk can now be expressed in terms of X(k).
k
F(k) = ½ (X(k) + X(Nk)*) = ½(1  jW2N ) X(k)
+ W2N [1/(2j) (X(k)  X(Nk)*)] + ½(1 + jW2N ) X(Nk)*
k
k
k
Since the original g(n) is real the complex conjugate property may be used to calculate the upper half of F(k).
F(2Nk) = F(k)* The transform F(k) of the 2N sequence g(n) is now extracted from the Npoint transform x(n).
17
Fourier Transforms V1.0 0899
Appendix 5. Derivation of the Sliding FFT.
The sliding FFT ingeniously exploits the properties of a timedelayed input and the property of linearity for its derivation. First of all, the Npoint transform of a sequence x(n) is equal to the summation of the transforms of N separate transforms where each transform has just one of the original samples at it's original sample time. I.e. transform of [x0, x1, x2, x3, x4, x5,....xN1] is equal to transform of [x0, 0, 0, 0, 0, 0,....0] + transform of [0, x1, 0, 0, 0, 0,....0] + transform of [0, 0, x2, 0, 0, 0,....0] + transform of [0, 0, 0, x3, 0, 0,....0] . . . + transform of [0, 0, 0, 0, 0, 0,....xN1] Secondly, the transform of a timedelayed sequence is a phaserotated version of the transform of the original sequence. I.e. If Then x(n) transforms to X(k),
x(nm) transforms to X(k)W N
mk
where N is the FFT size, m is the delay in sample periods, and WN is the familiar phaserotating coefficient or twiddle factor e
j2/N
.
Therefore, if the Npoint transform X(k) of an individual sample is considered, and then the sample is moved back in time by one sample period, all frequency bins of X(k) are phaserotated by 2k/N radians. The important thing here is that the transform is not performed again because the previous frequency results can be used by simply application of the correct coefficients. This is the technique that is applied when the rectangular sampling window slides along by one sample. The contributions of all samples that are included in both the original and the new windows are simply phaserotated. The end effects are that the transform of the new sample must be added, and the transform of the oldest sample that `disappeared off the end' must be subtracted. These endeffects are easy to perform if we treat the new sample as occurring at time t = 0, because the transform of a single sample at t=0, say (a + bj), simply has all frequency bins equal to (a + bj). Similarly, the oldest sample that has just `disappeared off the end' of the window is exactly N samples old. I.e. it occurred at t = N. The transform of this sample, say (c + dj), is also straightforward since every frequency bin has now been th phaserotated an integer number of times from when the sample was at t = 0. (The k frequency bin has been rotated by 2k radians). The transform of the sample at t = N is therefore the same as if it was still at t = 0. I.e. it has all frequency bins equal to (c + dj). All that is needed therefore is to phaserotate each frequency bin in F(k) by W N and then add [(a + bj) (c + dj)] to each frequency bin. One complex multiplication and two complex additions per frequency bin are therefore required, per sample period, regardless of the size of the transform. For example, a traditional 1024point FFT needs 5120 complex multiplies and 10240 complex additions to calculate all 1024 frequency bins. A 1024point Sliding FFT however needs 1024 complex multiplies and 2048 complex additions for all 1024 frequency bins, and as each frequency bin is calculated separately, it is only necessary to calculate the ones that are of interest.
k
18
Fourier Transforms V1.0 0899
One drawback of the Sliding FFT is that in using feedback from previous frequency bins, there is potential for instability if the coefficients are not infinitely precise. Without infinite precision, stability can be guaranteed by making each phaserotation coefficient have a magnitude of slightly less than unity. E.g. th 0.9999. This then has to taken into account when the N sample is subtracted, because the factor 0.9999 has been applied N times to the transform of this sample. The sample cannot therefore be directly subtracted, it must first be multiplied by the factor of 0.9999 . This unfortunately means there is another multiplication to perform per frequency bin. Another drawback is that a circular buffer is needed in which to keep N samples, so that the oldest sample, (from t= N), can be subtracted each time.
N
19
Fourier Transforms V1.0 0899
Information
long2.PDF
19 pages
Report File (DMCA)
Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:
Report this file as copyright or inappropriate
782879