1.FFT：
創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比銀海網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式銀海網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋銀海地區(qū)。費(fèi)用合理售后完善，10多年實(shí)體公司更值得信賴。
//?data為輸入和輸出的數(shù)據(jù)，N為長(zhǎng)度
bool?CFFT::Forward(complex?*const?Data,?const?unsigned?int?N)
{
if?(!Data?||?N??1?||?N??(N?-?1))
return?false;
//???排序
Rearrange(Data,?N);
//???FFT計(jì)算：const?bool?Inverse?=?false
Perform(Data,?N);
return?true;
}
2.IFFT：
//?Scale?為是否縮放
bool?CFFT::Inverse(complex?*const?Data,?const?unsigned?int?N,
const?bool?Scale?/*?=?true?*/)
{
if?(!Data?||?N??1?||?N??(N?-?1))
return?false;
//???排序
Rearrange(Data,?N);
//???FFT計(jì)算，ture表示是逆運(yùn)算
Perform(Data,?N,?true);
//???對(duì)結(jié)果進(jìn)行縮放
if?(Scale)
CFFT::Scale(Data,?N);
return?true;
}
3.排序：
void?CFFT::Rearrange(complex?*const?Data,?const?unsigned?int?N)
{
//???Swap?position
unsigned?int?Target?=?0;
//???Process?all?positions?of?input?signal
for?(unsigned?int?Position?=?0;?Position??N;?++Position)
{
//???Only?for?not?yet?swapped?entries
if?(Target??Position)
{
//???Swap?entries
const?complex?Temp(Data[Target]);
Data[Target]?=?Data[Position];
Data[Position]?=?Temp;
}
//???Bit?mask
unsigned?int?Mask?=?N;
//???While?bit?is?set
while?(Target??(Mask?=?1))
//???Drop?bit
Target?=?~Mask;
//???The?current?bit?is?0?-?set?it
Target?|=?Mask;
}
}
4.FFT計(jì)算：
void?CFFT::Perform(complex?*const?Data,?const?unsigned?int?N,
const?bool?Inverse?/*?=?false?*/)
{
const?double?pi?=?Inverse???3.14159265358979323846?:?-3.14159265358979323846;
//???Iteration?through?dyads,?quadruples,?octads?and?so?on...
for?(unsigned?int?Step?=?1;?Step??N;?Step?=?1)
{
//???Jump?to?the?next?entry?of?the?same?transform?factor
const?unsigned?int?Jump?=?Step??1;
//???Angle?increment
const?double?delta?=?pi?/?double(Step);
//???Auxiliary?sin(delta?/?2)
const?double?Sine?=?sin(delta?*?.5);
//???Multiplier?for?trigonometric?recurrence
const?complex?Multiplier(-2.?*?Sine?*?Sine,?sin(delta));
//???Start?value?for?transform?factor,?fi?=?0
complex?Factor(1.);
//???Iteration?through?groups?of?different?transform?factor
for?(unsigned?int?Group?=?0;?Group??Step;?++Group)
{
//???Iteration?within?group?
for?(unsigned?int?Pair?=?Group;?Pair??N;?Pair?+=?Jump)
{
//???Match?position
const?unsigned?int?Match?=?Pair?+?Step;
//???Second?term?of?two-point?transform
const?complex?Product(Factor?*?Data[Match]);
//???Transform?for?fi?+?pi
Data[Match]?=?Data[Pair]?-?Product;
//???Transform?for?fi
Data[Pair]?+=?Product;
}
//???Successive?transform?factor?via?trigonometric?recurrence
Factor?=?Multiplier?*?Factor?+?Factor;
}
}
}
5.縮放：
void?CFFT::Scale(complex?*const?Data,?const?unsigned?int?N)
{
const?double?Factor?=?1.?/?double(N);
//???Scale?all?data?entries
for?(unsigned?int?Position?=?0;?Position??N;?++Position)
Data[Position]?*=?Factor;
}
這是我寫的1024點(diǎn)的快速傅里葉變換程序，下面有驗(yàn)證，你把數(shù)組
double
A[2049]={0};
double
B[1100]={0};
double
powerA[1025]={0};
改成
A[256]={0};
B[130]={0};
power[129]={0};就行了，
void
FFT(double
data[],
int
nn,
int
isign)
的程序可以針對(duì)任何點(diǎn)數(shù)，只要是2的n次方
具體程序如下：
#include
iostream.h
#include
"math.h"
#includestdio.h
#includestring.h
#include
stdlib.h
#include
fstream.h
#include
afx.h
void
FFT(double
data[],
int
nn,
int
isign)
{
//復(fù)數(shù)的快速傅里葉變換
int
n,j,i,m,mmax,istep;
double
tempr,tempi,theta,wpr,wpi,wr,wi,wtemp;
n
=
2
*
nn;
j
=
1;
for
(i
=
1;
i=n
;
i=i+2)
//這個(gè)循環(huán)進(jìn)行的是碼位倒置。
{
if(
j
i)
{
tempr
=
data[j];
tempi
=
data[j
+
1];
data[j]
=
data[i];
data[j
+
1]
=
data[i
+
1];
data[i]
=
tempr;
data[i
+
1]
=
tempi;
}
m
=
n
/
2;
while
(m
=
2
j
m)
{
j
=
j
-
m;
m
=
m
/
2;
}
j
=
j
+
m;
}
mmax
=
2;
while(
n
mmax
)
{
istep
=
2
*
mmax;
//這里表示一次的數(shù)字的變化。也體現(xiàn)了級(jí)數(shù)，若第一級(jí)時(shí)，也就是書是的第0級(jí)，其為兩個(gè)虛數(shù)，所以對(duì)應(yīng)數(shù)組應(yīng)該增加4，這樣就可以進(jìn)入下一組運(yùn)算
theta
=
-6.28318530717959
/
(isign
*
mmax);
wpr
=
-2.0
*
sin(0.5
*
theta)*sin(0.5
*
theta);
wpi
=
sin(theta);
wr
=
1.0;
wi
=
0.0;
for(
m
=
1;
m=mmax;
m=m+2)
{
for
(i
=
m;
i=n;
i=i+istep)
{
j
=
i
+
mmax;
tempr=double(wr)*data[j]-double(wi)*data[j+1];//這兩句表示蝶形因子的下一個(gè)數(shù)乘以W因子所得的實(shí)部和虛部。
tempi=double(wr)*data[j+1]+double(wi)*data[j];
data[j]
=
data[i]
-
tempr;
//蝶形單元計(jì)算后下面單元的實(shí)部，下面為虛部，注意其變換之后的數(shù)組序號(hào)與書上蝶形單元是一致的
data[j
+
1]
=
data[i
+
1]
-
tempi;
data[i]
=
data[i]
+
tempr;
data[i
+
1]
=
data[i
+
1]
+
tempi;
}
wtemp
=
wr;
wr
=
wr
*
wpr
-
wi
*
wpi
+
wr;
wi
=
wi
*
wpr
+
wtemp
*
wpi
+
wi;
}
mmax
=
istep;
}
}
void
main()
{
//本程序已經(jīng)和MATLAB運(yùn)算結(jié)果對(duì)比，準(zhǔn)確無(wú)誤，需要注意的的是，計(jì)算中數(shù)組都是從1開始取得，丟棄了A[0]等數(shù)據(jù)
double
A[2049]={0};
double
B[1100]={0};
double
powerA[1025]={0};
char
line[50];
char
dataA[20],
dataB[20];
int
ij;
char
ch1[3]="\t";
char
ch2[3]="\n";
int
strl1,strl2;
CString
str1,str2;
ij=1;
//********************************讀入文件data1024.txt中的數(shù)據(jù),
其中的數(shù)據(jù)格式見該文件
FILE
*fp
=
fopen("data1024.txt","r");
if(!fp)
{
cout"Open
file
is
failing!"endl;
return;
}
while(!feof(fp))
//feof(fp)有兩個(gè)返回值:如果遇到文件結(jié)束，函數(shù)feof（fp）的值為1，否則為0。
{
memset(line,0,50);
//清空為0
memset(dataA,0,20);
memset(dataB,0,20);
fgets(line,50,fp);
//函數(shù)的功能是從fp所指文件中讀入n-1個(gè)字符放入line為起始地址的空間內(nèi)
sscanf(line,
"%s%s",
dataA,
dataB);
//我同時(shí)讀入了兩列值，但你要求1024個(gè)，那么我就只用了第一列的1024個(gè)值
//dataA讀入第一列，dataB讀入第二列
B[ij]=atof(dataA);
//將字符型的dataA值轉(zhuǎn)化為float型
ij++;
}
for
(int
mm=1;mm1025;mm++)//A[2*mm-1]是實(shí)部，A[2*mm]是虛部，當(dāng)只要輸入實(shí)數(shù)時(shí)，那么保證虛部A[mm*2]為零即可
{
A[2*mm-1]=B[mm];
A[2*mm]=0;
}
//*******************************************正式計(jì)算FFT
FFT(A,1024,1);
//********************************************寫入數(shù)據(jù)到workout.txt文件中
for
(int
k=1;k2049;k=k+2)
{
powerA[(k+1)/2]=sqrt(pow(A[k],2.0)+pow(A[k+1],2.0));//求功率譜
FILE
*pFile=fopen("workout.txt","a+");
//?a+只能在文件最后補(bǔ)充，光標(biāo)在結(jié)尾。沒有則創(chuàng)建
memset(ch1,0,15);
str1.Format("%.4f",powerA[(k+1)/2]);
if
(A[k+1]=0)
str2.Format("%d\t%6.4f%s%6.4f
%s",(k+1)/2,A[k],"+",A[k+1],"i");//保存fft計(jì)算的頻譜，是復(fù)數(shù)頻譜
else
str2.Format("%d\t%6.4f%6.4f
%s",(k+1)/2,A[k],A[k+1],"i");
strl1=strlen(str1);
strl2=strlen(str2);
//
用
法:fwrite(buffer,size,count,fp);
//
buffer：是一個(gè)指針，對(duì)fwrite來說，是要輸出數(shù)據(jù)的地址。
//
size：要寫入的字節(jié)數(shù)；
//
count:要進(jìn)行寫入size字節(jié)的數(shù)據(jù)項(xiàng)的個(gè)數(shù)；
//
fp:目標(biāo)文件指針。
fwrite(str2,1,strl2,pFile);
fwrite(ch1,1,3,pFile);
fwrite(ch1,1,3,pFile);
fwrite(str1,1,strl1,pFile);
fwrite(ch2,1,3,pFile);
fclose(pFile);
}
cout"計(jì)算完畢，到fft_test\workout.txt查看結(jié)果"endl;
}
快速傅氏變換，是離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。它對(duì)傅氏變換的理論并沒有新的發(fā)現(xiàn)，但是對(duì)于在計(jì)算機(jī)系統(tǒng)或者說數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換，可以說是進(jìn)了一大步。
設(shè)x(n)為N項(xiàng)的復(fù)數(shù)序列，由DFT變換，任一X（m）的計(jì)算都需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法，而一次復(fù)數(shù)乘法等于四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法，一次復(fù)數(shù)加法等于兩次實(shí)數(shù)加法，即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運(yùn)算”（四次實(shí)數(shù)乘法和四次實(shí)數(shù)加法），那么求出N項(xiàng)復(fù)數(shù)序列的X（m）, 即N點(diǎn)DFT變換大約就需要N2次運(yùn)算。當(dāng)N=1024點(diǎn)甚至更多的時(shí)候，需要N2=1048576次運(yùn)算，在FFT中，利用WN的周期性和對(duì)稱性，把一個(gè)N項(xiàng)序列（設(shè)N=2k,k為正整數(shù)），分為兩個(gè)N/2項(xiàng)的子序列，每個(gè)N/2點(diǎn)DFT變換需要（N/2）2次運(yùn)算，再用N次運(yùn)算把兩個(gè)N/2點(diǎn)的DFT 變換組合成一個(gè)N點(diǎn)的DFT變換。這樣變換以后，總的運(yùn)算次數(shù)就變成N+2（N/2）2=N+N2/2。繼續(xù)上面的例子，N=1024時(shí)，總的運(yùn)算次數(shù)就變成了525312次，節(jié)省了大約50%的運(yùn)算量。而如果我們將這種“一分為二”的思想不斷進(jìn)行下去，直到分成兩兩一組的DFT運(yùn)算單元，那么N點(diǎn)的 DFT變換就只需要Nlog2N次的運(yùn)算，N在1024點(diǎn)時(shí)，運(yùn)算量?jī)H有10240次，是先前的直接算法的1%，點(diǎn)數(shù)越多，運(yùn)算量的節(jié)約就越大，這就是 FFT的優(yōu)越性.
傅里葉變換（Transformée de Fourier）是一種積分變換。因其基本思想首先由法國(guó)學(xué)者傅里葉系統(tǒng)地提出，所以以其名字來命名以示紀(jì)念。
應(yīng)用
傅里葉變換在物理學(xué)、數(shù)論、組合數(shù)學(xué)、信號(hào)處理、概率論、統(tǒng)計(jì)學(xué)、密碼學(xué)、聲學(xué)、光學(xué)、海洋學(xué)、結(jié)構(gòu)動(dòng)力學(xué)等領(lǐng)域都有著廣泛的應(yīng)用（例如在信號(hào)處理中，傅里葉變換的典型用途是將信號(hào)分解成幅值分量和頻率分量）。
概要介紹
傅里葉變換能將滿足一定條件的某個(gè)函數(shù)表示成三角函數(shù)（正弦和/或余弦函數(shù)）或者它們的積分的線性組合。在不同的研究領(lǐng)域，傅里葉變換具有多種不同的變體形式，如連續(xù)傅里葉變換和離散傅里葉變換。最初傅里葉分析是作為熱過程的解析分析的工具被提出的（參見：林家翹、西格爾著《自然科學(xué)中確定性問題的應(yīng)用數(shù)學(xué)》，科學(xué)出版社，北京。原版書名為 C. C. Lin L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc., New York, 1974）。
傅里葉變換屬于諧波分析。
傅里葉變換的逆變換容易求出,而且形式與正變換非常類似;
正弦基函數(shù)是微分運(yùn)算的本征函數(shù),從而使得線性微分方程的求解可以轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解.在線性時(shí)不變的物理系統(tǒng)內(nèi),頻率是個(gè)不變的性質(zhì),從而系統(tǒng)對(duì)于復(fù)雜激勵(lì)的響應(yīng)可以通過組合其對(duì)不同頻率正弦信號(hào)的響應(yīng)來獲取;
卷積定理指出:傅里葉變換可以化復(fù)雜的卷積運(yùn)算為簡(jiǎn)單的乘積運(yùn)算,從而提供了計(jì)算卷積的一種簡(jiǎn)單手段;
離散形式的傅里葉變換可以利用數(shù)字計(jì)算機(jī)快速的算出(其算法稱為快速傅里葉變換算法(FFT)).
重慶分公司
重慶分公司
