8点基于DIT的FFT的实现

课课程程设设计计任任务务书书 学生姓名 学生姓名 专业班级 专业班级 指导教师 指导教师 工作单位 工作单位 题题 目目 8 点基于 DIT 的 FFT 的实现 初始条件 初始条件 具备 Matlab 编程能力 熟悉基于 DIT 的 FFT 的实现原理 提供编程所需要的计算机一台 要求完成的主要任务 要求完成的主要任务 包括课程设计工作量及其技术要求 以及说明 书撰写等具体要求 1 编写一个 8 点的基于 DIT 的 FFT 函数 不能使用 matlab 自带的 FFT 实现函数 2 并调用该函数实现 16 点的 FFT 运算 用 matlab 自带 函数对运行结果进行验证 3 完成符合学校要求的设计说明书 时间安排 时间安排 一周 其中 3 天程序设计 2 天程序调试 指导教师签名 指导教师签名 年年 月月 日日 系主任 或责任教师 签名 系主任 或责任教师 签名 年年 月月 日日 目 录 摘 要 I Abstract II 1 概述 1 1 1 快速傅立叶变换 FFT 简介 1 1 2 MATLAB 简介 2 2 直接计算 DFT 的问题及改进 4 2 1 直接计算 DFT 的运算量 4 2 2 改进措施 5 3 按时间抽选的基 2FFT 算法 DIT FFT 6 3 1 DIT FFT 算法原理 6 3 2 DIT FFT 的运算量 13 3 3 DIT FFT 算法的特点 14 3 4 N 16 时的 DIT FFT 算法 16 4 MATLAB 程序代码 18 4 1 N 8 点 DIT FFT 代码 18 4 2 N 16 点 DIT FFT 代码 19 5 MATLAB 仿真结果及验证 20 5 1 DIT FFT 函数调试 20 5 2 DIT FFT 函数运行结果 21 5 3 调用系统函数验证 22 6 心得体会 24 7 参考文献 25 摘 要 此次课程设计的目的是利用 MATLAB 实现 8 点基于 DIT 的 FFT 的仿真 不使用 MATLAB 自带的 FFT 实现函数 本文先就直接计算傅立叶变换 DFT 存在的问题进行讨论 之后详细介绍了快速傅立叶变换 FFT 的原 理以及推导过程 给出了 8 点 FFT 的蝶形流图以及 MATLAB 仿真的程序代码 并通过调用该函数代码计算 16 点的 FFT 最后给出了仿真调试结果和此次课程 设计的总结 关键词 FFT MATLAB 仿真 Abstract The aim of this Course Design is to use MATLAB to achieve 8 point DIT FFT simulation and cannot use the built in MATLAB FFT function to realize The beginning of this article discuss the problems of direct calculation of the Fourier transform DFT and then introduces the principle of Fast Fourier Transform FFT and the process of derivation Then there is given butterfly flow diagram of 8 point FFT and the MATLAB simulation program code and realize 16 point FFT calculation by calling the function code Finally enumerate the simulation results and make the summary of this curriculum design Keywords FFT MATLAB Simulation 1 概述 1 1 快速傅立叶变换 FFT 简介 傅立叶变换 表示能将满足一定条件的某个函数表示成三角函数 正弦和 或余弦函数 或者它们的积分的线性组合 傅立叶变换是一种分析信号的方法 它可分析信号的成分 也可用这些成分合成信号 傅立叶变换是声学 语音 电信和信号处理等领域中一种重要的分析工具 在不同的研究领域 傅立叶变 换具有多种不同的变体形式 如连续傅立叶变换和离散傅立叶变换 离散傅立叶变换 DFT 是傅立叶变换在时域和频域上都呈现离散的形 式 将时域信号的采样变换为在离散时间傅立叶变换 DTFT 频域的采样 在 形式上 变换两端 时域和频域上 的序列是有限长的 而实际上这两组序列 都应当被认为是离散周期信号的主值序列 即使对有限长的离散信号作 DFT 也应当将其看作经过周期延拓成为周期信号再作变换 有限长序列可以通过离 散傅立叶变换 DFT 将其频域也离散化成有限长序列 但其计算量太大 很难 实时地处理问题 因此引出了快速傅立叶变换 FFT 1965年 Cooley 和 Tukey 提出了计算离散傅立叶变换 DFT 的快速算法 将 DFT 的运算量减少了几个数量级 从此 对快速傅立叶变换 FFT 算法的 研究便不断深入 数字信号处理这门新兴学科也随 FFT 的出现和发展而迅速发 展 根据对序列分解与选取方法的不同而产生了 FFT 的多种算法 基本算法是 基2DIT 和基2DIF FFT 在离散傅立叶反变换 线性卷积和线性相关等方面也有 重要应用 计算离散傅立叶变换的快速方法 有按时间抽取的 FFT 算法 DIT FFT 和按频率抽取的 FFT 算法 DIF FFT 前者是将时域信号序列按偶奇分排 后 者是将频域信号序列按偶奇分排 它们都借助于的两个特点 一是周期性 二 是对称性 这样 便可以把离散傅立叶变换的计算分成若干步进行 计算效率 大为提高 快速傅立叶变换 FFT 是离散傅立叶变换的快速算法 它是根 据离散傅立叶变换的奇 偶 虚 实等特性 对离散傅立叶变换的算法进行改 进获得的 它对傅立叶变换的理论并没有新的发现 但是对于在计算机系统或 者说数字系统中应用离散傅立叶变换 可以说是进了一大步 1 2 MATLAB 简介 MATLAB 是美国 Math Works 公司出品的商业数学软件 用于算法开发 数据可视化 数据分析以及数值计算的高级技术计算语言和交互式环境 主要 包括 MATLAB 和 Simulink 两大部分 MATLAB 是 matrix依次类推 对于第 M 级蝶形 旋转因子的指数为 12 2 1 0 2 1 MML JJr 这样就可以算出每一级的旋转因子 对于 M 级的任一蝶形运算所对应的旋 转因子的指数 可以 如下方法得到 1 将待求的蝶形输入节点中上面节点的行标号值 k 写成 L 位二进制数 2 将此二进制数乘以 即将 L 位二进制数左移 L M 位 右边的空位 ML 2 补零 然后从低位到高位截取 L 位 即得到要求的指数 r 所对应的二进制数 3 4 N 16 时的 DIT FFT 算法 先将序列 x n 奇偶分组得 2 1 rxrx r 0 1 2 7 12 2 rxrx 3 4 1 将 DFT 运算也分为两组 12 2 2 16 1 8 7 0 2 168 7 0 1 12 12 0 2 12 0 1 0 kXkX rxrx rxrx nxnx nxnxDFTkX W WWW WW WW W k rk r krk r kr N N r rk N N r nk N n nk N n nk N N n 为奇数为偶数 3 4 2 其中与分别是与的8点 DFT 即 1 kX 2 kX 1 nx 2 nx 7 2 1 0 7 2 1 0 7 0 8 222 7 0 8 111 krxnxDFTkX krxnxDFTkX r rk r rk W W 3 4 3 这样 一个16点的 DFT 就被分解为两个8点的 DFT 即 k 0 1 2 7 8 2 16 1 2 16 1 kXkXkX kXkXkX W W k k 3 4 4 对两个8点的 DFT 再分别做进一步分解 每个8点的 DFT 分解成两个4点的 DFT 即 k 0 1 2 7 4 4 2 16 31 4 2 16 31 kXkXkX kXkXkX W W k k 3 4 5 对四个4点的 DFT 再分别做进一步分解 每个4点的 DFT 分解成两个2点的 DFT 即 k 0 1 2 7 2 6 4 16 53 6 4 16 53 kXkXkX kXkXkX W W k k 3 4 6 所以 N 16点的 DFT 最终可以分解成8个2点的 DFT 4 MATLAB 程序代码 4 1 N 8 点 DIT FFT 代码 根据蝶形图一级一级依次分解 可以把一个完整的8点的DFT分解成4个两 点的DFT进行运算 function y fft8 x 定义根据蝶形图计算8点DIT FFT的函 数 Wn exp j 2 pi 8 定义旋转因子计算公式 N j N e W 2 x1 1 x 1 x 5 计算第一级蝶形图输出 x 5 x 1 1 x 0 1WN x1 2 x 1 x 5 x 5 x 1 2 x 0 1WN x1 3 x 3 x 7 x 7 x 3 3 x 0 1WN x1 4 x 3 x 7 x 7 x 3 4 x 0 1WN x1 5 x 2 x 6 x 6 x 2 5 x 0 1WN x1 6 x 2 x 6 x 6 x 2 6 x 0 1WN x1 7 x 4 x 8 x 8 x 4 7 x 0 1WN x1 8 x 4 x 8 x 8 x 4 8 x 0 1WN x2 1 x1 1 x1 3 计算第二级蝶形图输出 3 x 1 x 1 x 1 0 12WN x2 2 x1 2 x1 4 Wn 2 4 x 2 x 2 x 1 2 12WN x2 3 x1 1 x1 3 3 x 1 x 3 x 1 0 12WN x2 4 x1 2 x1 4 Wn 2 4 x 2 x 4 x 1 2 12WN x2 5 x1 5 x1 7 7 x 5 x 5 x 1 0 12WN x2 6 x1 6 x1 8 Wn 2 8 x 6 x 6 x 1 2 12WN x2 7 x1 5 x1 7 7 x 5 x 7 x 1 0 12WN x2 8 x1 6 x1 8 Wn 2 8 x 6 x 8 x 1 2 12WN y 1 x2 1 x2 5 计算第三级蝶形图输出 5 x 1 x y 1 2 0 2WN y 2 x2 2 x2 6 Wn 1 6 x 2 x y 2 2 1 2WN y 3 x2 3 x2 7 Wn 2 7 x 3 x y 3 2 2 2WN y 4 x2 4 x2 8 Wn 3 8 x 4 x y 4 2 3 2WN y 5 x2 1 x2 5 5 x 1 x y 5 2 0 2WN y 6 x2 2 x2 6 Wn 1 6 x 2 x y 6 2 1 2WN y 7 x2 3 x2 7 Wn 2 7 x 3 x y 7 2 2 2WN y 8 x2 4 x2 8 Wn 3 8 x 4 x y 8 2 3 2WN 4 2 N 16 点 DIT FFT 代码 调用计算 N 8 点时编写的函数 fft8 来实现 N 16 点的 DIT FFT 运算 可以 先将 N 16 点的 DFT 根据奇偶分解成两个 8 点的 DFT 然后再分别用函数 fft8 对这两组 8 点的 DFT 进行计算 function y fft16 x 定义计算 16 点 DIT FFT 的函数 Wn exp j 2 pi 16 定义旋转因子计算公式 N j N e W 2 y1 fft8 x 1 2 16 计算偶数组的 8 点 FFT y2 fft8 x 2 2 16 计算奇数组的 8 点 FFT y 1 8 y1 y2 Wn 0 7 计算前八个点 y 9 16 y1 y2 Wn 0 7 计算后八个点 5 MATLAB 仿真结果及验证 5 1 DIT FFT 函数调试 1 运行 MATLAB 点击 file new function 新建函数编辑窗 输入 N 8点 DIT FFT 的代码并保存为 fft8 m 图5 1 N 8点 DIT FFT 函数调试 2 运行 MATLAB 点击 file new function 新建函数编辑窗 输入 N 16点 DIT FFT 的代码并保存为 fft16 m 图5 2 N 16点 DIT FFT 函数调试 5 2 DIT FFT 函数运行结果 1 在命令窗口输入 x 1 2 4 6 8 10 12 14 fft8 x 后 按回车运行程序 图5 3 N 8点 DIT FFT 函数运行结果 2 在命令窗口输入 x 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 fft16 x 后 按回车运行程序 图5 4 N 16点 DIT FFT 函数运行结果 5 3 调用系统函数验证 1 在命令窗输入 x 1 2 4 6 8 10 12 14 fft x 后按回车 通过调用系统函 数 FFT 计算 8 点 FFT 计算结果与上面一致 结果如下 图 5 5 调用系统函数验证 N 8 点 DIT FFT 2 在命令窗输入 x 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 fft x 后按 回车 通过调用系统函数 FFT 计算 8 点 FFT 计算结果与上面一致 结果如下 图 5 6 调用系统函数验证 N 16 点 DIT FFT 经过调用 MATLAB 系统自带函数的验证 所编写的程序运行的结果与系统自 带函数运行的结果一致 可以实现 8 点和 16 点的按时间抽取的基 2 FFT 运算 6 心得体会 通过此次课程设计 巩固了我在课堂上所学的关于快速傅里叶变换的相关 知识 加深了对课堂抽象概念的理解 巩固了课堂上所学的理论知识 并能很好 地理解与掌握数字信号处理中的基本概念 基本原理 基本分析方法 设计过 程中 学习了许多数字信号处理课程中关于数字滤波器的设计的内容 同时掌 握编程方法和解决实际问题的技巧 与其他高级语言的程序设计相比 MATLAB 环境下更方便 快捷 节省大量 的编程时间 提高编程效率 且参数的修改也十分方便 还可以进一步进行优 化设计 此外 在此次数字信号处理原理与实现课程设计中 通过查阅资料 请教 同学等途径 在摸索中不仅完成了教学任务 还对 MATLAB 这个强大的仿真软件 有了一定的认识 在完成了此次课程设计之后 掌握了自己的基础理论知识 提高了学习能力和基本动手能力 同时掌握了基本的文献检索和材料阅读的方 法 提高了我们的基本素质 培养了我们独立思考和解题的能力 树立了对所 学知识运用的信心 这些必将在我们今后的学习工作和生活中起到非常大的帮 助 在课程设计的这段时间里 我认为收获还是很多的 不但进一步掌握了信 号分析与处理的基础知识及一门专业仿真软件的基本操作 还提高了自己的设 计能力及动手能力 更多的是让我看清了自己 明白了凡事需要耐心 实践