Signal processing: ＜ three ＞ DFT and FFT

   DFT, Discrete Fourier transform , Fourier transform is discrete in both time domain and frequency domain , The time domain sampling of the signal is transformed into its DTFT Frequency domain sampling of .

1、 DFT Mathematical expression

$$X[k]=\sum _{n=0}^{N}x[n]W_N^{kn}=\sum _{n=0}^{N}x[n]e^{-j\frac{2\pi k\mathrm{n}}{N}}$$
among $0\le k\le N$.
   It can be seen from the above formula , do DFT need $N^2$ Multiple complex multiplication and $N(N-1)$ Sub complex addition 【 Find a point X[k] need $N$ Multiple complex multiplication and $N-1$ Sub complex addition 】, And a complex number multiplication is made up of 4 Times real number multiplication and 2 Sub real number addition constitutes , A plural addition consists of 2 Sub real number addition constitutes , The specific explanation is as follows ：
$$\begin{array}{l}\left(a+jb\right)\bullet \left(c+jd\right)=\left[ac-bd\right]+j\left[ad+bc\right]\\ \left(a+jb\right)+\left(c+jd\right)=\left[a+c\right]+j[b+d]\end{array}$$ therefore , do DFT need $4N^2$ Times real number multiplication and $(2N^2+2N^2-2N)or[2(2N^2-N]$ Sub real number addition . To reduce complexity , Raises the FFT Algorithm , Its idea is to use the idea of decomposition to N spot DFT The calculation of is decomposed into smaller DFT Calculate and use the complex number $W_N^{kn}$ Calculation of periodicity and symmetry of .

2 、$W_N^{kn}$ The understanding of the

  $W_N^{kn}=e^{-j2\pi kn/N}=cos(j2\pi kn/N)-jsin(j2\pi kn/N)$,$W_N^{kn}$ yes $W_N$ Of kn The next power ,$W_N^1=e^{-j2\pi kn/N}=cos(j2\pi /N)-jsin(j2\pi /N)$,$W_N^1$ It can be understood as the unit circle 360 Keratosis into $N$ Share , therefore $W_N^{1} It's actually a value that rotates on the unit circle of the complex plane . As shown in the figure below ： Set the unit circle to 360 Divided into 8 Share , Then each copy corresponds to 45 degree .

It is not difficult to get the properties of the rotation factor from the graph ：
a） periodic ：$W_N^{a+N}=W_N^a$
b) symmetry ：$W_N^{a+N/2}=-W_N^a$
c) Scalability ：$W_N^2=-W_{N/2}^1$

2 、FFT The understanding of the

2.1 Fourier transform based on time

As shown in the figure ：$x(n)$ The sum of two sequences decomposed into even and odd numbers , namely

$x1(n)$ and $x2(n)$ It's all the length of $N／2$,$x_1(n)$ Is an even sequence ,$x_2(n)$ Is an odd sequence ,$x_1(n)=x(2n)$,$x_2(n)=x(2n+1)$,$n=0,1...N/2-1$. be
$$X(k)=\sum _{n=0(nbyaccidentallyCount)}^{N}x[n]W_N^{kn}+\sum _{n=0(nbyp.Count)}^{N}x[n]W_N^{kn}=\sum _{n=0}^{N/2-1}{x}_1[n]W_N^{2kn}+\sum _{n=0}^{N/2-1}x[n]W_N^{k(2n+1)}$$
among $X_1(k)$ and $X_2(k)$ Respectively $x_1(n)$ and $x_2(n)$ Of N／2 spot DFT.
$$X_1[k]=\sum _{n=0}^{N/2-1}{x}_1[n]W_{N/2}^{kn}$$
$$X_2[k]=\sum _{n=0}^{N/2-1}{x}_2[n]W_{N/2}^{kn}$$
because $X_1(k)$ and $X_2(k)$ in N／2 For cycles , And we know from symmetry $W_N^{k+N/2}=-W_N^k$, therefore X(k) It can also be expressed as ：

The operation of the above formula can be represented by the following figure , According to its shape, it is called butterfly operation .

It can be seen from the above figure that N spot DFT Decompose into N／2 Two points DFT, Calculating a dish operation requires 1 Multiple complex multiplication and 2 Sub complex addition . From the beginning N=8 For example ,
Calculate a $N$ Dot DFT You need to calculate two $N/2$ Of DFT and N/2 Butterfly operation of , By analogy , You can find , Calculation N Dot DFT Finally, it can be divided into N/2 Two DFT, Through induction, we can find ,N Dot DFT It can be divided into $lo{g}_2^N$ level , Each level has $N/2$ Butterfly operations constitute , Therefore, there are a total of $N/2Time$ Multiplicative sum $N$ Add again , One $N$ Dot DFT All in all $N/2lo{g}_2^N$ Multiple complex multiplication and $Nlo{g}_2^N$
   Direct calculation DFT And utilization FFT Calculation DFT For example, the following figure shows ：

3、 Programming idea

3.1 In situ calculation

4、 Inverse Fourier transform

5、 Reference material

【1】 The fast Fourier transform FFT analysis
【2】 The fast Fourier transform (FFT) The derivation process of (DIT)
【3】 The fast Fourier transform FFTppt Courseware .ppt
【4】1024 spot fft Principle and fpga Realization
【5】 The fast Fourier transform FFT-PPT（ fine