知识卡片
位逆序后按级并行执行蝶形
完整FFT电路先对输入做位逆序置换,再运行lg n级蝶形。每一级有n/2个可并行的蝶形,所以总蝶形数为Θ(n lg n),而最长串行路径仅有Θ(lg n)级。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第30章 多项式与快速傅里叶变换 · 查看原书依据
The circuit begins with a bit-reversal permutation of the inputs, followed by lg n stages, each stage consisting of n/2 butterflies executed in parallel. Assuming that each butterfly circuit has constant depth, the full circuit has depth Θ(lg n). The butterfly operations at each level of recursion in the FFT procedure are independent,
参考来源
- 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[30000,35000))。
- 结论依据:原文说明位逆序、FFT电路、精确变换或数值稳定性;相应图和公式已核对。
- 原始内容:The circuit begins with a bit-reversal permutation of the inputs, followed by lg n stages, each stage consisting of n /2 butterflies executed in parallel. Assuming that each butterfly circuit has constant depth, the full circuit has depth Θ(lg n ). The butterfly operations at each level of recursion in the FFT procedure are independent,