（电路与系统专业论文）基于SEP3203微处理器的FFT系统设计与实现[电路与系统专业优秀论文].pdf

摘要 f i 叮作为时域和频域转换的基本运算 是数字信号处理中的核心算法 理论研究已经相当成熟 随着科学技术特别是微电子的飞速发展 人们使用高密度 高速度的f p g a 来实现f f t 算法 大大缩 短了它的运算时间 使之可以更好地应用于语音图像处理 通信 多媒体 雷达系统等众多领域 本文选择了s e p 3 2 0 3 微处理器 以及a l t g t a 公司的c y g l o n e l l 系列f p g a 设计了一个多接n 多用途的f f f 处理应用系统 在此平台上实现了多种不同结构的高精度f f r 算法 首先根据系统的功能要求 选择合适的器件 完成系统的硬件电路设计 包括s e p 3 2 0 3 微处理 器 f p g a 存储模块 输入输出模块 数据传输接口模块以及f p g a 外围电路 接着在f p g a 内 完成控制单元的设计 包括接口处理和数据输入部分 然后根据凡吓算法的原理和结构特点 实现 了基2 d i f 的f f t 为了提高运算速度 采取了两种方案对设计进行了优化 r a m 分块和提高基数 基4 经q u a r t u s l l 综合后 三种实现方式占用的逻辑资源都为l o 左右 占用的m e m o r y 资源 和底层乘法器资源有所不同 r a m 分块的基2 结构占用了8 0 左右的m e m o r y 资源 r a m 不分块 的基2 和基4 结构占用了5 0 左右的m e m o r y 资源 基2 结构占用了3 i 的乘法器资源 基4 结构 占用了9 3 最后对f f t 模块进行了板级测试 通过逻辑分析仪测出基2 d i f 的f f t 运算时间约 为1 0 0 v s 而优化后的两种结构运算时间都约为6 帅8 整个设计的截断信噪比高于6 0 d b 该系统包含性能优异的嵌入式处理器s e p 3 2 0 3 和快速的f f t 处理模块 以及丰富的接口功能 特别是扩展了以太网 c a n 总线和u s b 接口 在数据处理 传输方面具有极大优势 可以应用于 谱分析等众多场合 关键词ls e p 3 2 0 3 微处理器f p g a 基2 f f t 算法基4 f f t 算法 a b s t r a c t a b s t r a c t a sab a s i co p e r a t i o nb e t w e e nt i m ed o m a i na n df r e q u e n c yd o m a i n f f ta l g o r i t h mp l a y sa l li m p o r t a n t r o l ei nm o d e nd i g i t a ls i g n a lp r o c e s s i n g a n dt h et h e o r yo ff f ti sq u 妇m a t u r en o w a l o n ew i t ht h e d e v e l o p m e n to f s c i e n c ea n dt e c h n o l o g y e s p e c i a l l yi nt h em i c r o c l e c t r o n i c sf i e l d f p g a w i t hl a r g ec a p a c i t y a n dh i g hs p e e d h a sb e e na p p l i e di ni m p l e m e n t i n gf f ta l g o r i t h m i tg r e a t l ys h o r t e n st h ec a l c u l a t i o nt i m e a n di n a k c sf f rw e l la p l l i e di nv a r i o u sf i e l d s s u c ha sv o i c ea n di m a g ep r o c e s s i n g c o m m u n i c a t i o ns y s t e m m u l f i m e d i a r a d r as y s t e ma n ds o0 1 1 t b em a i nc o n t e n to ft h i st h e s i si st od e s i g naf f tp r o c e s s i n ga p p l i c a t i o ns y s t e m w h i c hi sv e r s a t i l e 埘t hm a n yi n t e r f a c e s t h es y s t e mm a i n l yb a s e do nm i c r o p r o c e s s o rs e p 3 2 0 3a n df p g ac y e l o n e l lf r o m a r e r a f f ta l g n r i t h e ma r ei m p l e m e n t e di nd i f f e r e n ts t n i e t u r e sw i t hh i g hp r e c i s i o no nt h i sp l a t f o r m f i r s t s u i t a b l ed e v i c e sa r es e l e c t e dt oc o m p l e t et h eh a r d w a r ed e s i g na c c o r d i n gt ot h ef u n c t i 0 1 1 r e q u i r e m e n t so ft h es y s t e m i n c l u d i n gm i c r o p r o c e s s o r f p g a m e m o r y i n t e r f a c em o d a l ca n df p g a p e r i p h c r yc i r c u i t s t h e n t h ec o n t r o lm o d u l ew h i c hi n c l u d e si n t e r f a c ep r o c e s s i n gm o d u l ea n dd a t ap a t hi n f p g ai sg i v e no u t a n dr a d i x 2f f rs 缸1 l 咖聘i sd e s i g n e dh a s e do nt h ep r m c i p l e sa n ds t n l c t m a lf e a t u r e so f f f ta l g o r i t h m ho r d e rt oi n l p r o v et h eo p e r a t i n gs p e e d t h ed e s i g ni so p t i m i z e di nt w ow a y so n ei s s e p e r a t e i n gt h er a m t h eo t h e ri si n c r e a s i n gt h er a d i xf r o mr a d i x 2t or a d i x 4 a l lo ft h et h r e ea p p r o a c h e s o c c u p y1 0 l o g i cr e s o u r c ea p p r o x i m a t e l y b u t0 1 1t h em e m o r yo c c u p a t i o na s p e c r t t h e r ea r cs o n i c d i f f e r e n c e s r a d i x 2w i 血r a mb l o c k s8 0 r a d i x 2a n dr a d i x 4w i t h o u tr a mb l o c k5 0 t h ed i f f e r e n c e s a b o u tc r a b e d d e dm u l t i p l i e rr e s o u e ea l e r a d i x 2h a s3 1 r u d i x4h a s9 3 a tl a s t t h ef f tm o d u l ei s t e s t e d 1 1 r e s u l t ss h o wt h a tt h eo p e r 4 t i o nt i m eo f 凡可w i 血r a d i x 2s l r u c t u r ei sa b o u tl 伽l u sa n dt h eo t h e r t w oo p t i m i z e ds t r u c t u r e sn e a r l y6 0 u s n et r u n c a t i o ns n ro f t h ew h o l ed e s i g ni sh i 曲e l t h a n6 0 d b r h es y s t e mi n c l u d e ss e p 3 2 0 3w h i c hi s 如e x c e l l e n te m b e dm i c r o p r o c e s s o r f f tp r n e e s s i n gm o d u l e a n d a b u n d a n tp e r i p h e r a li n t e r f a c e s e s p c e i n l l yt h ec a nb u si n t e r f a c e e t h e r n e tn e t w o r ki n t e r f a e na n du s b w h i c hm a k et h es y s t e mh a sg r e a ts u p e r i o r i t yi nd a mp r o c e s s i n ga n du a m c a t i n nt h i ss y s t e mc a nb ea p p l i e d i nm a n yf i e l d ss u c ha ss p e c t s u ma n a l y s i sa n de o n m a u n i c a t i o n k e yw o r d s e p 3 2 0 3m i c r o p r o e n s s o rf p g ar a d i x 2f f ta r i t h m e t i c r a d i x 4h 叮a r i t h m e t i c 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过 的研究成果 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料 与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 研究生签名 线么咀日期 上幽业培 东南大学学位论文使用授权声明 东南大学 中国科学技术信息研究所 国家图书馆有权保留本人所送交学位论文的复印 件和电子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文档的内容和纸质 论文的内容相一致 除在保密期内的保密论文外 允许论文被查阅和借阅 可以公布 包括 刊登 论文的全部或部分内容 论文的公布 包括刊登 授权东南大学研究生院办理 研究生签名 址导师签名 g 玉罂兰 一日期 z 回以四 第一章绪论 第一章绪论 本章介绍了快速傅立叶变换 f a s t f o u r i e r t r a n s f o r m f f t 的发展历史 重要意义及其实现方 式 说明了课题的来源 研究目的 阐述了本文的工作内容及章节安排 1 1 课题背景及意义 1 1 1f f t 概述 数字信号处理 d i g i t a ls i g n a lp r o c e s s i n g d s p 是 n 涉及许多技术并且应用广泛的学科 在 科学和工程技术领域中 常常需要对信号进行处理 所谓信号处理就是将观测数据进行所需的变换 或按预定规则进行运算 使之更便于分析 识别和使用 离散傅立叶变换 d i s c r e t ef o u r i e r t r a n s f o r m d f t 是最常见的数字信号处理算法之一 通过计算信号序列的d f t 可以得到序列的数 字频谱 从而在频域进行分析 往往比时域分析更加方便和高效 在计算数字滤波器的脉冲响应时 可以先进行d f t 运算而后将信号频谱与系统频响相乘 再进行d f t 的反变换来得到卷积结果 在 信号处理中的匹配滤波所需要的相关运算 同样可以通过d f t 运算得到 在数字图像的各种处理过 程中也要频繁用到d f t 运算 因此 d f t 成为数字信号处理的核心算法 但因其计算量太大而一 直难以实现 2 0 世纪6 0 年代 库利 c o o l e y 和图基 t u k e y 在 计算数学 上发表著名论文 提出了f f t f a s t f o u r i e r t r a n s f o r m 快速傅立叶变换 算法 立即引起广泛的注意 t u k e y 主要利用了旋转因 子的周期性和对称性 将d f t 运算中的某些项合并 使d f f 运算尽量分解为更少点数的d f t 运算 因为d f f 的运算量与 2 成比例 所以将一个大点数的d f t 分解为若干个小点数的d f t 的组合 可以有效的减少运算量 f f t 算法将运算量从正比于 2 减少为正比于n l o g n 运算时间减少了 1 一2 个数量级 从理论上解决了数字信号处理运算量大的问题 在数字信号处理技术从理论走向实 用的过程中发挥了重要作用 从而大大的推动了信号处理技术的发展口 f f t 的众多应用如图l l 所示 1 1 2f f t 的实现方式 图1 1f f t 的多种应用 虽然丌可算法极大程度的减少了d f t 的计算量 但计算大点数的d f t 时计算量还是大的惊人 所以它的推广与计算机的发展也是密切相关的 计算机技术为f f t 算法提供了坚实的运行平台 初始 人们通常在通用处理器上用软件来实现这些算法 其缺点是处理速度侵 延时大 效搴 低 主要的原因有两个 1 通用处理器作为c p u 需要完成大量的控制任务和管理任务 硅片中大 量资源被用于通讯与控制电路 耗时的数学运算只集中在很小一部分的硅片上执行 2 通用处理 东南大学硕士学位论文 器是基于传统的冯 诺依曼结构设计的 其取指令与存指令的瓶颈导致指令只能串行执行 随着现代科技的发展 对电子系统的速度和体积的要求也越来越高 实时 快速已经成为电子 与信号处理行业的一大发展趋势 因此 需要将用软件实现的设计思想用高效硬件来实现 而微电 子技术的蓬勃发展 也为用硬件实现f f t 算法提供了更加理想的实现手段 使之可以更好的应用于 各个领域pj 现代数字信号处理器件向以下三个方向发展 l 通用数字信号处理器 d s p 通用d s p 是专用于数字信号处理的微处理器 d s p 处理 器的突出之处主要在于针对信号箍理算法中的乘 加算法进行了结构的改进 使之能在单周期内执 行 这与大多数通用处理器相比是一个很大的进步 但由于d s p 处理器仍然是依照冯 诺依曼结构 设计的 因此还是需要按照串行的顺序来执行 因此优化后的结构尽管提高了运算速度 还是未能 真正体现出信号处理算法的内在特征 2 专用数字信号处理器 a s i c a s i c 技术克服了传统的微处理器的串行取指译码执行 的工作模式 采用阵列处理器作为基本处理单元 并以高度并行流水的方式 因而能够最大程度的 提高算法的运算速度和效率 但作为专用的处理器带来的不足之处也是明显的 1 它不具备通用 及d s p 处理器的可编程性及由此带来的灵活性 2 开发费用过高 周期较长 尤其是算法改进时 必须付出昂贵的代价投入芯片的再生产 3 可编程逻辑器件 以f p g a 为代表 利用f p g a 实现算法是最近提出的一种方案 它 综合了软件编程的灵活性和专用芯片快速性 在性能 成本 开发周期和功耗等方面都具有很大优 势 非常适合实现数字信号处理算法 随着f p g a 技术的普及 以及f f t 算法在各个领域的广泛应用 使用f p g a 芯片设计f f t 正 在世界范围内兴起 国内外都有关的研究与应用 并取得良好的效益 f p g a 芯片生产厂商 如 a l t e r a x i l i a x 公司在基于f p g a 设计f f r 的综合研究方面处于领先地位 由于生产厂商对本厂芯 片性能上的了解 设计的f f t 模块可以最大限度的发挥芯片的特点 性能非常优越 然而这些公司 研制的f f t 模块价格十分昂贵 a l t e r a 公司的f f t 核售价为7 9 9 5 美元 还难以在我国基层应用领 域普及 而且由于产权问题 用户往往看不到口里面的设计 无法深入地理解 掌握算法 更无法 移植到其它厂商的f p g a 平台和a s i c 平台上 因此 自主研发基于f p g a 的f f t 算法 利用f p g a 芯片的丰富硬件资源和设计的灵活性 在 深刻理解f f t 算法原理和结构的基础上 实现快速的f f t 算法模块 鞴足现代信号处理的高速度 高可靠性要求 是一项非常有意义的工作 1 2f p g a 的设计流程 一般来说 完整的f p g a c p l d 设计流程包括电路设计与输入 功能仿真 综合 综合后仿真 实现 布线后仿真与验证 板级仿真验证与调试等主要步骤 如图l 2 所示 1 电路设计与输入 电路设计与输入是指通过某些规范的描述方式 将工程师电路构思输入给e d a 工具 常用的 设计输入方法有硬件描述语言 h d l 合原理图设计输入方法等 目前进行大型工程设计时 最常 用的设计方法是h d l 设计输入法 其中影响最为广泛的h d l 语言是v h d l 和v e f i l o gh d l 它们 的共同特点是利用自顶向下的设计方法 利于模块的划分与复用 可移植性好 通用性好 设计不 因芯片的工艺与结构的不同而变化 更利于向a s i c 的移植 2 功能仿真 电路设计完成后 要用专用的仿真工具对设计进行功能仿真 验证电路功能是否符合设计要求 功能仿真有时也被称为前仿真 常用的仿真工具有m o d e lt e c h 公司的m o d e l s i m s y n o p s y s 公司的 v c s c a d e n c e 公司的n c v e r i l o g 和n c v h d l a l d e e 公司的a c t i v e h d l v h d l v e r i l o g h d l 等 通过仿真能及时发现设计中的错误 加快设计进度 提高设计的可靠性 3 综合优化 综合优化 s y n t h e s i z e 是指将h d l 语言 原理图等设计输入翻译成由与 或 非门 r a m 触发器等基本逻辑单元组成的逻辑连接 网表 并根据目标与要求 约束条件 优化所生成的逻 辑连接 输出如e d f 和e d n 等标准格式的网表文件 供f p g a c p l d 厂家的布局布线器进行实现 2 第一章绪论 常用的专业综合优化工具有s y n p l i e i t y 公司的s y n p l i f y s y n p l i f yp r o s y n o p s y s 公司的f p g ac o m p i l e r i i m e n t o r 公司l e o n a r d os p e c t r u m 和p r e c i s i o nr t l 等 另外 f p g a c p l d 厂商的集成开发环境也 自带综合工具 图1 2 完整的f p g a c p l d 设计流程 4 综合后仿真 综合完成后需要做综合后仿真 检查综合结果是否与原设计一致 在仿真时 把综合生成的标 准延时文件反标注到综合仿真模型中去 可估计门延时带来的影响 综合后仿真虽然比功能仿真精 确一些 但是只能估计门延时 不能估计线延时 仿真结果与布线后的实际情况还有一定的差距 并不十分准确 这种仿真的主要目的在于检查综合器的综合结果是否与设计输入一致 5 实现与布局布线 综合结果的本质是一些由与 或 非门 触发器 r a m 等基本逻辑单元组成的逻辑网表 它 与芯片实际的配置情况还有较大差距 此时应该使用f p g a c p l d 厂商提供的软件工具 根据所选 芯片的型号 将综合输出的逻辑网表适配到具体f p g a c p l d 器件上 这个过程就叫做实现过程 因为只有器件开发商最了解器件的内部结果 所以实现步骤必须选用器件开发商提供的工具 在实 现过程中最主要的过程是布局布线 p a r p l a c ea n dr o u t e 所谓布局 是将逻辑网表中的硬件原 语或者底层单元合理地适配到f p g a 内部的固有硬件结构上 布局的优劣对于设计的最终设计结果 在速度和面积两个方面 影响很大 所谓布线 是指根据布局的拓扑结果 利用f p g a 内部的各 种连线资源 合理正确连接各个元件的过程 f p g a 的结构相对复杂 为了获得更好的实现结果 特别是保证能够更好的实现结果 特别是 保证能够满足设计的时序条件 一般采用时序驱动的引擎进行布局布线 所以对于不同的设计输入 东南大学硕士学位论文 特别是不同的时序约束 获得的布局布线结果一般有较大差异 6 时序仿真与验证 将布局布线的时延信息反标注到设计网表中 所进行的仿真就叫时序仿真或布局布线后仿真 简称为后仿真 布局布线之后生成的仿真时延文件包含的时延信息最全 不仅包含门延时 还包含 实际布线延时 所以布线后仿真最准确 能较好地反映芯片的实际工作情况 一般来说 布线后仿 真步骤必须进行 通过布局布线后仿真能检查设计时序与f p g a 实际运行情况是否一致 确保设计 的可靠性和稳定性 布局布线后仿真的主要目的是在于发现时序违规 t i m i n gv i o l a t i o n 即不满足 时序约束条件或者器件固有时序规则 建立时间 保持时间等 的情况 在功能仿真中介绍的仿真 工具一般都支持布局布线后仿真功能 有时为了保证设计的可靠性 在时序仿真后还要做一些验证 验证的手段比较丰富 可以用 q u a r t u s l l 内嵌时序分析工具完成静态时序分析 s t a s t a t i ct i m i n ga n a l y z e r 也可以用q u a r t u s l i 内嵌的c h i pe d i t o r 分析芯片内部的连接与配置情况 7 调试与加载配置 设计开发的最后步骤就是在线调试或者将生成的配置文件写入芯片中进行调试 示波器和逻辑 分析仪是逻辑设计的主要调试工具 任何仿真或验证步骤出现问题 都需要根据错误的定位返回到相应的步骤 更改或者重新设计 1 3 课题的主要内容和工作 一个高速的数字信号处理系统 需要有输入输出单元和数据的分析部分 从而还应该选择一个 合适的处理器 有存储模块以及丰富的通讯接i 1 模块 嵌入式微处理器的优势在于将微处理器内核 与丰富多样的外围接口设备紧密结合 在提供强大的运算 控制功能的同时 降低了系统成本和功 耗 因而适合作为数字系统的控制核心 f p g a 的优势在于高速 逻辑资源丰富以及逻辑功能用户 可灵活配置 适用于专用算法和逻辑接口功能多种多样 灵活可变的场合 将核心算法放于f p g a 中 使其与嵌入式微处理器相结合 共置于同一线路板上来完成具体操 作 形成优势互补 在执行复杂运算时 将算法映射到f p g a 上 执行完成后 再从f p g a 读取结 果以供程序使用 同时通过f p g a 还可以灵活地扩充各种数字 模拟通讯接口 本文选择了s e p 3 2 0 3 微处理器 以及a l t c r a 公司的c y c l o n e l l 系列f p g a 设计了一个多接口 多用途的f f t 处理应用系统 在此平台上实现了多种不同结构的高精度f f t 算法 论文的工作主要分为三大部分 l 系统硬件部分 根据系统功能要求的分析 结合s e p 3 2 0 3 微处理器的特点 提出了基于 s e p 3 2 0 3 微处理器的f f r 系统硬件架构 并实现硬件平台搭建 2 根据f f i 系统功能要求 在f p g a 中完成功能模块划分 实现了控制部分的各模块设计 如与s e p 3 2 0 3 微处理器的接口信号处理 对外围接口电路的控制等 充分理解f f t 算法的原理和结 构 在f p g a 中实现多种结构的f f r 算法 并从速度 面积 设计复杂性等角度比较它们的性能 3 将通过仿真的代码综合后烧录到f p g a 中 进行板级验证 并分析运算结果的正确性以及 精确性 1 4 论文结构 本文一共分为六章 第一章 绪论 简要地阐述了该课题的背景和意义 概括了论文的主要工作和结构 第二章 介绍了f f r 算法的原理 主要推导了结构规整 控制简单 易于用f p g a 实现的基 2 基4 算法 为硬件实现算法提供良好的理论基础 第三章 基于s e p 3 2 0 3 微处理器的f f t 系统硬件平台的具体实现 首先根据系统的功能要求 选择合适的器件 完成系统的硬件电路设计 包括微处理器 f p g a 存储模块 输 入输出模块 数据传输接口模块以及f p g a 外围电路 第四章 f f t 模块在f p g a 内的实现 根据f p g a 的设计流程 首先在f p g a 内对f f t 模块进 行了功能划分 主要包括控制单元和f f t 算法模块 然后针对具体的设计方案 对各 个模块进行分别设计 通过仿真验证 井进行了综合 布局布线和下载 4 第一章绪论 第五章 f f t 模块的测试与验证 对通过仿真的代码进行板级测试与验证 并对结果进行分析 确保f f t 运算的正确性和精确性 第六章 总结和展望 提出后续工作以及对系统进一步优化的设想 东南大学硕士学位论文 第二章f f t 算法的原理 离散傅立叶变换 d i s c 瞅ef o u r i e rt r a n s f o r m d v r 是信号分析与处理中的一种重要变换 而 且d f f 有多种快速算法 统称为快速傅立叶变换 f a s tf o u r i e rt r a n s f o r m f f t 这些算法可以使 d f t 的运算效率提高l 2 个数量级 为各种信号的实时处理创造了良好的条件 大大推动了数字 信号处理技术的发展嘲 本章主要介络了d f t 的原理和其快速算法的推导过程 并讨论了f f t 算法 的特点 介绍了一些基本概念 为硬件实现提供良好的理论基础 2 1 离散傅立叶变换 离散傅立叶变换 d f t 开辟了频域离散化的道路 使数字信号处理也可以在频域上采用数字 运算方法进行 它可以作为一种数学工具来描述离散信号的时域表示与频域表示之间的关系 大大 增加了数字信号处理的灵活性 在理论上有重要意义 在各种数字信号处理中起着核心的作用 对 点序列x n d f t 变换的定义为 必一盘 x 七 乏 h 讳 k o l n 一1 熙 e 2 1 n 一 o 1 n 一 i x n 专 x 后 陌 n 0 l n l 2 2 j tk o 式2 l 称为正变换 式2 2 称为反变换 根据公式2 1 2 2 计算一个x 寿 需要将每 个x 口 乘以相应的纾铲 然后再相加 即共 需要n 次复数相乘和n 1 次复数相加 计算全部j 女 0 k n 1 共需要n 2 次复数乘法 和n n 1 1 次复数加法 实现一次复数乘法需要四次实数乘法和两次实数加法 实现一次复数加法 需要两次实数加法 因此直接计算全部的x 七 共需要4 n 2 次实数乘法和2 一1 次实数加法 当 很大时 其计算量是相当可观的 例如 若n 1 0 2 4 则需要1 0 4 8 5 7 6 次复数乘法 即4 1 9 4 3 0 4 次实数乘法 所需时间过长 难以 实时 实现 于是如何减少计算离散傅立叶变换的运算量 变得至关重要 j w c o o l e y 和j w t u k e y 于1 9 6 5 年在 计算数学 杂志上发表了 机器计算傅立叶级数的一 种算法 此论文最早提出了快速傅立叶变换算法理论 仔细研究d f t 运算可以发现 如果充分充分利用复函数矸 的下列特性 就可以改善d f t 的 运算效率 i 片 的共扼对称性 k 时 孵州卅 2 矽 的周期性 h f 呓州 3 咄的可约性 嘭 形 略 彬警 4 矽o l 肛 1 为了能利用降学的上述特性 必须将x 0 或 和 x 女 的排列次序按某些特定的规律重排 或者将j 1 或 和 x t 序列按一定规律分解成一些短序列进行运算 这样可减少复数乘法次数 提高计算d f t 的运算速度 如果算法是通过对 进行逐次分解 称为时间抽取 d e c i m a t i o ni n t i m e d i t f f t 算法 如果算法是通过对x t 进行逐次分解 称为频率抽取 d e c i m a t i o ni n f r e q u e n e e d i f f f t 算法 c o o l e y 和1 蚀e y 的著名论文将计算d f f 的运算量大大降低后 出现了更多的快速算法 大概 可以分为两类 一类是递归型算法 将一维的d z i 化为容易计算的二维或多维d f t 且这个过程 可以重复 其代表算法是c o o l e y t u k e y 算法 r a d e r b r e n n e r 算法和分裂基算法等 另一类是将d f t 转变为卷积 利用计算卷积的方法计算 其代表是w i n o g r a d 快速傅立叶变换算法 w f t a 和素因 子 p f a p r i m ef a c t o ra l g o r i t h m 相比较而言 w f t a 和p f a 在运算量上占优 用的乘法器比 6 第二章f f t 算法的原理 c o o l e y t u k e y 算法少 但控制复杂 控制单元较难实现 在硬件实现中 不仅仅需要考虑算法的运 算量 更重要的是算法的复杂性 规整性和模块化 控制简单 实现规整的算法在硬件系统实现中 要优于仅仅是在运算量上占优的算法 6 j 7 j 8 9 2 2 基2 的f f t 算法 2 2 1d i t 算法的推导 在2 一l 式中 令n 2 m 为正整数 我们可虬将x n 按奇 偶分成两组 即令n 2 r 及 n 2 r l 而 0 1 2 一1 于是 n 2 一l 2 一i 2 一i t r l 2 一l 彳 i x 2 r 孵 艺x 2 r 1 彤妒 m 艺 2 一 孵 x 2 r 1 w 苗2 r 0r 0r m例 一 旦 e 州2 e j 4 l n 令爿 x 2 r w f v o n 2 1 口 x 2 h 1 k o i 2 1 k o 1 j v 2 1 那么 x t 一 七 孵占 t 后 o l n 2 1 2 3 爿 i b 盘 都是n 2 点的d f r x k 是n 点d f r 因此单用2 3 式表示x i 并不完全 但因x 女 2 一 七 一阡譬b t k o l n 2 1 所以用a k b k 可完整地表示x j n 8 时 彳 t 口 i 及石 t 的关系如图2 1 所 示 a 钟 1 2 3 b 0 j b 1 b 2 j b 3 叼 一l 图2 1 d f t 的分解示意图 彳 女 占 仍是高复合数 n 2 的d f t 我们可按上述方法继续加以分解 分剐令r 2 l r 2 l l 而 o l 4 1 则彳 七 可表示为 r 4 ln 4 i 4 l v 4一i 爿 t j 4 f 嘴 z 4 2 嘴o 艺x 4 1 w 茄l 孵 x 4 1 2 彤n 4 i 0i o瑚i o 懈一 令c k 艺x 4 1 哟 k o 1 n 4 1 7 o 1 2 3 4 5 6 7 东南大学硕士学位论文 d 妁 工 郇 2 啼 k o l 4 一l i 0 那么a k c 女 噼 2 d k k o l n 4 一l 一 七十 c 七 一陟嚣 2 d 七 七 o 1 4 1 叶 z v 4 t 同理 令e t 工 4 1 阡磊 k o l 4 一l 0 n 4 1 f t 缸4 3 嘴 k o 1 4 1 m 则君 露 七 降嚣 2 f k k o l u 4 一l 占 i 手 e 七 一蹄譬 2 f 七 k o l n 4 1 若n 8 这时c d k e k 都是二点的d f t 无需再分 即 c o 工 0 j 4 e o 工 1 工 5 c 1 x o 一z 4 e 1 x o 一j 5 d o x 2 x 6 f 0 可3 十z 7 d 0 可2 一工 6 f 1 z 3 一x 7 若n 1 6 3 2 或2 的更高的幂 可按上述方法继续分下去 直到两点的d f t 为止 以上算法 是将时间n 按奇 偶分开 故称时间抽取算法 上述过程如图2 2 所示 2 2 2d i f 算法的推导 图2 28 点f f r 时问抽取算法信号流图 x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 和d i t 相对应 d i f 算法是将频域x t 的序号t 按奇偶分开 对2 一l 式的d f t 先将j 月 按 序号分成上下两部分 得 2 一ln i 工 七 艺z 时 x 一 时 卸n 2 s 咿嘭刁 w 珈 m 昨咖 芝日 第二章f f t 算法的原理 x n 时 x n n 2 w 式中阡铲 i 分别令t 2 r k 2 r l 而 o 1 n 2 1 于是得 聊 芝1 m 州一 要 m 2 j j 2 r 1 x n 一x n 詈 f w r o l n 2 一l 令g n x h x n n 2 n x 一x n n 2 蝶 2 一i 2 d 则x 2 力 艺g p 而 x 2 r 1 口 这样 就将一个 点d f t 分成了两个n 2 点的d f r 分的办法是将x k 按序号k 的奇偶分 开 仿照时间抽取的办法继续分下去 直到得到两点的d f t 图2 3 给出了一个8 点d i f 算法流图 可以和d i t 的算法相比较 由该图可以看出 输入是正序 输出是按奇偶分开的倒序 x o x t x 2 x 6 x o x s x 3 x 7 图2 3s 点f f t 频率抽取算法信号流图 不论是d i t 算法还是d i f 算法 都可以看作是将n x n 的w 矩阵傲分解来实现的 2 2 3 算法的讨论 级 的概念 将n 点d f t 先分成两个n 2 点d f t 再是四个n 4 点d f t 进而八个n 8 点d f t 直至n 2 个两点d f t 每分一次 称为一 级 运算 因为m l o g n 所以n 点d f t 可分成m 级 图 2 2 中 n 8 因此m 3 从左至右 依次为m 0 级 m l 级 m 2 级 组 的概念 由图2 2 可以看出 每一级的n 2 个蝶形单元可以分成若干组 每一组有着相同的结构及 园 子分布 如m 0 级分成了两组 m m i 级分成了一组 因此 第m 级的组数是 2 1 m 0 l 肼一l 螺形单元 在图2 2 和图2 3 中有大量如图2 4 的运算结构 由于该运算结构的几何形状像蝴蝶 故称 蝶 形运算单元 左边为d i t 算法的蝶形单元 右边为d i f 算法的蝶形单元 9 州 州 埘 州 州 啪 州 州 东南大学硕士学位论文 k p g k p k g 图2 4 第m 级蝶形单元 左图为d i t 算法 右圈为d i f 算法 d i t 算法中 在第m 级t 有靠 i p p 蝶k g g 靠 p 一暇z g d i f 算法中 在第i n 级 有 l p p k g l g k p 一 g 暇 p q 是参与本蟆形单元运算的上 下节点的序号 很明显 第m 级序号为mq 的两点只参与 这一个蝶形单元的运算 其输出在第m 1 级 且这一蝶形单元也不再涉及别的点 由于这一特点 在计算机编程时 我们可将蝶形单元的输出仍放在输入数组中 故称为 同址运算 由于每一级都含有n 2 个蝶形单元 每一个蝶形单元又只需要一次复数乘 两次复数加 因此 完成m l o g n 级共需要的复数乘法数肘 和复数加法数m 分别是 m e 型 l o g n m n 2 m l a n 1 0 9n 让每一级的数据自上而下都按自然顺序排列 那么在第m 级 上 下节点p q 之间的距离为 p q 2 矽 因子的分布 如图2 2 和2 3 所示 在n 点f f t 运算流图中 每级都有n 2 个蝶形 每个蝶形都要乘以因子 称其为旋转因子 r 称为旋转因子的指数 但各级的旋转因子和循环方式都有所不同 为了便 于硬件实现 应先找出旋转因子 与运算级数的关系 仔细观察推导公式和图2 2 2 3 可以得 出每一级 因子分布的规律如下 m 0 级 孵 r 0 m l 级 町 r 0 l m 2 级 町 r 0 l 2 3 m m l 级 矽 r 0 l n 2 一l 因此 不难总结出形 因子分布的一般规律 第m 级 f r 0 l 2 l 码位倒置 由图2 2 可以看出 变换后的输出序列x t 依照正序排列 但输入序列j n 的次序不再是原 来的自然顺序 这正是由于将x 按奇 偶分开所产生的 对n 8 其自然序号是0 1 2 3 4 5 6 7 第一次按奇偶分开 得到两组n 2 点d f t j h 的序号是 0 t2 4 6 1 l 3 5 7 对每一组再按奇偶分开 这时应将每一组仍按自然顺序排列 故抽取后得四组 每组得序号是 0 42 6 ii 5 i3 7 这一顺序正是图中输入端序列x 行 的排列次序 掌握这一规律 对n 为2 的更高次幂 我们 都可得到正确的抽取次序 如果将x n 的序号n 0 l n l 写成二进制 以n 8 为例 x o x 7 对应为 x o o o x o o d x o l o rx 0 1 1 x 1 0 0 x 1 0 1 x 1 1 0 x t 1 1 l o 第二章f f r 算法的原理 将二进制数码翻转 得 x o o o x o o o x 0 1 0 1 1 0 x 0 0 1 1 0 1 o l l 如 1 1 1 它们对应得十进制序号分别是 x 0 x 4 x 2 x 6 x o x 5 x 3 x 7 这也正是按奇偶抽取所得到的宇列 掌握了这一规律 我们就可以正确编程 取相应地址的数 据进行处理 在全部运算完成后 也可以按照相同的规律将数据按顺序取出 算法结构变形 将基2 f f q 算法的结构进行变形 可以得到固定几何结构的基2 f f t 算法 8 点的d i f 结构如 图2 5 所示 变形后 每级的结构固定 容易扩展 而且每个螓形运算单元的第一个操作数都在r a m 的上 部分 第二个操作数在下部分 因此 可以将r a m 分成上下2 块 这样可以同时读取2 个操作数 不过这种结构的运算结果存储地址与操作数的地址不一致 因此需要增加一倍的r a m 用来存储结 果 另外 一个蝶形的两个运算结果需要存放在同一块r a m 中 必须花费两个时钟周期 不过可 以通过合理的读数据顺序来实现流水线操作 来缩短运算时间 i 0 图2 5 固定几何结构的8 点d i f 基2 f f t 2 3 基4 的f f t 算法 令n 4 对n 点d f f 可按如下方法作频率抽取 4 in 2 川3 n 4 1 n i x t 艺z 嘭 z 一 略 x 吲 x n 略 分别令七 4 r 七 4 r 2 k 4 r l 及k 4 r 3 而 0 1 4 1 有 洲 瓠似小砌 钟 料等冲 刳k 州m 瓠似卅咖掣nh 井等h 期p 4 倍s 州川 熟似州n 计小c 井等 x n 3 了n 计棚n n r 删川 篙1 除c 沪m 纠 小c 井警 1 c 州等 p c o 4 2 6 1 5 3 r l 2 3 r i x i i x i i 东南大学硕士学位论文 表示x 女 之后可以按照基2 的结构 将x 4 r x 4 r 1 x 4 r 2 一x 4 r 3 继续分成 n 1 6 点的d f t 直至分成若干组4 点的d f t 若n 1 6 通过上述推导即可把一个1 6 点的d f t 分成分为m 0 m i 两级 每级有4 个4 点d f r 运算 具体的蝶形运算单元如图2 6 所示 其信号流程如图2 7 所示 基4 算法使f f t 的级 数减少了一半 且每级的蝶形单元的个数也降低了一半 因此总共需要运算的蝶形个数大大降低了 图2 61 6 点基4 频率抽取f f l 算法信号流程 d a t al 图2 7 基4 频率抽取蝶形运算结构 1 2 a b c d 第三章基于s e p 3 2 0 3 微处理器的f f t 系统硬件实现 第三章基于s e p 3 2 0 3 微处理器的f f t 系统硬件实现 嵌入式系统必须面向应用 对功能 可靠性 成本 功耗等有着严格的要求 可以根据实际的 应用进行软 硬件的添加和删除 并且不影响其他模块的正常运行 在设计应用系统之前 首先要 考虑系统的应用领域 明确系统功能需求 提出相应的系统设计方案 然后设计实现系统硬件 最 后通过测试来判断设计是否满足要求 3 1 系统硬件功能分析 高速 实时的f f r 处理系统 需要有快速的数据处理 分析部分 丰富的数据传输接1 7 1 以及 存储数据和程序的存储单元 根据这些要求 将系统的硬件划分为相应的几个模块 数据处理份析模块 数据处理分析模块使用嵌入式微处理器 它的优势在于指令吞吐量大 而且它将微处理器内核 与丰富多样的外围接1 3 设备紧密结合 在提供强大的运算 控制功能的同时 降低了系统成本和功 耗 另外 嵌入式微处理器一般都有相应的嵌入式操作系统支持 可以满足应用软件平台的需求 因而适合作为数字系统的控制核心 但是通过软件在微处理器上实现f f t 算法 速度比较慢 难以满足快速 实时系统的要求 可 以将f p g a 与嵌入式微处理器相结合 f f t 运算由f p g a 来实现 处理器将运算的数据输入到f p g a 中 在完成f f t 运算后 再从f p g a 读取结果进行后续处理 嵌入式处理器和f p g a