设单位根 ω=e−2πi/N,则离散 Fourier 变换是对长度为 N 的向量 x 的变换,满足
yk=N1j=0∑N−1ωjkxj
这可以视为一个矩阵向量乘法,矩阵为
F=N11111⋮11ωω2ω3⋮ωN−11ω2ω4ω6⋮ω2(N−1)1ω3ω6ω9⋮ω3(N−1)⋯⋯⋯⋯⋯1ωN−1ω2(N−1)ω3(N−1)⋮ω(N−1)(N−1)
该变换为酉变换 FF†=1。
快速 Fourier 变换
上述变换可以在 O(NlogN) 的时间而非 O(N2) 的时间内完成。核心在于注意到上式是递归的:定义 k=k1+N2k2、n=n1+N1n2,则有
yk1+N2k2=N1n1=0∑N1ωN1n1k2ωk1n1n2=0∑N2ωN2n1k2xn1+N1n2
例如,对于 Radix-2 的快速 Fourier 变换,计算方法为:
f^n=Fnfn=(In/2In/2In/2−In/2)(Fn/2feDFn/2fo)
其中 D=diag{ω0,⋯,ωn/2−1}.
正弦、余弦变换
第一类余弦变换:要求函数能偶拓展到 [0,2π] 区间内
f^j=n2k=0∑n−1fkcosn−1πjk=ℜ(n2k=0∑n−1fke−2πijk/2(n−1))
第二类正弦变换:要求函数能奇拓展到 [0,2π] 区间内
f^j=n2k=0∑n−1fksinn+1π(j+1)(k+1)=ℑ(n2k=0∑n−1fke2πi(j+1)(k+1)/2(n−1))
相关内容
离散 Fourier 变换可以认为是在求 Fourier 系数的时候使用了梯形法则。
f^k=L1∫0Lf(x)e−2πikx/Ldx=N1n=0∑N−1f(nL/N)e−2πikn/N
参考文献