（电力电子与电力传动专业论文）基于fpga的高性能32位浮点fft+ip核的开发.pdf

t h ed e v e l o p m e n to fa3 2 b l tf l o a t i n g p o l n t f f ti pc o r eb a s e do nf p g a a b s t r a c t a st h eb a s i co p e r a t i o n so ft h et r a n s f o r mb e t w e e nt i m ef i e l da n df r e q u e n c yf i e l d ，f f th a s b e e nw i d e l yu s e di ns u c hf i e l d sa sd e t e c t i o n ，c o m m u n i c a t i o n , i m a g ep r o c e s s i n g ，m u l t i m e d i a e t c t h er e s e a r c ho ft h ei m p l e m e n t a t i o no ft h ef l o a t i n g - p o i n tf f ta l g o r i t h m so nf p g ai s b e c o m i n gt h en e w r e s e a r c hh o ts p o t s ，w h i c hh a sb e e np a i dh i 曲a t t e n t i o nt o i nt h et h e s i s ，o nt h eb a s i so ft h ea n a l y s i so ft h em a i nk i n d so ff f ta l g o r i t h m sa n d h a r d w a r ea r c h i t e c t u r e sw h i c hc a nb eu s e dt o i m p l e m e n t f f t p r o c e s s o r ，t h e d e c i m a t i o n i n - t i m er a d i x 一2a l g o r i t h mi sc h o s e na st h et a r g e ta l g o r i t h m a n dt h ea r c h i t e c t u r eo f s i n g l e b u t t e r f l y - s e q u e n t i a l p r o c e s s i n gi su t i l i z e dt oi m p l e m e n tt h ed e s i g ni nd e t a i l t h e nt h e d e s c r i p t i o no ft h ed e s i g no ft h eh a r d w a r ea r c h i t e c t u r eo ft h ef l o a t i n g - p o i n tm u l t i p l i e ra n dt h e f l o a t i n g - p o i n t a d d e ri sm a d e ，i nw h i c hs e v e r a ln o v e lt e c h n i q u e sa r e a d o p t e d s u c h 鹤 h i g h - s p e e df i x i n g - p o i n tm u l t i p l i e r , f a s tl e a d i n g 0 一d e t e c t o r - l o g i ca n dp i p e l i n ee t c b a s e do n t h i s ，t h ed e s i g no ft h ew h o l ea r c h i t e c t u r eo ft h ef f ti sd e t a i l e d , i nw h i c ht h em o d i f i e d b u t t e r f l y u n i t ，m e m o r yu n i t ，a d d r e s sg e n e r a t i o nu n i te t ca r ei n c l u d e d ah a r d w a r et e s ta n da n a l y s i sa r ep e r f o r m e do nt h ef p g ah a r d w a r et e s tp l a t f o r m t h e t e s ts h o w st h a tb o t ht h eo p e r a t i o np r e c i s i o na n ds p e e da r eh i g h ，a n dt h es y s t e mc a ns t e a d i l y r a na tt h ef r e q u e n c yo f5 0 m h z ，a n dt h ep r o c e s s o rc a nf i n i s ht h ef f to p e r a t i o no faf r a m eo f 2 5 6 - p o i n tf l o a t i n g - p o i n tc o m p l e xd a t aw i t h i n81 9 2 “s i ts h o w sa na d v a n t a g et ot h e u n i v e r s a ld s pa n dm c i ， k e y w o r d s ：f f t f p g a ；f l o a t i n g p o i n ta d d e r ；f l o a t i n g - p o i n tm u l t i p l i e r ；p i p e l i n e 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相关知识产权 属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容。除己注明 部分外，论文中不包含其他人已经发表过的研究成果，也不包含本人为获得其它学位而使h j 过的内 容。对本文的研究工作提供过重要帮助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名： 软沟却 加磐7 月z 日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 幺即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者竽名：弓氏沟葡导师虢 7 月e l 广西大学硕士掌位论文基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 第一章绪论 1 1 课题的研究背景、目的及意义 在现代化建设过程中，数字信号处理( d i g i t a ls i g n a lp r o c e s s i n g ，d s p ) 技术极大地 推动了很多领域的发展。而在d s p 技术中，作为时域和频域转换的基本工具，快速傅 立叶变换( f a s tf o u r i e rt r a n s f o r m ，f f t ) 正在谐波检测、实时图像处理、数字通信、语 音识别、匹配滤波等应用上发挥着巨大的作用。在不同的领域中，随着功能的不同，对 f f t 实现的要求也存在着差别：在速度上，低端应用和高端应用存在着每秒万次至每秒 亿次的不同；在精度上，定点、块浮点和浮点运算可满足不同的需求，其中又以浮点运 算实现的精度最高，可胜任各种应用场合对精度的需求。因此，使用浮点f f t 运算，配 合以高速、低成本的电路实现，可全面提升系统性能。 二十世纪7 0 年代以来，微电子技术及其制造工艺取得了蓬勃的发展。特别是进入 9 0 年代后，随着超大规模集成电路的飞速发展，s o c ( s y s t e mo nc h i p ，片上系统) 和 i p ( i n t e l l i g e n tp r o p e r t y ，知识产权核) 技术的异军突起，电子设计自动化( e d a ) 已成 为电子设计领域的标准设计方法。属于可编程逻辑器件的f p g a ( f i e l dp r o g r a m m a b l e g a t e a r r a y ，现场可编程门阵列) 技术就是在这样的背景下发展起来的。f p g a 因其越来 越高的集成度、越来越低的成本、设计手段灵活方便、可配置m 丰富、容易实现流水 线结构、设计周期短以及软硬件升级方便等优点，已得到越来越广泛的应用，并在多个 行业中发挥着重要作用。 如今，学界对f f t 运算软、硬件实现的研究正在积极的进行，并取得了众多突出的 成果，各种方法都有其优势所在。而如何在保证系统对高速度、低成本的要求下，实现 高精度的f f t 运算，已经成为各研发机构的研究重点。如前所述，f p g a 因其在e d a 领域的众多优势，正在渐渐替代专用处理器和d s p 器件而成为数字信号处理硬件实现 的新方法。那么，如何使用f p g a 完成浮点f f t 运算，就成为眼下亟待解决的热点问题。 本论文就是在这样一个背景下提出，旨在设计出适合f p g a 实现的、具有高速高精 度特点的、可实现浮点f f t 运算的i p 核，以期望打破国际市场对国内的垄断，填补我 国i p 库之空白。 1 2 f f t 实现方法的研究现状 到目前为止，f f t 算法的理论研究已趋于成熟。随着社会发展，在通讯、实时图像 处理、检测等领域，对快速、高精度f f t 运算的需求已越来越迫切。随着微电子技术的 高速发展，开发手段的不断优化升级，已不断有科研单位和个人着手研究f f t 的实现方 基于f p g a 的高性能3 2 位浮点f f ti p 核的开裳 法，并取得了显著成就，以下将简单介绍主要的实现方式，并与f p g a 实现进行对比。 1 2 1f f t 算法的实现方法 在研究历史上，f f t 实现方法共经历了以下几个发展阶段l l j ： ( 1 ) 在通用计算机( 如p c 机) 上，用软件( 如c 语言) 实现。 ( 2 ) 单片机实现。 ( 3 ) 专用f f t 处理器，这种实现方法的出现归功于电子及芯片设计技术的飞速发展。 典型器件包括：a 4 1 1 0 2 、p d s p l 6 5 1 0 1 6 5 1 5 、t m c 2 3 1 0 等( 具体参数见参考文献【5 1 】) 。 ( 4 ) 通用可编程数字信号处理器( d s p ) 实现。相对于单片机而言，d s p 器件具有 更加适合于数字信号处理实现的软硬件资源，已广泛应用于通信、语音图像图形处理、 仪器仪表、自动控制、医疗仪器、民用电器、雷达导航与导弹制导等诸多领域。 目前国际上使用较多的d s p 芯片实现1 0 2 4 点1 6 位字长，定点、块浮点或浮点运 算的f f t ，其处理速度达到几十和数百弘s 量级。其中采用t i 公司的t m s 3 2 0 c 6 2 x 系列 d s p 达到6 6 9 s 处理速度，t m s 3 2 0 c 6 4 x 系列d s p 达到1 0 1 1 s 量级，t m s 3 2 0 c 6 7 x 处理 1 0 2 4 点基2 算法的f f t 需时1 2 4 3 9 s 弛j 。 ( 5 ) f p g a 实现。该方法因其具有通用性、可实现算法的并行运算等特点，既可作 为独立的数字信号处理器，亦可作为d s p 芯片的协处理器。 当今国际上，以f p g a 芯片生产厂商为主的公司在基于f p g a 实现f f t 的研究方 面处于绝对领先的地位。例如x i l i n x 公司推出了1 4 0 m h z 时钟频率下，处理速度达到1 岬 的1 0 2 4 点f f t 处理i p 核，采用8 0 0 万门的v i r t e xi i 器件实现；a l t e r a 公司在2 0 0 5 年 推出的f f ti p 核全面支持其最新器件，此口核计算1 6 位1 0 2 4 点定点f f t 仅需6 6 3 9 s u j 。 虽然这些公司的i p 核可最大程度的发挥芯片的性能，但由于其价格昂贵( a k e m 公司的 f f ti p 核售价为7 9 9 5 美元) 、往往只具备定点运算功能以及无法按照系统的实际需求进 行改进等缺点，使其还难以在我国基层应用领域普及。 我国f p g a 技术起步较晚，但进入2 1 世纪后，发展势头迅猛。目前，许多大学和 研究所都在积极研发具有自主知识产权的f f t 模块，包括定点、块浮点以及浮点。但由 于技术基础薄弱，所设计的f f t 处理器无论在速度、精度还是系统可扩展度上都与国外 产品有一定差距。因此，如何使用f p g a 设计出满足高速、高精度、高可靠性要求的 f f ti p 核，已成为现今我国数字信号处理硬件实现的研究热点，并已取得一定成绩。 1 2 2 各种实现方法对比 ( 1 ) 通用计算机实现，缺点是速度较慢、且不便于系统的独立运行，工程应用受到 较大限制，因此一般应用于d s p 算法的模拟仿真。 ( 2 ) 单片机实现，由于单片机大多采用冯诺伊曼结构，所以单片机在点数大、需要 高精度及实时处理的系统中，很难发挥作用，其只适合在系统对实时性要求不高的情况 2 广西大学硕士学位论文 基于f v g a 的高性能3 2 位浮点f f ti p 核的开发 下实现简单的d s p 算法。 ( 3 ) 专用f f t 处理器实现，即a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ，专用集 成电路) 实现。由于在这种芯片的设计过程中，设计人员可以针对算法和电路的特性， 对整个系统进行最大程度的优化，从而使其具有最佳的性能。如：高速、高精度、低功 耗。但迄今为止这种器件大都只能完成定点、块浮点的运算。虽然已有浮点f f t 处理器 推出，但由于其昂贵的价格、所用算法、数据宽度、计算点数等相对固定，难以更改， 且当系统对性能、速度等提出更高要求时，就需要通过增加外围电路，甚至重新设计印 刷电路板来完成设计，从而决定了高性能是通过牺牲面积、提高成本等因素换取的。 ( 4 ) d s p 器件实现，其优点是处理速度快、灵活性强、适用于多种复杂的d s p 算法， 缺点是硬件电路复杂、功耗大，并且在运行速度和精度方面存在矛盾。 ( 5 ) f p g a 实现的发展和优势所在： 现今，利用可编程逻辑器件来进行系统集成设计是一种很普遍的现象，但利用f p g a 实现d s p 算法却是最近提出的一种方案。它主要是针对以前出现的一系列d s p 或a s i c 实现方案而提出的。 若在f p g a 中实现数字信号处理功能，则在处理速度上有可能超过通用的d s p 器 件，而且具有高度灵活和快速上市的特点。同时由于当前f p g a 的集成度已达到上千万 门，因此在高性能数字信号处理中已越来越多地采用f p g a 。 用f p g a 来实现d s p 算法( 如f f t 算法) 主要有以下几点优势： ( 1 ) f p g a 可以进行并行运算，比通用d s p 处理器性能更高。因此f p g a 非常适合 于重复型的d s p 任务，包括含有重复乘加运算的数字信号处理算法。如x i l i n x 的2 0 0 万门f p g a 产品v i r t e x e 系列每秒可以进行2 7 0 亿次累加运算，而目前最快的d s p 处理器也只能达到每秒1 6 亿次运算，大大低于f p g a 产品【4 j 。 ( 2 ) 相对通用处理器和d s p 处理器而言，f p g a 可以由设计者根据算法的内在结构 设计合适的处理阵列，避免前者串行执行指令的低效。 ( 3 ) 相对a s i c 而言，采用f p g a 可避免初期巨大的开发投资，同时拥有微处理器 的通用性和灵活性。在算法修改时，短时间内就可将新的算法付诸实际。当然由于f p g a 仍然属于通用器件，效率要比a s i c 低，但其灵活性的优势仍然可以在很大程度上弥补 其缺点【5 1 。 综上所述，利用f p g a 完成d s p 算法是一种方便、快捷、最具优势的设计方案。 近年来，国外利用f p g a 已经实现了许多d s p 算法，其中以定点和块浮点f f t 的 成果最为显著，它们已经被应用到许多实际问题中，如医用超声波图像相位补偿系统， 人工神经网络等【5 】【6 】【7 1 。目前，国内的集成电路设计水平还比较低，对于复杂的逻辑设 计仍然缺乏经验。为改变现状，赶上国际先进水平，国家投资1 0 0 亿元启动了9 0 9 系统 工程，设立了4 个重点工作实验室作为开发集成设计的实验基地【8 】，已取得了令人瞩目 的成就。但就目前的水平，利用f p g a 开发d s p 算法特别如浮点f f t 、d c t 、小波变 基于f p g a 的高性能3 2 位浮点f f ti p 核的a f - - 戈 换等，在国内仍属弱项。1 9 9 9 年1 月，复旦大学a s i c 国家重点实验室研制出了一种采 用f p g a 实现f i r 滤波器的方法，它从改良乘、加结构入手，利用b o o t h 编码实现了高 阶数的f i r 滤波器，而这是利用国外的乘法器无法实现t 9 1 。 1 3 课题研究内容与论文组织结构安排 f f t 算法可采用定点、块浮点和浮点这三种不同的数据结构进行实现。其中，定点 运算速度快、硬件消耗小( 成本低) ，但精度差；浮点运算速度较慢、硬件开销大，但 可实现高精度；块浮点运算居于两者之间。随着器件集成规模的不断加大，对设计方法 的不断优化，浮点运算的缺陷已越来越不明显。为满足高精度场合的需要，本文提出了 一种基于f p g a 的高速高精度浮点f f t 专用处理器i p 核的设计，各章的内容安排如下： 第二章分析了f f t 的算法，并从算法的复杂性和模块性等方面进行了对比。随后列 举了4 种硬件实现结构，并结合设计特点和目标确定所选用的算法与硬件结构。介绍了 流水线技术。 第三章详细介绍了该i p 核的重要模块浮点运算部件的设计。包括数据格式、 运算原理分析、定点加法器和乘法器的设计、电路结构以及结果验证等内容，并说明了 设计的优势所在。 第四章详细介绍了浮点f f t 处理器的设计。采用f p g a 实现设计，分析了系统性能， 证明了在保证正确性的前提下，系统具有高速高精度等优点。 第五章介绍了设计过程中采用的验证方法、流程、所用软件及技巧，并分析了验证 结果，从而证明了设计目标的实现。 第六章是整个课题研究阶段的回顾以及对该研究方向的展望。 其中，3 、4 、5 章是论文的核心内容，做了重点阐述。 1 4 本章小结 本章简要的回顾了微电子技术和f f t 实现技术的发展史，以及f f t 算法在各个领 域的应用和重要性。虽然在运算速度和精度上，相对于专用d s p 器件而言，f p g a 还是 有一定差距，但由于其编程简单、开发快捷、更改灵活以及成本低廉等特点，使其运用 范围迅速地扩大，有进一步取代a s i c 的趋势【l o 】，用户可以在一定程度上使用f p g a 来 代替各种d s p 器件，从而使设计更加有效和紧凑。 f f t 是d s p 领域中最基本，也是最重要的理论之一。因此，研究用f p g a 实现f f t 是为在数字信号处理领域中应用f p g a 技术奠定基础。其重大意义在于，设计人员可以 用成本低廉的超大规模集成电路来设计灵活多用的专用芯片，而不受传统a s i c 设计的 风险制约。我们相信，随着可编程逻辑器件在d s p 领域中广泛的应用，d s p 应用技术 必将产生一个质的飞跃。 4 广西大掌硕士学位论文基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 第二章设计原理、方案与方法 本章回顾了f f t 运算的发展历程和几种重要的算法，包括c o o l e y t u k e y 算法、分 裂基算法和素因子算法等。在详细分析了算法的复杂性、运算量以及是否易于f p g a 实 现后，设计了该f f ti p 核的硬件结构。同时，本章简单介绍了设计过程中所使用的流 水线技术。 2 1 f f t 算法的重要性 通过第一章的介绍我们知道，f f t 是时域和频域转换的基本运算，人们也早已知道 频域分析常常比时域分析更优越，不仅简单，而且易于分析复杂信号。通过总结，我们 知道用硬件实现f f t 具有如下的优点和重要性： ( 1 ) f f t 在数字信号处理领域有着极为广泛的应用，部分应用更有高速实时运算的要 求。 ( 2 ) 使用f f t 专用硬件，可以使成本降低，速度大幅度提高，例如6 0 年代末，国外 制作的一部f f t 处理专用机，这种系统每小时计算所需费用比一台大型通用机少5 倍， 而计算速度快2 0 倍【l l 】。 ( 4 ) f f t 作为数字信号处理的关键技术之一，具有极为广泛的应用。但是国外高性能 的f f t 实现技术对中国限制出口。自主研发这一技术，不仅具有很高的经济效益，还将 在国家安全等方面发挥巨大的社会效益【1 1 1 。 2 2f f t 的数学原理与运算方法 。离散傅立叶变换( d i s c r e t ef o u r i e rt r a n s f o r m ，d f t ) 是频域离散化的重要工具，它 使得在频域上可以用数字运算方法进行数字信号处理。下面简单介绍d f t 、f f t 的发展 历程和运算方法。 2 2 1 离散傅立叶变换( d f t ) 原理 离散傅立叶变换描述分析有限长序列，其本质是建立了以时间为自变量的信号与 以频率为自变量的频谱函数之间的变换关系。也就是说，d f t 定义了时域与频域之间的 映射关系。对于d f t ，时间和频率变量都是离散值。下面讨论有限长序列的离散傅立叶 变换。 对于长度为的有限长序列石( 刀) ，只在n = o 至j j ( n - 1 ) 个点上为非零值，其余都是零值。 因此，我们可以把它看成是周期为的周期序列x ( 行) 中的一个周期，从而有限长序列的 5 广西大学硕士掌位论文基于f p g a 的商性能3 2 位浮点f f ti p 核的开发 傅立叶变换为： 正变换 x ( j ) ：d f t x ( 甩) 】_ 艺w n k x ( ，2 ) ， 后：o ，1 ，一1 ( 2 。1 ) n = o 反变换 x ( 刀) = i d f t x ( 后) 】= 万1 刍n - i x ( 尼) w ， 刀2 。，1 ，一1 ( 2 2 ) 其中，w = e x p ( 一j 2 r m k n ) ，r k = o ，1 ，n 一1 。w 为d f t 的旋转因子。 由( 2 1 ) 式可以看出，在 x ( ，z ) ) 为复数序列的情况下，直接计算点的d f t 需要进行 ( n - 1 ) 2 次复乘和朋，_ 1 ) 次复加。由此可见，d f t 的运算量与2 成正比，当较大时( 如 本课题中的2 5 6 点) ，n 点的d f t 运算量将非常大，严重妨碍了d f t 在生产实践中的应 用。因此，如何解决d f t 的快速运算成为了将d f t 运用到实践中所需解决的首要问题。 2 2 2 快速傅立叶变换( f f t ) 原理 d f t 因其运算过于复杂而在实际应用中受阻后，人们开始研究d f t 的快速算法。 而直到1 9 6 3 年，c o o l y 根据t u k e y 的想法编写了第一个f f t 算法程序后，这种情况才 得以改变。在f f t 算法中，t u k e y 主要利用了旋转因子的周期性和对称性，使d f t 运 算中的某些项得以合并，从而使运算分解成更少点数的d f t 运算，有效减少了运算量。 随后，于1 9 6 5 年，c o o l e y 和t u k e y 在计算数学( m a t h e m a t i c so f c o m p u t a t i o n ) 杂志 上发表了著名的“机器计算傅里叶级数的一种算法”( a na l g o r i t h mf o rt h em a c h i n e c o m p u t a t i o no fc o m p l e xf o u r i e rs e r i e s m a t h e m a t i c so fc o m p u t a t i o n ) 的文章【l ，引 起了人们的广泛注意。在这篇文章中，f f t 算法的运算量从正比于妒减少为正比 于m o g n , 运算量减少了l 2 个数量级，从理论上解决了d f t 计算运算量过大的问题， 为数字信号处理技术走向实际应用做出了巨大贡献。 随后，人们对c o o l e y t u k e y 算法也提出了一些改进，从而很快发展和完善成一整套 高效的运算方法，即现在普遍称之为快速傅立叶变换的算法。至此，d f t 的运算大为简 化。之后，又有许多学者提出了许多不同的算法以提高d f t 的运算速度，这其中包括 基4 f f t 算法【1 3 1 、分裂基算法【1 2 1 、主因子分解算法【1 6 1 、w i n o g r a d 卟n 算法【1 7 】等。这些 快速算法都利用了的周期性和对称性，通过将一个大点数的d f t 分解为若干小 点数的d f t 的组合来减少运算量。对于d f t 运算的快速算法的研究在8 0 年代中期已经 成熟，近年有关f f t 算法的文献已不多见，而大多集中在算法的实现上【1 8 j 【1 9 】【2 0 】。 2 2 3 按时间抽选基- 2 f f t 算法 f f t 的基本思想在于：利用旋转因子的固有特性，将原有的n 点序列分解成两个或 者更多的较短序列，这些短序列的d f t 可重新组合成原序列的d f t ，而总的运算量相 6 广西大掌硕士掌位嵌誓 基于f p g a 的高性能3 2 位浮点f f ri p 核的开发 比原算法则有很大减少，从而达到提高速度的目的。这种分解包括：按时间抽选算法 ( d i t ：d e c i m a t i o ni nt i m e ) ，即按时间序列x ( 胛) 分解；按频率抽选算法( d i f ：d e c i m a t i o n i nf r e q u e n c y ) ，即分解傅立叶变换序列坦助。本章分析使用较广的按时间抽选算法。 r l t 以上分解基于旋转因子诋的如下性质： 1 周期性 w n k = w ( n + n ) k = w “ ( 2 3 ) 2 共轭对称性 ( w ) o = w - n k ( 2 - 4 ) 3 可约性 w n k = w n k ，l 所mw n k = w 删n r a k ( 2 5 ) 对于长度n = 2 以的序y l j x ( n ) ，定义两个分别为 x ( 功) 的偶数项和奇数项的n 2 点序 列x t ( n ) 和耽) ，即： x l ) 鼍( 2 刀) ，耽0 ) 2 x ( 2 甩+ 1 ) n = 0 ，1 ，, n 2 - 1 ( 2 - 6 ) 于是，点d f t 可写成： ( 2 7 ) 利用系数荫的可约性，即w 2 ：w ，：，可以将( 2 7 ) 式写为： 2 - 1 n 1 2 1 x ( 七) = x i ( r ) w ：+ w ：r 恐驴) w 睹，2 = 五( 后) + w 江( 后) ( 2 - 8 ) r = or = o 此时，利用系数的周期性：w r k ，：= w ：；竺驯2 1 ，可以得到： 五( n 2 + k ) = 五( 七)五( n 2 + k ) = 五( 后)( 2 9 ) 再利用 m 的以下性质： ( n 2 + k ) n 1 2i女 w 2 w uw 2 一w 将( 2 9 ) 式、( 2 - 1 0 ) 式代入( 2 - 8 ) 式，可以将x 表达为两部分： 前部分 x ( 后) = 五( 七) + w z ( 后) k = - o ，1 ，州2 - 1 后部分 x ( | j + 2 ) = 五( 七+ 2 ) + w 筹+ 坨k ( k + n 2 ) 7 ( 2 - 1 0 ) ( 2 - 1 1 ) 腑w 、，吃 m 脚 + 睹w 、， x 脚 = 腑w 功攻 脚 = 、j x u h 但w d +r2x 一脚 + 捕w r2x 脚 = 砖 w p砭 一脚 七彬 + 睹 弋w xo 一脚 = 广西大掌硕士学位论文基于f p g a 的高性冀皂3 2 位浮点f f ri p 核的开发 = 墨( 七) 一w ( 后) 肛o ，l ，朋- 1 ( 2 1 2 ) 这样，只要求出0 到( n 2 1 ) 区间的所有五( 助和( 幼值，即可求出0 到( 人r - 1 ) 区间所有坦句 的值，从而大大缩小了运算量。 上述将点d f t 化为m 2 点d f t 的处理方法可以一直持续到运算单元为两点d f t 为止，即有如图2 1 的蝶形运算单元： 五 弼五w 区u # 弼( d 五( 七) + w 江( 七) 五( 后) 一w r 疋( 七) 图2 1 蝶形运算单元 f i g 2 1b u n c h yu n i t 综上所述，按时间抽选基一2 f f t 的基本原理就是将原有点的d f t 逐步分解，直 至对两点按照蝶形单元的规则进行d f t 运算，并最终合成点的d f t 。在此过程中， 复数乘法和复数加法的次数都大为减少，将在后文详细阐述。 2 2 4 按时间抽选基- 4 f f t 算法 对于长度：4 撑的序列，可参照基2 算法的思想，将其分解成4 个n 1 4 点的序列， 于是式( 2 7 ) 可写成： 庐0 ，1 ，1( 2 - 1 3 ) 也可以写成： 五= 扩k 。t + 矿五。七+ w 2 。五。i + 矿七置脚，l ，1 ( 2 1 4 ) x h n | 4 = 对x 畔t j 、护x p k w m x h k + j o k x 弧k 鼍+ 2 = w o k t 一矿五。七一w 2 。置。t 一矿五 鼍+ 3 4 = w o k 。七+ 五七一w 2 七蔓。七一伽3 七墨 由以上推导可以看出，按时间抽选基4 f f t 算法可以将= 4 一点的d f t 最终分解成 4 点d f t ，从而简化计算。基6 、基8 f f t 算法的运算规律可以依此类推。 2 2 5 分裂基算法 d i t 基2 算法的运算量仍然较大，基- 4 算法受到4 的整数次幂限制，而下面介绍的 分裂基算法既能最大程度的缩减运算量，又只要求为2 的整数次幂： 分裂基算法的特点在于对序列的不同部分分别进行基2 和基4 两种运算，它基于以 8 旆 w m矗 脚 肟 渺 ，脚 = 戤 基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 下分解【1 2 】： x ( 2 k ) ：n 2 - 1 x ( 刀) + 工。+ n 2 ) w n ，2 k 扣o ，”, n 2 1( 2 1 5 a ) x ( 4 七+ 1 ) = 【x ( 刀) 一x ( ，z + 2 ) 卜歹 x ( 刀+ 4 ) 一x ( 以+ 3 4 ) w v 矿4 k = - 0 ，l ，, n 4 一l( 2 - 1 5 b ) n 4 - 1 x ( 4 七+ 3 ) = x ( 拧) 一x ( 玎+ 2 ) 】+ 歹【x ( 刀+ 4 ) 一x ( 刀+ 3 4 ) 】w w 蔫4 k - - 0 ，1 i i ee , n 4 一l ( 2 1 5 e ) 由式( 2 1 5 ) 可知，分裂基算法的基本思想是将一个点的d f t 最终分解成一个两点 d f t 和两个4 点d f t 的组合。从图2 2 可以看出分裂基算法和c o o l e y t u k e y 算法的不 同。 图2 - 2 分裂基算法蝶形单元 f i g 2 2b u t t e r f l yu n i to fs p l i tr a d i x 分裂基算法的蝶形运算单元形状为不规则的“l 形，这将导致控制信号过于复杂， 且基本单元的模块性较差，从而造成硬件电路实现上的困难。这种算法适合于乘加运算 是瓶颈的软程序实现。 2 2 6 其他主要算法 1 、素因子算法： 前文所讨论的f f t 算法有一个共同特点：通过不同的抽选方式将长点数d f t 转换 成多个短点数d f t 的组合，并引入了与旋转因子的复乘。而素因子分解算法采用的是 中国余数定理，使映射后各d f t 的变换长度互为素数，将一维d f t 运算映射为标准的 多维d f t 运算，而各素因子的d f t 运算可以通过循环卷积算法完成。在素因子算法中， 由于避免了乘旋转因子的运算，因此比c o o l e y t u k e y 算法的乘法次数要少得多，而加法 次数则与之相当。 2 、w i n o g r a d 傅立叶变换算法( w f t a ) 9 广西大学硕士学位论文基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 w f t a 是s l l i i l u e lw i n o 删博士于1 9 7 5 年提出的一种计算d f t 的新方法i l 。这一 算法的特点是：在计算d f t 的过程中，其乘法次数显著减少( 比基2 f f t 少4 倍) ，而 且全都是实数或纯虚数运算，避免了复数运算和三角函数的调用，加法次数则与f f t 相近。w f t a 算法有两个主要思想：一是将小点d f t 转换为循环卷积，利用多项式 理论使卷积计算具有尽可能少的乘法次数；二是将小点d f t 运算进行嵌套来完成大 点的d f t 运算。这种算法比素因子算法的乘法次数更少，而加法次数差别不大。 2 3f f t 算法的比较与选择 前面简要分析了几种重要的f f t 算法。从实现的角度而言，选择何种算法进行f p g a 硬件实现，需要综合考虑算法的运算量、复杂性：包括结构是否规则、是否适合f p g a 实现、是否可同址运算、内存的消耗量等问题。以下将对上述各种算法从各个角度进行 详细比较，并最终确定课题所使用的f f t 算法。 2 3 1 几种f f t 算法的运算量比较 f f t 算法的运算量是衡量算法的首要指标，表2 1 给出了各种快速算法的运算量与 变换点数n 的关系式【2 l 】，表2 2 直观的给出了不同变换长度下各算法的实数乘法和实数 加法次数。 由此可以看出： ( 1 ) 分裂计算法可达到为2 的整数次幂时能达到的最小乘法次数。 但对于如5 1 2 点的f f t ，若选用基4 算法进行处理，就必须先将其扩展为1 0 2 4 点 再进行处理，这削弱了基4 算法在运算量方面的优势。同样，基8 、基1 6 算法也具有 这样的问题。 ( 2 ) 对于素因子算法和w f t a 算法而言，基本思想都是将一维d f t 转换为多维d f t 进行运算，在转换中避免了与旋转因子相乘的运算，从而更有效的减少了乘法的次数， 而两者加法次数则相近。但是这两种算法对于2 的整数次幂点数的处理都比较复杂，因 为其将d f t 分解为互素因子进行运算。 2 3 2 几种f f t 算法的复杂性比较 对于具体的f p g a 硬件实现而言，算法的运算量只是在选择算法时所需考虑的因素 之一，而算法的复杂性，如算法是否规则、是否具有模块性等往往是更重要的。以下将 就算法的复杂性对上述算法进行比较。 ( 1 ) c o o l e y 呲e y 算法，以基2 、基4 算法为代表。算法对输入数据的提取可以由 地址线的简单变换得到，而旋转因子可以保存在r o m 中，并同样由地址线来确定。由 此可见，这种算法的控制电路仅由计数器和地址变换装置组成。因此，这一算法简单、 1 0 g - 西大掌硕士学位论文 基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 规则、具有良好的模块性，并可以实现原位运算，非常适合f p g a 实现。 对比基2 和基4 两种算法。基4 蝶形单元包含的乘法器比基2 算法所包含的多， 即使是经过优化的基4 蝶形单元仍然包含三个乘法器，而同样经过优化的基2 蝶形单元 则只需两个乘法器。由于乘法器的硬件消耗很大，因此基- 4 蝶形单元的硬件开销比基2 算法大近3 0 【2 1 1 。其次，基4 蝶形单元内的硬件拓扑结构和连线方式比基2 蝶形单元要 复杂的多，将导致连线延迟大于逻辑门延迟，在f p g a 中这一现象尤为严重。基一4 蝶形 单元的复杂连线方式不但增加了连线的长度，而且降低了布线效率，这必将降低整个处 理器的速度。综上所述，从系统的复杂性和硬件消耗角度考虑，d i t 基2 算法优于基4 算法，可以通过优化运算单元和地址单元的硬件结构来弥补其在运算速度方面的不足。 ( 2 ) 分裂基算法。由上文的推导可知，分裂基算法是基于2 的整数次幂，因此具有 很大的灵活性，其运算量也是f f t 算法中较小的，随着点数的增加，其乘加次数远远小 于c o o l e y t u k e y 算法。下面，从硬件设计的复杂性来分析这种算法的适用性。 在分裂基算法中，由于不同地址的数据分别输入到2 点和4 点的d f t 运算模块并 与旋转因子相乘，按照这样的算法流程，地址逻辑和控制逻辑将变得非常复杂。由图2 2 可以看出，分裂基算法的蝶形单元是不规则的“l 形，因此其基本运算单元的规则性 较差。这些特点决定了这种算法并不适合对模块性要求很高的f p g a 实现，且在目前大 容量的f p g a 价格仍然偏高的情况下，分裂基算法的性价比也不高。 表2 1 运算量与变换点数的关系【2 3 1 t a b l e 2 1r e l a t i o n s h i pb e t w e e no p e r a t i o nt i m e sa n de x c h a n g ep o i n tn u m b e rn ( 3 ) 素因子算法。由于没有与旋转因子相乘的运算，因此该算法避免了对旋转因子 广西大昔巴硕士学位论文基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 的抽取。但指标映射过程造成了地址表达式中具有乘、加运算，而这些运算又需要专门 的运算单元实现。因此，该算法的控制电路要比c o o l e y t u l 【e y 算法复杂得多。其次，由 于素因子算法中的短点数d f t 变换长度各不相同，所以要求每一个d f t 都采用不同的 运算单元。这不仅加大了硬件的消耗量，同时也影响了运算单元的速度。由此可见，素 因子算法同样具有模块性较差，结构与控制逻辑复杂，不适于f p g a 实现的问题。 ( 4 ) w f t a 算法。该算法的地址产生可以根据其计算公式或算法流图来实现。由于 该算法不能采用原位计算【6 1 ，因此参与运算的数据、中间结果以及最终结果将占用很大 的存储空间，这在内存有限的f p g a 中是很不合适的。其次，为减少运算所需的加法次 数，随着变换点数n 的不同，要求采用不同的运算次序，这导致运算过程的规则性较差， 控制过程也过于复杂。同时对于各“小 ，运算单元也不同，导致模块性较差。 2 3 3 算法的选择 虽然c o o l e y t u l ( e y 算法的运算次数要多于其它几种快速算法，但由于其算法规则， 可共用运算单元，模块性良好，所以它的结构更加适合f p g a 实现。在设计过程中，将 通过优化运算单元结构、缩短关键路径延迟、用面积换速度等方法提升系统速度。 比较这几种算法，d i t 基2 f f t 算法具有最好的综合性能。故课题选用d i t 基2 f f t 算法进行硬件实现。 2 4 硬件整体结构的设计 根据前文的分析，可构造出f f t 的硬件实现结构【l l 】【1 9 】【2 l 】【2 2 】，现分述如下： 2 4 1单蝶形顺序处理结构 图2 3 给出了用单蝶形顺序处理结构实现的d i t 基2 f f t 的硬件结构图。 由图2 3 可以看出：该结构只使用一个蝶形运算单元，它按蝶形图自左向右，自上 而下的顺序依次递归计算所有的蝶形单元，从而使蝶形运算单元一直处于工作状态。若 蝶形运算单元的时钟周期为l 则完成所有序列计算的时间为删l o g ，n 2 。输入量、输 出量和中间结果共用一个存储单元，存取数据的操作由地址发生部件控制，计算出的每 一级中间结果被原位存储，倒位序的输出结果可以经过地址线的调整得到原位序输出。 1 2 广西大掌硕士掌位论文基于f p g a 的高性能3 2 位浮点f f ti p 核的开发 表2 2 各算法的实数乘法和实数加法次数 t a b l e 2 - 2t h ec o m p a r i s o no ft h et i m e so fr e a ln u m b e ra d d i t i o na n dm u l t i p l i c a t i o ni ns e v e r a l d i f f e r e n ta l g o r i t h m s 变换长度基2 算法基- 4 算法分裂基素因子算法w f t a 算法 1 6 3 0 3 2 6 0 6