信号处理原理 F F T 实 验 张哲 沈阳广播电视大学

FFT不是一种新的算法，而只是DFT的快速算法 N*N=N2次复数乘法 N*N=N2次复数加法 直接计算DFT的复杂度为O(N2) FFT不是一种新的算法，而只是DFT的快速算法 被称为旋转因子，可以预先算好并保存

离散谱的性质 离散谱定义 离散谱性质 离散序列h(nTs) (0n<N)的DFT离散谱为 周期性 序列的N点DFT离散谱是周期为N的序列。 如果离散序列x(nTs)(0n<N)为实序列，则其N点DFT关于原点和N/2都有 ☆共轭对称性 ☆幅度对称性

FFT的原理 N点DFT运算可以分解为两组N/2点DFT运算，然后再取和。 1 W具有周期性 2 W具有对称性

FFT的原理

FFT逐级分解 N/4点DFT N/4点 DFT N 点 组 合 相 加 N/4点DFT N/4点 DFT N/4点DFT N/4点DFT 第一级 第二级 第三级

FFT运算流程图 蝶形运算单元 群 第一级 第二级 第三级

一个蝶形单元只需一次复数乘法和两次复数加法 FFT蝶形运算单元 可以共享 一个蝶形单元只需一次复数乘法和两次复数加法

FFT算法流程说明 ☆ 全部计算分解为M级，或称为M次迭代。 ☆ 输入序列x(n)按码位倒读顺序排列，输出序列X(k)按自然顺序排列。 ☆ 每级的若干蝶形单元组成“群”。第1级群数为N/2，第2级群数为N/4，……第i级群数为N/2i，最后一级的群数为1。 ☆ 每个蝶形单元都包含乘Wnk与-Wnk的运算（可简化为乘Wnk与加、减法各一次）。 ☆ 同一级中，各个群的W分布规律完全相同。

FFT算法流程说明 各级中W的排列规律（自上而下） 第1级： 第2级： 第3级： …… 第i级： 第M级： …… …… W的指数为： 次序*本级群数 ……

FFT算法流程说明 码位倒读 输入序列x(n)的排列次序不符合自然顺序。此现象是由于按n的奇偶分组进行DFT运算而造成的，这种排列方式称为“码位倒读”的顺序。 所谓“倒读”，是指按二进制表示的数字首尾位置颠倒，重新按十进制读数。 码位倒读示例（N=8）

码位倒读算法 int BitReverse(int src, int size) // src是待倒读的数，size是数二进制位数 { int tmp = src; int des = 0; for (int i=size-1; i>=0; i--) des = ((tmp & 0x1) << i) | des; tmp = tmp >> 1; } return des; 取出tmp的最后一位， 放到des的指定位上。

FFT算法流程框架 1 按下标二进制对输入进行整序 2 FOR(I=0，L=N/2; I<R; I++){ // 逐级计算. L:级内群数 FOR(J=0, M=1; J<L; J++){ // 逐群计算. M:群内单元数 FOR(K=0; K<M; K++){ // 逐蝶形单元计算 POS = K + J * (M*2) ; TMP = DATA[POS + M] * W[K*L] ; DATA[POS + M] = DATA[POS] - TMP ; DATA[POS] += TMP ; } L /= 2; // 群数减少一倍 M *= 2; // 蝶形单元数增加一倍 N=2R是FFT的点数。 I表示当前级，J表示当前群，K表示当前蝶形单元。 L表示当前级内的群数，M表示当前群内的蝶形单元数。 符号说明

IDFT同样可用FFT实现，算法复杂度相同。 预先计算好 一个对偶结点对的计算需要2次复数加法和1次复数乘法 对任一次迭代，共有N/2对结点，因此共需N次复数加法和N/2次复数乘法 复数加法次数 r次迭代的总计算量为 复数乘法次数 算法复杂度 IDFT同样可用FFT实现，算法复杂度相同。

FFT实验 二维离散傅里叶变换2D-DFT 空间中的矩阵向量(或点)表示为 ☆ 可以把[g(m,n)]看作是一幅二维数字图像，则g(m,n)是图像在坐标(m,n)处的亮度(灰度级)。 ☆ 若把g(m,n)视为一个二元函数（自变量为m和n），则它是数字图像在平面上的亮度分布函数。

FFT实验 定义1：二维矩阵向量[g(m,n)]的2D-DFT 定义2：二维矩阵谱向量[G(p,q)]的2D-IDFT

FFT实验 二维FFT for (int i=0; i<M; i++) FFT_1D(ROW[i]，N); for (int j=0; j<N; j++) FFT_1D(COL[j]，M); 数据第i行 数据第j列

FFT实验 实验数据 实验数据为一图像数据文件，文件格式是纯文本格式。 文件正文的第一行的值表示矩阵的大小，即N值。后面的N行是点阵图像，每行有N个数据。N最大为256。 在图像点阵中，‘.’代表0（即没有点）， ‘o’代表1（即有点）。 文件内容示例 （9x9汉字大） 9 可视为一个9X9的二维矩阵向量

FFT实验 实验内容 施加FFT，再直接IFFT，显示还原后的N*N汉字图像。 施加FFT，再压缩为（N/2）*（N/2）的谱，然后IFFT，最后显示还原后的（N/2）*（N/2）的汉字图像。 施加FFT，再压缩为（N/2）*（N/2）的谱，然后先补零再IFFT，最后显示还原后的N*N的汉字图像。

FFT实验 实验注意事项 ☆ 图像数据是以文本形式存放在文件中的，读入后要转化为数值（如·转为0，o转为10），才能进行FFT变换。 ☆ 为了显示还原后的图像，需要将IFFT变换后的数据以文本形式入文件中。 ☆ IFFT变换后的数据是复数，根据复数模的大小，将它们分别转成·和o字符。这就要设定一个控制阈值，模大于阈值的复数对应o字符，模小于阈值的复数对应·字符。 ☆ 控制阈值要通过实验确定。

再 见

关于FFT的概念 FFT（Fast Fourier Transform)快速 傅里叶变换的缩写。它是由Cooley和Tukey于1965年提出来的。是一种按时间序列的奇偶顺序分组的算法。又称为“时间抽取基2FFT算法。 FFT具有 线性性、对偶性、频移性等特性。

关于对偶性： 就是把频域的波形形状放到时域去，变成:F(t ),求其傅里叶变换，所求频谱与原信号时域的波形形状f(t)的内在关系，就是对偶特性 f [F(t)]=2πf(-w)

关于线性性： 线性性包含两部分内容:: 一是齐次性，即信号倍数的傅里叶变换等于信号傅里叶变换的倍数： F[af(t)]=aF[f(t)] 二是叠加性，即和的傅里叶变换等于傅里叶变换的和： F[f1(t)+f2(t)]=F[f1(t)]+F[f2(t)]

关于频移特性： 当时域信号乘以一个复指数信号时，相当于把其频谱搬移到复指数信号的频率处。又称为“频谱搬移”。

关于DFT的概念 DFT：（Discrete Fourier Transform)是离散傅里叶变换的缩写。是一个连续信号经过时域抽样、截断和周期延拓后的信号，是一个离散的和周期的冲激序列，我们从时域和频域各取一个周期内的N个点，在它们的强度之间建立对应关系，就是离散的傅里叶变换DFT。