离散傅里叶变换(DFT),是傅里叶变换在时域和频域上都呈现离散的形式,将时域信号的采样变换为在离散时间傅里叶变换(DTFT)频域的采样。
# 定义
# DFT (离散傅里叶转换)
是一个均匀采样序列,即均匀时间间隔,; 为第 个 DFT 系数,; 。
# IDFT (离散傅里叶逆转换)
其中, *
表示复共轭运算。DFT 的变换对可以使用下式表示:
式 (2.1b) 中的归一化因子 可以平均分配在 DFT 和 IDFT 中(称为归一化 DFT)。也可以全部放在 DFT 运算中。
# 归一化 DFT
或
利用欧拉公式: ,有
和 均为长度为 的序列。
注意:;
一般情况下,当 为整数时,
# 矩阵形式
DFT:
IDFT:
有以下结论:
- DFT 矩阵 是对称的,即
- 是酉函数,,其中 为 的单位矩阵。
于是乎,可利用矩阵化简,提高计算效率。
# 代码实现(Python)
式 (2.2) 的实现:
import numpy as np
# 一维朴素 DFT 实现
def myDFT(x):
N = x.shape[0]
y = np.zeros(N, dtype=complex) # 初始化
for i in range(N):
for k in range(N):
real = np.cos(2 * np.pi / N * i * k) # 实部
imag = -1j * np.sin(2 * np.pi / N * i * k) # 虚部
y[i] += x[k] * (real + imag)
return y
# 一维朴素 IDFT 实现
def myIDFT(x):
dim = x.shape[0]
y = np.zeros(dim, dtype=complex) # 初始化
for i in range(dim):
for k in range(dim):
real = np.cos(2 * np.pi / dim * i * k) # 实部
imag = +1j * np.sin(2 * np.pi / dim * i * k) # 虚部
y[i] += x[k] * (real + imag)
y[i] = y[i] / dim
return y
x = np.array([1+0j,2+0j,3+0j])
print("x: ",x)
print("np.fft: ",np.fft.fft(x))
print("myDFT: ",myDFT(x))
print("myIDFT: ",myIDFT(myDFT(x)))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
结果:(事实上限于精度,numpy.fft.fft
与本文 myDFT
代码所得并不完全一致,可看到精度误差大概在 级别)
>>> python DFT.py
x: [1.+0.j 2.+0.j 3.+0.j]
np.fft: [ 6. +0.j -1.5+0.8660254j -1.5-0.8660254j]
myDFT: [ 6. +0.j -1.5+0.8660254j -1.5-0.8660254j]
myIDFT: [1.-9.62193288e-16j 2.-1.48029737e-16j 3.+3.70074342e-16j]
2
3
4
5
# 推导
有关傅里叶级数推导先看看 傅里叶级数推导过程
首先对比一下连续和离散方程的差异,并注意这里都是系数
取步长 并利用梯形积分法来近似代替,并注意
即有:
其中
# 性质
# Z 变换
令 为采样速率,或者 即采样间隔(单位为 s),有
此式表示 在 z 平面以原点为中心的单位圆上的取值。 通过对单位圆进行等间隔采样,
式中
的 DFT 实际上是 的 Z 变换在单位圆的等间隔采样。 表示 在频率为 时的 DFT,。 由于存在频率混叠,因此 的最高频率系数为 ,即 。
关于频率混叠,推荐看看 这篇文章 (opens new window)
# 线性
其中, 均为常数
# 复共轭定理
当 为实序列时,有
功率谱在频域内是关于 对称的偶函数
# 帕斯瓦尔定理
该定理对所有酉变换都成立
证明:
# 循环移位
给定 ,则
式中,便是在时域向左循环移位 个采样间隔,即 为
因为 ,所以原序列的 DFT 和循环移位后的序列的 DFT 仅相位是相关的。对一个序列进行循环移位操作,其幅度谱和功率谱均保持不变。
# 置换序列的 DFT
其中 为 对 求余的余数。同时 与 互质,为整数。
其中 为 对 求余的余数。同时 与 互质,为整数。
即:
附一个示例:
令 ,则有 。令 ,则
则有:
当 时,;当 时,,同理。
本文为《快速傅里叶变换 算法与应用》的笔记,部分内容为摘抄,请悉知。