知识卡片
FFT电路可把深度降到对数级
FFT递归电路先并行运行两个半规模子电路,再以n/2个蝶形运算合并。每层电路深度只增加常数,递归层数为lg n,故从输入到输出的最长计算路径为Θ(lg n)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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