知识卡片
逆DFT换逆单位根并除以长度
设系数向量为a=(a₀,…,aₙ₋₁),多项式A(x)=Σⱼ aⱼxʲ,ωₙ是n次本原单位根。DFT的输出是yₖ=A(ωₙᵏ);逆变换用
aⱼ=(1/n)Σₖ₌₀ⁿ⁻¹ yₖωₙ^(−j k)
恢复系数。把正变换代入后,每对系数会出现Σₖωₙ^((ℓ−j)k):当j=ℓ时和为n,否则为0,因而只保留aⱼ。算法上可沿用FFT结构,把单位根换成其逆,再将每个结果除以n,时间为Θ(n lg n)。
补充教学演示:n=2时,y₀=a₀+a₁、y₁=a₀−a₁,所以a₀=(y₀+y₁)/2、a₁=(y₀−y₁)/2。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第30章 多项式与快速傅里叶变换 · 查看原书依据
By comparing equations (30.8) and (30.11), you can see that if you modify the FFT algorithm to switch the roles of a and y, replace ωn by , and divide each element of the result by n, you get the inverse DFT (see Exercise 30.2-4). Thus, is computable in Θ(n lg n) time as well. Thus, the FFT and the inverse FFT provide a way to
参考来源
- 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[20000,25000))。
- 结论依据:原文比较式(30.8)与(30.11),说明交换 a、y,以逆单位根取代单位根,并将结果除以 n 即得逆DFT;单位根幂和引理给出对角项为n、其余为0的抵消。n=2算例是依据该公式补充的教学演示。
- 原始内容:By comparing equations (30.8) and (30.11), you can see that if you modify the FFT algorithm to switch the roles of a and y , replace ω n by , and divide each element of the result by n , you get the inverse DFT (see Exercise 30.2-4). Thus, is computable in Θ( n lg n ) time as well. Thus, the FFT and the inverse FFT provide a way to