知识卡片

普通读书笔记卡 · 3693.c.2

逆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。

这张卡片看不懂?

已有反馈 · 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