电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

FFTC快速傅里叶变换超级详细的原代码

FFTC快速傅里叶变换超级详细的原代码_第1页
1/8
FFTC快速傅里叶变换超级详细的原代码_第2页
2/8
FFTC快速傅里叶变换超级详细的原代码_第3页
3/8
快速傅立叶变换(FFT)的C++实现 收藏 标准的离散傅立叶 DFT 变换形式如: yk=Σj=0n-1 ajωn-kj = A (ωn-k). (ω nk 为复数 1 的第 k 个 n 次方根,且定义多项式 A (x) = Σj=0n-1 ajxj ) 而离散傅立叶逆变换 IDFT (Inverse DFT)形式如: aj=(Σk=0n-1 ykωnkj)/n . yk=Σj=0n-1 ajω n-kj = A (ω n-k). (ωnk 为复数 1 的第 k 个 n 次方根,且定义多项式 A (x) = Σj=0n-1 ajxj ) 而离散傅立叶逆变换 IDFT (Inverse DFT)形式如: aj=(Σk=0n-1 ykωnkj)/n . 以下不同颜色内容为引用并加以修正: 快速傅立叶变换(Fast Fourier Transform,FFT)是离散傅立叶变换(Discrete Fourier transform,DFT)的快速算法,它是根据离散傅立叶变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。它对傅立叶变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅立叶变换,可以说是进了一大步。 设 Xn 为 N 项的复数序列,由 DFT 变换,任一 Xi 的计算都需要 N 次复数乘法和 N -1 次复数加法,而一次复数乘法等于四次实数乘法和两次实数加法,一次复数加法等于两次实数加法,即使把一次复数乘法和一次复数加法定义成一次“运算”(四次实数乘法和四次实数加法),那么求出 N 项复数序列的 Xi ,即 N 点 DFT 变换大约就需要 N2 次运算。当 N =1024 点甚至更多的时候,需要 N2 = 1048576 次运算,在 FFT 中,利用 ωn 的周期性和对称性,把一个 N 项序列(设 N 为偶数),分为两个 N / 2 项的子序列,每个 N / 2 点 DFT 变换需要 (N / 2)2 次运算,再用 N 次运算把两个 N / 2 点的 DFT 变换组合成一个 N 点的 DFT 变换。这样变换以后,总的运算次数就变成 N + 2 * (N / 2)2 = N + N2 / 2。继续上面的例子,N =1024 时,总的运算次数就变成了 525312 次,节省了大约 50% 的运算量。而如果我们将这种“一分为二”的思想不断进行下去,直到分成两两一组的 DFT 运算单元,那么 N 点的 DFT 变换就只需要 N * log2N 次的运算,N = 1024 点时,运算量仅有 10240 次,是先前的直接算法的1% ,点数越多,运算量的节约就越大,这就是 FFT 的优越性。 FFT 的实现可以自顶而下,采用递归,但是对于硬件实现成本高,对于软件实现都不够高效,改用...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

FFTC快速傅里叶变换超级详细的原代码

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部