（电路与系统专业论文）基于FPGA实现可扩展高速FFT处理器的研究[电路与系统专业优秀论文].pdf

中文摘要摘要d f t ( n 散傅立叶变换) 作为将信号从时域转换到频域的基本运算，在各种数字信号处理中起着核一t x , 作用 1 ，2 l ，其快速算法f f t ( 快速傅立叶变换) 在无线通信、语音识别、图像处理和频谱分析等领域有着广泛的应用。特别是随着o f d m ( 正交频分复用) 技术的出现，不同o f d m 系统需要不同变换点数的f f t 运算，如何更快速、更灵活地实现f f t 变得越来越重要。本文提出了基于f p g a ( 现场可编程门阵列) 实现傅立叶变换点数可灵活扩展的高速f f t 处理器的结构设计以及各功能模块的算法实现，包括高组合数f f t 算法能按流水线方式工作的f f t 级联实现结构、级间混序r a m 读写地址规律及其地址发_ i 器的设计、补码实现的短点数f f t 阵列处理结构以及补码实现的可用于不同级间完成数据相位旋转而又具有相同流水线结构的c o r d l c ( 坐标旋转数字计算机) 处理器等；实现了具有流水线处理能力的高速f f t 处理器及其功能验证平台。对基于f p g a 实现可扩展高速f f t 处理器的研究表明：( 1 ) 随着现场可编程i c ( 集成电路) 技术的发展和应用的成熟，器件规模和品种不断增加，现场可编程i c 设计和应用成本不断降低，在越来越多的领域和产品中，特别是生产批量小，更新快的数字化系统产品中，直接采用f p g a 为代表的现场可编程i c 来实现硬件的单片集成，已成为必然趋势。对于f f t 等算法的快速原型，c p l d ( 复杂可编程逻辑器件) f p g a 技术是一个理想工具。( 2 ) 面向高速、大容量数据流的f f t 的实时处理，可以通过v l s i ( 超大规模集成电路) 器件的并行处理或多级流水线处理等来达到。特别是多级流水线处理的f f t结构使得基于c p l d f p g a 器件的f f t 处理器完成不同点数的f f t 计算时可以通过增减模块级数很容易地实现。( 3 ) 通过分析和比较各种f f t 算法的特性和规律后得出，基于f p g a 设计傅立叶变换点数可灵活扩展的高速f f t 处理器，高组合数f f t 算法是最优选择，基一x 这种任何基f f t 都有扩展的局限性，因为后者是前者的特例，对前者的研究可以得出一般规律的总结，使得高速f f t 处理器的结构扩展更为方便和灵活。( 4 ) 为了f p g a 更加优化地实现f f t 设计的综合以及布局布线，需要针对f p g a的特点，改变一些功能模块的算法原理，如实现旋转因子乘法的c o r d i c 算法；调接一些模块单元的设计结构，如c o r d l c 迭代单元的补码实现结构等。( 5 ) 能够从理论上，一般性地总结出组合数f f t 算法实现过程中用流水线读写同一块r a m 来实现级与级之间的数据混序的读写r a m 地址发生规律，以它为指导，可以灵活地改变f f t 处理器的结构及其进行傅立叶变换的数据规模，此结重庆人学硕士论文构取代了用两块r a m 完成数据混序的乒乓结构，不涉及存储器之间的读写切换，控制逻辑非常简单，而且消耗的存储器资源节省一半。( 6 ) 根据设计结构用f p g a 实现的具有流水线处理能力的高速f f t 处理器的实验结果表明：时钟工作在4 0 m h z 时，输入数据速率达到2 0 m h z ，计算1 0 2 4 点1 6 位字长定点f f t 运_ 算可以达- 至l j 5 2 u s 量级( 实测结果) 。由此说明，基于f p g a 实现的f f t处理器的各功能模块涉及的算法的理论分析正确，设计结构能够达到满足实时处理的高速性能。关键词：组合数快速傅立叶变换，现场可编程f 阵列，存储器，坐标旋转数字计算机，结构扩展，流水线i i英文摘要a b s t r a c td f t ( d i s c r e t ef o u r i e rt r a n s f o r m ) i st h em o s ti m p o r t a n tf u n d a m e n t a lo p e r a t i o n sa n dp l a y sac o r er o l ei na l ls o r t so fd i g i t a ls i g n a lp r o c e s s i n g l l ，2 1 f f t ( f a s tf o u r i e rt r a n s f o r m ) a l g o r i t h mh a sa c h i e v e dad r a m a t i ci n c r e a s ei nt h ee f f i c i e n c yo fc o m p u t a t i o no ft h ed f t , w h i c hi sw i d e l yu s e di nt h ed o m a i n so fw i r e l e s sc o m m u n i c a t i o n ，s p e e c hr e c o g n i t i o n ，i m a g ep r o c e s s i n g ，a n ds p e c t r u ma n a l y s i s a so f d m ( o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ) t e c h n o l o g ya p p e a r s ，d i f f e r e n to f d ms y s t e m sn e e df f to p e r a t i o no fd i f f e r e n tl e n g t h s ，i ti sm o r ea n dm o r ei m p o r t a n tt oi m p l e m e n th i g h s p e e da n ds c a l a b l el e n g t hf f ti nt h i sp a p e r ，t h ea r c h i t e c t u r eo fs c a l a b l el e n g t ha n dh i 曲s p e e df f tp r o c e s s o rb a s e do nf p g a ( f i e l dp r o g r a m m a b l eg a t e a r r a y ) i sp r o p o s e d ，i n c l u d i n gt h ep i p e l i n ea r c h i t e c t u r eo ft h er a d i xm i x e df f ta l g o r i t h m ，t h ea d d r e s sr e g u l a r i t yo ft h er e a d 。t h e n 。w r i t er a m ，t h ea r r a ya r c h i t e c t u r eo fs h o r t l e n g t hf f ta n dt h ep i p e l i n ec o m p l e m e n ta r c h i t e c t u r eo fc o r d i c ( c o o r d i n a t er o t a t i o nd i g i t a lc o m p u t e r )a l g o r i t h m a c c o r d i n gt ot h ea r c h i t e c t u r eo fd e s i g n ，t h ei m p l e m e n t a t i o no fas c a l a b l el e n g t ha n dp i p e l i n e - p r o c e s s i n gf f tp r o c e s s o ra n di t sf u n c t i o nv e r i f i c a t i o np l a t f o r ma r ep r e s e n t e d t h ei m p l e m e n t a t i o nr e s u l to ff f tp r o c e s s o ri n d i c a t e ：( 1 ) a st h ef p i c ( f i e l dp r o g r a m m a b l ei n t e g r a t e dc i r c u i t ) t e c h n o l o g yi sd e v e l o p e d ，t h ed e v i c eo fl a r g e rs c a l ea n dm o r ek i n dw i l lr e d u c et h ec o s to fd e s i g n sa n da p p l i c a t i o n sb a s e do nf p i c d e s i g n so nac h i po ff p g a ，ar e p r e s e n t a t i v ef p i cd e v i c e ，m u s tb ep o p u l a ri nm o r ea n dm o r ed o m a i n sa n dp r o d u c t s ，e s p e c i a l l yi nd i g i t a ls y s t e mp r o d u c t s i t sp r o d u c e di ns m a l la m o u n t ，a n du p d a t e di ns h o r tt i m e r e c e n tc p l d ( c o m p l e xp r o g r a m m a b l el o g i cd e v i c e ) f p g at e c h n o l o g yi sa ni d e a lt o o lf o rd e v e l o p m e n ta n df a s tp r o t o t y p i n go f f f t ( 2 ) t h er e a l t i m ec o m p u t a t i o no ff f tw i t hh i g h s p e e da n dl a r g ec a p a c i t yd a t af l o wi sr e a l i z e db yp a r a l l e lp r o c e s s i n ga r c h i t e c t u r ea n dm u l t i l e v e lp i p e l i n ep r o c e s s i n ga r c h i t e c t u r ei nv l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) i t se a s yt oi m p l e m e n tt h es c a l a b l ef f tb a s e do nm u l t i l e v e lp i p e l i n ep r o c e s s i n ga r c h i t e c t u r ei nf p g a c p l d ( 3 ) a c c o r d i n gt ot h ec o n t r a d i s t i n g u i s ho fa l lk i n d so ff f tp r o c e s s i n ga r c h i t e c t u r e ，t h ed e s i g nt h o u g h t s ，r i d e ，m e t h o d ，t h ec h a r a c t e r i s t i c so fr a d i xm i x e df f ta l g o r i t h mm e e t st h er e q u i r e m e n t so fs c a l a b l ef f ta r c h i t e c t u r e t h eo t h e rf f ta l g o r i t h m sh a v ei i i重庆大学硕士论文t h e i ro w nl i m i t a t i o n s f 4 ) i no r d e rt h a tt h ed e s i g ni sa p p r o p r i a t e l ys y n t h e s i z e da n dl a i do u ti nf p g a i t sn e c e s s a r yt oa d a p tt h eu n d e r l y i n ga l g o r i t h ma n dt oo p t i m i z et h ed e s i g nt os u i tt h ef a c i l i t i e so fd a t ap r o c e s s i n gm a d ep o s s i b l eb yf p g a c p l d s u c ha sc o r d i ca l g o r i t h mf o rt h et w i d d l ef a c t o rm u l t i p l i c a t i o na n ds u c ha st h ec o m p l e m e n tp i p e l i n ea r c h i t e c t u r eo fc o r d l cp r o c e s s o r ( 5 ) t h e r ei sar u l eo ft h ea d d r e s so ft h er e a d t h e n w r i t er a m w h i c hd i r e c t st h ec h a n g eo ft h es c a l a b l ef f ta r c h i t e c t u r e ，a n di t sf o u n di nt h ea b s t r a c t ( 6 ) t h ee x p e r i m e n t a lr e s u l to ff f tp r o c e s s o ri n d i c a t e ：t h et h e o f i e so ff u n c t i o n a lm o d u l ea r ec o r r e c t ，a n dt h e i ra r c h i t e c t u r e sa r ef a i re n o u g h t h ee x p e r i m e n tr e s u l ti n d i c a t e st h a tt h ec o m p u t a t i o nt i m eo f1 0 2 4 一p o i n tf f ti s5 2 u sw h e nt h e 行e q u e n c ys y s t e mc l o c ki s4 0m h za n dt l l er a t eo f d a t ai s2 0 m h z k e y w o r d ：r a d i xm i x e df f t , f p g a ，r a m ，c o r d i c ，s c a l a b l e ，p i p e l i n e1 绪论1 1 课题的提出1 绪论在现代科学技术领域里，电子信息系统的应用范围极为广泛，主要有通信、导航、雷达、声纳、地震勘探、医学仪器和射电天文等等。在短短几十年的时间里，这些系统几经更新换代，发展极其迅速。系统的发展进程常常和信息的利用程度分不开，而信息的利用程度又和信号与信息处理技术的发展紧密相连。6 0 年代以来，微电子集成电路技术、工艺迅猛发展，为复杂信号处理的实现提供了可能，从而将信号处理的发展推向高潮。从此，信号处理的研究不仅限于一般理论和方法的探讨，更多侧重于实现方面，新的实现方法与算法的成果层出不穷。在此基础上发展起来的新一代系统，其优化和自适应性能大大提高，早期系统已无法与其相提并论。现代信号处理的研究的一个特色是理论与实用研究同步进行，既重视基础理论的研究，又重视实际实现和应用的研究 1 1 。随着数字技术与计算机技术的发展，数字信号处理技术已深入到各个学科领域，其应用又是多种多样的，但数字信号处理基本上从两方面来解决信号的处理问题：一个是时域方法，即数字滤波；另一个是频域方法，即频谱分析。处理的任务大致分为三类：卷积：用于各种滤波器，对给定频率范围的原始信号进行加工( 通过或滤出) 来提高信噪比；相关：用于信号比较，去除随机事件而放大重复的信号；变换：用于分析信号的频率内容，寻找特征“指纹”。其中，d f t ( 离散傅立叶变换) 和卷积是信号处理中两个最基本也是最常用的运算，它们涉及到信号与系统的分析与综合这一广泛的信号处理领域。由数字信号处理的基本理论可知，卷积可以转化为d f t 来实现，实际上其他许多算法，如相关、谱分析等也都可以转化为d f t 来实现；此外，各种系统的分析、设计和实现中都会用至t j d f t 的计算问题。所以，d f t 在各种数字信号处理中起着核心作用，而d f t 的快速算法f f t ( 快速傅立叶变换) 就成为了数字信号处理的最基本技术之一，对f f t 及其实现方式方法的研究是很有意义的1 2 】。现代信号处理是面向高速、大容量数据流的实时处理，其特点在于系统的输入、处理、和输出等各个处理阶段都具有绝对的时间限制，若超过所限定的时间，系统将被认为不起作用而失败。因此，处理单元的速度要足够快，以满足操作的实时性限制。研究表明高速、大容量数据流的实时处理可以通过高速v l s l 器件并行处理或多级流水处理等来达到。随着现场可编程i c ( 集成电路1 技术的发展和应用的成熟，器件规模和品种不断增加，现场可编程i c 设计和应用成本不断降低，重庆人学硕士论文存越来越多的领域和产品中，特别是生产批量小，更新快的数字化系统产品中，直接采用f p g a c p l d 为代表的现场可编程i c 来实现硬件单片集成，己成为必然趋势1 ”。目前，f f t 已广泛应用在无线通信、语音识别、图像处理和频谱分析等领域。在不同应用场合，需要不同性能要求的f f t 处理器，特别是随着o f d m ( 正交频分复用1 技术的出现，不同o f d m 系统需要不同变换点数f f t ，如何更快速、更灵活地实现f f t 变得越来越重要。这就提出了根据c p l d f p g a 的特点，研究基于f p g a实现变换点数可扩展的高速f f t 专用处理器的课题。1 2 相关技术的发展和研究现状1 2 1f f t 算法的研究现状d f t 在信号的频谱分析、系统分析、设计和实现中得到了广泛的应用，原因之一就是计算d f t 有很多的快速算法，从快速计算d f t 的理论观点看，这些快速计算d f t 的方法大概可以分为两类【4 6 1 ：一类是将d f t 转变为卷积，利用卷据的快速算法计算d f t ，其代表是线性调频z 变换算法、素数d f t 算法，前者可将n 点d f t 转换成线性卷积，然后借助于快速卷积算法来计算d f t ，而后者在n 为素数时，可将n 点的d f t 转换成n 一1 点的循环卷积；另一类是递归型快速算法，是将一维d f t 分解为容易计算的二维或多维d f t ，且这个过程可以重复，其代表是c o o l e y t u k e y 算法、分裂基算法等，统称为f f t算法。从1 9 6 5 年，j w c o o l e y 和j w t u k e y 提出离散傅立叶变换的快速算法c o o l e y t u k e y 算法以来，f f t 又有多种算法，各种算法也发展得比较成熟。从f f t算法理论的发展看，主要有两个方向：( 1 ) 组合数f f t 算法，如实因子算法、分裂基算法、基2 、基4 、基8 、基1 6 及任意组合因子等的组合数f f t 算法，利用阡，的周期性和对称性，使长序列的d f t 分解为更小点数的d f t ，从而大大减少了运算工作量，共同特点是每两级d f t 之间需要乘以旋转因子。( 2 ) 另一个是以维诺格( w i n o g r a d ) 代表的一类傅立叶变换算 法( w i n o g r a d傅立叶变换算法( w f t a ) ，素因子算法( p f a ) ) ，利用下标映射和数论以及近代数的知识，去掉了级问的旋转因子，因而减少了运算量，但是这一点得益所付出的代价是输入输出信号排列次序是“乱”序的，而且这种“乱”序并不具备同位交换性质。1 绪论1 2 2f f t 处理器的研究现状f f t 在无线通信、语音识别、图像处理和频谱分析等领域有着广泛的应用。其实现形式主要有两种：( 1 ) 一种是使用单片机或d s p ，通过软件编程来实现。利用软件编程来实现f f t ，虽然有很大的灵活性，但受d s p 本身性能及程序指令顺序执行的限制，难以实现高速、大规模的f f t 运算。( 2 ) 另一种是应用专用f f t 芯片或用户定制的大规模集成电路实现。专用f f t芯片或用户定制的大规模集成电路可以实现很高的运算速度，非常适合高速信号处理系统的应用。目前，国际上的高速f f t 实现方案分为d s p 、f p g a 和a s i ci p 等。专用的f f t模块可以达到的速度数量级普遍为1 0 2 4 点1 6 位字长定点、浮点运算在几十和数百u s 量级。其中采用t i 公司的d s p c 6 7 x 系列实现1 0 2 4 个复数点f f t 达至1 5 6 u s 量级处理速度，需要多片d s p 芯片的拼接；x i l i n x 公司推出了1 4 0 m h z 时钟频率下处理速度达到l u s 的1 0 2 4 点f f t 处理模块，其采用的是8 0 0 万f v i r t e x i i 器件实现。1 2 3f p g a 的发展现状2 0 世纪8 0 年代中期，a l t e r a 和x i l i n x 公司分别推出了类似于p a l ( 可编程阵列逻辑) 结构的扩展型c p l d ( 复杂可编程逻辑器件) 和与标准门阵列类似的f p g a ( 现场可编程门阵y o ) ，它们都具有体系结构和逻辑单元灵活、集成度高以及适用范围宽等特点。这两种器件兼容了p l d 和通用门阵列的优点，可实现较大规模的电路，编程也很灵活。与门阵列等其它的a s i c 相比，它们又具有设计开发周期短、设计制造成本低、开发工具先进、标准产品无需测试、质量稳定以及可实时在线检验等优点，因此被广泛应用于产品的原型设计和产品生产( 一般在1 0 ，0 0 0 件以下) 之中。几乎所有应用门阵列、p l d 乖i 中小规模通用数字集成电路的场合均可应用f p g a 和c p l d 器件。随着超大规模集成电路( v l s i ) i 艺的不断提高，单一芯片内部可以容纳上百万个晶体管，f p g a c p l d 芯片的规模也越来越大，其单片逻辑门数已达到上百万门，它所能实现的功能也越来越强，同时也可以实现系统集成【7 1 。用户可以对f p g a c p l d 芯片反复地编程、擦除、使用或者在外围电路不动地情况下用不同软件就可实现不同的功能。所以，用f p g a c p l d 试制样片，能以最快地速度占领市场。f p g a c p l d 软件包中有各种输入工具和仿真工具，及版图设计工具和编程器等全线产品，电路设计人员在很短的时间内就可以完成电路的输入、编译、优化、仿真，直至最后芯片的制作。当电路有少量改动时，更能显示冉f p g a c p l d 的优势。电路设计人员使用f p g a c p l d 进行电路设计时，不需要重庆大学硕士论文具备专门的集成电路o f ) 深层次的知识，f p g a j c p l d 软件易学易用，可以使设计人员更能集中精力进行电路设计，快速将产品推向市场。1 2 41 pc o r e 的发展现状目前在单个芯片上己可以集成成千上万乃至上亿个晶体管，实现了以前需要印刷电路板甚至机架乃。能完成的功能。在这样高的集成度下，设计难度已变得非常高，设计代价事实上主导了芯片的代价。这不仅要求设计者必须具备系统和芯片两方面的知识，同时也必须充分考虑市场竞争的压力，最大限度地缩短设计周期。凡事从零做起的思路显然不能适应这种新情况。而采用前人成功的设计经验和设计资料是解决这个问题的明智选择。具有知识产权的内核( i n t e l l e c t u a lp r o p e r t y c o r e ) 是一个经过验证的集成电路设计，可以被他人重用。i p c o r e 通常具备比较复杂的功能，而且经过验证，i pc o r e 设计资料内不仅仅包含一些物理功能和技术特性，更重要的是包含了设计者的创造性思维，具有很强的知识内涵【8 1 。从实现形式和应用层次上来看，i pc o r e 可以有三种不同的表现形式：软核( s o f t c o r e ) 、固核( f i r m c o r e ) 、硬核( h a r d c o r e ) 。软核以硬件描述语言的形式提交，其性能通过时序模拟进行验证。由于软核不依赖于任何实现工艺或实现技术，具有很大的灵活性。使用者可以方便地将其映射到自己所使用的工艺上去，可复用性很高。软核的另外一个优点是使用者拥有全部源代码。使用者可以通过修改源代码，方便地生成同样功能且自有版权的新软核，从而避免向原有软核的作者支付版税。同时聪明的软核使用者还可以通过增加自己的知识和经验，产生出远比原始软核应用范围广泛得多的新软核。正是由于软核的上述优点，它的价格不菲，且提供者寥寥无几，但软核也有自身的弱点，由于软核的载体是硬件描述语言，而且与实现的工艺无关，使用者在最终将其嵌入到自己的设计中时就要对从描述到版图的转换的全过程负责。显然这要涉及经典集成电路的全部内容，集成电路设计人员必须具有相当的风险意识。另外，工艺映射和系统的性能有着一定的内在关系，是否可以不加修改地将个软核映射到任何一个工艺上，仍然是需要探讨的一个问题。硬核是以集成电路版图( l a y o u t ) 的形式提交，并且经过了实际工艺流片验证。显然，硬核强烈地依赖于某一特定的实现工艺，而且在具体的物理尺寸，物理形态上具有不可更改性。这些特定对使用者来说有喜有忧。喜的是硬核已经通过验证并且具有最优的面积代价和性能的设计，使用者不需考虑与此相关的优化问题。忧的是硬核与工艺的强相关性迫使使用者只能使用该工艺来完成电路其它部分的设计，而且要在布局布线( p l a c e & r o u t e ) 时注意遵守硬核的物理限制。显然，硬核1 绪论的特点决定了使用者进行电路设计时的灵活性很小，希望通过获得硬核来生成其它硬核的可能性基本上没有，即使有，受到加工工艺、经费和知识产权等方面的限制，也会失去意义。从另外一个角度来看，正是因为硬核的这些缺点，使得它的使用价格在软核、固核、硬核三种i p 核中是最低的。固核处于软核和硬核之间，以电路网表( n e t l i s t ) 的形式提交，并且通常采用硬件进行验证，硬件验证的方式有很多种，比如可以采用可编程逻辑器件( f p g a c p l d ) 进行验证，采用硬件仿真器( h a r d w a r ee m u l a t o r ) 进行验证等。固核往往对应于一个特定的实现工艺，在该实现工艺条件下固核具有最优秀的面积和性能特性。对使用者来说，不需要对固核的功能给予过多的关注，可以减少许多相关性的设计工作，同时由于固核的时序特性是经过严格验证的，设计者只要保证在布局布线过程中电路关键路径的分布参数不会引起时序混乱就可以保证芯片的设计成功。但是固核也有其自身的缺点，那就是它与实现工艺的相关性及其网表的难读性，与实现工艺的相关性限制了固核的使用范围，网表的难读性使得布局布线后发生的时序违反的排除变得比较困难。由于固核在使用的方便程度上和开放程度上均介于软核和硬核之间，其价格也介于软核和硬核之间。1 3 本论文的研究工作本文所进行的研究工作有：( 1 ) 比较f f t 算法，结合器件结构寻找适合f p g a 器件实现处理结构可方便扩展的f f t 算法，选定采用高组合数的f f t 算法旋转因子算法，对此算法进行了仿真，证明了其模块化设计的可行性。见第3 章。( 2 ) 研究了c o r d i c 算法实现级间数据的相位旋转的原理，提出了流水线结构的c o r d i c 处理器的设计方案：从理论的高度，一般性地总结了补码实现加减法和右移除2 的运算规则，设计出采用补码运算的阵列结构的短点数f f t 单元和流水线c o r d i c 处理器结构；设计出了适应于不同变换点数的计算其方向向量的统一结构，见第4 章和第6 章。( 3 ) l g 较y f f t 处理器的各种实现结构，设计出可扩展高速f f t 处理器的结构，采用流水线结构、用读写r a m 混序方式、阵列结构的短点数f f t 单元、流水线c o r d i c 处理器结构实现级间数据的相位旋转，提出时分复用阵列结构的短点数f f t 运算单元等设计思路和结构框图，见第5 章。( 4 ) 从理论的高度，一般性地总结了组合数f f t 算法实现过程中用流水线读写r a m 来实现级与级之间的数据混序的读写地址规律，以它为指导，可以灵活地改变f f t 处理器的结构及其数据进行傅立叶变换的规模，见第6 章。重庆大学硕士论文( 5 ) 厍 f p g a 设计实现了可扩展高速f f t 处理器的各功能模块，并对其进行了后验仿真；实现了具有流水线处理能力的高速f f t 处理器及其功能验证平台；对8 8 a 的f f t 处理器进行了后验仿真、误差分析和器件测试，见第7 章。1 4 论文结构第1 章为绪论，介绍了可扩展f f t 处理器的研究背景、研究现状以及基于f p g a实现f f t 处理器的相关技术。第2 章为f p g a c p l d 技术的介绍，包括从概念上介绍f p g a c p l d 的原理，分析目前比较成功的芯片结构，介绍f p g a c p l d 的开发流程，使用的丌发语言v h d l ( v e r yh i g hs p e e di ch d l ) 和开发工具以及对f p g a c p l d 技术的展望等。第3 章为高组合数的f f t 算法旋转因子算法原理，归纳总结出这一类递归型快速算法的规律，是将一维d f t 分解为容易计算的二维或多维d f t ，且这个过程可以重复，利用。的周期性和对称性，使长序列的d f t 分解为更小点数的d f t ，从而大大减少了运算工作量，共同特点是每两级d f t 之蚓需要乘以旋转因子，基2 、基4 、基8 、基1 6 f f t 算法是任意组合因子的组合数f f t 算法的特殊情况，并对此算法进行了仿真，证明了其模块化设计的可行性。第4 章为用c o r d i c 算法实现高组合数的f f t 算法的每两级d f t 之间乘以旋转因子的相位旋转原理，分析证明了这种转换方法的正确性，提出了流水线结构的c o r d i c 处理器的设计方案。第5 章为可扩展高速f f t 处理器的结构设计，比较t f f t 处理器的各种实现结构，设计出采用流水线结构、用读写r a m 混序方式、阵列结构的短点数f f t 单元、流水线c o r d i c 处理器结构实现级间数据的相位旋转的可扩展高速f f t 处理器的结构。第6 章为可扩展高速f f t 处理器的模块设计，包括各功能模块设计的算法实现，结构优化等，理论论述清晰，论述方法独特，设计结构新颖，为论文的核心内容。第7 章为可扩展高速f f t 处理器的模块设计的后验仿真以及误差分析。第8 章为结论及展望。2f p g a c p l d 技术2f p g a c p l d 技术当今社会是数字化的社会，是数字集成电路广泛应用的社会。数字集成电路本身在不断地进行更新换代。它由早期的电子管、晶体管、小中规模集成电路发展到超大规模集成电路以及许多具有特定功能的专用集成电路。随着微电子技术的发展，设计与制造集成电路的任务已不完全由半导体厂商来独立承担，系统设计师们更愿意自己设计专用集成电路( 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 )芯片，而且希望a s i c 的设计周期尽可能短，最好是在实验室里就能设计出合适的a s i c 芯片，并且立即投入实际应用之中，这就出现了现场可编程逻辑器件( f p l d ) ，其中应用最广泛的当属现场可编程门阵y l j ( f p g a ：f i e l d p r o g r a m m a b l e g a t e a r r a y )和复杂可编程逻辑器件( c p l d ：c o m p l e xp r o g r a m m a b l el o g i cd e v i c e ) 。可编程逻辑器件( p l d ) 的使用，使电子产品达到小型化、集成化和高可靠性。而f p g a 器件的现场可编程技术和c p l d 器件的在系统可编程( i s p ：i ns y s t e mp r o g r a m m a b l e ) 技术，使p l d 在使用上更为方便。随着e d a 技术的进步和软件开发系统的日趋完善，应用f p g a 和c p l d 进行电子系统设计已成为发展趋势。本次设计主要是以现场可编程门阵列( f p g a ) 技术为基础来完成的，所以需要从概念上介绍f p g a c p l d 的原理、芯片结构和性能特点，介绍f p g c p l d 的开发流程，使用的开发语言v h d l ( v e r yh i g hs p e e di cn d l ) 和开发工具以及对f p g a c p l d 技术的展望等。2 1f p g a c p l d 器件2 1 1f p g a c p l d 器件概述早期的可编程逻辑器件只有可编程只读存储器( p r o m ) 、紫外线可擦除只读存储器( e p r o m ) 和电可擦除只读存储器( e e p r o m ) y 种。由于结构的限制，它们只能完成简单的数字逻辑功能。其后，出现了一类结构上稍微复杂的可编程芯片，即可编程逻辑器件( p l d ) ，它能够完成各种数字逻辑功能，这一阶段的产品主要有p a l ( 可编程阵列逻辑) 和g a l ( 通用阵列逻辑) 。这些早期的p l d 器件的一个共同特点是可以实现速度特性较好的逻辑功能，但其过于简单的结构也使他们只能实现规模较小的电路一j 。为了弥补这一缺陷，2 0 世纪8 0 年代中期，a l t e r a 和x i l i n x 分别推出了类似于p a l结构的扩展型c p l d j f f i 与标准门阵列类似的f p g a ，它们都具有体系结构和逻辑单重庆人学硕士论文元灵活、集成度高以及适用范围宽等特点。这两种器件兼容了p l d 和通用门阵列的优点，可实现较大规模的电路，编程也很灵活。与门阵列等其它的a s l c t h 比，它们又具有设计开发周期短、设计制造成本低、开发工具先进、标准产品无需测试、质量稳定以及可实时在线检验等优点，因此被广泛应用于产品的原型设计和产品生产( 一般在1 0 ，0 0 0 件以下) 之中。几乎所有应用门阵列、p l d 和中小规模通用数字集成电路的场合均可应用f p g a 和c p l d 器件。自从x i l i n x 公司1 9 8 4 年发明了第一片f p g a 以来，f p g a 的集成密度和性能提高很快，其集成密度最高达数百万门片，系统性能可达2 0 0 m h z 。由于f p g a 器件集成度高，方便易用，开发和上市周期短，在数字设计和电子生产中得到迅速普及和应用，并一度在高密度的可编程逻辑器件领域中独占鳌头。而9 0 年代初l a t t i c e 公司推出高性能的具有在系统可编程( i s p ) 功能的c p l d 以来，c p l d 发展迅速。具有i s p 功能的c p l d 器件由于具有同f p g a 器件相似的集成度和易用性，在速度上还有一定的优势，使其在可编程逻辑器件技术的竞争中与f p g a 并驾齐驱，成为两支领导可编程器件技术发展的力量之一。f p g a c p l d 芯片都是特殊的a s i c 芯片它们除了具有a s i c 的特点之外，还具有以下几个优点：( 1 ) 随着v l s i ( 超大规模集成电路) 工艺的不断提高，单一芯片内部可以容纳上百万个晶体管，f p g a c p l d 芯片的规模也越来越大，其单片逻辑门数已达到上百万门，它所能实现的功能也越来越强，同时也可以实现系统集成。( 2 ) f p o a c p l d 芯片在出厂之前都做过百分之百的测试，不需要设计人员承担投片风险和费用，设计人员只需在自己的实验室里就可以通过相关的软硬件环境来完成芯片的最终功能设计。所以，f p g a c p l d 的资金投入小，节省了许多潜在的花费。( 3 ) 用户可以反复地编程、擦除、使用或者在外围电路不动地情况下用不同软件就可实现不同的功能。所以，用f p g a c p l d 试制样片，能以最快地速度占领市场。( 4 ) f p g a c p l d 软件包中有各种输入工具和仿真工具，及版图设计工具和编程器等全线产品，电路设计人员在很短的时间内就可以完成电路的输入、编译、优化、仿真，直至最后芯片的制作。当电路有少量改动时，更能显示出f p g a c p l d的优势。电路设计人员使用f p g a c p l d 进行电路设计时，不需要具备专门的i c ( 集成电路) 深层次的知识，f p g a c p l d 软件易学易用，可以使设计人员更能集中精力进行电路设计，快速将产品推向市场。2f p g a c p l d 技术2 1 2f p g a c p l d 器件结构2 1 2 1 查找表的原理与结构基于查找表( l o o k - u p 。t a b l e ) 结构的p l d 芯片我们称之为f p g a 如a l t e r a 的a c e x 、a p e x 系列，x i l i n x 的s p a r t a n 、v i r t e x 系列等1 1u j 。查找表简称为l u t ，l u t 本质上就是一个r a m 。目前f p g a 中多使用4 输入的l u t ，所以每一个l u t 可以看成一个有4 位地址线的1 6 x l 的r a m 。当用户通过原理图或h d l 语言描述了一个逻辑电路以后，p l d f p g a 丌发软件会自动计算逻辑电路的所有可能的结果，并把结果事先写入r a m ，这样，每输入一个信号进行逻辑运算就等于输入一个地址进行查表，找出地址对应的内容，然后输出即可。下面是一个4 输入与门电路用查找表实现逻辑功能的例子：实际逻辑电路l u t 的实现方式。地址钱l输出i 量p 一。u t!1 6 x 1 圳；ig a f f )ia ，c ，d 输八逻辑输出地址r a m 中存储的内容0 0 0 000 0 0 000 0 0 l00 0 0 loool l l lll l l l1我们以图2 1 所示电路为例，进一步说明基于查找表结构的p l d 实现逻辑电路的原理。a ，b ，c ，d 由p l d 芯片的管脚输入后进入可编程连线，然后作为地址线连到到l u t ，l u t 中已经事先写入了所有可能的逻辑结果，通过地址查找到相应的数据然后输出，这样组合逻辑就实现了。该电路中d 触发器是直接利用l u t后面d 触发器来实现。时钟信号c l k 由i o 脚输入后进入芯片内部的时钟专用通道，直接连接到a日cdc t r图2 1 需要实现的逻辑电路触发器的时钟端。触发器的输出与o 脚相连，把结果输出到芯片管脚。这样p l d就完成了图2 1 所示电路的功能( 以上这些步骤都是由软件自动完成的，不需要人为干预) 。9重庆大学硕士论文这个电路是一个很简单的例子，只需要一个l u t ；b i i 上一个触发器就可以完成。对于一个l u t 无法完成的的电路，就需要通过进位逻辑将多个单元相连，这样p l d就可以实现复杂的逻辑。由于l u t 主要适合s r a m 2 1 2 艺生产，所以目前大部分f p g a 都是基于s r a m 工艺的，而s r a m 工艺的芯片在掉电后信息就会丢失，一定需要外加一片专用配置芯片，在上电的时候，由这个专用配置芯片把数据加载到f p g a 中，然后f p g a 就可以正常工作，由于配置时间很短，不会影响系统正常工作。也有少数f p g a 采用反熔丝或f l a s h 工艺，对这种f p g a ，就不需要外加专用的配置芯片。2 1 2 2 基于查找表的f p g a 的结构鳓勰幽2 2x i l i n xs p a r t a n - i i 芯片内部结构x i l i n x 公司的f p g a 器件s p a r t a n i i 系列的基本结构如图2 2 所示。其主要包括5 个可配置部分：( 1 )可配雹逻辑块( c l b s c o n f i g u r a b l e圈2 3s p a r t a n 1 i 系列c l b 一个s l i c e 的原理框图l o g i cb l o c k s ) ，用于实现大部分逻辑功能；( 2 ) 在c l b s 的四周分布着可编程的输入输出块( 1 0 b s i n p u t o u t p u t b l o c k ) ，提供封装引脚与内部逻辑之间的连接接口；( 3 )丰富的多层互连结构的可编程连线( 未表示出) ；( 4 ) 片上的随机存取块状r a m ( b l o c kr a m ) ；( 5 ) 全数字式延迟锁相环( d l l ) 时钟控制块，与每个全局时钟输入缓冲器相连，该闭环系统确保时钟边沿到达内部触发器与其到达输入引脚同步，有效地消除时钟分配时的延迟。在s p a r t a n i i 中，每个c l b 由相似的2 个部分