General Information

The following two figures refer to the radix-2 FFT algorithm’s recursive tree. The first one depicts the recursive calls done in each stage, whereas the second pictorially outlines the intuition behind the bit-reversal permutation.

Recursive Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
\documentclass{standalone}
\usepackage[edges]{forest}
\begin{document}
    \begin{forest}
        for tree={
            draw,
            fill=gray!30,
            s sep+=3ex,
            l sep+=4ex,
            math content,
            edge={semithick},
            where n children={0}{}{label={}}}
        [{
            a_{0}~~
            a_{1}~~
            a_{2}~~
            a_{3}~~
            a_{4}~~
            a_{5}~~
            a_{6}~~
            a_{7}
          }
         [{
            a_{0}~~
            a_{2}~~
            a_{4}~~
            a_{6}
          }
          [{
            a_{0}~~
            a_{4}
           }
           [a_{0}]
           [a_{4}]
          ]
          [{
            a_{2}~~
            a_{6}
           }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Recursive Tree – Binary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
\documentclass{standalone}
\usepackage[edges]{forest}
\usepackage{xcolor}
\definecolor{mycolor0}{RGB}{44, 117, 226}
\definecolor{mycolor1}{RGB}{255, 103, 15}
\begin{document}
    \begin{forest}
        for tree={
            draw,
            fill=gray!30,
            s sep+=1ex,
            l sep+=4ex,
            math content,
            edge={semithick},
            where n children={0}{}{label={}}}
        [{
            a_{00{\color{mycolor0}0}}~~
            a_{00{\color{mycolor1}1}}~~
            a_{01{\color{mycolor0}0}}~~
            a_{01{\color{mycolor1}1}}~~
            a_{10{\color{mycolor0}0}}~~
            a_{10{\color{mycolor1}1}}~~
            a_{11{\color{mycolor0}0}}~~
            a_{11{\color{mycolor1}1}}
          }
         [{
            a_{0{\color{mycolor0}0}0}~~
            a_{0{\color{mycolor1}1}0}~~
            a_{1{\color{mycolor0}0}0}~~
            a_{1{\color{mycolor1}1}0}
          }, for tree={edge=mycolor0}
          [{
            a_{{\color{mycolor0}0}00}~~
            a_{{\color{mycolor1}1}00}
           }
           [a_{000}, for tree={edge=mycolor0}]
           [a_{100}, for tree={edge=mycolor1}]
          ]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX