FFTW使用说明 课件.ppt
《FFTW使用说明 课件.ppt》由会员分享,可在线阅读,更多相关《FFTW使用说明 课件.ppt(24页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1,FFTW使用说明 王 武中科院超级计算中心Email: ,2010 年 5月,2,内 容 提 要一. 快速傅立叶变换二. FFTW 的使用指南三. FFTW 的技术特点四. FFTW 的调用算例五. FFTW在Unix上的安装,3,1.1.1 Fourier Transform (FT)1.1.2 Discrete Fourier Transform (DFT)One-dimension:Multi-dimension:,一. 快速傅立叶变换,4,1.1.3 DFT in Matrix-vector FormEg: DFT in 1D F is a matrix as in right:C
2、omplexity:Its applied in DSP ( Digital Signal Processing ): analyse and manipulate real-world signals by computer Toys and consumer electronics (Spectrogram ) Speech recognition Audio/video compression Medical imaging Communications Radar,一. 快速傅立叶变换,5,1.2.1 Fast Fourier Transform (FFT)Cooley & Tukey
3、 , 1965 FFT is a divide-and-conquer algorithm using binary reversal sortEg: FFT in 1DOrder: even, odd Complexity:,一. 快速傅立叶变换,01234567,04261537,6,1.2.3 Parallel FFT in 1DCombine: using butterfly computation1.2.4 FFT in Multi-dimensionEg: DFT in 2D, Complexity : reduced to 2 steps of DFT in 1DComputed
4、 by FFT,Complexity :,一. 快速傅立叶变换,0, 4 2, 6 1, 5 3, 7Log28 transform steps,7,1.3 Example: FFT for Convolution FormStep 1: FFT for x(N) and h(N) Step 2: Vec-Vec Mult: Y(n)=X(n)H(n)Step 3: IFFT for Y(N): Complexity:,一. 快速傅立叶变换,8,2.1 FFTW简单概述FFTW ( the Faster Fourier Transform in the West) 是一个快速计算离散傅里叶变换
5、的标准C语言程序集FFTW 由MIT的 M. Frigo 和 S. Johnson 开发,可计算一维或多维, 实和复数据以及任意规模的DFT.FFTW 还包含对共享和分布式存储系统的并行变换,它可自动适应你的机器, 缓存, 存储器大小, 寄存器个数 .FFTW 通常比目前其它开源Fourier变换程序都要快 !FFTW 最新版本为fftw-3.2.2FFTW下载及相关资料提供http:/ www.fftw.org,二. FFTW的使用指南,9,2.2. FFTW 计算:1)复(实)一维变换及其逆变换: 由于没有正规化:2)复(实)多维变换及其逆变换:计算一个向前变换随后一个向后变换将用 乘以输
6、入(正规化).变换的正确性检验:3)以上变换的并行实现共享和分布式存储系统,一维和多维DFT, 实变换和复变换,多线程和MPI.,二. FFTW的使用指南,10,2.3.1 复一维变换#include fftw_complex inN, outN; /定义数据类型:复数组 fftw_plan p; /定义计划 /创建计划 ,向前变换 p = fftw_create_plan(N, FFTW_FORWARD, FFTW_ESTIMATE); / ESTIMATE表示不运行任何计算/而只是建立一个合理的计划 fftw_one(p, in, out); /一维变换的输入(出)数组 fftw_dest
7、roy_plan(p); /用完后,取消计划 / 在Unix上,一个使用FFTW的程序应该与-lfftw lm相连接,二. FFTW的使用指南,11,2.3.2 复多维变换#include /对于FFTW3.0以上版本则采用fftw3.h fftw_complex inLMN; /数据类型 fftwnd_plan p; / fftwnd代表N维fftw p = fftwnd_create_plan(L, M, N, FFTW_FORWARD, FFTW_MEASURE | FFTW_IN_PLACE); /在位(in-place)变换 用输出数组覆盖组 /MEASURE即FFTW实际执行和测量
8、几个FFT的执行时间 以发现计算规模为N的变换的最好方式 ; fftwnd_one(p, /程序编译时需与-lfftwnd lfftw lm相连接,二. FFTW的使用指南,12,2.3.3 实一维变换#include /专门针对实型数据的rfftw变换/ 数据类型 fftw_real inN, outN; rfftw_plan p; /计划 int k /创建计划 ,实到复的变换,复到实则为逆变换 p = rfftw_create_plan(N, FFTW_REAL_TO_COMPLEX, FFTW_ESTIMATE); rfftw_one(p, in, out); rfftw_destro
9、y_plan(p); /程序编译时需与-lrfftw lfftw lm相连接,二. FFTW的使用指南,13,2.3.4 实多维变换#include /专门针对实型数据的rfftw变换/ 数据类型 fftw_real inM, N, outM, N; rfftw_plan p; /计划 int k /创建计划 ,实到复的变换,复到实则为逆变换 p = rfftwnd_create_plan(M, N, FFTW_REAL_TO_COMPLEX, FFTW_ESTIMATE); rfftwnd_one(p, in, out); rfftwnd_destroy_plan(p); /程序编译时需与-
10、lrfftwnd lfftw lm相连接,二. FFTW的使用指南,14,2.4.1. FFTW的多线程并行1.头文件: 或 2.线程初始化: int fftw_threads_init(void); 3.用到的函数fftw_threads_one(nthreads, plan, in, out); /一维复变换fftwnd_threads_one(nthreads, plan, in, out); /n维复变换rfftw_threads_one(nthreads, plan, in, out); /一维实变换rfftwnd_threads_one(nthreads, plan, in, ou
11、t); /n维实变换以一维复变换为例用 fftw_threads_one (nthreads, plan, in, out) 代替调用单机 fftw_one (plan, in, out) 在Unix上,使用并行复变换的程序应该与-lfftw_threads - lfftw - lm相连接, 使用并行实变换的程序应与-lrfftw_threads -lfftw_threads -lrfftw -lfftw lm 相连接,二. FFTW的使用指南,15,2.4.2. FFTW的MPI并行调用头文件创建计划:fftw_mpi_plan fftw_mpi_create_plan(MPI_Comm c
12、omm, int nFFTW_FORWARD, FFTW_ESTIMATE );用完后通过fftw_mpi_destroy_plan(plan)来取消.3. 变换函数为:void fftw_mpi(fftw_mpi_plan p, int n_fields, fftw_complex *local_data,fftw_complex *work); 返回时, local_data包含局限于当前进程的输出部分, 可调用:void fftw_mpi_local_sizes(fftw_mpi_plan p, int *local_n, int *local_start,int *local_n_af
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- fftw 使用说明 课件
限制150内