An Implementation of Fast Fourier Transform
├── LICENSE
├── README.md
├── src
│ ├── complex.h
│ ├── dft.h
│ ├── dif_fft.h
│ ├── dit_fft.h
│ ├── fft
│ ├── fft.cpp
│ └── validate_n_evaluate.h
└── tex
-
Work by Brian Lin, Tzu-Heng
- W42, 2014011054
- Dept. of Electronic Engineering, Tsinghua University
- DSP Course Work
-
Decimate in Time/Frequency, Fast Fourier Transform
-
2-base DIT-FFT, 2-base DIF-FFT & the Original DFT method
-
You can change the
[input sequence]
in themain()
function offft.cpp
. -
Usage:
make ./fft ./fft [N_max] [validate_or_evaluate] [dft_dit_dif]
-
-
There are two modes.
- Mode 1: Output the result of DFT using three methods respectively.
- Mode 2: Evaluate the performance of three algorithms respectively.
-
Mode 1: Output
-
To output result of N=2^k point DFT / DIT-FFT / DIF-FFT:
# DFT: ./fft 8 1 1 # Calc a 8-point sequence ./fft 16 1 1 # Calc a 16-point sequence # DIT-FFT: ./fft 16 1 2 # DIF-FFT: ./fft 16 1 3 # All: ./fft 16 1 4
-
-
Mode 2: Evaluate Performance
-
To output the run time of DFT / DIT-FFT / DIF-FFT
- executing N = 2^{ (10), (11), ..., (10+N_max-1) } respectively.
# DFT: ./fft 4 0 1 # Calc 2^{10~13} ./fft 6 0 1 # Calc 2^{10~15} ./fft 7 0 1 # Calc 2^{10~16} # DIT-FFT: ./fft 7 0 2 # DIF-FFT: ./fft 7 0 3 # All: ./fft 7 0 4
-
-
Mode 1: Output
-
The result of command
./fft 8 1 4
may look like this:Lin, Tzu-Heng's Work, 2014011054, W42 Dept. of Electronic Enigeering, Tsinghua University Starting, This project is to calc DFT in Original-DFT / DIT-FFT / DIF-FFT... For Usage, Please see 'fft.cpp' Calculating DFT... X[0] = 2 + j*0 X[1] = 1.70711 + j*-0.707107 X[2] = 1 + j*-1 X[3] = 0.292893 + j*-0.707107 X[4] = 1.33227e-15 + j*-5.35898e-08 X[5] = 0.292893 + j*0.707107 X[6] = 1 + j*1 X[7] = 1.70711 + j*0.707107 Calculating DIT-FFT... X[0] = 2 + j*0 X[1] = 1.70711 + j*-0.707107 X[2] = 1 + j*-1 X[3] = 0.292893 + j*-0.707107 X[4] = 0 + j*0 X[5] = 0.292893 + j*0.707107 X[6] = 1 + j*1 X[7] = 1.70711 + j*0.707107 Calculating DIF-FFT... X[0] = 2 + j*0 X[1] = 1.70711 + j*-0.707107 X[2] = 1 + j*-1 X[3] = 0.292893 + j*-0.707107 X[4] = 0 + j*0 X[5] = 0.292893 + j*0.707107 X[6] = 1 + j*1 X[7] = 1.70711 + j*0.707107
-
-
Mode 2: Output
-
The result of command
./fft 7 0 4
may look like this:Lin, Tzu-Heng's Work, 2014011054, W42 Dept. of Electronic Enigeering, Tsinghua University This project is to calc DFT in Original-DFT / DIT-FFT / DIF-FFT... For Usage, Please see 'fft.cpp' Calculating DIT-FFT... N = 1024 Run time = 2 ms N = 2048 Run time = 6 ms N = 4096 Run time = 14 ms N = 8192 Run time = 24 ms N = 16384 Run time = 53 ms N = 32768 Run time = 106 ms N = 65536 Run time = 200 ms Calculating DIF-FFT... N = 1024 Run time = 1 ms N = 2048 Run time = 3 ms N = 4096 Run time = 7 ms N = 8192 Run time = 16 ms N = 16384 Run time = 39 ms N = 32768 Run time = 79 ms N = 65536 Run time = 154 ms Calculating DFT... N = 1024 Run time = 38 ms N = 2048 Run time = 180 ms N = 4096 Run time = 771 ms N = 8192 Run time = 2948 ms N = 16384 Run time = 12811 ms N = 32768 Run time = 61836 ms N = 65536 Run time = 356046 ms
-