|
级数 级数
series
将数列un的项 u1，u2，…，un，…依次用加号连接起来的函数。数项级数的简称。如：u1＋u2＋…＋un＋…，简写为∑un,un称为级数的通项，记Sm=∑un称之为级数的部分和。如果当m→∞时 ，数列Sm有极限S，则说级数收敛，并以S为其和，记为∑un=S否则就说级数发散。
级数是研究函数的一个重要工具，在理论上和实际应用中都处于重要地位，这是因为：一方面能借助级数表示许多常用的非初等函数， 微分方程的解就常用级数表示；另一方面又可将函数表为级数，从而借助级数去研究函数，例如用幂级数研究非初等函数，以及进行近似计算等。
级数的收敛问题是级数理论的基本问题。从级数的收敛概念可知，级数的敛散性是借助于其部分和数列Sm的敛散性来定义的。因此可从数列收敛的柯西准则得出级数收敛的柯西准则 ：∑un收敛＜＝＞任意给定正数ε，必有自然数N，当n＞N，对一切自然数 p，有｜un+1＋un+2＋…＋un+p｜＜ε，即充分靠后的任意一段和的绝对值可任意小。
如果每一un≥0（或un≤0），则称∑un为正（或负）项级数，正项级数与负项级数统称为同号级数。正项级数收敛的充要条件是其部分和序列Sm 有上界，例如∑1/n！收敛，因为
Sm=1+1/2!+1/3!+···+1/m!<1+1+1/2+1/2^2+···+1/2^(m-1)<3(2^3表示2的3次方)。
有无穷多项为正，无穷多项为负的级数称为变号级数，其中最简单的是形如∑[(-1)^(n-1)]*un(un>0)的级数，称之为交错级数。判别这类级数收敛的基本方法是莱布尼兹判别法 ：若un ≥un+1 ，对每一n∈N成立，并且当n→∞时lim un=0，则交错级数收敛。例如∑[(-1)^(n-1)]*(1/n)收敛。对于一般的变号级数如果有∑|un|收敛，则称变号级数绝对收敛。如果只有 ∑un收敛，但是∑|un|发散，则称变号级数条件收敛。例如∑[(-1)^(n-1)]*(1/n^2)绝对收敛，而∑[(-1)^(n-1)]*(1/n)只是条件收敛。
如果级数的每一项依赖于变量x,x 在某区间I内变化,即un＝un(x),x∈I，则∑un(x)称为函数项级数,简称函数级数。若x＝x0使数项级数∑un(x0)收敛，就称x0为收敛点，由收敛点组成的集合称为收敛域，若对每一x∈I，级数∑un(x)都收敛，就称I为收敛区间。显然，函数级数在其收敛域内定义了一个函数，称之为和函数S(x)，即S(x)=∑un(x)如果满足更强的条件，Sm(x)在收敛域内一致收敛于S(x)。
一类重要的函数级数是形如∑an(x-x0)^0的级数，称之为幂级数 。它的结构简单 ，收敛域是一个以为中心的区间（不一定包括端点），并且在一定范围内具有类似多项式的性质，在收敛区间内能进行逐项微分和逐项积分等运算。例如幂级数∑(2x)^n/x的收敛区间是[-1/2,1/2]，幂级数∑[(x-21)^n]/(n^2)的收敛区间是[1，3]，而幂级数∑(x^n)/(n!)在实数轴上收敛。
还有一类非常常用的级数是傅里叶级数。
拉普拉斯变换 拉普拉斯变换（英文：Laplace Transform)，是工程数学中常用的一种积分变换。
如果定义：
f(t),是一个关于t,的函数，使得当t<0,时候，f(t)=0,；
s, 是一个复变量；
mathcal 是一个运算符号，它代表对其对象进行拉普拉斯积分int_0^infty e^ ,dt；F(s),是f(t),的拉普拉斯变换结果。
则f(t),的拉普拉斯变换由下列式子给出：
F(s),=mathcal left =int_ ^infty f(t),e^ ,dt
拉普拉斯逆变换，是已知F(s),，求解f(t),的过程。用符号 mathcal ^ ,表示。
拉普拉斯逆变换的公式是：
对于所有的t>0,；
f(t)
= mathcal ^ left
=frac int_ ^ F(s),e^ ,ds
c,是收敛区间的横坐标值，是一个实常数且大于所有F(s),的个别点的实部值。
为简化计算而建立的实变量函数和复变量函数间的一种函数变换。对一个实变量函数作拉普拉斯变换，并在复数域中作各种运算，再将运算结果作拉普拉斯反变换来求得实数域中的相应结果，往往比直接在实数域中求出同样的结果在计算上容易得多。拉普拉斯变换的这种运算步骤对于求解线性微分方程尤为有效，它可把微分方程化为容易求解的代数方程来处理，从而使计算简化。在经典控制理论中，对控制系统的分析和综合，都是建立在拉普拉斯变换的基础上的。引入拉普拉斯变换的一个主要优点，是可采用传递函数代替微分方程来描述系统的特性。这就为采用直观和简便的图解方法来确定控制系统的整个特性（见信号流程图、动态结构图）、分析控制系统的运动过程（见奈奎斯特稳定判据、根轨迹法），以及综合控制系统的校正装置（见控制系统校正方法）提供了可能性。
用 f(t)表示实变量t的一个函数，F(s)表示它的拉普拉斯变换，它是复变量s＝σ＋j&owega;的一个函数，其中σ和&owega; 均为实变数,j2＝-1。F(s)和f(t)间的关系由下面定义的积分所确定：
如果对于实部σ ＞σc的所有s值上述积分均存在，而对σ ≤σc时积分不存在，便称 σc为f(t)的收敛系数。对给定的实变量函数 f(t)，只有当σc为有限值时，其拉普拉斯变换F(s)才存在。习惯上,常称F(s)为f(t)的象函数,记为F(s)＝L[f(t)];称f(t)为F(s)的原函数,记为ft＝L-1[F(s)]。
函数变换对和运算变换性质 利用定义积分，很容易建立起原函数 f(t)和象函数 F(s)间的变换对，以及f(t)在实数域内的运算与F(s)在复数域内的运算间的对应关系。表1和表2分别列出了最常用的一些函数变换对和运算变换性质。
在工程学上的应用
应用拉普拉斯变换解常变量齐次微分方程，可以将微分方程化为代数方程，使问题得以解决。在工程学上，拉普拉斯变换的重大意义在于：将一个信号从时域上，转换为复频域（s域）上来表示；在线性系统，控制自动化上都有广泛的应用。 傅立叶变换 中文译名
Transformée de Fourier有多种中文译名，常见的有“傅里叶变换”、“傅立叶变换”、“付立叶变换”、“富里叶变换”、“富里哀变换”等等。为方便起见，本文统一写作“傅里叶变换”。
应用
傅里叶变换在物理学、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用（例如在信号处理中，傅里叶变换的典型用途是将信号分解成幅值分量和频率分量）。
概要介绍
* 傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。最初傅里叶分析是作为热过程的解析分析的工具被提出的（参见：林家翘、西格尔著《自然科学中确定性问题的应用数学》，科学出版社，北京。原版书名为 C. C. Lin & L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc., New York, 1974）。
* 傅里叶变换属于谐波分析。
* 傅里叶变换的逆变换容易求出,而且形式与正变换非常类似;
* 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;
* 卷积定理指出:傅里叶变换可以化复杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段;
* 离散形式的傅里叶变换可以利用数字计算机快速的算出(其算法称为快速傅里叶变换算法(FFT)).
基本性质
线性性质
两函数之和的傅里叶变换等于各自变换之和。数学描述是：若函数f \left( x\right )和g \left(x \right)的傅里叶变换\mathcal[f]和\mathcal[g]都存在，α 和 β 为任意常系数，则\mathcal[\alpha f+\beta g]=\alpha\mathcal[f]+\beta\mathcal[g]；傅里叶变换算符\mathcal可经归一化成为么正算符；
频移性质
若函数f \left( x\right )存在傅里叶变换，则对任意实数 ω0，函数f(x) e^{i \omega_ x}也存在傅里叶变换，且有\mathcal[f(x)e^{i \omega_ x}]=F(\omega + \omega _0 ) 。式中花体\mathcal是傅里叶变换的作用算子，平体F表示变换的结果（复函数），e 为自然对数的底，i 为虚数单位\sqrt；
微分关系
若函数f \left( x\right )当|x|\rightarrow\infty时的极限为0，而其导函数f'(x)的傅里叶变换存在，则有\mathcal[f'(x)]=-i \omega \mathcal[f(x)] ，即导函数的傅里叶变换等于原函数的傅里叶变换乘以因子 ? iω 。更一般地，若f(\pm\infty)=f'(\pm\infty)=\ldots=f^{(k-1)}(\pm\infty)=0，且\mathcal[f^{(k)}(x)]存在，则\mathcal[f^{(k)}(x)]=(-i \omega)^ \mathcal[f] ，即 k 阶导数的傅里叶变换等于原函数的傅里叶变换乘以因子( ? iω)k。
卷积特性
若函数f \left( x\right )及g \left( x\right )都在(-\infty,+\infty)上绝对可积，则卷积函数f*g=\int_{-\infty}^{+\infty} f(x-\xi)g(\xi)d\xi的傅里叶变换存在，且\mathcal[f*g]=\mathcal[f]\cdot\mathcal[g] 。卷积性质的逆形式为\mathcal^[F(\omega)G(\omega)]=\mathcal^[F(\omega)]*\mathcal^[G(\omega)] ，即两个函数乘积的傅里叶逆变换等于它们各自的傅里叶逆变换的卷积。
Parseval定理
若函数f \left( x\right )可积且平方可积，则\int_{-\infty}^{+\infty} f^2 (x)dx = \frac{2\pi}\int_{-\infty}^{+\infty} |F(\omega)|^d\omega 。其中 F(ω) 是 f(x) 的傅里叶变换。
傅里叶变换的不同变种
连续傅里叶变换
主条目：连续傅立叶变换
一般情况下,若“傅立叶变换”一词的前面未加任何限定语，则指的是“连续傅里叶变换”。“连续傅里叶变换”将平方可积的函数f(t) 表示成复指数函数的积分或级数形式。
f(t) = \mathcal^[F(\omega)] = \frac{\sqrt{2\pi}} \int\limits_{-\infty}^\infty F(\omega) e^{i\omega t}\,d\omega.
上式其实表示的是连续傅里叶变换的逆变换，即将时间域的函数f(t)表示为频率域的函数F(ω)的积分。反过来,其正变换恰好是将频率域的函数F(ω)表示为时间域的函数f(t)的积分形式。一般可称函数f(t)为原函数,而称函数F(ω)为傅里叶变换的像函数,原函数和像函数构成一个傅立叶变换对(transform pair)。
一种对连续傅里叶变换的推广称为分数傅里叶变换（Fractional Fourier Transform）。
当f(t)为奇函数(或偶函数)时,其余弦(或正弦)分量将消亡,而可以称这时的变换为余弦转换(cosine transform) 或 正弦转换(sine transform).
另一个值得注意的性质是,当f(t) 为纯实函数时,F(?ω) = F(ω)*成立.
傅里叶级数
主条目：傅里叶级数
连续形式的傅里叶变换其实是傅里叶级数的推广，因为积分其实是一种极限形式的求和算子而已。对于周期函数，其傅里叶级数是存在的：
f(x) = \sum_{n=-\infty}^{\infty} F_n \,e^ ,
其中Fn 为复振幅。对于实值函数，函数的傅里叶级数可以写成：
f(x) = \fraca_0 + \sum_{n=1}^\infty\left[a_n\cos(nx)+b_n\sin(nx)\right],
其中an和bn是实频率分量的振幅。
离散时间傅里叶变换
主条目：离散时间傅里叶变换
离散傅里叶变换是离散时间傅里叶变换（DTFT）的特例（有时作为后者的近似）。DTFT在时域上离散，在频域上则是周期的。DTFT可以被看作是傅里叶级数的逆。
离散傅里叶变换
主条目：离散傅里叶变换
为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数xn 定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下, 使用离散傅里叶变换，将函数 xn 表示为下面的求和形式：
x_n = \frac1 \sum_{k=0}^ X_k e^{i\frac{2\pi} kn} \qquad n = 0,\dots,N-1
其中Xk是傅里叶振幅。直接使用这个公式计算的计算复杂度为\mathcal(n^2)，而快速傅里叶变换（FFT）可以将复杂度改进为\mathcal(n \log n)。计算复杂度的降低以及数字电路计算能力的发展使得DFT成为在信号处理领域十分实用且重要的方法。
在阿贝尔群上的统一描述
以上各种傅里叶变换可以被更统一的表述成任意局部紧致的阿贝尔群上的傅里叶变换。这一问题属于调和分析的范畴。在调和分析中, 一个变换从一个群变换到它的对偶群(dual group)。此外，将傅里叶变换与卷积相联系的卷积定理在调和分析中也有类似的结论。傅里叶变换的广义理论基础参见庞特里雅金对偶性（英文版）中的介绍。
时频分析变换
主条目：时频分析变换
小波变换，chirplet转换和分数傅里叶转换试图得到时间信号的频率信息。同时解析频率和时间的能力在数学上受不确定性原理的限制。
傅里叶变换家族
下表列出了傅里叶变换家族的成员. 容易发现,函数在时(频)域的离散对应于其像函数在频(时)域的周期性.反之连续则意味着在对应域的信号的非周期性.
变换 时间 频率
连续傅里叶变换 连续, 非周期性 连续, 非周期性
傅里叶级数 连续, 周期性 离散, 非周期性
离散时间傅里叶变换 离散, 非周期性 连续, 周期性
离散傅里叶变换 离散, 周期性 离散, 周期性
傅里叶变换的基本思想首先由法国学者傅里叶系统提出，所以以其名字来命名以示纪念。
从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。
傅立叶变换属于调和分析的内容。"分析"二字，可以解释为深入的研究。从字面上来看，"分析"二字，实际就是"条分缕析"而已。它通过对函数的"条分缕析"来达到对复杂函数的深入理解和研究。从哲学上看，"分析主义"和"还原主义"，就是要通过对事物内部适当的分析达到增进对其本质理解的目的。比如近代原子论试图把世界上所有物质的本源分析为原子，而原子不过数百种而已，相对物质世界的无限丰富，这种分析和分类无疑为认识事物的各种性质提供了很好的手段。
在数学领域，也是这样，尽管最初傅立叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类，这一想法跟化学上的原子论想法何其相似！奇妙的是,现代数学发现傅立叶变换具有非常好的性质,使得它如此的好用和有用,让人不得不感叹造物的神奇:
1. 傅立叶变换是线性算子,若赋予适当的范数,它还是酉算子;
2. 傅立叶变换的逆变换容易求出,而且形式与正变换非常类似;
3. 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;
4. 著名的卷积定理指出:傅立叶变换可以化复杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段;
5. 离散形式的傅立叶变换可以利用数字计算机快速的算出(其算法称为快速傅立叶变换算法(FFT)).
正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。
有関傅立叶变换的FPGA実现
傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数Ｎ的平方成正比关系，因此，在Ｎ较大时，直接应用ＤＦＴ算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用ＦＰＧＡ来实现２ｋ／４ｋ／８ｋ点ＦＦＴ的设计方法。
１ 整体结构
一般情况下，Ｎ点的傅立叶变换对为：
其中，ＷＮ＝ｅｘｐ(－２ｐｉ／Ｎ)。Ｘ(ｋ)和ｘ(ｎ)都为复数。与之相对的快速傅立叶变换有很多种,如ＤＩＴ(时域抽取法)、ＤＩＦ（频域抽取法）、Ｃｏｏｌｅｙ－Ｔｕｋｅｙ和Ｗｉｎｏｇｒａｄ等。对于２ｎ傅立叶变换，Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法可导出ＤＩＴ和ＤＩＦ算法。本文运用的基本思想是Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法，即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然ＤＩＴ与ＤＩＦ有差别，但由于它们在本质上都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能上的优劣之分，所以可以根据需要任取其中一种，本文主要以ＤＩＴ方法为对象来讨论。
Ｎ＝８１９２点ＤＦＴ的运算表达式为：
式中，ｍ＝(４ｎ１＋ｎ２)(２０４８ｋ１＋ｋ２)(ｎ＝４ｎ１＋ｎ２，ｋ＝２０４８ｋ１＋ｋ２)其中ｎ１和ｋ２可取０,１,．．．,２０４７,ｋ１和ｎ２可取０,１,２,３。
由式（３）可知，８ｋ傅立叶变换可由４×２ｋ的傅立叶变换构成。同理，４ｋ傅立叶变换可由２×２ｋ的傅立叶变换构成。而２ｋ傅立叶变换可由１２８×１６的傅立叶变换构成。１２８的傅立叶变换可进一步由１６×８的傅立叶变换构成，归根结底，整个傅立叶变换可由基２、基４的傅立叶变换构成。２ｋ的ＦＦＴ可以通过５个基４和１个基２变换来实现；４ｋ的ＦＦＴ变换可通过６个基４变换来实现；８ｋ的ＦＦＴ可以通过６个基４和１个基２变换来实现。也就是说：ＦＦＴ的基本结构可由基２／４模块、复数乘法器、存储单元和存储器控制模块构成，其整体结构如图１所示。
图１中，ＲＡＭ用来存储输入数据、运算过程中的中间结果以及运算完成后的数据，ＲＯＭ用来存储旋转因子表。蝶形运算单元即为基２／４模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结果。
２ 蝶形运算器的实现
基４和基２的信号流如图２所示。图中，若Ａ＝ｒ０＋ｊ＊ｉ０，Ｂ＝ｒ１＋ｊ＊ｉ１，Ｃ＝ｒ２＋ｊ＊ｉ２，Ｄ＝ｒ３＋ｊ＊ｉ３是要进行变换的信号，Ｗｋ０＝ｃ０＋ｊ＊ｓ０＝１，Ｗｋ１＝ｃ１＋ｊ＊ｓ１，Ｗｋ２＝ｃ２＋ｊ＊ｓ２，Ｗｋ３＝ｃ３＋ｊ＊ｓ３为旋转因子，将其分别代入图２中的基４蝶形运算单元，则有：
Ａ′＝[ｒ０＋(ｒ１×ｃ１－ｉ１×ｓ１)＋(ｒ２×ｃ２－ｉ２×ｓ２)＋(ｒ３×ｃ３－ｉ３×ｓ３)]＋ｊ[ｉ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)＋(ｉ２×ｃ２＋ｒ２×ｓ２)＋(ｉ３×ｃ３＋ｒ３×ｓ３)] （４）
Ｂ′＝[ｒ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)－(ｒ２×ｃ２－ｉ２×ｓ２)－(ｉ３×ｃ３＋ｒ３×ｓ３)]＋ｊ[ｉ０－(ｒ１×ｃ１－ｉ１×ｓ１)－(ｉ２×ｃ２＋ｒ２×ｓ２)＋(ｒ３×ｃ３－ｉ３×ｓ３)] (５）
Ｃ′＝[ｒ０－(ｒ１×ｃ１－ｉ１×ｓ１)＋(ｒ２×ｃ２－ｉ２×ｓ２)－(ｒ３×ｃ３－ｉ３×ｓ３)]＋ｊ[ｉ０－(ｉ１×ｃ１＋ｒ１×ｓ１)＋(ｉ２×ｃ２＋ｒ２×ｓ２)－(ｉ３×ｃ３＋ｒ３×ｓ３)] （６）
Ｄ′＝[ｒ０－(ｉ１×ｃ１＋ｒ１×ｓ１)－(ｒ２×ｃ２－ｉ２×ｓ２)＋(ｉ３×ｃ３＋ｒ３×ｓ３)]＋ｊ[ｉ０＋(ｒ１×ｃ１－ｉ１×ｓ１)－(ｉ２×ｃ２＋ｒ２×ｓ２)－(ｒ３×ｃ３－ｉ３×ｓ３)] （７）
而在基２蝶形中，Ｗｋ０和Ｗｋ２的值均为１，这样，将Ａ，Ｂ，Ｃ和Ｄ的表达式代入图２中的基２运算的四个等式中，则有：
Ａ′＝ｒ０＋(ｒ１×ｃ１－ｉ１×ｓ１)＋ｊ[ｉ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)] （８）
Ｂ′＝ｒ０－ (ｒ１×ｃ１－ｉ１×ｓ１)＋ｊ[ｉ０－(ｉ１×ｃ１＋ｒ１×ｓ１)] （９）
Ｃ′＝ｒ２＋(ｒ３×ｃ３－ｉ３×ｓ３)＋ｊ[ｉ０＋(ｉ３×ｃ３＋ｒ３×ｓ３)] （１０）
Ｄ′＝ｒ２－(ｒ３×ｃ３－ｉ３×ｓ３)＋ｊ[ｉ０－(ｉ３×ｃ３＋ｒ３×ｓ３)] （１１）
在上述式（４）～（１１）中有很多类同项，如ｉ１×ｃ１＋ｒ１×ｓ１和ｒ１×ｃ１－ｉ１×ｓ１等，它们仅仅是加减号的不同，其结构和运算均类似，这就为简化电路提供了可能。同时，在蝶形运算中，复数乘法可以由实数乘法以一定的格式来表示，这也为设计复数乘法器提供了一种实现的途径。
以基４为例，在其运算单元中，实际上只需做三个复数乘法运算，即只须计算ＢＷｋ１、ＣＷｋ２和ＤＷｋ３的值即可，这样在一个基４蝶形单元里面，最多只需要３个复数乘法器就可以了。在实际过程中，在不提高时钟频率下，只要将时序控制好 便可利用流水线（Ｐｉｐｅｌｉｎｅ）技术并只用一个复数乘法器就可完成这三个复数乘法，大大节省了硬件资源。
图2 基2和基4蝶形算法的信号流图
３ ＦＦＴ的地址
ＦＦＴ变换后输出的结果通常为一特定的倒序,因此，几级变换后对地址的控制必须准确无误。
倒序的规律是和分解的方式密切相关的，以基８为例，其基本倒序规则如下：
基８可以用２×２×２三级基２变换来表示，则其输入顺序则可用二进制序列（ｎ１ ｎ２ ｎ３）来表示，变换结束后，其顺序将变为（ｎ３ ｎ２ ｎ１），如：Ｘ ０１１ → ｘ １１０ ，即输入顺序为３，输出时顺序变为６。
更进一步，对于基１６的变换，可由２×２×２×２，４×４，４×２×２等形式来构成，相对于不同的分解形式，往往会有不同的倒序方式。以４×４为例，其输入顺序可以用二进制序列（ｎ１ ｎ２ ｎ３ｎ４）来表示变换结束后，其顺序可变为（（ｎ３ ｎ４）（ｎ１ ｎ２）），如： Ｘ ０１１１ → ｘ １１０１ 。即输入顺序为７，输出时顺序变为１３。
在２ｋ／４ｋ／８ｋ的傅立叶变换中，由于要经过多次的基４和基２运算，因此，从每次运算完成后到进入下一次运算前，应对运算的结果进行倒序，以保证运算的正确性。
４ 旋转因子
Ｎ点傅立叶变换的旋转因子有着明显的周期性和对称性。其周期性表现为：
FFT之所以可使运算效率得到提高，就是利用
ＦＦＴ之所以可使运算效率得到提高，就是利用了对称性和周期性把长序列的ＤＦＴ逐级分解成几个序列的ＤＦＴ，并最终以短点数变换来实现长点数变换。
根据旋转因子的对称性和周期性，在利用ＲＯＭ存储旋转因子时，可以只存储旋转因子表的一部分，而在读出时增加读出地址及符号的控制，这样可以正确实现ＦＦＴ。因此,充分利用旋转因子的性质，可节省７０％以上存储单元。
实际上，由于旋转因子可分解为正、余弦函数的组合，故ＲＯＭ中存的值为正、余弦函数值的组合。对２ｋ／４ｋ／８ｋ的傅立叶变换来说，只是对一个周期进行不同的分割。由于８ｋ变换的旋转因子包括了２ｋ／４ｋ的所有因子，因此，实现时只要对读ＲＯＭ的地址进行控制，即可实现２ｋ／４ｋ／８ｋ变换的通用。
５ 存储器的控制
因ＦＦＴ是为时序电路而设计的，因此，控制信号要包括时序的控制信号及存储器的读写地址，并产生各种辅助的指示信号。同时在计算模块的内部，为保证高速，所有的乘法器都须始终保持较高的利用率。这意味着在每一个时钟来临时都要向这些单元输入新的操作数，而这一切都需要控制信号的紧密配合。
为了实现ＦＦＴ的流形运算，在运算的同时，存储器也要接收数据。这可以采用乒乓ＲＡＭ的方法来完成。这种方式决定了实现ＦＦＴ运算的最大时间。对于４ｋ操作，其接收时间为４０９６个数据周期，这样 ＦＦＴ的最大运算时间就是４０９６个数据周期。另外，由于输入数据是以一定的时钟为周期依次输入的，故在进行内部运算时，可以用较高的内部时钟进行运算，然后再存入ＲＡＭ依次输出。
为节省资源，可对存储数据ＲＡＭ采用原址读出原址写入的方法，即在进行下一级变换的同时，首先应将结果回写到读出数据的ＲＡＭ存贮器中；而对于ＲＯＭ，则应采用与运算的数据相对应的方法来读出存储器中旋转因子的值。
在２ｋ／４ｋ／８ｋ傅立叶变换中，要实现通用性，控制器是最主要的模块。２ｋ、４ｋ、８ｋ变换具有不同的内部运算时间和存储器地址，在设计中，针对不同的点数应设计不同的存储器存取地址，同时，在完成变换后，还要对开始输出有用信号的时刻进行指示。
６ 硬件的选择
本设计的硬件实现选用的是现场可编程门阵列(ＦＰＧＡ)来满足较高速度的需要。本系统在设计时选用的是ＡＬＴＥＲＡ公司的ＳＴＲＡＴＩＸ芯片，该芯片中包含有ＤＳＰ单元，可以完成较为耗费资源的乘法器单元。同时，该器件也包含有大量存储单元，从而可保证旋转因子的精度。
除了一些专用引脚外，ＦＰＧＡ上几乎所有的引脚均可供用户使用，这使得ＦＰＧＡ信号处理方案具有非常好的Ｉ／Ｏ带宽。大量的Ｉ／Ｏ引脚和多块存储器可使设计获得优越的并行处理性能。其独立的存储块可作为输入／工作存储区和结果的缓存区，这使得Ｉ／Ｏ可与ＦＦＴ计算同时进行。在实现的时间方面，该设计能在４０９６个时钟周期内完成一个４０９６点的ＦＦＴ。若采用１０ＭＨｚ的输入时钟，其变换时间在２００μｓ左右。而由于最新的ＦＰＧＡ使用了ＭｕｌｔｉＴｒａｃｋ互连技术，故可在２５０ＭＨｚ以下频率稳定地工作，同时，ＦＦＴ的实现时间也可以大大缩小。
ＦＦＴ运算结果的精度与输入数据的位数及运算过程中的位数有关，同时和数据的表示形式也有很大关系。一般来说，浮点方式比定点方式精度高。而在定点计算中，存储器数据的位数越大，运算精度越高， 使用的存储单元和逻辑单元也越多。在实际应用中，应根据实际情况折衷选择精度和资源。本设计通过ＭＡＴＬＡＢ进行仿真证明：其实现的变换结果与ＭＡＴＬＡＢ工具箱中的ＦＦＴ函数相比，信噪比可以达到６５ｄｂ以上，完全可以满足一般工程的实际应用要求。
离散余弦变换 离散余弦变换(DCT for Discrete Cosine Transform)是与傅里叶变换相关的一种变换，它类似于离散傅里叶变换(DFT for Discrete Fourier Transform),但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)，在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型，其中4种是常见的)。
最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为"反离散余弦变换"，"逆离散余弦变换"或者"IDCT"。
有两个相关的变换，一个是离散正弦变换(DST for Discrete Sine Transform),它相当于一个长度大概是它两倍的实奇函数的离散傅里叶变换；另一个是改进的离散余弦变换(MDCT for Modified Discrete Cosine Transform),它相当于对交叠的数据进行离散余弦变换。
应用
离散余弦变换，尤其是它的第二种类型，经常被信号处理和图像处理使用，用于对信号和图像(包括静止图像和运动图像)进行有损数据压缩。这是由于离散余弦变换具有很强的"能量集中"特性:大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分，而且当信号具有接近马尔科夫过程(Markov processes)的统计特性时，离散余弦变换的去相关性接近于K-L变换(Karhunen-Loève 变换--它具有最优的去相关性)的性能。
例如，在静止图像编码标准JPEG中，在运动图像编码标准MJPEG和MPEG的各个标准中都使用了离散余弦变换。在这些标准制中都使用了二维的第二种类型离散余弦变换，并将结果进行量化之后进行熵编码。这时对应第二种类型离散余弦变换中的n通常是8，并用该公式对每个8x8块的每行进行变换，然后每列进行变换。得到的是一个8x8的变换系数矩阵。其中(0,0)位置的元素就是直流分量，矩阵中的其他元素根据其位置表示不同频率的交流分类。
一个类似的变换, 改进的离散余弦变换被用在高级音频编码(AAC for Advanced Audio Coding)，Vorbis 和 MP3 音频压缩当中。
离散余弦变换也经常被用来使用谱方法来接偏微分方程，这时候离散余弦变换的不同的变量对应着数组两端不同的奇/偶边界条件。
计算
尽管直接使用公式进行变换需要进行O(n2)次操作，但是和快速傅里叶变换类似，我们有复杂度为O(nlog(n))的快速算法，这就是常常被称做蝶形变换的一种分解算法。另外一种方法是通过快速傅里叶变换来计算DCT，这时候需要O(n)的预操作和后操作。
参考
K. R. Rao and P. Yip, 离散余弦变换 : 算法、优点和应用 (Discrete Cosine Transform: Algorithms, Advantages, Applications) (Academic Press, Boston, 1990).
A. V. Oppenheim, R. W. Schafer, and J. R. Buck, 时间离散信号处理 (Discrete-Time Signal Processing), second edition (Prentice-Hall, New Jersey, 1999).
S. A. Martucci, 对称卷积和离散正弦余弦变换 (Symmetric convolution and the discrete sine and cosine transforms), IEEE Trans. Sig. ProcessingSP-42, 1038-1051 (1994).
Matteo Frigo and Steven G. Johnson: FFTW, http://www./. 一个免费的C语言库GPL，可以计算DCT-I~IV的1维到多维的任意大小的变换
M. Frigo and S. G. Johnson, "FFTW3的设计和实现," Proceedings of the IEEE93 (2), 216–231 (2005).
[编辑本段]改进的离散余弦变换
改进的离散余弦变换（Modified Discrete Cosine Transform, MDCT）是一种与傅立叶变换相关的变换，以第四型离散余弦变换（DCT-IV）为基础，重叠性质如下：它是应用于处理较大的资料集合，当连续的资料区块中，当前的资料区块跟后续的资料区块有重叠到的情形；即当前资料区块的后半段与下一个资料区块的前半段为重叠的状态。这样的重叠情形，除了具有离散余弦变换（Discrete Cosine Transform, DCT）的能量压缩特性外，也使这种变换在应用于信号压缩时更引人注目。因为它有助于避免由于资料区块边界所产生的多余资料。因此，这种变换可应用于MP3，AC-3， ogg vorbis，和AAC的音频压缩等方面。
改进的离散余弦变换是由Princen，Johnson和Bradley承接早前（1986年）Princen和Bradley所提出关于时域混叠消除法（Time-Domain Aliasing Cancellation, TDAC ）的改进的离散余弦变换基本定理，于1987年所提出，详述如下。至于其他类似的变换还有如以离散正弦变换为基础的改进的离散正弦变换（Modified Discrete Sine Transform, MDST）。以及其他较少使用的变换，例如以其他不同类型的DCT或DCT/DST的组合为基础的改进的离散余弦变换。
在MP3的应用上，改进的离散余弦变换，并不适用于直接处理音频信号，而适用于处理32波段多相正交滤波器（Polyphase quadrature filter, PQF）阵列的输出端信号。这样的改进的离散余弦变换输出是由一个混叠削减公式作后置处理，用以减少多相正交滤波器阵列的特殊混叠。这样的改进的离散余弦变换与滤波器阵列组合，被称作混合滤波器阵列或子带改进的离散余弦变换 。相反地，AAC通常使用一个纯粹的改进的离散余弦变换；仅Sony公司使用的MPEG – 4 AAC - SSR技术采用了运用改进的离散余弦变换的四波段多相正交滤波器阵列（但也是很少使用）。自适应听觉变换编码（Adaptive TRansfeorm Acoustic Coding, ATRAC）利用运用改进的离散余弦变换的堆叠型正交镜像滤波器（Quadrature Mirror Filter, QMF）。 小波变换 小波变换的概念是由法国从事石油信号处理的工程师J.Morlet在1974年首先提出的，通过物理的直观和信号处理的实际需要经验的建立了反演公式，当时未能得到数学家的认可。正如1807年法国的热学工程师J.B.J.Fourier提出任一函数都能展开成三角函数的无穷级数的创新概念未能得到??名数学家J.L.Lagrange，P.S.Laplace以及A.M.Legendre的认可一样。幸运的是，早在七十年代，A.Calderon表示定理的发现、Hardy空间的原子分解和无条件基的深入研究为小波变换的诞生做了理论上的准备，而且J.O.Stromberg还构造了历史上非常类似于现在的小波基；1986年??名数学家Y.Meyer偶然构造出一个真正的小波基，并与S.Mallat合作建立了构造小波基的同意方法??多尺度分析之后，小波分析才开始蓬勃发展起来，其中比利时女数学家I.Daubechies撰写的《小波十讲（Ten Lectures on Wav ...
|
