## Contents

# Homework 6 Solution, ECE438 Fall 2014, Prof. Boutin

## Question 1

Diagram of "decimation by two" FFT computing N-pt DFT. N=8 in this question.

where $ W_N^k = e^{-j2\pi k/N} $

Recall the definition of DFT:

$ X[k]=\sum_{n=0}^{N-1} x[n]e^{-j2\pi k/N},\ k=0,...,N-1 $.

For each k, we need N times complex multiplications and N-1 times complex additions.

In total, we need $ N^2 = 64 $ times of complex multiplications and $ N^2-N = 56 $ times of complex additions.

Using "decimation by two" FFT algorithm, the DFT is computed in two steps. For the first step, two N/2-pt DFT are computed with $ 2\cdot (\frac{N}{2})^2 $ multiplications and $ 2((\frac{N}{2})^2-\frac{N}{2}) $. For the second step, $ \frac{N}{2} $ multiplications and $ N $ additions are needed.

When $ N=8 $, the total numbers of complex operations are

multiplications: $ 2\cdot (\frac{N}{2})^2 + \frac{N}{2} = 36 $

additions: $ 2((\frac{N}{2})^2-\frac{N}{2}) + N = 32 $

## Question 2

Diagram of "radix-2" FFT computing 8-pt DFT.

where $ W_N^k = e^{-j2\pi k/N} $

Recall the definition of DFT:

$ X[k]=\sum_{n=0}^{N-1} x[n]e^{-j2\pi k/N},\ k=0,...,N-1 $

In this question N=8

If we use summation formula to compute DFT, for each k, we need N times complex multiplications and N-1 times complex additions.

In total, we need N*N=64 times of complex multiplications and N*(N-1)=56 times of complex additions.

In decimation-in-time FFT algorithm, we keep on decimating the number of points by 2 until we get 2 points DFT. At most, we can decimate $ v=log_2 N $ times. As a result, we get v levels of DFT. Except for the first level (2-pt FFT), which only needs N times complex additions, for the rest of levels, we need N/2 times of complex multiplications and N times of complex additions.

In total, we need $ \frac{N}{2}(log_2 N -1)=8 $ times of complex multiplications and $ Nlog_2 N=24 $ times of complex additions.

(Note: when $ N $ is large, $ log_2 N -1 \approx log_2 N $. So the number of multiplications becomes $ \frac{N}{2}log_2 N $.)

## Question 3

The diagram is identical to the diagram in Question 1 except N=122.

By similar argument presented in Question 1, a direct computation of DFT requires $ N^2 = 14884 $ times of complex multiplications and $ N^2-N = 14762 $ times of complex additions.

Using "decimation by two" FFT algorithm, the total number of multiplications is $ 2\cdot (\frac{N}{2})^2 + \frac{N}{2} = 7503 $ and the total number of additions is $ 2((\frac{N}{2})^2-\frac{N}{2}) + N = 7442 $

## Question 4

Denote N is the points number of the input signal's DFT. In this question N=6.

1) The normal DFT algorithm: If we use summation formula to compute DFT, according to the analysis of Question 1. We need N*N=36 times of complex multiplications and N*(N-1)=30 times of complex additions.

Flow diagram of FFT：

Analytical Expressions:

$ \begin{align} X_6(k)&=\sum_{n=0}^{5} x(n)e^{-\frac{j2\pi kn}{6}} \\ &\text{Change variable n=2m+l, m=0,1,2; l=0,1 } \\ X_6(k)&=\sum_{l=0}^{1}\sum_{m=0}^{2}x(2m+l)e^{-\frac{j2\pi k(2m+l)}{6}} \\ &=\sum_{l=0}^{1}e^{-\frac{j2\pi kl}{6}}\sum_{m=0}^{2}x(2m+l)e^{-\frac{j2\pi km}{3}} \\ &=\sum_{l=0}^{1}W_6^{kl}X_l(k) \text{ ,k=0,1,...,5 } \end{align} $

Note that $ X_l(k) = X_l(k+3),\ k=0,1,2 $

In this FFT algorithm, the computing of DFT is divided into two levels. First, we compute two 3-point DFT, which are DFT of even and odd points.

In this step we need 4 times of complex multiplications (consider when m=0 and k=0,3, there are no multiplies needed) and 6 times of complex additions for each 3-point DFT. Since we have to do this twice, we need 4*2=8 times of complex multiplications and 6*2=12 times of complex additions.

Second, we compute the final DFT by combing the first level result. According to the analysis of Question 1, we need N/2=3 times of complex multiplications and N=6 times of complex additions.

In total, we need 8+3=11 times of complex multiplications and 12+6=18 times of complex additions.

2)

Flow diagram of FFT：

Analytical Expressions:

$ \begin{align} X_6(k)&=\sum_{n=0}^{5} x(n)e^{-\frac{j2\pi kn}{6}} \\ &\text{Change variable n=3m+l, m=0,1; l=0,1,2 } \\ X_6(k)&=\sum_{l=0}^{2}\sum_{m=0}^{1}x(3m+l)e^{-\frac{j2\pi k(3m+l)}{6}} \\ &=\sum_{l=0}^{2}e^{-\frac{j2\pi kl}{6}}\sum_{m=0}^{1}x(3m+l)e^{-\frac{j2\pi km}{2}} \\ &=\sum_{l=0}^{2}W_6^{kl}X_l(k) \text{ ,k=0,1,...,5 } \end{align} $

Note that $ X_l(k) = X_l(k+2) = X_l(k+4),\ k=0,1 $

In this FFT algorithm, the computing of DFT is still divided into two levels. However, we will first compute three 2 points DFT, which are DFT of the first half points and the second half points. According to analysis of Question 1, we need N/2=3 times of complex multiplications and N=6 times of complex additions.

Second, we compute the two 3 points DFT using first level result. we need 4 times of complex multiplications (consider when l=0 and k=0,3 there are no multiplies needed) and 6 times of complex additions for each 3-point DFT. Since we have to do this twice, we need 4*2=8 times of complex multiplications and 6*2=12 times of complex additions.

In total, we need 3+8=11 times of complex multiplications and 6+12=18 times of complex additions.

Note that the output sequences of DFT of 2) is different from 1).

Compare 1) and 2), both methods have the same amount of complex operations.

## Question 5

Flow Diagram:

$ 5120=5*1024=5*2^{10} $ So we can split the 5120-point DFT into 5 1024-point DFTs using decimation-in-time and compute the 1024-point DFT using the subroutine of radix 2 FFT.

Analytical expression:

$ \begin{align} X^{(5120)}(k)&=\sum_{n=0}^{5119} x(n)e^{-\frac{j2\pi kn}{5120}} \\ &\text{Change variable n=5m+l, m=0,1,...,1023; l=0,1,...,4 } \\ X^{(5120)}(k)&=\sum_{l=0}^{4}\sum_{m=0}^{1023}x(5m+l)e^{-\frac{j2\pi k(5m+l)}{5120}} \\ &=\sum_{l=0}^{4}e^{-\frac{j2\pi kl}{5120}}\sum_{m=0}^{1023}x(5m+l)e^{-\frac{j2\pi km}{1024}} \\ &=\sum_{l=0}^{4}W_{5120}^{kl}X_l^{(1024)}(k) \text{ ,k=0,1,...,5119 } \end{align} $

Direct computation requires N*N=5120*5120=26214400 times of complex multiplications and N*(N-1)=5120*5119=26209280 times of complex additions.

Using FFT we first perform five 1024-point FFTs, which each require $ \frac{N}{2}log_2 N=512*10=5120 $ complex multiplications and $ Nlog_2 N=1024*10=10240 $ complex additions.

To calculate each of the 5120 final output of the 5120 DFT, we have to perform 5 complex multiplications and 4 complex additions. So we need 5120*5= 25600 times of complex multiplications and 5120*4=20480 times of complex additions.

For the FFT based method we have a total of 5120+25600=30720 complex multiplications and 10240+20480=30720 complex addtions.

By compare the two methods, we see that FFT based method is far more efficient than the direct computation.