FFT的中文名称是最终幻想战略版。在战乱纷争的年代，有两个少年改变了历史。一个是智慧过人的迪利塔，一个是伸张正义的拉姆萨。他们在贵族挑起的不义之战中寻求真理，却发现曾经信任的长者，手中却握着名曰圣石的宝物，一个个变成了面目狰狞的野兽……

中文名：最终幻想战略版

游戏类别：PS策略角色扮演类(S●RPG)

游戏平台：PC

开发商：Square Enix

发行时间：1997/6/20

PS版本(中文名称 游戏原名 游戏平台 制作厂商 游戏类型 汉化小组 汉化程度 发布日期 游戏人数 游戏简介)

PSP版本(最终幻想战略版 游戏原名 游戏平台 游戏类型 开发厂商 发售厂商 发售日期 游戏人数 适应人群 汉化小组 游戏简介)

快速傅氏变换(算法简介 DFT算法 源码表示)

PS版本

中文名称

最终幻想战略版（简称：FFT）

游戏原名

ファイナルファンタジータクティクス

Final Fantasy Tactics

游戏平台

PS

制作厂商

Square Enix

游戏类型

策略角色扮演类（S●RPG）

汉化小组

天幻汉化组

汉化程度

完整汉化版

发布日期

1997/6/20（PS日版）1998/1/29（PS美版）

游戏人数

1

游戏简介

尘封的历史被打开，历史学家带你走进伊法利斯大陆的过去。

在战乱纷争的年代，有两个少年改变了历史。一个是智慧过人的迪利塔，一个是伸张正义的拉姆萨。他们在贵族挑起的不义之战中寻求真理，却发现曾经信任的长者，手中却握着名曰圣石的宝物，一个个变成了面目狰狞的野兽，也许这就是他们高贵权杖和华丽长袍下的本质。你不能要求一个少年在这样的环境下一尘不染，迪利塔的善良在吉克丹城砦被炸得灰飞烟灭，平民出身的孩子发誓要改写历史，要用尽他的智慧去践踏他所厌恶的贵族。而拉姆萨虽然经历一系列惨烈之事，却依然坚守信仰，为自己的亲人战斗到最后。

这就是命运，当坐在草地上吹着树叶的两个少年，最终走上了完全不同的人生道路，你会发现竟似曾相识。这是游戏也好，这是历史也好，这就是最终幻想战略版：Final Fantasy Tactics。

PSP版本

最终幻想战略版

狮子战争（简称：FFT）

游戏原名

ファイナルファンタジータクティクス 狮子戦

Final Fantasy Tactics: Shishi Sensou

游戏平台

PSP

游戏类型

策略角色扮演类（S●RPG）

开发厂商

Square Enix

发售厂商

Square Enix

发售日期

2007-05-10

游戏人数

1-2

适应人群

12岁以上

汉化小组

天幻汉化组

游戏简介

两个年轻的英雄...

埋葬在历史的影子中的“真实”...

诉说伊瓦利斯世界的原点的故事...

传说，正在苏醒……

很久以前，大国伊瓦利斯在一场战乱之后一分为二。而这次分裂国家的混乱，被历史称为“狮子战争”。

在纷飞的硝烟中，出现了两个年轻人的身影。一个是结束了狮子战争的英雄王迪瑞达，而另一个，便是故事的主人公——在历史的波涛中寂寂无名拉姆扎。二人的存在，使埋葬在历史的影子中的“真实”日渐明朗，最终壮大成为一部华美的史诗……

狮子战争厚重的幕帘依然静默。潮湿的街道，暗淡的神像，祈祷的少女，阴霾的天空，伊利瓦斯的故事将在5月10日拉开序幕，灾难、战争、硝烟、杀戮，一切等待着你来结束！

快速傅氏变换

算法简介

FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。

设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+N^2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。

DFT算法

For length N input vector x, the DFT is a length N vector X,

with elements

N

X(k) = sum x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N.

n=1

The inverse DFT (computed by IFFT) is given by

N

x(n) = (1/N) sum X(k)*exp( j*2*pi*(k-1)*(n-1)/N), 1 <= n <= N.

k=1

源码表示

在C环境下的源码

// 快速傅立叶变换

// 入口参数：

// l: l=0, 傅立叶变换;l=1, 逆傅立叶变换

// il: il=0,不计算傅立叶变换或逆变换模和幅角；il=1,计算模和幅角

// n: 输入的点数，为偶数，一般为32，64，128，...,1024等

// k: 满足n=2^k(k>0),实质上k是n个采样数据可以分解为偶次幂和奇次幂的次数

// pr[]: l=0时，存放N点采样数据的实部

// l=1时, 存放傅立叶变换的N个实部

// pi[]: l=0时，存放N点采样数据的虚部

// l=1时, 存放傅立叶变换的N个虚部

//

// 出口参数：

// fr[]: l=0, 返回傅立叶变换的实部

// l=1, 返回逆傅立叶变换的实部

// fi[]: l=0, 返回傅立叶变换的虚部

// l=1, 返回逆傅立叶变换的虚部

// pr[]: il=1,i=0 时，返回傅立叶变换的模

// il=1,i=1 时，返回逆傅立叶变换的模

// pi[]: il=1,i=0 时，返回傅立叶变换的辐角

// il=1,i=1 时，返回逆傅立叶变换的辐角

void fft(double pr[], double pi[], int n, int k, double fr[], double fi[], int l, int il){

int it,m,is,i,j,nv,l0;

double p,q,s,vr,vi,poddr,poddi;

for(it=0;it<=n-1;m=it++){

is=0;

for(i=0;i<=k-1;i++){

j=m/2;

is=2*is+(m-2*j);

m=j;

}

fr[it]=pr[is];

fi[it]=pi[is];

}

//----------------------------

pr[0]=1.0;

pi[0]=0.0;

p=6.283185306/n;

pr[1]=cos(p);

pi[1]=-sin(p);

if (l)

pi[1]=-pi[1];

for(i=2;i<=n-1;i++){

p=pr[i-1]*pr[1];

q=pi[i-1]*pi[1];

s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);

pr=p-q;

pi=s-p-q;

}

for(it=0;it<=n-2;it+=2){

vr=fr[it];

vi=fi[it];

fr[it]=vr+fr[it+1];

fi[it]=vi+fi[it+1];

fr[it+1]=vr-fr[it+1];

fi[it+1]=vi-fi[it+1];

}

m=n/2;

nv=2;

for(l0=k-2;l0>=0;l0--){

m/=2;

nv<<=1;

for(it=0;it<=(m-1)*nv;it+=nv)

for(j=0;j<=(nv/2)-1;j++){

p=pr[m*j]*fr[it+j+nv/2];

q=pi[m*j]*fi[it+j+nv/2];

s=pr[m*j]+pi[m*j];

s*=(fr[it+j+nv/2]+fi[it+j+nv/2]);

poddr=p-q;

poddi=s-p-q;

fr[it+j+nv/2]=fr[it+j]-poddr;

fi[it+j+nv/2]=fi[it+j]-poddi;

fr[it+j]+=poddr;

fi[it+j]+=poddi;

}

}

if(l)

for(i=0;i<=n-1;fr/=n,fi[i++]/=n);

if(il)

for(i=0;i<=n-1;i++){

pr=sqrt(fr*fr+fi*fi);

if(fabs(fr)<0.000001*fabs(fi))

pi=fi*fr>0?90.0-90.0;

else

pi=atan(fi/fr)*360.0/6.283185306;

}

return;

}

在C++环境下的源码

bool FFT(complex<double> * TD, complex<double> * FD, int r)

{

//一维快速Fourier变换。

//complex<double> * TD ——指向时域数组的指针; complex<double> * FD ——指向频域数组的指针; r ——2的幂数，即迭代次数

LONG count; // Fourier变换点数

int i,j,k; // 循环变量

int bfsize,p; // 中间变量

double angle; // 角度

complex<double> *W,*X1,*X2,*X;

count = 1 << r; // 计算Fourier变换点数为1左移r位

W = new complex<double>[count / 2];

X1 = new complex<double>[count];

X2 = new complex<double>[count]; // 分配运算所需存储器

// 计算加权系数（旋转因子w的i次幂表）

for(i = 0; i < count / 2; i++)

{

angle = -i * PI * 2 / count;

W[ i ] = complex<double> (cos(angle), sin(angle));

}

// 将时域点写入X1

memcpy(X1, TD, sizeof(complex<double>) * count);

// 采用蝶形算法进行快速Fourier变换

for(k = 0; k < r; k++)

{

for(j = 0; j < 1 << k; j++)

{

bfsize = 1 << (r-k);

for(i = 0; i < bfsize / 2; i++)

{

p = j * bfsize;

X2[i + p] = X1[i + p] + X1[i + p + bfsize / 2] * W[i * (1<<k)];

X2[i + p + bfsize / 2] = X1[i + p] - X1[i + p + bfsize / 2] * W[i * (1<<k)];

}

}

X = X1;

X1 = X2;

X2 = X;

}

// 重新排序

for(j = 0; j < count; j++)

{

p = 0;

for(i = 0; i < r; i++)

{

if (j&(1<<i))

{

p+=1<<(r-i-1);

}

}

FD[j]=X1[p];

}

// 释放内存

delete W;

delete X1;

delete X2;

return true;

}

在Matlab环境下的源码

function X=myfft(x)

%myfft函数 用递归实现

N=length(x);

t=log2(N);

t1=floor(t);

t2=ceil(t);

if t1~=t2; %若x的长度N不为2的整数次幂，则补0至最接近的2的整数次幂

x=[x zeros(1,2^t2-N)];

N=2^t2;

end

w0=exp(-j*2*pi/N);

X=zeros(1,N);

if N==2

X(1)=x(1)+x(2);

X(2)=x(1)-x(2);

else

n=1:N/2;

xe(n)=x(2*n-1);

xo(n)=x(2*n);

XE=myfft(xe); %递归调用

XO=myfft(xo);

for n=1:N/2

X(n)=XE(n)+XO(n)*(w0^(n-1));

X(n+N/2)=XE(n)-XO(n)*(w0^(n-1));

end

end