笔下文学

第三章 与傅立叶有关的科学概念（第3页）

连续傅里叶变换连续，非周期性连续，非周期性

傅里叶级数连续，周期性离散，非周期性

离散时间傅里叶变换离散，非周期性连续，周期性

离散傅里叶变换离散，周期性离散，周期性

傅里叶变换的基本思想首先由法国学者傅里叶系统提出，所以以其名字来命名以示纪念。

从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。

傅立叶变换属于调和分析的内容。"分析"二字，可以解释为深入的研究。从字面上来看，"分析"二字，实际就是"条分缕析"而已。它通过对函数的"条分缕析"来达到对复杂函数的深入理解和研究。从哲学上看，"分析主义"和"还原主义"，就是要通过对事物内部适当的分析达到增进对其本质理解的目的。比如近代原子论试图把世界上所有物质的本源分析为原子，而原子不过数百种而已，相对物质世界的无限丰富，这种分析和分类无疑为认识事物的各种性质提供了很好的手段。

数学领域

尽管最初傅立叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类，这一想法跟化学上的原子论想法何其相似！奇妙的是，现代数学发现傅立叶变换具有非常好的性质，使得它如此的好用和有用，让人不得不感叹造物的神奇:

1。傅立叶变换是线性算子，若赋予适当的范数，它还是酉算子;

2。傅立叶变换的逆变换容易求出，而且形式与正变换非常类似;

3。正弦基函数是微分运算的本征函数，从而使得线性微分方程的求解可以转化为常系数的代数方程的求解。在线性时不变的物理系统内，频率是个不变的性质，从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;

4。著名的卷积定理指出:傅立叶变换可以化复杂的卷积运算为简单的乘积运算，从而提供了计算卷积的一种简单手段;

5。离散形式的傅立叶变换可以利用数字计算机快速的算出（其算法称为快速傅立叶变换算法（FFT））。

正是由于上述的良好性质，傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。

有関傅立叶变换的FPGA实现

傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数Ｎ的平方成正比关系，因此，在Ｎ较大时，直接应用ＤＦＴ算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用ＦＰＧＡ来实现２ｋ／４ｋ／８ｋ点ＦＦＴ的设计方法。

整体结构

一般情况下，Ｎ点的傅立叶变换对为：

其中，ＷＮ＝ｅｘｐ（－２ｐｉ／Ｎ）。Ｘ（ｋ）和ｘ（ｎ）都为复数。与之相对的快速傅立叶变换有很多种，如ＤＩＴ（时域抽取法）、ＤＩＦ（频域抽取法）、Ｃｏｏｌｅｙ－Ｔｕｋｅｙ和Ｗｉｎｏｇｒａｄ等。对于２ｎ傅立叶变换，Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法可导出ＤＩＴ和ＤＩＦ算法。本文运用的基本思想是Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法，即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然ＤＩＴ与ＤＩＦ有差别，但由于它们在本质上都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能上的优劣之分，所以可以根据需要任取其中一种，本文主要以ＤＩＴ方法为对象来讨论。

Ｎ＝８１９２点ＤＦＴ的运算表达式为：

式中，ｍ＝（４ｎ１＋ｎ２）（２０４８ｋ１＋ｋ２）（ｎ＝４ｎ１＋ｎ２，ｋ＝２０４８ｋ１＋ｋ２）其中ｎ１和ｋ２可取０，１，．．．，２０４７，ｋ１和ｎ２可取０，１，２，３。

由式（３）可知，８ｋ傅立叶变换可由４×２ｋ的傅立叶变换构成。同理，４ｋ傅立叶变换可由２×２ｋ的傅立叶变换构成。而２ｋ傅立叶变换可由１２８×１６的傅立叶变换构成。１２８的傅立叶变换可进一步由１６×８的傅立叶变换构成，归根结底，整个傅立叶变换可由基２、基４的傅立叶变换构成。２ｋ的ＦＦＴ可以通过５个基４和１个基２变换来实现；４ｋ的ＦＦＴ变换可通过６个基４变换来实现；８ｋ的ＦＦＴ可以通过６个基４和１个基２变换来实现。也就是说：ＦＦＴ的基本结构可由基２／４模块、复数乘法器、存储单元和存储器控制模块构成，其整体结构如图１所示。

图１中，ＲＡＭ用来存储输入数据、运算过程中的中间结果以及运算完成后的数据，ＲＯＭ用来存储旋转因子表。蝶形运算单元即为基２／４模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结果。

蝶形运算器的实现

基４和基２的信号流如图２所示。图中，若Ａ＝ｒ０＋ｊ＊ｉ０，Ｂ＝ｒ１＋ｊ＊ｉ１，Ｃ＝ｒ２＋ｊ＊ｉ２，Ｄ＝ｒ３＋ｊ＊ｉ３是要进行变换的信号，Ｗｋ０＝ｃ０＋ｊ＊ｓ０＝１，Ｗｋ１＝ｃ１＋ｊ＊ｓ１，Ｗｋ２＝ｃ２＋ｊ＊ｓ２，Ｗｋ３＝ｃ３＋ｊ＊ｓ３为旋转因子，将其分别代入图２中的基４蝶形运算单元，则有：

Ａ′＝[ｒ０＋（ｒ１×ｃ１－ｉ１×ｓ１）＋（ｒ２×ｃ２－ｉ２×ｓ２）＋（ｒ３×ｃ３－ｉ３×ｓ３）]＋ｊ[ｉ０＋（ｉ１×ｃ１＋ｒ１×ｓ１）＋（ｉ２×ｃ２＋ｒ２×ｓ２）＋（ｉ３×ｃ３＋ｒ３×ｓ３）]?（４）

Ｂ′＝[ｒ０＋（ｉ１×ｃ１＋ｒ１×ｓ１）－（ｒ２×ｃ２－ｉ２×ｓ２）－（ｉ３×ｃ３＋ｒ３×ｓ３）]＋ｊ[ｉ０－（ｒ１×ｃ１－ｉ１×ｓ１）－（ｉ２×ｃ２＋ｒ２×ｓ２）＋（ｒ３×ｃ３－ｉ３×ｓ３）]（５）

Ｃ′＝[ｒ０－（ｒ１×ｃ１－ｉ１×ｓ１）＋（ｒ２×ｃ２－ｉ２×ｓ２）－（ｒ３×ｃ３－ｉ３×ｓ３）]＋ｊ[ｉ０－（ｉ１×ｃ１＋ｒ１×ｓ１）＋（ｉ２×ｃ２＋ｒ２×ｓ２）－（ｉ３×ｃ３＋ｒ３×ｓ３）]（６）

Ｄ′＝[ｒ０－（ｉ１×ｃ１＋ｒ１×ｓ１）－（ｒ２×ｃ２－ｉ２×ｓ２）＋（ｉ３×ｃ３＋ｒ３×ｓ３）]＋ｊ[ｉ０＋（ｒ１×ｃ１－ｉ１×ｓ１）－（ｉ２×ｃ２＋ｒ２×ｓ２）－（ｒ３×ｃ３－ｉ３×ｓ３）]?（７）

而在基２蝶形中，Ｗｋ０和Ｗｋ２的值均为１，这样，将Ａ，Ｂ，Ｃ和Ｄ的表达式代入图２中的基２运算的四个等式中，则有：

Ａ′＝ｒ０＋（ｒ１×ｃ１－ｉ１×ｓ１）＋ｊ[ｉ０＋（ｉ１×ｃ１＋ｒ１×ｓ１）]?（８）