目录

离散傅里叶变换 (DFT)
离散傅里叶变换的基
对于周期为 2 π  的函数而言，它的傅里叶变换为

离散傅里叶变换
现在我们知道，f ( t 在采样点处的值 f ( k 2 π N ) 
​
其实是 N  个基的线性组合，并且函数值 f ( k 2 π N ) 


和 N 个基是已知的，因此我们就可以列出关于 N 个系数 的 N  个方程，组成线性方程组，最终就可以解出 N  个系数

但我们想解的其实是傅里叶系数 C k，因此离散傅里叶假设 f ( t ) f(t)f(t) 的傅里叶级数里只包含 C 0 , C 1 , . . , C N − 1 
​
  项 (只要 N 足够大，就可以非常接近原函数)，此时我们就可以写出如下线性方程组并解出 C 0 , C 1 , . . , C N − 1 

def DFT_slow(x):
    x = np.asarray(x, dtype=float)  # 输入信号采样点
    N = x.shape[0]  # 采样点个数

    spectro = []    # 信号频谱
    for k in range(N):  # 依次计算 N 个傅里叶系数
        real = 0    # 傅里叶系数的实部
        img = 0     # 傅里叶系数的虚部
        for n in range(N):  # 遍历所有采样点
            t = 2 * math.pi * k * n / N
            real += math.cos(t) * x[n]  # 累加实部
            img -= math.sin(t) * x[n]   # 累加虚部
        
        spectro.append(real + img * 1j)
    return np.asarray(spectro)

def DFT_slow(x):
    # 用矩阵乘积的形式实现 DFT
    x = np.asarray(x, dtype=float)  # 输入信号采样点
    N = x.shape[0]  # 采样点个数
    n = np.arange(N)
    k = n.reshape((N, 1))
    M = np.exp(-2j * np.pi * k * n / N) # 傅里叶变换矩阵
    return np.dot(M, x)

快速傅里叶变换 (FFT)

FFT 实际上只要求 N 可以被分解为两个正整数的乘积 (e.g. F 9  可以被分解为 9 个 3 × 3  的矩阵)，但我们一般都选择 N NN 为 2 的整数次幂，如果信号采样次数不够 2 k ，那我们就在信号后面补 0

通过 FFT，我们可以将 DFT 原先 O ( N 2 ) 

def FFT(x):
    """A recursive implementation of the 1D Cooley-Tukey FFT"""
    x = np.asarray(x, dtype=float)
    N = x.shape[0]
    
    if N % 2 > 0:
        raise ValueError("size of x must be a power of 2")
    elif N <= 32:  # this cutoff should be optimized
        return DFT_slow(x)
    else:
        X_even = FFT(x[::2])
        X_odd = FFT(x[1::2])
        factor = np.exp(-2j * np.pi * np.arange(N) / N)
        return np.concatenate([X_even + factor[:N // 2] * X_odd,
                               X_even + factor[N // 2:] * X_odd])

卷积

  • 卷积本身没有实际意义，它只是一种数学操作，但是卷积是很多场景下都会遇到的一类重复操作，因此单独起名为卷积。下面介绍两个卷积经常出现的场景：线性时不变系统和傅里叶级数

线性时不变系统

傅里叶级数

卷积这一节后面还有些内容，以后再看

参考文献
纯干货数学推导_傅里叶级数与傅里叶变换
傅立叶变换夯实基础系列视频
离散傅里叶变换零基础入门
a very fast implementation of FFT: pyFFTW package
L i n e a r LinearLinear a l g e b r a algebraalgebra a n d andand i t s itsits a p p l i c a t i o n s applicationsapplications
傅里叶分析之掐死教程（完整版）
more:

Understanding the FFT Algorithm
FFT with Python