离散傅立叶变换（Discrete Fourier Transform）

离散傅立叶变换概述

傅立叶分析得名于法国数学家和物理学家JeanBaptiste JosephFourier ，这是一种将信号分解为其谐波成分的途径。如图1至图3所示 ，通过使用9个余弦函数和9个正弦函数的不同组合与叠加 ，可以实现对具有16个采样点的离散信号的有效重建 。其周期保持一致；其频率则取决于所分解的具体信号；仅振幅不同 。

图 1-1 离散信号与对应的三角波

信号既可以表现为连续形式，也可以以离散形式存在，并且其时域特征可能呈现周期性变化也可能不具有这种规律性。基于以上两个关键属性的不同组合情况，傅里叶变换理论形成了四种主要分析方法：

傅里叶转换（Fourier Transform）用于处理非循环性的连续信号。

该傅里叶分析方法用于研究具有周期性的连续时间信号（Periodic-Continuous）。

该方法用于分析非周期性的离散信号（Aperiodic-Discrete）。

discrete Fourier transform (DFT)，用于处理具有周期特性的离散序列。

计算机仅能处理离散且长度有限的信号由此可见离散傅立叶变换(DFT)是唯一能在计算机中通过算法实现的那种信号处理方法

图1-2 四种不同类型的傅立叶分析

实数离散傅立叶变换（RealDFT）的格式和表示

如图1-3所示，在离散傅里叶变换的作用下，原始信号将经过处理后生成两个新的频谱图。其中具有N个采样点的输入信号会被转换为具有N/2+1个采样点的新信号序列；其输出则被称为频域特征

在时域与频域中所包含的信息具有相同的内涵，在呈现形式上则存在差异性。通过离散傅立叶变换（DFT），实现了时间序列从时域到频域的转换；而其逆过程则被称为反变换（IDFT）。在频域分析中，数据被划分为实部分量ReX[ ]与虚部分量ImX[]两个组成部分，在处理余弦波(Cosine)幅度方面分别发挥着关键作用，在处理正弦波(Sine)幅度方面也扮演着同等重要的角色。

图 1-3 实数傅立叶变换示意图

DFT基函数

DFT中使用的三角函数被称作基函数（BasisFunction），其周期保持不变，而振幅则有所变化。其数学表达式如下：

C k[i]= cos(2 k i /N)

S k[i]= sin(2 k i /N)

公式1-1

在其中,C(k,i) 和 S(k,i)代表由N个离散点构成的一组正弦曲线, 其中变量i从某个起点变化至 N−1的位置, 参数k决定了这些正弦曲线的周期特性, 其取值区间限定在0至 N/2之间.

多余的系数

经过DFT运算后, 信号的频谱成分数量从N个增加至N+2个的状态下看似多出两个冗余系分存在. 在频域中确实存在两个这样的冗余系分分别为_imx[0]和_imx[n/2]. 这些冗余的存在导致频域中的其他各个系数组分彼此独立, 且这些系数组分的值始终恒定为零, 从而不影响后续反变换过程.

反变换的计算(IDFT)

公式1-2

在上述公式中所述之振幅采用的是和，并非ImX[k]与ReX[k]

公式1-3

反变换的算法实现

下面是反变换算法的伪代码实现：

100'THE INVERSE DISCRETE FOURIER TRANSFORM

110'The time domain signal, held in XX[ ], is calculated from thefrequency domain signals,

120'held in REX[ ] and IMX[ ].

130'

140DIM XX[511] 'XX[ ] holds the time domain signal

150DIM REX[256] 'REX[ ] holds the real part of the frequency domain

160DIM IMX[256] 'IMX[ ] holds the imaginary part of the frequency domain

170'

180PI = 3.14159265 'Set the constant, PI

190N% = 512 'N% is the number of points in XX[ ]

200'

210GOSUB XXXX 'Mythical subroutine to load data into REX[ ] and IMX[ ]

220'

230

240'__'Findthe cosine and sine wave amplitudes using Eq. 1-3

250FOR K% = 0 TO 256

260REX[K%] = REX[K%] / (N%/2)

270IMX[K%] = -IMX[K%] / (N%/2)

280NEXT K%

290'

300REX[0] = REX[0] / 2

310REX[256] = REX[256] / 2

320'

330'

340FOR I% = 0 TO 511 'ZeroXX[ ] so it can be used as an accumulator

350XX[I%] = 0

360NEXT I%

370'

380'Eq. 1-2 SYNTHESIS METHOD #1. Loop through each

390'frequency generating the entire length of the sine and cosine

400'waves, and add them to the accumulator signal, XX[ ]

410'

420FOR K% = 0 TO 256 'K% loops through each sample in REX[ ] and IMX[ ]

430FOR I% = 0 TO 511 'I% loops through each sample in XX[ ]

440'

450XX[I%] = XX[I%] + REX[K%] * COS(2PIK%*I%/N%)

460XX[I%] = XX[I%] + IMX[K%] * SIN(2PIK%*I%/N%)

470'

480NEXT I%

490NEXT K%

500'

510END

_

_

图1-4 IDCT示意图

该文详细阐述了IDCT的过程及其与反变换中振幅分布的关系。（如图1-4所示）
在时间域中（如图1-4a所示），我们有一条曲线在0点处振幅为32。
而经过DFT变换后（如图1-4b所示），实部数据ReX值已达到32。
值得注意的是，在这种情况下虚部数据ImX均为零值，
因此在频谱分析中并未体现出来。
具体而言，
公式 通过傅里叶变换将时间域信号转化为频率域信号，
其中实部数据ReX对应余弦分量，
而虚部数据ImX则对应正弦分量。
在这种特殊情况下，
由于虚部数据ImX全为零，
因此其对应的正弦分量并不存在于频谱中。

频率域与三角函数振幅在性质上有所区别,原因在于频率域被定义为谱密度（spectraldensity）

图1-4展示了实部信号在频率域中的分布情况，在包含从0到16号采样点的情况下包含了32个数据点。 谱密度是指每单位频带内能够表示的信号强度（振幅），其计算方式是将三角函数的结果除以对应的频带宽度。

在图1-4中，虚线用于说明带宽计算的方法；具体而言，在采样区间内采用均分的方式实现这一过程。其中第一个和第十六个采样点对应的带宽值为每份区间的长度；而中间其他各个采样点（编号从第二个到第十五个）对应的带宽则均为两倍于每份区间长度。这正是导致公式1-3中ReX[0]与ReX[N/2]及其他各ReX存在差异的根本原因

图 1-5频率域的带宽(bandwidth)

DFT的分析与计算

DFT 的计算共有三种主要方法：第一种方法是解线性方程组（System of Linear Equations），虽然操作简便但其计算复杂度较高，在实际应用中通常不采用该方法；第二种方法基于相关函数（Correlation Function），建立在已知另一条相关曲线的基础上；第三种则是快速傅里叶变换算法（Fast Fourier Transform, FFT）。该算法通过将处理一个包含 N 个数据点的数据序列转换为处理 N 个单独的一点序列来显著降低运算复杂度。

线性方程组求解DFT

这种计算方法用于DFT运算显得很自然。它是指从一组N个方程中求解出这组方程中的N个未知数。然而该方法的计算量相当庞大因而通常不会在实际情况中被采用

关联法（correlation）求解DFT

通过correlation技术求解DFT是一种标准方法，在本节中将通过具体实例阐述这一过程。在本例中涉及64点信号频域分析，在这种情况下需要分别计算频率域中的实部与虚部各含有的共轭复数值数量。在此具体实现过程中我们仅需计算其中一个复数值即虚部分量X[3]（记作_I_ X[3]）。

denoted X[3]表示该正弦函数具有三个完整周期且其幅度为X[3]；其曲线位于点0至点63这一区间内（如图1-6a所示）。

在图1-6所示的示例中，a与b代表两个时间域内的典型信号，在其中分别标记为x₁和x₂。该正弦波曲线（标记为x₁）在一个从0到63的时间范围内恰好包含三个完整的周期。对于复合信号x₂而言，在其构成的所有三角函数分量中，并无任何一个分量能够在0至63的时间区间内完成完整的三个周期。

借助这两条曲线能说明该算法执行的功能。具体来说，在输入函数x1的情况下（即对于输入函数x1的情形），其计算结果应为32（即表示该信号中的正弦波幅度）；而在输入函数x2的情形下（即对于输入函数x2的情况），其计算结果应为零（由于x2代表的曲线不在该信号范围内）。

因为除x1[]外的任意函数与正弦函数相乘，在区间0到63（包含3个完整周期）上的积分为零。在示意图中，图e则表示图a与图c的乘积，在所有点处的数值求和即可得出32；而图f则是由图b与图d相乘所得，在求各点数值之和时得到的结果为零。

上面的计算过程可以用公式1-4来表示。

公式1-4

图1-6关联法（correlation）求DFT

下面是关联法计算DFT的算法伪代码：

100'THE DISCRETE FOURIER TRANSFORM

110'The frequency domain signals, held in REX[ ] and IMX[ ], are calculatedfrom

120'the time domain signal, held in XX[ ].

130'

140DIM XX[511] 'XX[ ] holds the time domain signal

150DIM REX[256] 'REX[ ] holds the real part of the frequency domain

160DIM IMX[256] 'IMX[ ] holds the imaginary part of the frequency domain

170'

180PI = 3.14159265 'Set the constant, PI

190N% = 512 'N% is the number of points in XX[ ]

200'

210GOSUB XXXX 'Mythical subroutine to load data into XX[ ]

220'

230'

240FOR K% = 0 TO 256 'Zero REX[ ] & IMX[ ] so they can be used as accumulators

250REX[K%] = 0

260IMX[K%] = 0

270NEXT K%

280'

290' 'Correlate XX[ ] with the cosine and sine waves, Eq. 8-4

300'

310FOR K% = 0 TO 256 'K% loops through each sample in REX[ ] and IMX[]

320FOR I% = 0 TO 511 'I% loops through each sample in XX[ ]

330'

340REX[K%] = REX[K%] + XX[I%] * COS(2PIK%*I%/N%)

350IMX[K%] = IMX[K%] - XX[I%] * SIN(2PIK%*I%/N%)

360'

370NEXT I%

380NEXT K%

390'

400END

二元性（Duality）

DFT与IDFT的变换公式在本质上非常相似。在将信号转换至另一个域时,通常会使用当前域中的已有数值与基函数进行相乘运算,并将这些乘积结果累加起来。实际上,在时间域中存在N个数据点,而在频率域中则有N/2+1个频谱线。在复数傅里叶变换过程中,时间序列和频谱图均包含相同数量的数据点（共N个）,这种结构上的对称性使得DFT与IDFT之间的转换公式几乎一致。这种对称性进一步体现在两个变换公式的高度相似性上

可将时间和频率之间的这种对偶关系称为Duality（对偶性）。二元性将表现出许多有趣的特性。例如，在频谱中的一个单一数据点会被映射到时域中的一条三角波形状。基于Duality原理，则时频之间的这种映射关系是相互对应的。