并行計(jì)算課程設(shè)計(jì)任務(wù)書

21*******************實(shí)踐教學(xué)*******************蘭州理工大學(xué)理學(xué)院2016年春季學(xué)期并行計(jì)算課程設(shè)計(jì)專業(yè)班級：2013級信息與計(jì)算科學(xué)2班姓名：學(xué)號：13540216指導(dǎo)教師：成績：基于串行FFT蝶式遞歸計(jì)算摘要本文主要設(shè)計(jì)快速傅氏變換兩種經(jīng)典的串行算法之一的遞歸算法（蝶式）。它是利用分治的思想來推導(dǎo)遞歸的FFT計(jì)算算法，將b元素或a元素之下標(biāo)分別按偶下標(biāo)與奇下標(biāo)展開而推導(dǎo)出的遞歸式。算法主要過程如下：首先主進(jìn)程對輸入的元素按其下標(biāo)進(jìn)行奇偶劃分，然后分配給兩個(gè)處理器，分別在各自的處理器在進(jìn)行同樣的劃分、并計(jì)算其結(jié)果，將結(jié)果帶入到上一層再進(jìn)行計(jì)算，最后將結(jié)果帶入到主進(jìn)程合并進(jìn)行計(jì)算，輸出結(jié)果。關(guān)鍵字：蝶式計(jì)算傅里葉變換遞歸算法

目錄一． 題目及要求 11.1設(shè)計(jì)題目 11.2設(shè)計(jì)參數(shù) 11.3測試實(shí)例 1二． 設(shè)計(jì)算法及要求 12.1算法設(shè)計(jì)原理 12.2算法設(shè)計(jì) 2三．算法描述與設(shè)計(jì)流程 33.1算法描述 33.2流程圖 4四．原程序代碼與運(yùn)行結(jié)果 54.1源程序 54.2運(yùn)行結(jié)果 10五．算法分析及其優(yōu)缺點(diǎn) 115.1算法分析 115.2優(yōu)缺點(diǎn) 12六．總結(jié) 13七．參考文獻(xiàn) 14一．題目及要求1.1設(shè)計(jì)題目串行FFT遞歸算法（蝶式遞歸計(jì)算原理）求傅里葉變換1.2設(shè)計(jì)參數(shù)蝶式遞歸計(jì)算原理、算法性能和誤差分析1.3測試實(shí)例對給定的，利用串行FFT遞歸算法（蝶式遞歸計(jì)算原理）計(jì)算其傅里葉變換的結(jié)果。二．設(shè)計(jì)算法及要求2.1算法設(shè)計(jì)原理令為n/2次單位元根，則有.將b向量的偶數(shù)項(xiàng)和奇數(shù)項(xiàng)分別記為和注意推導(dǎo)中反復(fù)使用2.2算法設(shè)計(jì)對于以上的分析可畫出如圖1所示的離散傅里葉變換遞歸計(jì)算流圖。圖1n=8的FFT蝶式計(jì)算圖三．算法描述與設(shè)計(jì)流程3.1算法描述開始3.2流程圖開始輸入序列對應(yīng)值（例如5+j3，輸入53）輸入序列對應(yīng)值（例如5+j3，輸入53）計(jì)算出前size_x/2個(gè)計(jì)算出前size_x/2個(gè)exp(-j*2π*k/size_x)個(gè)值，即W的值級數(shù)i>=QUOTE級數(shù)i>=QUOTE錯誤!未找到引用源。？級數(shù)i加1是輸出fft結(jié)果序列輸出fft結(jié)果序列結(jié)束否結(jié)束該級該組起始下標(biāo)j>=QUOTE該級該組起始下標(biāo)j>=QUOTE錯誤!未找到引用源。？計(jì)算出該級需要的W的個(gè)數(shù)l否該級該組元素序數(shù)k>=QUOTE該級該組元素序數(shù)k>=QUOTE錯誤!未找到引用源。？組起始下標(biāo)加2*lK加1是K加1X[j+k]X[j+k]lX[j+k+l]*W[(size_x/2/l)*k]X[j+k+l]X[j+k]X[j+k]lX[j+k+l]*W[(size_x/2/l)*k]X[j+k+l]-1圖2算法設(shè)計(jì)流程圖四．原程序代碼與運(yùn)行結(jié)果4.1源程序/************FFT***********///整個(gè)程序輸入和輸出利用同一個(gè)空間x[N]，節(jié)約空間#include<stdio.h>#include<math.h>#include<stdlib.h>#defineN1000//定義輸入或者輸出空間的最大長度typedefstruct{doublereal;doubleimg;}complex;//定義復(fù)數(shù)型變量的結(jié)構(gòu)體voidfft();//快速傅里葉變換函數(shù)聲明voidinitW();//計(jì)算W(0)~W(size_x-1)的值函數(shù)聲明voidchange();//碼元位置倒置函數(shù)函數(shù)聲明voidadd(complex,complex,complex*);/*復(fù)數(shù)加法*/voidmul(complex,complex,complex*);/*復(fù)數(shù)乘法*/voidsub(complex,complex,complex*);/*復(fù)數(shù)減法*/voiddivi(complex,complex,complex*);/*復(fù)數(shù)除法*/voidoutput();/*輸出結(jié)果*/complexx[N],*W;/*輸出序列的值*/intsize_x=0;/*輸入序列的長度，只限2的N次方*/doublePI;//pi的值intmain(){inti;system("cls");PI=atan(1)*4;printf("Pleaseinputthesizeofx:\n");/*輸入序列的長度*/scanf("%d",&size_x);printf("Pleaseinputthedatainx[N]:(suchas:56)\n");/*輸入序列對應(yīng)的值*/for(i=0;i<size_x;i++)scanf("%lf%lf",&x[i].real,&x[i].img);initW();//計(jì)算W(0)~W(size_x-1)的值fft();//利用fft快速算法進(jìn)行DFT變化output();//順序輸出size_x個(gè)fft的結(jié)果return0;}/*進(jìn)行基-2FFT運(yùn)算,蝶形算法。這個(gè)算法的思路就是，先把計(jì)算過程分為log(size_x)/log(2)-1級（用i控制級數(shù)）；然后把每一級蝶形單元分組（用j控制組的第一個(gè)元素起始下標(biāo)）；最后算出某一級某一組每一個(gè)蝶形單元（用k控制個(gè)數(shù)，共l個(gè)）。*/voidfft(){inti=0,j=0,k=0,l=0;complexup,down,product;change();//實(shí)現(xiàn)對碼位的倒置for(i=0;i<log(size_x)/log(2);i++)//循環(huán)算出fft的結(jié)果{l=1<<i;for(j=0;j<size_x;j+=2*l)//算出第m=i級的結(jié)果【i從0到（log(size_x)/log(2)）-1】{for(k=0;k<l;k++)//算出第i級內(nèi)j組蝶形單元的結(jié)果 {//算出j組中第k個(gè)蝶形單元mul(x[j+k+l],W[(size_x/2/l)*k],&product);/*size/2/l是該級W的相鄰上標(biāo)差，l是該級該組取的W總個(gè)數(shù)*/add(x[j+k],product,&up);sub(x[j+k],product,&down);x[j+k]=up;//up為蝶形單元右上方的值x[j+k+l]=down;//down為蝶形單元右下方的值}}}}voidinitW()//計(jì)算W的實(shí)現(xiàn)函數(shù){inti;W=(complex*)malloc(sizeof(complex)*size_x);/*申請size_x個(gè)復(fù)數(shù)W的空間(這部申請的空間有點(diǎn)多，實(shí)際上只要申請size_x/2個(gè)即可)*/for(i=0;i<(size_x/2);i++)/*預(yù)先計(jì)算出size_x/2個(gè)W的值，存放,由于蝶形算法只需要前size_x/2個(gè)值即可*/{W[i].real=cos(2*PI/size_x*i);//計(jì)算W的實(shí)部W[i].img=-1*sin(2*PI/size_x*i);//計(jì)算W的虛部}}voidchange()//輸入的碼組碼位倒置實(shí)現(xiàn)函數(shù){complextemp;unsignedshorti=0,j=0,k=0;doublet;for(i=0;i<size_x;i++){k=i; j=0;t=(log(size_x)/log(2));while((t--)>0){j=j<<1;j|=(k&1);k=k>>1;}if(j>i){temp=x[i];x[i]=x[j];x[j]=temp;}}}voidoutput()//輸出結(jié)果實(shí)現(xiàn)函數(shù){inti;printf("Theresultareasfollows\n");for(i=0;i<size_x;i++){printf("%.4f",x[i].real);//輸出實(shí)部if(x[i].img>=0.0001)//如果虛部的值大于0.0001，輸出+jx.img的形式printf("+j%.4f\n",x[i].img);elseif(fabs(x[i].img)<0.0001)//如果虛部的絕對值小于0.0001，無需輸出printf("\n");elseprintf("-j%.4f\n",fabs(x[i].img));//如果虛部的值小于-0.0001，輸出-jx.img的形式}}voidadd(complexa,complexb,complex*c)//復(fù)數(shù)加法實(shí)現(xiàn)函數(shù){c->real=a.real+b.real;//復(fù)數(shù)實(shí)部相加c->img=a.img+b.img;//復(fù)數(shù)虛部相加}voidmul(complexa,complexb,complex*c)//復(fù)數(shù)乘法實(shí)現(xiàn)函數(shù){c->real=a.real*b.real-a.img*b.img;//獲取相乘結(jié)果的實(shí)部c->img=a.real*b.img+a.img*b.real;//獲取相乘結(jié)果的虛部}voidsub(complexa,complexb,complex*c)//復(fù)數(shù)減法實(shí)現(xiàn)函數(shù){c->real=a.real-b.real;//復(fù)數(shù)實(shí)部相減c->img=a.img-b.img;//復(fù)數(shù)虛部相減}voiddivi(complexa,complexb,complex*c)//復(fù)數(shù)除法實(shí)現(xiàn)函數(shù){c->real=(a.real*b.real+a.img*b.img)/(b.real*b.real+b.img*b.img);//獲取相除結(jié)果的實(shí)部c->img=(a.img*b.real-a.real*b.img)/(b.real*b.real+b.img*b.img);//獲取相除結(jié)果的虛部}4.2運(yùn)行結(jié)果圖3運(yùn)行結(jié)果圖五．算法分析及其優(yōu)缺點(diǎn)5.1算法分析（1）FFT算法的基本原理是把長序列的DFT逐次分解為較短序列的DFT。按照抽取方式的不同可分為DIT-FFT（按時(shí)間抽?。┖虳IF-FFT（按頻率抽取）算法。按照蝶形運(yùn)算的構(gòu)成不同可分為基2、基4、基8以及任意因子（2n,n為大于1的整數(shù)），基2、基4算法較為常用[5]。（2）總體結(jié)構(gòu)說明，輸入數(shù)據(jù)為串行的數(shù)據(jù)流，故在第一級蝶形運(yùn)算模塊前加入串并轉(zhuǎn)換模塊，將串行數(shù)據(jù)流轉(zhuǎn)換為并行的兩列數(shù)據(jù)流以適應(yīng)基2蝶形運(yùn)算模塊的輸入信號要求。

由于每級蝶形運(yùn)算一次處理的兩個(gè)輸入數(shù)據(jù)不能直接由前一級蝶形運(yùn)算一次性輸出，故在兩個(gè)蝶形運(yùn)算單元之間插入延時(shí)對齊模塊，將前一級蝶形運(yùn)算的結(jié)果（兩列并行的數(shù)據(jù)流）作適當(dāng)?shù)难訒r(shí)并通過轉(zhuǎn)接器對齊，形成后一級蝶形運(yùn)算模塊所需要的2列輸入序列[6]。

在最后一級蝶形運(yùn)算后加入串并轉(zhuǎn)換模塊，將2列并行的數(shù)據(jù)流合成為1列。最后加入倒序模塊將DIF-FFT得到的倒序輸出序列整理為順序輸出。

基2蝶形運(yùn)算模塊由兩個(gè)復(fù)數(shù)加法器和一個(gè)復(fù)數(shù)乘法器構(gòu)成。旋轉(zhuǎn)因子由ROM產(chǎn)生后，作為復(fù)數(shù)乘法器的輸入之一，與前面復(fù)數(shù)加法器得到的結(jié)果相乘完成一次蝶形運(yùn)算。為提高系統(tǒng)的運(yùn)行速度可在蝶形運(yùn)算單元中插入流水線寄存中間結(jié)果[2]。（3）蝶形運(yùn)算單元如圖所示：圖4蝶式運(yùn)算單元圖5.2優(yōu)缺點(diǎn)優(yōu)點(diǎn)：相對于DFT算法，F(xiàn)FT算法較高的效率，其基本思想是利用權(quán)函數(shù)的周期性、對稱性、特殊性及周期的互換性，將點(diǎn)DFT運(yùn)算逐次分解為較短序列的DFT運(yùn)算。因DFT的運(yùn)算量與序列長度的平方成比，故序列分解可大大減少運(yùn)算量[10]。從FFT算法實(shí)現(xiàn)角度講，應(yīng)具有運(yùn)算量較少、結(jié)構(gòu)規(guī)整、易實(shí)現(xiàn)、可同址運(yùn)算、內(nèi)部數(shù)據(jù)不需重拍等特點(diǎn)。缺點(diǎn)：由于定點(diǎn)乘法運(yùn)算時(shí)間和占用資源都比定點(diǎn)加法都多得多，因此硬件實(shí)現(xiàn)定點(diǎn)FFT算法時(shí)，一般以乘法次數(shù)作為預(yù)算量的度量，對于浮點(diǎn)操作，因加法流水線比乘法流水線長，故不能忽略浮點(diǎn)加法運(yùn)算時(shí)間而只根據(jù)浮點(diǎn)乘法運(yùn)算次數(shù)推斷計(jì)算時(shí)間