1、二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0i<Mi++)
FFT_1D(ROW[i]，N)
for (int j=0j<Nj++)
FFT_1D(COL[j]，M)
其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。
所以，关键是一维FFT算法的实现。
2、例程：
#include <stdio.h>#include <math.h>
#include <stdlib.h>
#define N 1000
/*定义复数类型*/
typedef struct{
double real
double img
}complex
complex x[N], *W /*输入序列,变换核*/
int size_x=0 /*输入序列的大小，在本程序中仅限2的次幂*/
double PI /*圆周率*/
void fft() /*快速傅里叶变换*/
void initW() /*初始化变换核*/
void change() /*变址*/
void add(complex ,complex ,complex *) /*复数加法*/
void mul(complex ,complex ,complex *) /*复数乘法*/
void sub(complex ,complex ,complex *) /*复数减法*/
void output()
int main(){
int i /*输出结果*/
system("cls")
PI=atan(1)*4
printf("Please input the size of x:\n")
scanf("%d",&size_x)
printf("Please input the data in x[N]:\n")
for(i=0i<size_xi++)
scanf("%lf%lf",&x[i].real,&x[i].img)
initW()
fft()
output()
return 0
}
/*快速傅里叶变换*/
void fft(){
int i=0,j=0,k=0,l=0
complex up,down,product
change()
for(i=0i< log(size_x)/log(2) i++){ /*一级蝶形运算*/
l=1<<i
for(j=0j<size_xj+= 2*l ){ /*一组蝶形运算*/
for(k=0k<lk++){ /*一个蝶形运算*/
mul(x[j+k+l],W[size_x*k/2/l],&product)
add(x[j+k],product,&up)
sub(x[j+k],product,&down)
x[j+k]=up
x[j+k+l]=down
}
}
}
}
/*初始化变换核*/
void initW(){
int i
W=(complex *)malloc(sizeof(complex) * size_x)
for(i=0i<size_xi++){
W[i].real=cos(2*PI/size_x*i)
W[i].img=-1*sin(2*PI/size_x*i)
}
}
/*变址计算，将x(n)码位倒置*/
void change(){
complex temp
unsigned short i=0,j=0,k=0
double t
for(i=0i<size_xi++){
k=ij=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
}
}
}
/*输出傅里叶变换的结果*/
void output(){
int i
printf("The result are as follows\n")
for(i=0i<size_xi++){
printf("%.4f",x[i].real)
if(x[i].img>=0.0001)printf("+%.4fj\n",x[i].img)
else if(fabs(x[i].img)<0.0001)printf("\n")
else printf("%.4fj\n",x[i].img)
}
}
void add(complex a,complex b,complex *c){
c->real=a.real+b.real
c->img=a.img+b.img
}
void mul(complex a,complex b,complex *c){
c->real=a.real*b.real - a.img*b.img
c->img=a.real*b.img + a.img*b.real
}
void sub(complex a,complex b,complex *c){
c->real=a.real-b.real
c->img=a.img-b.img
}
#include <stdio.h>#include <math.h>
#include <stdlib.h>
#define N 1000
/*定义复数类型*/
typedef struct{
double real
double img
}complex
complex x[N], *W/*输入序列,变换核*/
int size_x=0 /*输入序列的大小，在本程序中仅限2的次幂*/
double PI/*圆周率*/
void fft()/*快速傅里叶变换*/
void initW() /*初始化变换核*/
void change()/*变址*/
void add(complex ,complex ,complex *)/*复数加法*/
void mul(complex ,complex ,complex *)/*复数乘法*/
void sub(complex ,complex ,complex *)/*复数减法*/
void output()
int main(){
int i/*输出结果*/
system("cls")
PI=atan(1)*4
printf("Please input the size of x:\n")
scanf("%d",&size_x)
printf("Please input the data in x[N]:\n")
for(i=0i<size_xi++)
scanf("%lf%lf",&x[i].real,&x[i].img)
initW()
fft()
output()
return 0
}
/*快速傅里叶变换*/
void fft(){
int i=0,j=0,k=0,l=0
complex up,down,product
change()
for(i=0i<log(size_x)/log(2) i++){ /*一级蝶形运算*/
l=1<<i
for(j=0j<size_xj+= 2*l ){ /*一组蝶形运算*/
for(k=0k<lk++){/*一个蝶形运算*/
mul(x[j+k+l],W[size_x*k/2/l],&product)
add(x[j+k],product,&up)
sub(x[j+k],product,&down)
x[j+k]=up
x[j+k+l]=down
}
}
}
}
/*初始化变换核*/
void initW(){
int i
W=(complex *)malloc(sizeof(complex) * size_x)
for(i=0i<size_xi++){
W[i].real=cos(2*PI/size_x*i)
W[i].img=-1*sin(2*PI/size_x*i)
}
}
/*变址计算，将x(n)码位倒置*/
void change(){
complex temp
unsigned short i=0,j=0,k=0
double t
for(i=0i<size_xi++){
k=ij=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
}
}
}
/*输出傅里叶变换的结果*/
void output(){
int i
printf("The result are as follows\n")
for(i=0i<size_xi++){
printf("%.4f",x[i].real)
if(x[i].img>=0.0001)printf("+%.4fj\n",x[i].img)
else if(fabs(x[i].img)<0.0001)printf("\n")
else printf("%.4fj\n",x[i].img)
}
}
void add(complex a,complex b,complex *c){
c->real=a.real+b.real
c->img=a.img+b.img
}
void mul(complex a,complex b,complex *c){
c->real=a.real*b.real - a.img*b.img
c->img=a.real*b.img + a.img*b.real
}
void sub(complex a,complex b,complex *c){
c->real=a.real-b.real
c->img=a.img-b.img
}
