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 REAL-VALUED SEQUENCES.................................................................................................................. 5 Two independent Real-Valued Sequences of length N .................................................................................. 6 Real-Valued 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, IN-PLACE FFTS ................................................................... 12 THE RADIX 2, IN-PLACE, DISPLACEMENT-IN-TIME FFT ................................................................................... 12 Example of 8-point, Radix2, DIT FFT. ....................................................................................................... 13 THE RADIX 2, IN-PLACE, DISPLACEMENT-IN-FREQUENCY 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)

((n-1) /2)

for odd n,

F(n) = 0 for even n, giving us discrete frequency spectra for the time-continuous 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 frequency-continuous 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 = N-1

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 N-point Discrete Fourier Transform. It takes N discrete time-domain samples, (a non-infinite 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 8-point 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 N-point 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. radix-4 transforms can be 4-point, 16-point, 64-point, 256-point, 1024-point, etc. A 512point transform for example, must be radix-2. An in-place 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 in-place algorithms are the most popular. In-place FFT algorithms work with either the input samples (in the case of decimation-in-time FFT's), or the output samples (in the case of decimation-in-frequency FFT's), jumbled into bit-reversed order. I.e. decimation-in-time transforms need their input samples to be swapped into bit-reversed order prior to the transform which gives normal-order results, and decimation-in-frequency transforms use normal ordered input samples and generate their output samples in bit-reversed 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 = N-1

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 1024-point 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 Real-Valued 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 Real-Valued Sequences of length N It is possible to evaluate the transforms of two unrelated real sequences of time-domain samples with a single transform. This is done by combining the two real N-length sequences into one complex N-length sequence, performing one N-point complex FFT, and then splitting the single complex output into the two desired frequency sequences. Performing just one N-point 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 N-length sequences x1(n) and x2(n) are combined into one N-length complex, x(n), it can be shown that the transforms of the two sequences can be extracted as follows: X1(k) = ½ (X(k) + X(N-k)*) X2(k) = 1/(2j) (X(k) - X(N-k)*) 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 divide-by-two 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 divide-by twos. This is significantly better than the extra N/2 log2N complex multiplies and Nlog2N complex additions, of another separate N-point transform. For the derivation, see Appendix 3. Real-Valued Sequence of length 2N Similarly, it is possible to evaluate the transform of a data sequence of 2N real time-domain samples with a single transform N-point complex transform. This is done by combining the even and odd elements of the input into one complex N-length sequence, performing one N-point 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(N-k)*]

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 N-point FFT instead of a 2N-point 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 1024-point 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 non-zero 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 8-point 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 decimation-in-time type, the weighting factors are applied before any bit-reversed 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 well-known window families that are used include the Bartlett window, the raised cosine or Hanning window, the Welch window, the Hamming window, and the Dolph-Chebychev 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 time-domain 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, r-2 Complex, r-4 Real, radix-2 Real, radix-4 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 floating-point 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 floating-point benchmark). To calculate the number of cycles for a complex 256 point radix-2 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 post-processing. This extra processing is identical for all real FFT implementations. Note 3: the n/2 term in the floating point complex radix-2 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 on-chip 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 Radix-2, in place FFTs have been discussed, along with some practical techniques for reducing the calculation times further still when dealing with real-valued 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, mixed-radix 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

(t-nTS)

where is the Dirac-delta function: 1 at 0, 0 at all other times.

The transform becomes

T0/2 n = +

F(kw0) =

f(t)

-T0/2

(t-nTS) e

­jkw0t

dt

n = -

This integral degenerates into another discrete summation.

n = N-1

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, in-place FFTs

The Radix 2, in-place, Displacement-in-Time FFT

Split the single N-point 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 = N-1

n = N-1

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,....N-2], replace n with 2m, letting m be [0,1,2...(N/2 ­ 1)]. In the odd summation, where n is [1,3,5,....N-1], 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 N-point 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 radix-2, Displacement-In-Time FFT. The process is repeated over and over, until a simple 2-point transform remains. This is why the number of points in a radix 2 algorithm must be a power of two. The 2-point 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 8-point, Radix2, DIT FFT. The number of passes in an N-point radix 2 transform log2 N. For example, an 8-point transform has three stages or passes, as shown below. First split into X into two 4-point transforms. X1 is the 4-point transform of [f(0),f(2),f(4),f(6)], (even elements) X2 is the 4-point 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 2-point transforms.

7 3 6 2 5 1 4 0 3 2 1 0

A1 is the 2-point transform of [f(0),f(4)], (even:even elements ) A2 is the 2-point transform of [f(2),f(6)], (odd:even elements ) B1 is the 2-point transform of [f(1),f(5)], (even:odd elements ) B2 is the 2-point 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 2-point 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 1024-point 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, in-place, Displacement-in-Frequency FFT

Split the single N-point 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 = N-1

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 = N-1

Fk =

n=0 n = N-1

x(n) W N

n(2k1+k0)

n = N-1

Fk(even) =

x(n) W N

n(2k1)

=

n=0

x(n) WN/2

n(k1)

n=0

n = N-1

n = N-1

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 two-element 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 N-point transform Fn obeys the following symmetry. FN-n = (Fn)* where * denotes complex conjugation.

E.g. in a 1024-point 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 N-point transform Fn obeys the following symmetry. FN-n = -(Fn)* E.g. in a 1024-point 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(N-k) = X1(k)*, and X2(k) is the transform of an imaginary sequence, so X2(N-k) = -X2(k)*. Therefore,

X(N-k) = X1(k)* - X2(k)* It then follows that and

or, X(N-k)* = X1(k) - X2(k).

X1(k) = ½ (X(k) + X(N-k)*) X2(k) = 1/(2j) (X(k) - X(N-k)*)

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 2N-length real sequence into an N-length complex sequence, x(n). If g(n) is the 2N input, where n takes values from 0 to 2N-1, make: x1(n) = g(2n) and x2(n) = g(2n+1) where n takes values from 0 to N-1. 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(N-k)*) X2(k) = 1/(2j) (X(k) - X(N-k)*) 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=N­1 n=N-1

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 2N-point transform as the sum of two N­ point transforms.

n=N-1 n=N-1

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(N-k)*) = ½(1 - jW2N ) X(k)

+ W2N [1/(2j) (X(k) - X(N-k)*)] + ½(1 + jW2N ) X(N-k)*

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(2N-k) = F(k)* The transform F(k) of the 2N sequence g(n) is now extracted from the N-point 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 time-delayed input and the property of linearity for its derivation. First of all, the N-point 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,....xN-1] 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,....xN-1] Secondly, the transform of a time-delayed sequence is a phase-rotated version of the transform of the original sequence. I.e. If Then x(n) transforms to X(k),

x(n-m) 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 phase-rotating coefficient or twiddle factor e

­j2/N

.

Therefore, if the N-point 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 phase-rotated 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 phase-rotated. 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 end-effects 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 phase-rotated 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 phase-rotate 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 1024-point FFT needs 5120 complex multiplies and 10240 complex additions to calculate all 1024 frequency bins. A 1024-point 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 phase-rotation 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


You might also be interested in

BETA
Thesis
Microsoft Word - EE-III-IV-11-12.doc
Microsoft Word - GA_in_hot_steel_rolling_final.doc
Improving the Response of Accelerometers for Automotive Applications by Using LMS Adaptive Filters: Part II