关键词: 逆序, 原位, FFT, 空间复杂度, 时间复杂度

Abstract: The on-chip memory in DSP is small, and applications for DSP are often data-intensive, which requires that space complexity as well as time complexity must be considered when algorithms are designed. So a in-place bit reverse algorithm was proposed. Then, to take advantage of memory bandwidth offered by DSP, an effective in-place FFT algorithm with part bit reverse was designed and implemented on BWDSP. Experiment result shows that, compared with the out-of-place FFT algorithm, its space complexity is significantly reduced，while the loss of time efficiency for the proposed in-place FFT algorithm is acceptable.

Key words: bit reverse, inplace, FFT, space complexity, time complexity