也来谈谈离散傅里叶变换(DFT)

2016-12-22 12:59阅读：

http://blog.sina.cn/dpool/blog/u/2728844600

上一次认真看关于DFT和FFT相关的知识恐怕得是本科学习《通信原理》这门课程的时候了，此后屡屡听到这兄弟俩的大名，但因为未涉及到具体的使用就没有深入研究，现在毕业设计是与认知无线电相关的课题，涉及大量的数字信号处理的相关术语、概念，是时候捡起遗落的知识了。

本文主要是对数字信号处理(DSP)中离散傅里叶变换(DFT)相关知识学习的一个总结，内容涉及线性系统，离散傅里叶变换(DFT)和快速傅里叶变换(FFT)。

一、线性系统

大多数的数字信号处理技术基于被称为叠加的策略，也就是说在处理信号时，信号会被分解为一些简单的部分，每个部分单独处理，再把各个部分的处理结果进行叠加。此方法可把复杂的问题分解为一些相对简单的问题来处理。叠加的方法只能应用于线性系统，这意味着该类系统需要满足一些与线性相关的数学法则。下面就来简要总结一下，线性系统中涉及的一些基本概念和线性系统所具有的特征。

1.1 基本概念
信号是对一种参数如何随着另一种参数的变化而变化的描述。
系统是对每个输入信号都产生一

个输出信号的过程。
如下所示是信号和系统的示意图，连续信号多用圆括号表示，而离散信号多用方括号表示。所有信号都用小写字母，在频域中用大写字母。除非特殊说明，一般输入信号用 x(t) 或 x[n] 表示，输出信号用 y(t) 或 y[n] 表示。

也来谈谈离散傅里叶变换(DFT)

考虑到大多数实用的系统都可以归为一类，即线性系统，这是极为重要的一点，因此了解线性系统所具有的特征对于我们处理实用系统就显得非常必要了。

1.2 线性系统具有的特征
一个系统如果同时满足两条数学性质即: 齐次性和可加性，那么该系统就被称为线性系统。如果一个系统不满足其中一条性质或两条都不满足，那就可以证明该系统是非线性的。第三个性质，位移不变性，它不是线性系统的必备条件，但对于大部分DSP技术，是一种必需的性质。上述三个特征共同构成了线性系统理论定义和应用的数学基础。
齐次性，就是说输入信号振幅的变化会导致输出信号振幅的相应变化。用数学语言来描述就是当输入信号为x[n]，输出信号为y[n]，那么当输入信号为 kx[n]时，输出信号就为 ky[n]，这种关系对于任意输入信号和常数k均成立。
可加性，就是说假设一个系统的输入信号为x1[n] 时，输出信号为y1[n]。当输入另一个信号x2[n]时，系统的输出信号为y2[n]。如果输入信号为x1[n]+x2[n] 时，输出信号是y1[n]+y2[n]，且对所有可能的输入信号都成立，我们就说此系统具有可加性。
位移不变性是指输入信号的位移对于输出信号不会产生什么影响，只会使得输出信号产生相应的位移。也就是说，如果输入信号为x[n]时，系统产生的输出信号为 y[n]，那么对于任意的输入信号和常数s，都有输入信号为x[n+s]时输出信号为y[n+s]成立。通过给变量n加上常数s，可以使波形在水平方向上左移或右移，注意左'+'右'-'。
上述的齐次性、可加性和位移不变性提供了定义线性系统的数学基础，但是这三个性质还不足以直观地向我们呈现究竟什么是线性。另外的两个重要的特征能够相对直观地呈现什么是线性：静态线性和正弦保真性。

静态线性定义了当信号不发生变化（即为直流的或静态的）时系统的行为表现。线性系统的静态表现为：输出是输入乘以一个常数。就是说，输入值和对应的输出值位于一条通过原点的直线上。以下我们熟悉的电阻的欧姆定理和弹簧的胡克定律都是线性系统。

也来谈谈离散傅里叶变换(DFT)

所有的线性系统都具有静态线性的性质，但反之并不一定成立。如果一个系统是静态线性的，也是无记忆的（无记忆系统中输出信号只取决于输入信号当前的情况，和之前的情况无关。例如电阻中的电流），那么该系统一定是线性的。
正弦保真性指的是如果一个线性系统的输入波形是正弦波，那么它的输出波形也是正弦波，并且频率是完全一样的。正弦波是唯一具有该性质的波形。傅里叶分解正是利用了正弦保真性。

1.3 常见的分解
前文已经提到DSP的核心是叠加以及如何分析信号与系统的整体方法。对于一个单一信号x[n]，通过一个线性系统，产生信号y[n]。如下图所示，我们可以将输入信号x[n]分解为一组更简单的信号: x0[n]、x1[n]、x2[n]等。接下来分别让每个输入信号单独通过系统，产生对应的输出信号y0[n]、y1[n]、y2[n]等，然后将输出信号各部分求和即得到最终的输出信号y[n]，如下所示:

也来谈谈离散傅里叶变换(DFT)

由上述信号过程可知，我们在处理一个复杂信号时，不必考虑该复杂信号通过系统时是如何被改变的，我们只需知道简单信号是如何被改变的即可。也就是说我们需要知道复杂信号是由哪些简单信号组成的，这就涉及到信号的分解了。在信号处理中，输入和输出信号可以被视为由一些简单波形叠加而成的，这是几乎所有数字信号处理的基础。
信号分解的目的是化繁为简，如果分解未使得问题在某方面得以简化，那么分解就是无意义的。在信号处理中有两种主要的方法来分解信号: 脉冲分解和傅里叶分解。另外交错分解是快速傅里叶变换(FFT)的基础，在这里主要讨论这三种分解方法。

脉冲分解是将一个包含N个抽样点的信号分解为N个分量信号，每个分量中都含有N个抽样点。每一个分量信号只含有原信号的一个抽样点，而其余各点的取值都为零。在一系列零点中的一个唯一的非零点叫做一个脉冲。

也来谈谈离散傅里叶变换(DFT)

在傅里叶分解中，任何一个信号都会被分解为N+2个信号：一半是正弦波形，一半是余弦波性。在N个样点中余弦波的最低频率是0，这是一个直流信号。接下来的余弦成分：xc1[n]、xc2[n]和xc3[n]在N个样点中分别具有1、2和3个周期。此种分配方式适用于余弦波也适用于正弦波。

也来谈谈离散傅里叶变换(DFT)

交错分解把信号分解为两部分信号：偶数样点信号和奇数样点信号。为了获得偶数样点信号，将原始信号的所有奇数样点的信号都设置为0。为了得到奇数样点信号，将原始信号的所有的偶数样点都设置为0。该分解是快速傅里叶变换(FFT)的基础。

也来谈谈离散傅里叶变换(DFT)

二、离散傅里叶变换(DFT)

傅里叶分析是以将信号分解成正弦波为基础的一种数学分析方法。离散傅里叶变换(DFT)是信号数字化中的一个分支，这里将讨论傅里叶分解的数学理论及其计算方法。

2.1 傅里叶变换
傅里叶变换是以法国数学家和物理学家吉恩·巴蒂斯特·约瑟夫·傅里叶的名字来命名的。傅里叶于1807年向法国科学院呈交了一篇有关用正弦波表示温度分布的论文，在该论文中提出任意一个连续周期信号都能够用恰当的正弦波叠加的形式来表示。
为什么要用正弦波进行分解而不用其它波形？这是因为分解后的正弦波和余弦波要比原始信号简单的多，它们具有原始信号不具有的特性——正弦保真性。所有的波形中唯有正弦波具有该种特性。
考虑到信号是连续还是离散的，以及是周期性的还是非周期性的，一般的傅里叶变换可以分为四种类型，包括:
非周期-连续——这种类型的信号沿正、负无穷方向伸展，并且不会出现周期性的重复。此类信号的傅里叶变换称为傅里叶变换(Fourier Transform)。
周期-连续——该类型的信号有正弦波、方波以及所有按一定时间间隔从负无穷到正无穷周而复始出现的波形。此类信号的傅里叶变换称为傅里叶级数(Fourier Series)。
非周期-离散——在负无穷到正无穷区间里，这类信号仅在一些不连续的点处有定义，并且不会周期性地反复出现，此类信号的傅里叶变换称为离散时间傅里叶变换(Discrete Time Fourier Transform)。
周期-离散——这种类型的信号是按一定时间间隔从负无穷到正无穷反复出现的离散信号。此类信号的傅里叶变换有时被称为离散傅里叶级数，但最经常被称作离散傅里叶变换(Discrete Fourier Transform, DFT)。

也来谈谈离散傅里叶变换(DFT)

事实证明，要合成一个非周期性的信号必须要有无穷多的正弦波，这就使离散时间傅里叶变换无法用计算机算法来实现。DFT是唯一可用于DSP领域的傅里叶变换。 2.2 DFT
离散傅里叶变换可以将一个N点的输入信号变成两个N/2+1点的输出信号。输入信号含有已被分解的信号，而两个输出信号分别包含正弦波和余弦波的幅值信息。输入信号应是时域的。这是由于进行DFT的信号都是由固定周期抽样所得的样点组成。术语'频域'是用来描述正弦波和余弦波的幅值的。
频域与时域描述的都是同一信号，只是表述形式不同。如果已知其中的一个域，就能计算出另外一个域。通过给定的时域信号计算频域信号的过程称为 DFT。而通过给定的频域信号计算时域信号的过程被称为逆向DFT。
通常时域的样点数用常量 N 表示。N 的取值通常选择2的k次方(k为任意正整数)，也就是128、256、1024等。通常情况下，N 值选在32和4096之间。
在数字信号处理中采用小写字母代表时域信号，如：x[]、y[]、z[]。而相应的大写字母则用于描述频域信号，即 X[]、Y[]和Z[]。假设有一个 N 点的时域信号为x[]，而这个信号在频域中的变换就被称做X[]，并且它由两个数组组成，每个数组含有 N/2+1个样点。这两个数组分别被称作X[]的实部(写作 ReX[]) 和 X[]的虚部(写作ImX[])。ReX[]中的数值是余弦波的幅值，而ImX[]中的数值则是正弦波的幅值。
如图显示了 N=128时DFT的例子。时域信号包含于数组x[0]到x[127]中，频域信号包括两个数组，分别为：ReX[0]到ReX[64]，以及 ImX[0]到ImX[64]。注意：时域中的128个点对应于频域各组中的65个点，频率索引区间为[0, 64]。更确切地讲，时域中的N个点对应于频域中的N/2+1个点(不是N/2个点)。

也来谈谈离散傅里叶变换(DFT)

2.3 分析、计算DFT
计算DFT有3种不同的方法，分别是：

首先，可以通过联立方程来求解，它因效率太低而无法在实际中使用。
已知时域中N个点的值，求这N个点在频域中的值(忽略频域中必为零的两个值)。由基本的代数常识可知：要求解N个未知数，就必须写出N个方程。为了求这些值，将每个正弦波的第一个样点加起来，这个和必等于时域信号必等于时域信号的第一个样点值，即可得到第一个方程。同理，时域信号中的每个样点都可以写成类似的方程，就得到了所需的N个方程。使用该方法进行求解时，计算量非常大，实际上从未在 DSP 中使用。该方法的提出说明了一个信号为什么可以被分解成正弦波，需要分解出多少个正弦波，以及这些基本函数必须线性不相关。
第二种方法是通过相关性计算 DFT。它是以从一个信号中检测已知信号为基础的，是DFT的标准算法。
将时域信号与适当的正弦或余弦波相乘，再把所得结果全部累加起来，即可得到频域中的每个样点值，这就是 DFT 的分析方程，也就是从时域值求解频域值的数学方法，如下图：
第三种方法，称为快速傅里叶变换(FFT)，该算法将一个含有N个点的DFT分解为N个只含有一个点的 DFT，将在第三部分详细介绍该算法。

在实际应用中，如果进行 DFT 的点数少于32个，则选用相关性的方法来计算，否则选用FFT进行计算。

三、快速傅里叶变换(FFT)
3.1 FFT简介
由前文介绍可知，快速傅里叶变换(Fast Fourier Transform)是一种快速的计算DFT的方法，它的计算结果和其它方法相同，但是很高效，能减少上百倍的计算时间。
FFT是J·W·库利和J·W·图基在他们的论文“用机器计算复序列傅里叶级数的一种算法”中首次提出的。FFT基于复数DFT，是实数离散傅里叶变换的一种更为复杂的变形。
实数DFT将N点的时域信号转换成两个N/2+1点的频域信号。时间域内的信号称之为：时域信号。频域的两个信号称为实部和虚部，分别对应地存放着余弦和正弦波幅值。而复数DFT将两个N点的时域信号转换成两个N点的频域信号，两个时域信号称为实部和虚部，和频域信号一样。
假设有N点信号，需要通过复数DFT计算实数DFT(比如用FFT算法)。首先，将N点信号移入复数DFT的时域实部，然后将虚部的所有样点都置零。计算复数DFT，在频域得到一个实部和虚部信号，每一个都包含N个样点。从样点0到样点N/2的信号相当于实数DFT的频谱。实数DFT和复数DFT的比较，如下图所示：

也来谈谈离散傅里叶变换(DFT)

3.2 FFT的工作原理
FFT变换首先把一个N点时域信号分解成N个时域信号，其中每个信号只包含一个点。第二步是计算出这N个时域信号相对应的N个频谱。最后，由这N个频谱合成一个频谱。
接下来以一个包含16点的信号的FFT变换过程为例，来展示FFT变换的具体过程。一个16点的信号通过4个独立的步骤来进行分解。第一步将这个16点信号分解成2个8点信号。第2步是将两个8点信号分解成4个4点信号，继续进行直至得到由16个1点组成的信号为止。每次信号一分为二均用到了交错分解，即信号被分解成为偶数抽样点和奇数抽样点。这种分解共需要 Log2(N)次，如下图所示：

也来谈谈离散傅里叶变换(DFT)

观察上图中分解的结果，可以发现分解只不过是对信号的抽样点进行了重新排列。下图列出了所需的重新排列，图的左边列出了原始信号抽样点序号和序号对应的二进制数值。图的右边列出了重新排列的抽样点序号和序号对应的二进制数值，对比左右两边数据发现：右边的二进制数正好是对左边的二进制数进行了反转(按位反转)。FFT时域分解是通过位反转分类算法实现的。
接着，FFT算法寻找1点时域信号的频谱。要注意，此时的每一个1点信号是一个频谱，而不再是一个时域信号了。

也来谈谈离散傅里叶变换(DFT)

FFT的最后一步是将N个频谱按照时域分解时重新排列的顺序进行组合。在第一步，16个频谱(每个频谱包含一点)被合成为8个频谱(每个频谱包含2点)。第二步，8个频谱(每个频谱包含2点)被合成为4个频谱(每个频谱包含4点)。最后一步使得FFT的输出是一个16点的频谱。
参考资料
1. Fourier Analysis Made Easy
2. The Scientist and Engineer's Guide to Digital Signal Processing By Steven W. Smith, Ph.D.

举报/Report

我的更多文章

下载客户端阅读体验更佳