当前位置：网站首页>MATALB signal processing - signal transformation (6)

MATALB signal processing - signal transformation (6)

2022-06-29 03:13:00 【It's an egg】

2-6 The fast Fourier transform

The fast Fourier transform (fast Fourier transform), That is, the discrete Fourier transform is calculated by computer （DFT) It's efficient 、 Fast computing methods , abbreviation FFT. The fast Fourier transform is 1965 Year by year J.W. Cooley and T.W. Tuki proposed . This algorithm can greatly reduce the number of multiplication required by the computer to calculate the discrete Fourier transform , In particular, the number of samples to be transformed N The more ,FFT The more significant the computational cost of the algorithm is .

1.DFT The existing problems and FFT Basic flow

Finite length sequences can be transformed by discrete Fourier transform (DFT） The frequency domain is also discretized into finite sequences . This involves complex multiplication and complex addition , Compared with real number multiplication and real number addition , The number of operations of a complex number is several times more , And we actually take N The value of is also very large , Therefore, the calculation amount of the whole process is too large , It's hard to deal with problems in real time .

take DFT Medium $e^{-j\frac{2\pi}{N}nk}$ Defined as an exponential factor $w_{N}$ , Because of the particularity of its exponential function , It has symmetry and periodicity , Its properties can be used to reduce the amount of calculation .

FFT The basic process is ：1. Put the original N Point sequence , It is decomposed into a series of short sequences ;2. Find out the corresponding DFT And make appropriate combination , To remove double counting , The purpose of reducing multiplication and simplifying structure . Does it sound very similar to the combinatorial operations learned in primary school .

2.FFT The calculation method of

A fast method for computing discrete Fourier transform , There are time - based FFT Algorithm and frequency decimation FFT Algorithm . The former is to divide the time-domain signal sequence into even and odd , The latter is to arrange the frequency domain signal sequence according to even and odd . They all rely on two features of ： One is periodicity ; The second is symmetry , Here symbol * Represents its conjugate . such , The calculation of the discrete Fourier transform can be divided into several steps , Greatly improved computing efficiency .

1. Extract by time

Let the signal length be N（2 The power of ）, Time domain signal sequence can be x(n) Break it down into two parts , One is the even part x（2n）, The other is the odd part x（2n+1）, $x_{1}(n)=x(2n)$ , $x_{2}(n)=x(zn+1)$ ,DFT The operation of is also divided into 2 part

$x(k)=\sum_{n=0}^{N-1}x(n)w_{N}^{nk}=\sum_{r=0}^{N/2-1}x(r)w_{N}^{2rk}+\sum_{r=0}^{N/2-1}x(2r+1)w_{N}^{(2r+1)k}=\sum_{r=0}^{N/2-1}x(2r)w_{N}^{2rk}+w_{N}^{k}\sum_{r=0}^{N/2-1}x(2r+1)w_{N}^{2rk}$

among $w_{N}^{2n}=e^{-j\frac{2\pi}{N}2n}=e^{-j\frac{2\pi}{N/2}n}=w_{N/2}^{n}$

Yes $X(k) = \sum_{r=0}^{N/2-1}x(2r)W_{\frac{N}{2}}^{rk}+W_{N}^{k}\sum_{r=0}^{N/2-1}x(2r+1)W_{N\frac{N}{2}}^{rk}=G(k)+W_{N}^{k}H(k)$ .H(k),G(k) There are N/2 A little bit , from 0 To N/2-1.

According to symmetry , Yes $w_{N/2}^{r(N/2+k)}=w_{N/2}^{rk},W_{N}^{k+N/2}=-W_{N}^{k}$ , that $X(k+\frac{N}{2})=G(k)-W_{N}^{k}H(k),k=0,1,\cdot \cdot\cdot,\frac{N}{2}-1$ , therefore , A sampling point is N Signal sequence x(n） Discrete Fourier transform based on Wavelet Transform , It can be made up of two N/2 The discrete Fourier transform of the sampling point sequence is obtained . And so on , This time-based decimation algorithm divides the input signal sequence into smaller and smaller subsequences for discrete Fourier transform calculation , Finally, it is synthesized into N Discrete Fourier transform of points .

$X(k+\frac{N}{2}) = G(k)-W_{N}^{k}H(k),k = 0,1,\cdot\cdot \cdot ,\frac{N}{2}-1$

Usually, the signal flow graph of butterfly algorithm is used to represent the discrete Fourier transform operation . for example ,N=8 The signal sequence of sampling points x(n） Discrete Fourier transform based on Wavelet Transform , Available as shown in the figure 2 Shown FET The signal flow graph of the algorithm .

about N=2^M, adopt M Second decomposition , Will eventually become 2 Dot DFT operation , Constitute from x(n) To X(k) Of M Level operation .　N=2 The calculation of the discrete Fourier transform of points consists entirely of butterfly operations , need M Level operation , Each level includes N/2 Butterfly operation , All in all $log_{2}N$ (M) Butterfly operation . therefore , The total amount of calculation is $\frac{N}{2}log{_{2}}^{}N$ Multiple complex multiplication and $Nlog_{2}N$ Sub complex addition operation .

2. Extract by frequency

For frequency extraction , The input sequence is not decomposed by odd or even numbers , Instead, the entire sequence is truncated from the middle , Front and back halves , namely

$X(k) = \sum_{n=0}^{N/2-1}x(n)W_{N}^{nk}+\sum _{n=N/2}^{N-1}x(n)W_{N}^{nk}=\sum_{n=0}^{N/2-1}x(n)W_{N}^{nk}+\sum _{n=0}^{N/2-1}x(n+\frac{N}{2})W_{N}^{(n+\frac{N}{2})k}=\sum_{n=0}^{N/2-1}[x(n)+W_{N}^{(\frac{N}{2}k)}x(n+N/2)]W_{N}^{nk}$

According to the expansion of exponential factor , You can know $W_{N}^{N/2}=-1,W_{N}^{(N/2)k}=(-1)^k$ , $\sum_{n=0}^{N/2-1}[x(n)+(-1)^kx(n+N/2)]W_{N}^{nk}$ It is further decomposed into odd arrays and even groups ,