数字信号处理第三章离散傅里叶变换

这是一篇关于离散傅里叶变换的思维导图，梳理了离散傅里叶变换及其快速算法的关键知识点，从基本定义、性质到快速计算方法，内容全面且逻辑清晰，适合用于学习和复习数字信号处理中关于DFT和FFT的相关内容。

离散傅里叶变换

• 离散傅里叶变换DFS及其性质 时域和频域都是离散的
  • 性质
    • 线性
    • 移位
    • 周期卷积:设x1(n)与x2(n)都是周期为N的卷积序列 显然满足交换律
• 离散傅里叶变换DFT及其性质 时域和频域都是离散的
  • 旋转因子(注意有负号！)
    • 有几个特殊的值可以记一下，这里略
  • 离散傅里叶变化N点DFT(discrete Fourier transform)
    • 画图时可能要分实部和虚部
  • 一个周期为N的序列x(n)的离散傅里叶反变换N点IDFT
  • DFT和ZT关系:有限长序列x(n)的DFT系数X(k)可看作其ZT在单位圆上等距取样的样本值
  • DFT与FT的关系有限长序列x(n)的DFT系数X(k)可看作其FT在一个周期(0,2π)中等间距取样的样本值
  • 性质
    • 用来支撑DFT应用的
    • 线性
      • 这里貌似没讲那么细，只考虑x1(n)和x2(n)一样长的情况:
    • 循环移位性质
      • 循环移位:是先周期延拓与再移位的结合，并取一个主值周期:
        • 其中x((n+m))N是x(n)左移m位的，周期为N的序列
    • 循环卷积定理
      • y(n)为x1(n)、x2(n)的N点循环卷积:
        • N是一个具体的数字，由于打不出符号，中间式子的N应该在圈内
      • 特点
        • 只取主值
        • 每个序列长度均相等
        • 计算步骤:周期化、反折、平移、相乘、相加
          • 用矩阵计算:
            • 所以只要算出x2(n)的每一个值，就可以按竖行的规律写出矩阵了
          • 另外还有实用解法，见链接"实用解法"
    • 复共轭的DFT
    • DFT的共轭对称性
      • X(k)共轭对称，即
      • 若x(n)实偶对称，即x(n)=x(N-n)，则X(k)=X(N-k)
      • 若x(n)实奇对称，即x(n)=-x(N-n)，则X(k)=-X(N-k)
• 频率取样
  • 频率域采样定理:指的是对序列的傅里叶变换或系统的频率特性取样 如果序列x(n)长度为M，则只有当频域采样点数N³M时才有(否则会失真):
  • 奈奎斯特取样定理:取样频率至少要大于最大信号频率的两倍
• 快速傅里叶变换FFT(只是一种快速计算DFT的方法)
  • 时间抽取FFT算法
    • 掌握2、4、8点蝶形运算
      • 8点输入顺序x(n)是三位二进制数倒过来(不是指取反的倒)对应的值 不满2N个要补0，注意输入顺序！
      • 第L级旋转因子(都是给下半部分加)
        • 其中M是最大级数
    • 比较N点DFT与N点FFT算法次数公式
    • 利用FFT计算线性卷积: