并行计算课程设计任务书文库

《并行计算课程设计任务书文库》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*******************实践教学*******************兰州理工大学理学院2016年春季学期并行计算课程设计专业班级：2013级信息与计算科学2班姓名：学号：13540216指导教师：成绩：2基于串行FFT蝶式递归计算摘要本文主要设计快速傅氏变换两种经典的串行算法之一的递归算法（蝶式）。它是利用分治的思想来推导递归的FFT计算算法，将b元素或a元素之下标分别按偶下标与奇下标展开而推导出的递归式。算法主要过程如下：首先主进程对输入的元素按其下标进行奇偶划分，然后分配给两个处理

2、器，分别在各自的处理器在进行同样的划分、并计算其结果，将结果带入到上一层再进行计算，最后将结果带入到主进程合并进行计算，输出结果。关键字：蝶式计算傅里叶变换递归算法2目录一．题目及要求11.1设计题目11.2设计参数11.3测试实例1二．设计算法及要求12.1算法设计原理12.2算法设计2三．算法描述与设计流程33.1算法描述33.2流程图4四．原程序代码与运行结果54.1源程序54.2运行结果10五．算法分析及其优缺点115.1算法分析115.2优缺点12六．总结13七．参考文献142一．题目及要求

3、1.1设计题目串行FFT递归算法（蝶式递归计算原理）求傅里叶变换1.2设计参数蝶式递归计算原理、算法性能和误差分析1.3测试实例对给定的，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换的结果。二．设计算法及要求2.1算法设计原理令为n/2次单位元根，则有.将b向量的偶数项和奇数项分别记为和注意推导中反复使用22.2算法设计对于以上的分析可画出如图1所示的离散傅里叶变换递归计算流图。图1n=8的FFT蝶式计算图2三．算法描述与设计流程3.1算法描述2开始3.2流程图输入序列对应值（例如5+j

4、3，输入53）计算出前size_x/2个exp(-j*2π*k/size_x)个值，即W的值级数i>=错误!未找到引用源。？级数i加1是输出fft结果序列结束否该级该组起始下标j>=错误!未找到引用源。？计算出该级需要的W的个数l是否该级该组元素序数k>=错误!未找到引用源。？组起始下标加2*lK加1是X[j+k]X[j+k]lX[j+k+l]*W[(size_x/2/l)*k]X[j+k+l]-1否图2算法设计流程图2四．原程序代码与运行结果4.1源程序/************FFT*******

5、****///整个程序输入和输出利用同一个空间x[N]，节约空间#include#include#include#defineN1000//定义输入或者输出空间的最大长度typedefstruct{doublereal;doubleimg;}complex;//定义复数型变量的结构体voidfft();//快速傅里叶变换函数声明voidinitW();//计算W(0)~W(size_x-1)的值函数声明voidchange();//码元位置倒置函数

6、函数声明voidadd(complex,complex,complex*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complex,complex*);/*复数减法*/voiddivi(complex,complex,complex*);/*复数除法*/voidoutput();/*输出结果*/complexx[N],*W;/*输出序列的值*/intsize_x=0;/*输入序列的长度，只限2的N次方*/dou

7、blePI;//pi的值intmain(){inti;2system("cls");PI=atan(1)*4;printf("Pleaseinputthesizeofx:");/*输入序列的长度*/scanf("%d",&size_x);printf("Pleaseinputthedatainx[N]:(suchas:56)");/*输入序列对应的值*/for(i=0;i

8、(0)~W(size_x-1)的值fft();//利用fft快速算法进行DFT变化output();//顺序输出size_x个fft的结果return0;}/*进行基-2FFT运算,蝶形算法。这个算法的思路就是，先把计算过程分为log(size_x)/log(2)-1级（用i控制级数）；然后把每一级蝶形单元分组（用j控制组的第一个元素起始下标）；最后算出某一级某一组每一个蝶形单元（用k控制个数，共l个）。*/voidfft(){inti=0,j=0,k=