Fast Fourier Transform

Fast Fourier Transform

UNIT 3

FAST FOURIER TRANSFORM

Introduction to DFT – Efficient computation of DFT – Properties of DFT – FFT algorithms – Radix-2 and Radix-4 FFT algorithms – Decimation in Time – Decimation in Frequency algorithms – Use of FFT algorithms in Linear filtering and correlation.

THE DISCRETE FOURIER TRANSFORM (DFT)

We now consider the sequence such that and. Thus can be take non-zero values only for. Such sequences are known as finite length sequences, and N is called the length of the sequence. If a sequence has length M, we consider it to be a length N sequence where. In these cases last ( N - M ) sample values are zero. To each finite length sequence of length N we can always associate a periodic sequence defined by

------ (1)

Note that defined by equation (1) will always be a periodic sequence with period N, whether is of finite length N or not. But when has finite length N, we can recover the sequence from by defining

------ (2)

This is because of has finite length N , then there is no overlap between terms and for different values of. Recall that if
n = kN + r, where
then n modulo N = r ,

i.e. we add or subtract multiple of N from n until we get a number lying between 0 to N - 1. We will use ((n))N to denote n modulo N. Then for finite length sequences of length N equation (1) can be written as

------ (3)

We can extract from using equation (2). Thus there is one-to- one correspondance between finite length sequences of length N , and periodic sequences of period N.

Given a finite length sequence we can associate a periodic sequence with it.

This periodic sequence has discrete Fourier series coefficients which are also periodic with period N. Thus we define discrete Fourier transform of finite length sequence as

where is DFS coefficient of associated periodic sequence. From we can get by the relation.

we can write X [k ] directly in terms of x[n], and x[n] directly in terms of X[k] as

For convenience of notation, we use the complex quantity

------ (4)

with this notation, DFT analysis and synthesis equations are written a follows

Analysis equation:

---- (5)

Synthesis equation:

------ (6)

If we use values of k and n outside the interval 0 to N - 1 in equation (5) and (6), then we will not get values zero, but we will get periodic repetition of and respectively. In defining DFT, we are concerned with values only in interval 0 to N - 1. Since a sequence of length M can also be considered a sequence of length , we also specify the length of the sequence by saying N-point-DFT, of sequence.

Properties of the discrete Fourier transform

Since discrete Fourier transform is similar to the discrete Fourier series representation, the properties are similar to DFS representation. We use the notation

to say that are DFT coefficient of finite length sequence.

1. Linearity

If two finite length sequence have length M and N , we can consider both of them with length greater than or equal to maximum of M and N. Thus if

then

where all the DFTs are N-point DFT. This property follows directly from the equation (5)

2. Circular shift of a sequence

If we shift a finite length sequence of length N , we face some difficulties. When we shift it in right direction the length of the sequence will becam according to definition. Similarly if we shift it left , if may no longer be a finite length sequence as may not be zero for n < 0. Since DFT coefficients are same as DFS coefficients, we define a shift operation which looks like a shift of periodic sequence. From we get the periodic sequence defined by

We can shift this sequence by m to get

Now we retain the first N values of this sequence

This operation is shown in figure below for m = 2, N = 5.

We can see that is not a shift of sequence. Using the propertiesof the modulo arithmetic we have

and

------(7)

The shift defined in equation (7) is known as circular shift. This is similar to a shift of sequence in a circular register.

3. Shift property of DFT

From the definition of the circular shift, it is clear that it corresponds to linear shift of the associated periodic sequence and so the shift property of the DFS coefficient will hold for the circular shift. Hence

------ (8)

and

------(9)

4. Duality

We have the duality for the DFS coefficient given by , retaining one period of the sequences the duality property for the DFT coefficient will become

5. Symmetry properties

We can infer all the symmetry properties of the DFT from the symmetry properties of the associated periodic sequence and retaining the first period. Thus we have

and

We define conjugate symmetric and anti-symmetric points in the first period 0 to N - 1 by

Since

the above equation similar to

------ (10)

------(11)

and are referred to as periodic conjugate symmetric and periodic conjugate anti-symmetric parts of. In terms if these sequence the symmetric properties are

6. Circular convolution

We saw that multiplication of DFS coefficients corresponds of periodic convolution of the sequence. Since DFT coefficients are DFS coefficients in the interval, , they will correspond to DFT of the sequence retained by periodically convolving associated periodic sequences and retaining their first period.

Periodic convolution is given by

using properties of the modulo arithmetic

and then

Since we get

The convolution defined by equation (11) is known as N-point-circular convolution of sequence and , where both the sequence are considered sequence of length N. From the periodic convolution property of DFS it is clear that DFT of is. If we use the notation to denote the N point circular convolution we see that

------(12)

In view of the duality property of the DFT we have

------ (13)

Properties of the Discrete Fourier transform are summarized in the table

Finite length sequence (length N) / N-point DFT (length N)
1. / /
2. / /
3. / /
4. / /
5. / /
6. / /
7. / /
8. / /
9. / /
10. / /
11. / /
12. / /
13. / /
14. / If is real sequence /




FAST FOURIER TRANSFORM – INTRODUCTION

We will begin our discussion of the family of algorithms known as “Fast Fourier Transforms”, which have revolutionized digital signal processing

What is the FFT?

  • A collection of “tricks” that exploit the symmetry of the DFT calculation to make its execution much faster
  • Speedup increases with DFT size

We will outline the basic workings of the simplest formulation, the radix-2 decimation-in-time algorithm

Then we will discuss some of the variations and extensions

  • Alternate structures
  • Non-radix 2 formulations

We will discuss some of the variations and extensions

  • Alternate structures
  • Non-radix 2 formulations

In 1967 (spring of my freshman year), calculation of a 8192-point DFT on the top-of-the line IBM 7094 took ….

  • ~30 minutes using conventional techniques
  • ~5 seconds using FFTs

Measures of computational efficiency

We Could consider

  • Number of additions
  • Number of multiplications
  • Amount of memory required
  • Scalability and regularity

For the present discussion we’ll focus most on number of multiplications as a measure of computational complexity

  • More costly than additions for fixed-point processors
  • Same cost as additions for floating-point processors, but number of operations is comparable

DECIMATION-IN-TIME (DIT) RADIX-2 FFT

New Operation Counts

Reduction by almost a factor of two over direct DFT1computation

1 Additional Simplification

A basic "butterfly" operation is shown in Figure 1, which results in only N/2"twiddle factor" multiplies per stage.

The same trick can be applied recursively to the two length N/2DFT2s to save computation. The result is the radix-2 DIT FFT algorithm (figure 3).

Computational cost of radix-2 DIT FFT

Figure 1

Figure2

Both operations are equivalent

Comments

• Simple, short, elegant

• Three-loop structure

• For efficiency, a cosine-sine lookup table should be added

  • Input signal must be properly re-ordered using a bit reversal algorithm
  • In-place computation
  • Number of stages: log2 N
  • Stage 1: all the twiddle factors are 1
  • Last Stage: the twiddle factors are in sequential order

DIF FFT

  • Output signal must be properly re-ordered using a bit reversal algorithm
  • In-place computation
  • Number of stages: log2 N
  • Stage 1: the twiddle factors are in sequential order
  • Last Stage: all the twiddle factors are 1

Radix-4 Decimation-In-Time FFT Algorithm

  • A radix-4 FFT combines two stages of a radix-2 FFT into one, so that half as many stages are required.
  • The radix-4 butterfly is consequently larger and more complicated than a radix-2 butterfly.
  • N/4 butterflies are used in each of (log2N)/2 stages, which is one quarter the number of butterflies in a radix-2 FFT.
  • Addressing of data and twiddle factors is more complex, a radix-4 FFT requires fewer calculations than a radix-2 FFT.
  • It can compute a radix-4 FFT significantly faster than a radix-2 FFT

Review Questions

PART A

1. How many multiplication and additions are required to compute N point DFT

using radix 2 FFT?

2. Define DTFT pair.

3. What are Twiddle factors of the DFT?

4. State Periodicity Property of DFT.

5. What is the difference between DFT and DTFT?

6. Why need of FFT?

7. Find the IDFT of Y (k) = (1, 0, 1, 0)

8. Compute the Fourier transform of the signal x(n) = u(n) – u(n-1).

9. Compare DIT and DIF?

10. What is meant by in place in DIT and DIF algorithm?

11. Is the DFT of a finite length sequence is periodic? If so, state the reason.

12. Draw the butterfly operation in DIT and DIF algorithm?

13. What is meant by radix 2 FFT?

14. State the properties of W Nk?

15. What is bit reversal in FFT?

17. What is the use of Fourier transform?

18. What are the advantages FFT over DFT?

19. What is meant by section convolution?

20. Differentiate overlap adds and save method?

21.Distinguish between Fourier series and Fourier transform.

22.What is the relation between fourier transform and z transform.

23. Distinguish between DFT and DTFT.

PART B

  1. State and explain the properties of DFT
  2. The five samples of the 9 point DFT are given as follows

i)4 point DFT of X(n)={ 1, 2,2,1}

ii)x(n)= { 1,2,2,1}

iii)x(n)={1,2,3}

  1. Compute the 5 point of x(n)={0,1,2,3,4} .
  2. Compute the 8 point of x(n)={ 1 , 0 ≤ n ≤ 3

0, 4 ≤ n ≤ 7

  1. Compute 8 pt DFT of X(n)by radix-2 DIT FFT.

X(n)={1,3,2,2,2,1,3,2}

  1. Compute 8 pt DFT of X(n)by radix-2 DIT FFT.

X(n)={1,2,3,4,4,3,2,1 }

  1. Compute 8 pt DFT of X(n)by radix-2 DIT FFT.

X(n)={1,3,2,2,7,3,9,5 }

  1. Compute 8 pt DFT of X(n)by radix-2 DIT FFT.

X(n)={1,3,5,6,2,1,3,2 }

  1. Compute 8 pt DFT of X(n)by radix-2 DIT FFT.

X(n)={1,0,1,1,0,1,1,1}

  1. Compute 8 pt DFT of X(n)by radix-2 DIT FFT.

X(n)={1,1,1,1,0,1,1,1}

  1. Compute 8 pt DFT of X(n)by radix-2 DIF FFT.

X(n)={1,0,1,1,0,1,1,1}

  1. Determine 8 pt DFT of the signal

X(n)={1,1,1,1,1,1,0,0}

  1. An 8 point sequence is given by X(n)={2,2,2,2,1,1,1,1}.Compute 8pt DFT of x(n) by Radix-2 DIF-FFT.
  2. An 8 point sequence is given by X(n)={2,2,2,2,1,1,1,1}.Compute * pt DFT of x(n) by Radix-2 DIF-FFT.
Top View