知识卡片

普通读书笔记卡 · 3693.c.1.b.1

FFT电路可把深度降到对数级

理解等级:中级

FFT递归电路先并行运行两个半规模子电路,再以n/2个蝶形运算合并。每层电路深度只增加常数,递归层数为lg n,故从输入到输出的最长计算路径为Θ(lg n)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第30章 多项式与快速傅里叶变换 · 查看原书依据

      The FFT’s divide-and-conquer structure enables the circuit to have a parallel structure so that the depth of the circuit—the maximum number of computational elements between any output and any input that can reach it—is Θ(lg n). Moreover, the structure of the FFT circuit has several interesting

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[25000,30000))。 - 结论依据:原文定义单位根、DFT、FFT递归、逆变换与电路;相关公式和图已核对。 - 原始内容:The FFT’s divide-and-conquer structure enables the circuit to have a parallel structure so that the depth of the circuit—the maximum number of computational elements between any output and any input that can reach it—is Θ(lg n ). Moreover, the structure of the FFT circuit has several interesting