数字信号处理实验三基 4-FFT 算法编程.docxVIP

实验名称：基 4-FFT 算法编程 姓名：姚桂涛 学号：3190105597 实验名称：基 4-FFT 算法编程 姓名：姚桂涛 学号：3190105597 PAGE 2 PAGE 2 基 4-FFT 算法编程 一、 实验目的和要求 FFT 是快速计算 DFT 的一类算法的总称。通过序列分解，用短序列的 DFT 代替长序列的 DFT，使得计算量大大下降。基 4-FFT 是混合基 FFT 的一个特例。 通过编写基 4-FFT 算法程序，加深对 FFT 思路、算法结构的理解。 二、 实验内容和步骤 编写 16 点基 4-FFT 算法的 MATLAB 程序（studentname.m 文件）。 产生 16 点输入序列 x，用自己的学号作为前 10 点的抽样值，后面补 6 个零值抽样。算出 16 点频谱序列 X，用 stem(X) 显示频谱图形。 主要仪器设备 MATLAB 编程。 操作方法和实验步骤 （参见“二、实验内容和步骤”） 五、 实验数据记录和处理 1. 基 4-FFT 算法思路、流图结构简述如下 1.1 算法思路 该算法在时域上按 n 的特点对序列 x(n) 进行不断的以 4 为基数的分组以及位序调整，进而通过逐级的蝶形复合处理，间接地完成高点数 DFT 的计算，由此达到降低运算量以及节省存储空间的目的。 令序列 x(n) 的 N 点 DFT 结果为 X(k)，且有 N = 4m，按 ((4))n 的结果对序列 x(n) 分组得： x(0)(n) = x(4n) x(1)(n) = x(4n + 1) N x(2)(n) = x(4n + 2) 0 ?n? 4 ? 1 x(3)(n) = x(4n + 3) 且有： X(0)(k) = DFT4m?1 {x(1)(0)(n)} X(2)(1)(k) = DFT4m?1 {x(2)(n)} ? m? 0 ?k ?N 1 = 4 1 X(3)(k) = DFT4m?1 {x(3)(n)} X (k) = DFT4m?1 {x (n)} 令 0 ?k ? 4m?1 ? 1，则有： ?? X(k) = X(0)(k) + WNkX(1)(k) + WN2kX(2)(k) + WN3kX(3)(k) ????????? X (k + 4m××?1) =mm 11X(0)(k(0)(0)) ?jW?NkXNk(1)Nk ((1)k(1)) ?W?N2kXN2Nk2(2)k ((2)k(2)) + jW??N3kN3XkN3(3)k(3)(k(3)) X (k + 2 4 ? ) = X (k) W X (k) + W X (k) W X (k) X (k + 3 4 ? ) = X (k) + jW X (k) W X (k) jW X (k) 1.2 流图结构 图 1: 基 4 DIT-FFT 中的蝶形运算 对于 N 点，基 4DIT-FFT 的整体计算过程如下： 图 2: 基 4 DIT-FFT 计算过程 2. 16 点基 4-FFT 算法的流图绘出如下（因绘图限制，省略系数-1，-j，j，具体系数对应项见上一蝶形图） 图 3: 16 点基 4-FFT 算法的流图 3. 16 点基 4-FFT 算法的 MATLAB 程序（studentname.m）列出如下 studentname.m 1 2 3 4 5 6 7 8 9 10 11 12 13 % 原始序列 xn = [3,1,9,0,1,0,5,5,9,7,0,0,0,0,0,0]; n = 1:16; % 绘制原始序列 f1 = figure(1); set(gcf,’outerposition’,get(0,’screensize’)); stem(n, real(xn), ’filled’); title(’原序列’); set(gca,’FontSize’,16); axis([0 17 ?1 10]); saveas(f1, ’exp3_1’,’png’); % 基4 DFT 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 N = 16; W = exp(?1j?2?pi/N); W4 = dftmtx(4); % 第一级蝶形运算 X1 = W4?[xn(1); xn(5); xn(9); xn(13)]; X2 = W4?[xn(2); xn(6); xn(10); xn(14)]; X3 = W4?[xn(3); xn(7); xn(11); xn(15)