View source for Aufgaben:Exercise 5.5Z: Complexity of the FFT


{{quiz-Header|Buchseite=Signal_Representation/Fast_Fourier_Transform_(FFT)
}}

[[File:P_ID1179__Sig_Z_5_5.png|right|frame|Final step of the FFT for $N=8$]]
The&nbsp; $\rm FFT$&nbsp; algorithm&nbsp; ("Fast Fourier Transform")&nbsp; realises a&nbsp; "Discrete Fourier Transform"&nbsp; $\rm (DFT)$&nbsp; with the smallest possible computational effort if the parameter&nbsp; $N$&nbsp; is a power of two.&nbsp; In detail, the following calculation steps are necessary to carry out an FFT:
*The FFT occurs in&nbsp; ${\rm log_2} \ N$&nbsp; stages, whereby the exact same number of arithmetic operations must be carried out in each stage. 
*The diagram shows the third and last stage for the example&nbsp; $N = 8$.&nbsp; It can be seen that&nbsp; $N/2$&nbsp; basic operations have to be carried out in this and the other stages.
*In each basic operation called&nbsp; '''butterfly''',&nbsp; two complex outputs are calculated from the two complex input variables&nbsp; $E_1$&nbsp; and&nbsp; $E_2$&nbsp;:
:$$ A_1  = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, $$
:$$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$
*Here&nbsp; $w =  {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$&nbsp; denotes the complex rotation factor.&nbsp; For&nbsp;  $N = 8$&nbsp; the value&nbsp; $w =  {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.
*The exponent&nbsp; $\mu$&nbsp; for this complex rotation factor can take all integer values between&nbsp; $0$&nbsp; and&nbsp; $N/2-1$.&nbsp; For&nbsp; $N = 8$&nbsp; it is:
:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}
\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm
j},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j}
\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$

The purpose of this task is to determine the number of arithmetic operations&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; required for the FFT and compare it with the value&nbsp; $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$&nbsp; that can be specified for the DFT.





''Hints:'' 
*This task belongs to the chapter&nbsp; [[Signal_Representation/Fast_Fourier_Transform_(FFT)|Fast Fourier Transform (FFT)]].
*It makes sense to calculate the powers of&nbsp; $w$&nbsp; before the actual algorithm and store them in a lookup table.&nbsp; The operations necessary for this are to be disregarded.
*The&nbsp; "bit reversal operation"&nbsp; – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.
 




===Questions===

<quiz display=simple>
{How many real additions&nbsp; $(A_{\rm A})$&nbsp; does a complex addition require?
|type="{}"}
$A_{\rm A} \hspace{0.3cm} = \ $ { 2 }

{How many real additions&nbsp; $(A_{\rm M})$&nbsp; and multiplications&nbsp; $(M_{\rm M})$&nbsp; are required for a complex multiplication?
|type="{}"}
$A_{\rm M} \hspace{0.3cm} = \  $ { 2 }
$M_{\rm M} \hspace{0.2cm} = \  $ { 4 }

{How many complex additions/subtractions&nbsp; $(a_{\rm B})$&nbsp; does a single basic operationn&nbsp; ("butterfly")&nbsp; require?
<br>How many complex multiplications&nbsp; $(m_{\rm B})$&nbsp; are required per basic operation?
|type="{}"}
$a_{\rm B} \hspace{0.32cm} = \ $  { 2 }
$m_{\rm B} \hspace{0.2cm} = \ $  { 1 }

{How many arithmetic operations&nbsp; (additions, subtractions, multiplications alike)&nbsp; does a basic operation require?
|type="{}"}
$\mathcal{O}_{\rm B} \ = \ $  { 10 }

{How many real operations&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; does the entire FFT&ndash;algorithm require?&nbsp; What are the values for&nbsp; $N = 16$&nbsp; und&nbsp; $N = 1024$?
|type="{}"}
$N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }
$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 3% }

{What is the time gain&nbsp; $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$&nbsp; for&nbsp; $N = 16$&nbsp; and&nbsp; $N = 1024$?
|type="{}"}
$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }
$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $ { 164 3% }

</quiz>

===Solution===
{{ML-Kopf}}
'''(1)'''&nbsp; Each complex addition requires two real additions:
:$$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 +
R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
\hspace{0.15 cm}\underline{ A_{\rm A} =
2}\hspace{0.05cm}.$$


'''(2)'''&nbsp; Any complex multiplication requires four real multiplications and two real additions:
:$$(R_1 + {\rm j} \cdot I_1)  (R_2 + {\rm j} \cdot I_2) = (R_1 \cdot
R_2 - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \cdot
I_1)\hspace{0.3cm}
\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{A_{\rm M} = 2,\hspace{0.3cm}M_{\rm M} =
4} \hspace{0.05cm}.$$


'''(3)'''&nbsp; The basic operations with complex inputs&nbsp; $E_1$,&nbsp; $E_2$&nbsp; and&nbsp; $w^{\hspace{0.04cm}\mu}$ are:
:$$ A_1  = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu},\hspace{0.5cm}  A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$
*This means one complex multiplication and two complex additions: &nbsp; $\hspace{0.15 cm}\underline{a_{\rm B} = 2, \hspace{0.2cm}m_{\rm B} = 1}
 \hspace{0.05cm}.$


'''(4)'''&nbsp; In contrast to the first computers, a multiplication today does not take much more computing time than an addition or subtraction.

*Using the results of subtasks&nbsp; '''(1)''',&nbsp; '''(2)'''&nbsp; and&nbsp; '''(3)'''&nbsp; we obtain for the total number of arithmetic operations:
:$$ \mathcal{O}_{\rm B} = a_{\rm B}\cdot A_{\rm A} + a_{\rm B}\cdot (A_{\rm M}
+M_{\rm M} ) = 2 \cdot 2 + 1 \cdot 6\hspace{0.15 cm}\underline{ = 10}
 \hspace{0.05cm}.$$


'''(5)'''&nbsp; There are&nbsp; ${\rm log_2} \ N$ stages in total, each of which requires&nbsp; $N/2$&nbsp; basic operations to be performed:
:$$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot
\mathcal{O}_{\rm B} = 5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N$$
:$$\Rightarrow \hspace{0.3cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=16)  =  5\cdot 16 \cdot
4 \hspace{0.15 cm}\underline{= 320}, \hspace{0.5cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=1024)  =  5\cdot 1024
\cdot 10 \hspace{0.15 cm}\underline{= 51200}
 \hspace{0.05cm}.$$


'''(6)'''&nbsp; The computational time gain of the FFT over the conventional DFT is given by:
:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdot
N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm
log_2}\hspace{0.1cm}N}$$
:$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16)  =  1.6 \cdot
\frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024)  =  1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164}
 \hspace{0.05cm}.$$


{{ML-Fuß}}



[[Category:Signal Representation: Exercises|^5.5 Fast Fourier Transform ^]]