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

参考书：《实用数字信号处理：从原理到应用》 Steven W. Smith
本笔记的内容倾向于计算机专业，电路相关的内容会较少而程序方面的会比较多，且能够便于学习（复习）C++的知识；
本文是笔记而不是教程，所以仅供参考；

4.1.离散傅里叶变换（DFT）

4.2.如何从多个角度理解dft？

（以后补充详细内容，这部分先略过）
1.公式推导
2.正交分解
3.矩阵

离散傅里叶正变换：
复数形式:

$X[k]=\sum{ ^{N-1}_{n=0}}x[t] e^{ -jn2\pi ft}$

根据欧拉公式，改写成：

$X[k]=\sum{^{N-1}_{n=0}}x[n] (\cos{ (\frac{ {2\pi kn} }{N}) } -i\sin{ (\frac{ {2\pi kn} }{N})})$

离散傅里叶逆变换：

$X[k]=\frac{1}{N}\sum{^{N-1}_{n=0}}x[n] (\cos{(\frac{ {2\pi kn} }{N})} +i\sin{(\frac{ {2\pi kn} }{N})})$

实现代码：

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;
            // ret[k].real(ret[k].real() + arr[i].real() * temp.real()-arr[i].imag()*temp.imag());
            // ret[k].imag(ret[k].imag() + arr[i].real() * temp.imag()+arr[i].imag()*temp.real());
        }
    }
    return ret;
}

vector<complex<double>> IDFT(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;
        }
        ret[k].real(ret[k].real()/N);
        ret[k].imag(ret[k].imag()/N);
    }
    return ret;
}

(其实我感觉从代码上很容易看到dft的本质:信号对三角函数的正交分解

结果：

idft后的数值和初始数组一致（复数部分有误差）