快速傅里叶变换加速器

摘要

本发明涉及快速傅里叶变换加速器。通过将n个时域输入点分成多个含m个点的组执行FFT运算，对每个含m个点的组执行多个恒定几何蝶形运算，最后对该n个点的组执行至少一个原位蝶形运算。

主权项

一种在计算上对n个点执行快速傅里叶变换（FFT）的方法，包括：将n个点分成多个含m个点的组，其中m<n；对每个所述含m个点的组执行多个恒定几何FFT，每个所述恒定几何FFT包括：i.从计算机内存中读取所述m个点到输入缓冲器;ii.计算上对每一组m个点施加蝶形运算；iii.将蝶形运算的结果写在输出缓冲器；iv.将所述输出缓冲器中经过转置的内容存储到m个点在所述计算机存储器中的原始位置，从而覆盖原来的m个点；对于存储在所述计算机存储器中的多个恒定几何FFT的结果执行至少一个原位FFT，从而完成对n个点的FFT。