原书出处
Introduction to Algorithms, Fourth Edition
30 第30章 多项式与快速傅里叶变换
ion at the leaves. The full FFT circuit Figure 30.6 depicts the entire circuit for n = 8.
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,
and so the circuit performs them in parallel. The figure shows wires running from left to
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter030.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea