FFT中位反拷贝的分析

摘要

位反序拷贝是快速傅立叶变换中的一个重要步骤。在位反拷贝中,数据按照位反序进行重排,内存的读写是非连续的,会导致缓存多次失效。本文对位反序的计算以及位反拷贝进行了研究,定量的分析了几种位反序计算提出并且分析了一种新的位反序拷贝算法。在给定缓存大小的情况下,本文给出了位反序拷贝的缓存失效次数,为FFT的高效实现提供了一个关键步骤。