# Quiz Chapter 11.05: Informal Development of Fast Fourier Transform

 MULTIPLE CHOICE TEST INFORMAL DEVELOPMENT OF FAST FOURIER TRANSFORM FAST FOURIER TRANSFORMS

1. Using the definition $W=e^{-i (2 \pi / N)}$, and the Euler identity $e^{\pm i \theta}= \cos (\theta) \pm i \sin (\theta)$, the value of $W^{(N / 6)}$ can be computed as

2. Using the definition $W=e^{-i (2 \pi / N)}$, and the Euler identity $e^{\pm i \theta}= \cos (\theta) \pm i \sin (\theta)$, the value of $W^{(6N)}$ can be computed as

3. Given $N=2$, and

• $\{ f \} = \begin{Bmatrix} f(0) \\ f(1) \\ \end{Bmatrix} = \begin{Bmatrix} 14+6i \\ -2+4i \\ \end{Bmatrix}$

The first part of $\widetilde{C}(n) = \displaystyle\sum_{k=0}^{N-1} f (k) W^{nk}$ can be expressed as

• $\widetilde{C} (0) = \displaystyle\sum_{k=0}^{1} f(k)W^{nk} = f(0) W^{(0)(0)} + f(1)W^{(0)(1)}$
• $\,$
• $\widetilde{C} (1) = f(0)W^{(1)(0)} + f(1)W^{(1)(1)}$

The values for $\begin{Bmatrix}\widetilde{C}(0)\\ \widetilde{C}(1) \\ \end{Bmatrix}$ can be computed as

4. For $N=2^{4}=16$, level $L=3$ and referring to figure $1$ (shown in this link), the only terms of vector $f_{2}(-)$ which only need to compute are

5. For $N=2^{4}=16$, level $L=3$ and referring to figure $1$ (shown in this link), the only companion nodes associated with $f_{3}(0)$ and $f_{3}(1)$ are

6. Given $N=4$, and

• $f_{0} \left( \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ \end{matrix} \right) = \begin{Bmatrix} -4+i \\ 1-2i \\ -2+3i \\ 3-4i \\ \end{Bmatrix}$

Corresponding to level $L=1$, one can compute $f_{3}(2)$ as