Quiz Chapter 11.05: Informal Development of Fast Fourier Transform

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