如何理解FFT

admin

https://blog.csdn.net/shichaog/article/details/75692855

语音增强和语音识别系列博文

时域信号分为周期/非周期，连续和离散，这样有四中样式的傅里叶变换。

变换类型

时域信号特性

频谱特性

连续时域FT

连续，非周期

非周期，连续

离散时域傅里叶变换DTFT

离散非周期

周期，连续

傅里叶级数FS

连续，周期

非周期，离散

离散傅里叶变换DFT

离散，周期

周期，离散

如上可以看到，在一个域的离散信号，在另一个域将变成周期的，类似的，在一个域连续的信号，在另外一个域必然是非周期的。

DFT

分为实数和复数版本的DFT，实数版本输入是实数，得到的频域点将有两个集合，分别是<span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="cos" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">coscos和<span class="MathJax" id="MathJax-Element-4-Frame" tabindex="0" data-mathml="sin" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">sinsin函数的系数。复数输入表示的是正负频率。

实 DFT

对于输入是<span class="MathJax" id="MathJax-Element-5-Frame" tabindex="0" data-mathml="x(n)" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">x(n)x(n)的N点DFT将获得<span class="MathJax" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="N/2+1" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">N/2+1N/2+1的两组<span class="MathJax" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="cos" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">coscos和<span class="MathJax" id="MathJax-Element-8-Frame" tabindex="0" data-mathml="sin" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">sinsin系数

Xre[k]=2N∑n=0N−1x[n]cos(2πknN),K=0,1,..,N/2Xre[k]=2N∑n=0N−1x[n]cos⁡(2πknN),K=0,1,..,N/2

Xim[k]=2N∑n=0N−1x[n]sin(2πknN),K=0,1,..,N/2Xim[k]=2N∑n=0N−1x[n]sin⁡(2πknN),K=0,1,..,N/2

根据系数获取原始输入时，需要对Xre[0]Xre[0]和Xre[N/2]Xre[N/2]除以2。
复DFT

对于N点复数DFT变换后得到的是N点<span class="MathJax" id="MathJax-Element-13-Frame" tabindex="0" data-mathml="X[k]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">X[k]X[k]。

X[k]=1N∑n=0N−1x[n]e−j2πkn/NX[k]=1N∑n=0N−1x[n]e−j2πkn/N

变换后的X[0]X[0]是直流分量，1∼N/21∼N/2是正频成分，X[N/2]X[N/2]是奈奎斯特频率，接下来的N/2−1N/2−1是负频分量。
从频谱获得原始输入信号的公式是：

x[n]=∑k=0N−1X[k]ej2πkn/Nx[n]=∑k=0N−1X[k]ej2πkn/N

当时域信号是实数时，计算复DFT时，将虚部填零，下图是matlab fft函数计算的DFT结果。

FFT

FFT是DFT计算的快速方法。

X[k]=∑n=0N−1x[n]e−j2πkn/NX[k]=∑n=0N−1x[n]e−j2πkn/N

x[n]=1N∑k=0N−1X[k]ej2πkn/Nx[n]=1N∑k=0N−1X[k]ej2πkn/N

matlabx=fft(x,N),%计算X[k]x=ifft(x,N)

• 1
• 2
• 3
  

FFT结果举例

假设<span class="MathJax" id="MathJax-Element-22-Frame" tabindex="0" data-mathml="x[n]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">x[n]x[n]是频率<span class="MathJax" id="MathJax-Element-23-Frame" tabindex="0" data-mathml="fc=10Hz" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">fc=10Hzfc=10Hz余弦信号,采样率是<span class="MathJax" id="MathJax-Element-24-Frame" tabindex="0" data-mathml="fs=32&#x2217;fc" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">fs=32∗fcfs=32∗fc

fc=10;fs=32*fc;%sampling frequency with oversampling factor=32t=0:1/fs:2-1/fs;%2 seconds durationx=cos(2*pi*fc*t);%time domain signal (real number)subplot(3,1,1); plot(t,x);hold on; %plot the signaltitle('x[n]=cos(2 \pi 10 t)'); xlabel('n'); ylabel('x[n]');

• 1
• 2
• 3
• 4
• 5
• 6
• 7
  

做<span class="MathJax" id="MathJax-Element-25-Frame" tabindex="0" data-mathml="N=256" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">N=256N=256点FFT

X = fft(x,N);%N-point complex DFT%output contains DC at index 1, Nyquist frequency at N/2+1 th index%positive frequencies from index 2 to N/2%negative frequencies from index N/2+1 to N

• 1
• 2
• 3
• 4
  

matlab数组从1开始，输出1-N，频点间隔是<span class="MathJax" id="MathJax-Element-26-Frame" tabindex="0" data-mathml="&#x0394;f=fsN" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">Δf=fsNΔf=fsN,先输出直流分量，然后是正频分量，再然后是负频分量，在MATLAB中使用fftshift后将频率按，负频分量，直流以及正频分量排列。

实信号

1）实数信号以<span class="MathJax" id="MathJax-Element-27-Frame" tabindex="0" data-mathml="fs" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">fsfs为采样率，那奎斯特采样定理表明混跌频率是<span class="MathJax" id="MathJax-Element-28-Frame" tabindex="0" data-mathml="fs/2" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">fs/2fs/2，则
2）实数信号的fft结果中前半部分是<span class="MathJax" id="MathJax-Element-29-Frame" tabindex="0" data-mathml="[0,fs/2]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">[0,fs/2][0,fs/2]，后半部分是<span class="MathJax" id="MathJax-Element-30-Frame" tabindex="0" data-mathml="[fs/2,fs]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">[fs/2,fs][fs/2,fs]由于周期性，在频谱不混跌的情况下，后半部分等于<span class="MathJax" id="MathJax-Element-31-Frame" tabindex="0" data-mathml="[&#x2212;fs/2,0]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">[−fs/2,0][−fs/2,0]，在上图中看到第一个数是<span class="MathJax" id="MathJax-Element-32-Frame" tabindex="0" data-mathml="36+0i" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">36+0i36+0i，这就是直流分量，
3）另外还应该注意到第i个数，实际上等于第<span class="MathJax" id="MathJax-Element-33-Frame" tabindex="0" data-mathml="N&#x2212;i" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">N−iN−i个数的共轭，
4）所以实际上实数的快速傅里叶算法会利用这个性质减小运算量和存储空间，这是在代码级别的优化
5）在实际频率显示时，某些场合期望得到<span class="MathJax" id="MathJax-Element-34-Frame" tabindex="0" data-mathml="[&#x2212;fs/2,fs/2]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">[−fs/2,fs/2][−fs/2,fs/2]显示频谱，通常会使用matlab 的fftshift来实现这个功能。

复信号

1）对于复信号没有负频率，以<span class="MathJax" id="MathJax-Element-35-Frame" tabindex="0" data-mathml="fs" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">fsfs采样率的信号，fft频谱的结果是从<span class="MathJax" id="MathJax-Element-36-Frame" tabindex="0" data-mathml="[0,fs]" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">[0,fs][0,fs]；
2）在<span class="MathJax" id="MathJax-Element-37-Frame" tabindex="0" data-mathml="f&gt;fs/2" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">f>fs/2f>fs/2时，对复信号的fft结果进行fftshift会产生频谱混跌。