实用数字信号处理——笔记与基于C++与python的实验(5)

参考书：《实用数字信号处理：从原理到应用》 Steven W. Smith
本笔记的内容倾向于计算机专业的程序设计，便于学习（复习）C++、python等知识；
本文是笔记而不是教程，所以仅供参考；

5.1 DFT和DTFT

https://vrlab.meijo-u.ac.jp/edu/sinewave-dtft2dft.html

DFT:

$X[k]=\sum{^{N-1} _{n=0} }x[n]e^{-jn2 \pi ft} = \sum{ ^{N-1} _{n=0} }x[n]e^{ -jn2 \pi \frac{k}{N}} ( \omega _k = \frac{2 \pi k}{N})$

DTFT:

$X[k]=\sum{^{N-1} _{n=0} }x[n]e^{-jnf}=\sum{ ^{N-1} _{n=0} }x[n]e^{-jn\omega}$

区别：

1. DFT作用的对象是有限长离散时间非周期信号，DTFT作用的对象也是有限长离散时间非周期信号（回忆：DFS作用的对象是无限长离散时间周期序列）
2. DFT的结果是频域上的离散周期信号，DTFT的结果是频域上的无限长非周期信号

所以：对一个长度为N的有限长序列进行DTFT运算后，再把得到的频谱进行抽样频率为 $\omega _k = \frac{2 \pi k}{N}$ 的抽样，结果等于对此序列进行DFT运算的结果；

5.2 卷积和DFT

对比卷积和dft的代码：

vector<complex<double>> DFT(vector<complex<double>> arr,int N){
    vector<complex<double>> ret(N);
    complex<double> temp{0, 0};
    for (int k = 0; k < N;k++){
        ret[k].imag(0);
        ret[k].real(0);
        for (int i = 0; i < N;i++){
            temp.real(cos(2*M_PI*k*i/N));
            temp.imag(-sin(2*M_PI*k*i/N));
            ret[k] += arr[i] * temp;
        }
    }
    return ret;
}

template <typename T1,typename T2>
vector<double> convolution_output_side(vector<T1> X,vector<T2> H){
vector<double> Y(X.size()+H.size(), 0);
for(int i = 0; i < Y.size(); i++){ 
    for(int j = 0; j < H.size(); j++){ 
        if(i - j < 0) 
            continue;
        if(i - j >= X.size() ) 
            continue;
        Y[i] += X[i - j] * H[j];
    }
}
return Y;
}

发现dft和卷积进行的计算量一样大；仅仅简单地通过dft将问题换到频域去计算，计算量很大，对解决问题没有实质的帮助，后面FFT的诞生才出现了突破。