并行计算课程设计任务书

1*******************实践教学*******************兰州理工大学理学院2016年春季学期并行计算课程设计专业班级：2013级信息与计算科学2班姓名：学号：13540216指导教师：成绩：2基于串行FFT蝶式递归计算摘要本文主要设计快速傅氏变换两种经典的串行算法之一的递归算法（蝶式）。它是利用分治的思想来推导递归的FFT计算算法，将b元素或a元素之下标分别按偶下标与奇下标展开而推导出的递归式。算法主要过程如下：首先主进程对输入的元素按其下标进行奇偶划分，然后分配给两个处理器，分别在各自的处理器在进行同样的划分、并计算其结果，将结果带入到上一层再进行计算，最后将结果带入到主进程合并进行计算，输出结果。关键字：蝶式计算傅里叶变换递归算法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七．参考文献.................................................................................................................................141一．题目及要求1.1设计题目串行FFT递归算法（蝶式递归计算原理）求傅里叶变换1.2设计参数蝶式递归计算原理、算法性能和误差分析1.3测试实例对给定的)3,7,6,78,30,4,32,201(，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换的结果。二．设计算法及要求2.1算法设计原理令为n/2次单位元根，则有.将b向量的偶数项和奇数项分别记为和注意推导中反复使用DFTaaaaaabbblaaaaaaaaaaaaaaaaaaaaaaaaaaabbTnTnnkkklknlllnlllnllllllnkklkllnnnnnnnnnnnnnnnnnnnnn的是向量因此，：),...,,(),...,,(1,,1,0)(~)(~)(~)(~)()()()()(偶数时11110220210111222110111222411201122412112241201022222222222222222222222Tnbbb),...,,(220Tnbbb),...,,(131Tnbbb),...,,(1102Tnbbb),...,,(1102)2//(2＝~nie2~＝,,1,1,1ln2/ppsnnn2DFTaaaaaabbblaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbTnTnnkkkklknlllnlllnlllllnlnlllllnkkklllnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn的是因此，向量奇数时：))(),...,(),((),...,,(1,,1,0)(~)(~)(~)(~)()()()()(11111013121011112222110111122224112011121211122241201)12(11)12(1)12(1)12(12)12(2112010)12(1222222222222222222222222222222222.2算法设计对于以上的分析可画出如图1所示的离散傅里叶变换递归计算流图。图1n=8的FFT蝶式计算图2三．算法描述与设计流程3.1算法描述23.2流程图是否是否是否图2算法设计流程图输入序列对应值（例如5+j3，输入53）计算出前size_x/2个exp(-j*2π*k/size_x)个值，即W的值级数i=错误!未找到引用源。？输出fft结果序列结束计算出该级需要的W的个数l该级该组起始下标j=错误!未找到引用源。？级数i加1组起始下标加2*l该级该组元素序数k=错误!未找到引用源。？X[j+k]X[j+k]lX[j+k+l]*W[(size_x/2/l)*k]X[j+k+l]-1K加1开始2四．原程序代码与运行结果4.1源程序/************FFT***********///整个程序输入和输出利用同一个空间x[N]，节约空间#includestdio.h#includemath.h#includestdlib.h#defineN1000//定义输入或者输出空间的最大长度typedefstruct{doublereal;doubleimg;}complex;//定义复数型变量的结构体voidfft();//快速傅里叶变换函数声明voidinitW();//计算W(0)~W(size_x-1)的值函数声明voidchange();//码元位置倒置函数函数声明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次方*/doublePI;//pi的值intmain(){inti;2system(cls);PI=atan(1)*4;printf(Pleaseinputthesizeofx:\n);/*输入序列的长度*/scanf(%d,&size_x);printf(Pleaseinputthedatainx[N]:(suchas:56)\n);/*输入序列对应的值*/for(i=0;isize_x;i++)scanf(%lf%lf,&x[i].real,&x[i].img);initW();//计算W(0)~W(size_x-1)的值fft();//利用fft快速算法进行DFT变化output();//顺序输出size_x个fft的结果return0;}/*进行基-2FFT运算,蝶形算法。这个算法的思路就是，先把计算过程分为log(size_x)/log(2)-1级（