（电路与系统专业论文）1024点基4fft处理芯片及接口设计研究.pdf

摘要 摘要 快速傅立叶变换( f f t ) 是数字信号处理领域核心算法之一，可以通过f p g a ，d s p 和 a s i c 等多种方式来实现硬件设计。f f t 专用芯片广泛应用于宽带o f d m 系统，a d s l 调制 器，数字电视，雷达及声纳信号处理系统等，在高精度高速实时性环境更是首要选择。因此 高性能专用f f t 处理芯片设计具有重要意义。 本文研究的1 0 2 4 点f f t 处理芯片设计是基于t s m c0 1 8 i l mc m o s 标准单元库的半定 制a s i c 设计，采用自项向下与自底向上相结合，以关键模块为设计对象的设计方法，使用 v e r i l o gh d l 描述系统，在m o d e l s i m 、d e s i g nc o m p i l e r 和a s t r o 等电子设计自动化( e d a ) 工具中完成。 在高速度要求下，文章分析了基2 算法与基4 算法的优缺点，并在此基础上分析了原 位存取运算和固定结构运算的原理，最终确定采用基_ 4 算法，固定结构设计系统。文章分 析了数字系统的基本结构和高速a s i c 设计的方法，在此基础上，将本设计整个系统划分为： 蝶形运算单元，系统控制器，运算数据存储与寻址系统，旋转因子存储与寻址以及数据总线 交换器。其中蝶形单元是关键模块，采用全流水线结构，控制系统采用顶层控制和低层控制 相结合的方式。 系统架构和各个模块采用v e r i l o g 实现r t l 编码，并完成相应的功能仿真，然后经过 f p g a 验证证明了设计的正确性和硬件可实现性。按照设计要求，使用t s m c0 1 8 i t m 工艺 的标准单元库，通过d e s i g nc o m p i l e r 工具对整个系统进行逻辑综合，并完成相关的形式验 证和静态时序分析。综合结果满足设计目标要求，系统能够稳定运行于1 2 0 m h z ，完成1 0 2 4 点浮点复数f f t 运算需要1 1 6 i t s 。综合后使用a s t r o 工具完成布局布线。文章最后提出了对 接口改进的设想。 本文通过对1 0 2 4 点f f t 处理芯片的设计研究，积累了大量设计经验，为实现更高性能 的f f t 处理器打下坚实的基础，同时掌握了半定制方式设计芯片的整体过程，为a s i c 芯片 开发做好充足准备。 关键字：基_ 4f 兀 算法，固定寻址结构，蝶形单元，浮点加法器，浮点乘法器，b o o t h 编码， 逻辑综合，布局布线，i o 口设计 a b s t r a c t f a s tf o u r i e rt r a n s f o r m ( f f t ) i so n eo ft h em o s ti m p o r t a n tt r a n s f o r ma l g o r i t h m si nd i g i 【t a l s i g n a lp r o c e s s i n gf e l d i tc a nb ei m p l e m e n t e db yd s p , f p g a a n da s i c a m o n gt h e s e ，a s i cf f t p r o c e s s o ri sw i d e l yu s e di nw i d e b a n do f d ms y s t e m ，a d s lm o d u l a t o r , d i g i t a lt v , e s p e c i a l l yi n t h eo c c a s i o n st h a tn e e dh i g hp r e c i s i o n ，h i g h s p e e da n dh i g hr e a l - t i m e ( r a d a ra n ds o n a rs y s t e m ) s o i ti sv a l u a b l et or e s e a r c ht h eh i g hp e r f o r m a n c ef f tp r o c e s s i n gc h i p 10 2 4 - p o i n tf f tc h i pi nt h i sp a p e ri sd e s i g n e di nt h ew a yo fc o m b i n i n gt o p - d o w na n d b o t t o m - u pd e s i g nm e t h o d s ，b a s e do nt s m c0 18 mc m o ss t a n d a r dc e l l sl i b r a r ys e m i - c u s t o m a s i cd e s i g n t h ek e ym o d u l e sa r ed e s i g n e ds p e c i a l l ya n df i n a l l ym a k eu pt h ew h o l es y s t e m t h e c h i pi sd e s c r i b e di nv e r i l o gh d l ，a n df i n i s h e db ye d a ( e l e c t r o n i cd e s i g na u t o m a t i c ) t o o l s ，s u c h a sm o d e l s i m ，d e s i g nc o m p i l e r , a n da s t r oe t c r a d i x - 4f f ta l g o r i t h mi sa d o p t e dt oa c h i e v eh i g hp e r f o r m a n c e ，a f t e rc o m p a r i n gw i t hr a d i x - 2 f f ta l g o r i t h m t h e nt h e p a p e ra n a l y s e st h ei n - p l a c em o d ef 兀p r o c e s sf l o w a n dt h e f i x - a r c h i t e c t u r ef f rp r o c e s sf l o w a n dt h el a t e ri sa p p l i e di nt h ec u r r e a tf 兀p r o c e s ss y s t e m t h e n t h eg e n e r a la r c h i t e c t u r eo fd i g i t a ls y s t e ma n dt h ew a y sf o rh i g h - s p e e da s i ca r ep r e s e n t e d b a s e d o nt h e s e ，t h ep r o c e s s o ri ss p e c i f i e da n dd i v i d e di n t of i v em o d u l e s ：b u t t e r f l yu n i t ，s y s t e mc o n t r o l m o d u l e ，o p e r a t i o nd a t as t o r a g ea n da d d r e s s i n gs u b s y s t e m , t w i d d l ef a c t o rs t o r a g ea n d a d d r e s s i n gs u b s y s t e m ，a n db u ss w i t c h a m o n gt h e s em o d u l e s ，t h eb u t t e r f l yu n i tu s 伪p a r a l l e l p i p e l i n e da r c h i t e c t u r et om o e tt h ed e s i g nr e q u i r e m e n t s t h ew h o l ef f ts y s t e mi sd e s c r i b e di nv e r i l o gh d l , a n ds i m u l a t e di t sf u n c t i o ni nm o d e l s i m a f t e rt h a t ，t h es y s t e mi sv e r i f i e dt h r o u g hf p g a i tc o n f i r m si t sc o r r e c t n e s si nf u n c t i o na n dt h e c e r t a i n t yo fb e i n gi m p l e m e n t e di nh a r d w a r e t h e na c c o r d i n gt or e q u i r e m e n t s ，t h ef f t s y s t e mi ss y n t h e s i z e di nt h ed e s i g nc o m p i l e r , b a s e do nt s m c 0 18 i t mc m o ss t a n d a r d c e l l sl i b r a r y f o l l o w i n gt h a t ，s t a t i ct i m i n ga n a l y s i si np r i m e t i m ea n df o r m a lv e r i f i c a t i o ni n f o r m a l i t ya r ec o m p l e t e d 西er e p o r td e m o n s t r a t e st h a tt h es y s t e ma c h i e v e st h er e q u i r e m e n t so f d e s i g n i tc a no p e r a t es t a b l ya t1 2 0 m h z 、析t l lp r e c i s e l yo u t p u td a t aa n d1 0 2 4 - p o i n tf l o a t i n g - p o i n t c o m p l e xn u m b e rf f tc a nb ef i n i s h e di nl1 6 s a f t e rd c ，t h eg a t e - l e v e ln e f l i s ti ss e n ti n t oa s t r o f o rp l a c e m e n ta n dr o u t i n g f i n a l l y , am e t h o di sp r o p o s e dt oi m p r o v et h ei n t e r f a c eo fc h i p o nt h eb a s i so fd e s i g na n dr e s e a r c ho ft h e10 2 4 - p o i n tf f tc h i p ，t h ed e s i g n e rh a sa c c u m u l a t e d l o t so fe x p e r i e n c e ，a n df o u n d e ds o l i db a s eo fi m p l e m e n t i n gh i g h e rp e r f o r m a n c ef f fp r o c e s s o r ；, a t t h es a m et i m e , t h ed e s i g n e rh a sm a s t e r e dt h ew h o l ed e s i g nf l o wo fs e m i - c u s t o ma s i cd e s i g n ， m a k i n gf u l lp r e p a r a t i o n sf o rd e v e l o p i n ga s i cc h i p k e yw o r d s ：r a d i x - 4f f ta l g o r i t h m ，f i x e da d d r e s ss t r u c t u r e ，b u t t e r f l yu n i t ，f l o a t - p o i n t a d d e r , f l o a t - p o i n tm u l t i p l i e r , b o o t he n c o d e ，l o g i cs y n t h e s i s ，p & r ，f oi n t e r f a c ed e s i g n h i 图片索引 图2 1 图2 - 2 图2 3 图2 - 4 图3 1 图3 2 图3 3 图3 4 图3 5 图3 - 6 图4 1 图4 2 图4 3 图4 - 4 图4 5 图4 - 6 图4 - 7 图4 8 图4 - 9 图4 1 0 图4 一l l 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 _ 1 6 图4 - 1 7 图4 1 8 图4 1 9 图4 - 2 0 图4 2 1 图4 - 2 2 图4 2 3 图4 2 4 图4 - 2 5 图4 - 2 6 图4 - 2 7 图4 2 8 图4 - 2 9 图4 3 0 图片索引 基2 d n 蝶形单元4 基_ 4 d 1 1 r 蝶形单元6 基- 2 d i t4 点f f t 运算7 同定寻址结构的6 4 点f f t 算法流图8 数字系统基本构成。l1 f f t 处理器架构1 2 流水线设计。二1 3 非流水线设计一1 3 串行处理系统1 4 并行处理系统1 4 i e e e 7 5 4 的单精度浮点数格式1 5 基_ 4 蝶形单元架构1 7 浮点加法器运算流程1 7 2 4 位选择移位器结构1 8 2 6 位加法器设计1 9 2 4 位分段查询结构。2 0 浮点加法器端口连接2 0 浮点加法器功能仿真结果2 0 浮点乘法器操作流程2 l 乘法运算基本原理图2 2 尾数时序乘法器2 2 浮点乘法器端口连接2 3 浮点乘法器功能仿真结果2 4 r a m 存储器寻址架构。2 4 r a m 写地址产生器2 6 r a m 寻址模块端口关系图2 7 r a m 地址仿真( 一) 2 7 r a m 地址仿真( 二) 2 8 r a m 地址仿真( 三) 2 8 旋转因子实部和虚部波形图2 9 r o m 地址产生器结构3 0 系统状态转移图3 2 系统控制器顶层模块3 3 系统控制器仿真图3 4 数据总线交换器顶层模块3 4 f f t 设计端口关系3 6 f f t 运算采样点波形3 6 f f t 运算结果实部波形图3 7 f f t 运算结果虚部波形图3 7 f f t 运算结果模值比较。3 7 v i l 东南大学硕士学位论文 图5 1 图5 - 2 图5 3 图5 _ 4 图5 - 5 图5 石 图5 7 图5 8 图5 - 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图5 1 5 图5 1 6 图6 - l 图6 - 2 图6 3 图6 _ 4 图6 - 5 图6 6 图卯 图6 - 8 图6 - 9 f f r 处理器验证平台d e 2 开发板3 9 f f t 处理器f p g a 验证方案项层框图4 l f f t 处理器f p g a 设计顶层框图。4 l f f t 处理器f p a g 验证结果一4 l s y n o p s y sd c 逻辑综合过程示意图4 2 速度、面积和功耗的相互关系。4 3 d c 综合面积报告4 5 d c 综合功率报告4 5 静态时序分析图例。4 7 静态时序分析结果4 9 形式验证结果：5 0 物理综合流程图5 0 p a d 设计规则图5 2 宏单元布局5 4 常用的两个时钟树网络5 4 f f t 芯片布线结果5 5 芯片间采用并行方式连接关系图。5 7 芯片问连线的耦合电容。5 7 系统同步结构图：5 8 源同步结构图5 8 自同步结构图5 8 s e r d e s 结构图6 0 4 ：1 复接器串行结构图。 2 ：1 复接器并行结构图6 0 4 ：1 复接器树形结构图6 l v i 表格索弓 表格索引 表l基2 和基4 算法运算量比较7 表2m e e 7 5 4 点精度浮点数保留字。1 6 表3 浮点加法尾数有效位列表。1 9 表4 设计仿真与m a t l a b 仿真误差比较2 l 表5 改进b o o t h 算法表2 3 表6 浮点乘法器运算结果。2 4 表7r a m 地址产生实例2 6 表8 旋转因子地址产生规律3 0 表9 系统状态说明3 l 表1 0 系统控制器状态转移条件表3 2 表l l 统控制器输入输出信号定义3 3 表1 2 数据总线交换器输入输出信号定义3 5 表1 3 数据总线交换器交换功能说明3 5 表1 4 高速1 0 2 4 点f f r 处理器输入输出信号定义3 6 表1 51 0 2 4 点f f t 运算部分结果3 8 表1 6d e 2 各部件参数性能3 9 表1 7f f t 综合约束4 4 i x 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：导师签名艘日期：g ! 翌 第一章绪论 第一章绪论 1 1f f t 算法与硬件实现的发展状况 傅立叶变换是一种源于数学研究的理论，早期的傅立叶变换是数学分析的一个分支。十 八世纪法国数学家傅立叶提出以2 兀为周期的周期函数脚可以展开成为无限多个正弦函数 和余弦函数的和，也就是著名的傅立叶级数分解【l 】，求解傅立叶系数的过程就是傅立叶变换。 随着这一理论的完善和发展，傅立叶级数又被从以h 为周期的周期函数推广到任意周期的 周期函数，接着又从周期函数推广到非周期函数，并产生了傅立叶积分1 2 1 。 随着电子技术和集成电路技术的飞速发展，数字信号处理已广泛应用于语音、图像处理， 通信和多媒体等各个学科领域，傅立叶变换开始在这些领域中得到广泛应用。随着超大规模 集成电路及计算机技术的发展以及各种数字硬件信号处理方法的，“泛应用，出现了用于数字 信号即离散时间信号处理的离散傅立叶级数变换【3 1 。离散傅里叶变换( d f t ) 在现代数字信 号处理的各个领域应用极为广泛，成为很多数字信号处理器的核心部分。 一个n 点序列的离散傅立叶变换要进行n ( n 一1 ) 次复数加法和2 次复数乘法，并且 随着变换序列长度增加离散傅立叶变换的运算量将急剧增加【4 】。因此，为了推动离散傅立叶 变换在现代数字信号处理领域中更为广泛的应用，人们通过对离散傅立叶变换计算的大量深 入研究提出很多快速离散傅立叶变换f f t ( f a s tf o u r i e r t r a n s f o r m ) 算法。c o o l e y 根据t u k e y 的想法于1 9 6 3 年编写了第一个f f r 算法程序【5 】，1 9 6 5 年他们在计算数学上发表了著名 的论文【6 】。c o o l e y - t u k o y 的基- 2 h 可算法将运算量从正比于2 减少为正比于n l o g ，n ，从 理论上解决了d f t 计算运算量大的问题。此后又有许多学者提出了许多不同的算法，包括 基4 f f t 算法、分裂基算法、主因子分解算法、w i n o g r a d d x 算法等【6 。丌。其中，基- 2 和基 _ 4 算法由于其结构相对简单、规整，便于硬件实现，是目前使用较多的应用于a s i c 实现的 f f t 算法。分裂基算法、主因子分解算法、w i n o g r a d 卟胪算法虽然在运算量上逼近了最佳 值，但由于其较为复杂，主要应用于软件实现f f t 运算。 早期的快速傅立叶变换( f f t ) 算法可通过在通用计算机中运行相应的软件来实现，而随 着超大规模集成电路技术的发展，f f t 算法还可采用数字信号处理器( d s p ) ，现场可编程门 阵歹i j ( f p o a ) 以及专用f f i 处理器芯片等硬件来实现【6 8 】。d s p 处理器是一种采用特殊的软硬 件结构，专门用于实时快速地实现各种数字信号处理算法的专用微处理器，可以快速完成信 号的f f t 变换。而专用f f t 处理器芯片通过具有更高系统效率的硬件电路来进行f f t 变换 处理，因而具有比通用d s p 处理器更加快速，节能，便携的特点，适用于某些对数字信号 处理实时性要求更高的场合。在宽带o f d m 系统，a d s l 调制器，数字电视，雷达及声纳 信号处理系统，手持无线接收装置等具有低功耗，高速度，便携性特点的数字系统设计中， 东南大学硕士学位论文 专用f f r 处理器芯片已经成为其中的关键部件，其性能直接关系到整个系统的处理速度。 由此可见，设计高速度，大数据吞吐量的专用f f t 处理芯片f 9 l o 1 1 1 ，具有很高的实用价值以及 广泛的应用前景。 1 2 文章主要内容 本论文介绍了基于t s m c 0 1 8 i _ t m 工艺的1 0 2 4 点f f t 芯片设计，该处理芯片时钟可以稳 定运行于1 2 0 m h z ，能够在2 5 s 内完成1 0 2 4 点6 4 b i t 浮点数f f t 运算。 论文内容安排如下： 第一章是引言。简要介绍f f t 算法发展状况，以及f f t 运算硬件实现的发展状况和研 究目的意义。 第二章分析了f f t 算法原理，包括两种算法优缺点比较和两种运算流图的优缺点，确 立固定结构算法流图为f f t 芯片运算思路。 第三章阐述了数字系统设计的基本架构，并据此提出了本设计的结构，简要介绍了高性 能半定制数字a s i c 设计常用设计方法，是该f f t 处理芯片架构的设计思想。 第四章详细介绍了f f r 芯片架构中的处理模块划分，完成r t l 实现和功能仿真。 第五章介绍了n 丌处理器的f p g a 验证，并完成逻辑综合与版图综合。 第六章对f f t 芯片接口提出改进设想。 最后一章总结前五章内容，回顾整个流程的回顾以及对该研究方向的展望。 2 第二章f f t 算法原理及流图分析 第二章f f t 算法原理及流图分析 离散傅立叶变换d f t 【1 0 ( d i s c r e t ef o 岫矗e rt m s f o 他) 满足以下关系式： n - i 石( 后) = d f t “，1 ) 】= ，l 渺方， 七= o ，1 ， n - 1 ( 2 1 ) n = 0 x ( 七) 的离散傅立叶逆变换( r d f t ) 为 缸刀) = i d f t x ( 露) 卜丙1 缶n - ix ( 后) 陈勋， n = 。，l ，n - 1 ( 2 2 ) 式中，= e 。为旋转因子，x ( n ) 是一个长度为的有限长序列，称为d f t 变换区 间长度。通常称( 2 1 ) 式和( 2 2 ) 式为离散傅立叶变换对。 一般石伽) 、嘴均为复数，每计算一个x ( 尼) 值，需要作n 次复数乘法，n 1 次复 数加法。总共有个x ( k ) 值，所以总的计算量有2 次复数乘法，确i n ( n 一1 ) 次复数加法。 若n l ，则复加数也近似为n 2 2 , 4 , s , 7 1 。i d f t 与d f t 相比除了多乘系数1 n 外，具有相 同的运算形式，所以与d f t 有相同的运算量。 可以看出，离散傅立叶变换的正、反变换，其复乘数与复加数都与2 成正比。当较 大时。所需运算量是很大的。在此后出现的众多算法中，基2 算法和基4 算法比较简单， 结构规整，便于a s i c 实现。本文把基2 与基- 4 f f t 算法作为主要讨论对象。 2 1 基2d i tf f t 算法 当输入序列x ( n ) 长度为n = 2 m ，则该序列的离散傅立叶变换表达式为 - 1 x ( 尼) = x t , , ) w y 。在按时间抽取的基二f f t 运算中，首先将如) 按n 的奇偶分为两组 n f f i o ：芝工( 2 r ) 暇膺+ 孵窆z ( 2 ，+ 1 ) 峨砖 ( 2 3 ) 因为 = e - j 努姒= 矿镌糠= 乃寸2 ( 2 4 ) 所以巾) = 妯r = 02 缈+ 形? 美j ( 2 r + 1 ) 形f 吲m 形七) ( 2 5 ) 3 暇 d +厂2 ，l x 箸乙脚 + 睹 崂 、， r2 ，l x 譬乞脚 = 、， 七 ，_ 一 x 东南大学硕士学位论文 式中g ( 尼) 、日( 足) 分别为： g ( 胪萋坤r ) 哼 ( 2 6 ) 日( j j ) = 艺x ( 2 ，+ 1 ) 嘭 ( 2 7 ) g ( 助，刀为两个n 2 点序列的d f r ，g 仅包含原序列中偶数点序列，觑幼则仅包含 原序列中奇数点序列，它们的周期均为n 2 ，因为嘻= 一1 ，所以孵+ 譬= 一磷，考虑到 g ( d ，日( 后) 的周期特性，得到 x ( d = g 他) + 嘭以后) 后= 0 i ，u 一1 2 ( 2 8 ) x f 七+ 冬1 ：g ( 七) 一砾日( 七) 七：0 ，l ，譬一l ( 2 9 ) 二 二 可见，一个点序列缸刀) 的d f t 变换可以从两个n 2 点序列的d f t 变换求出。由式( 2 8 ) 和( 2 9 ) 可知，在由两个n 1 2 点序列d f t 变换求取一个点序列d f t 变换的合成运算中，两 个胞点序列中每两个对应点都可通过形式如彳= 彳+ b w ，b = a b w 运算求取 点d f t 序列中间隔为n 2 的两点。这种形式的运算通常被称为蝶形运算。由于该运算表达 式中一刀形和曰形两个乘法仅相差一个负号，所以一个蝶形运算可由两次加减法和一次乘 法完成，蝶形运算单元如图2 1 所示： a b 图2 1 基2 d i t 蝶形单元 a + b w a b w 图2 1 蝶形运算单元示意图的左边两支为运算输入数据，中间以一个圆点表示加减运 算，右上支为运算相加输出，右下支为相减输出。如果在某支路上信号需要进行乘法运算， 则将相乘的系数标在箭头边，表示信号与系数的相乘。可见，其中蝶形运算旋转因子与左下 支输入数据相乘后，再与左上支输入数据相加减得到蝶形运算单元的两个输出数据。 按照上述方法，继续对两个长度为n 2 点序列作进一步分解，即对g ( 七) 和日( 七) 分别 进行按奇、偶分解，从而通过对4 个长度为n 4 点序列的d f t 变换结果进行合成得到两个 n 2 点序列的d f t 变换结果。依次类推，可以将4 个长度为n 4 点序列各自按奇偶继续分解 下去，当序列逐级分解为1 7 2 个2 点序列后，再对这b l 2 个2 点序列分别按奇偶分解即可得 到n 2 对单点序列，其中每对单点序列可通过一个蝶形运算合成得到一个两点序列的d f t 4 第二章f f t 算法原理及流图分析 变换结果，其运算表达式如下： x ( 七) = g ( 后) + 乃刍2 剃日( 尼) k = o ( 2 1 0 ) x ( k + i ) - g ( k ) 一嚷日( 后) k = o ( 2 1 1 ) 接下来，根据前面的分析，可将每两个对应的两点序列d f t 变换结果合成为一个四点 序列的d f t 变换结果，以此类推，直至将按奇、偶分解后的序列逐级合成得到点序列的 d f r 交换结果。实际上，为求取点序列d f t 变换结果而进行的合成过程是之前序列按奇、 偶分解过程的逆过程。 2 2 基4d i tf f t 算法 对于n 点f f t , 根据d f t 的算法原理可得【5 ，6 ，刀： n | “n | “n | “n | “ = x ( 4 r ) 萨+ x ( 4 r + 1 ) 咿呻+ 竹+ 2 ) 垆+ 水+ 3 ) 咿 r = or = or - - - or = o w hn n “n | “ = 嘛十竹+ 1 ) 咏磷+ 水+ 2 ) 咏嘴+ 水+ 3 ) 喻嘭 p 旬r - - or=o扣旬 = x o ( 动+ 墨( d 磷+ 五嚼七+ 五( 动略 ( 2 1 2 ) 在式中k 司、l 、2 ”n - l ，凰( 忌) ，五( 后) ，置( 七) ，置( 尼) 为分解的n 4 点的d f t ， x ( 4 r ) 啉 x ( 4 r + 1 ) 。啉 x ( 4 r + 2 ) 。啉 x ( 4 r + 3 ) 。觋 考虑到的规律特性，秽4 = 一，赡4 = - l ，孵n 4 = ，职舭= 1 可以得到公式： 5 ( 2 1 3 ) 班稿睦乙艘脚 = = | i = 、!l 凰 墨 五 墨 东南大学硕士学位论文 f 义( 尼) 2 x o ( k ) + 爿l ( 七) 硝+ 爿2 ( 七) 蹦。+ 五3 ( ”蚴。 ix ( k + ) = x o ( k ) 一尚( 尼) 孵一置( 尼) 暇+ 粥( 后) 职 i x ( k + ) = x o ( k ) 一五( 后) 璐+ 五( 尼) 昭2 一五( 尼) 暇 【x ( k + 3 ) = x o ( k ) + 瞄( 后) 孵一弼( 后) 昭七一竭( 后) 硝 其中 k = 0 二n 4 1 ，= e 一2 石； 由此得到基4 f f t 基本蝶形运算如图2 2 所示： x ( k ) x ( k + n 4 ) x ( k + n 2 ) x ( k + 3 n 4 ) ( 2 1 4 ) 图2 2 基- 4 0 1 1 蝶形单元 由图可以看出，进行一次基4 蝶形运算需要3 次复数乘法和8 次复数加法。 按照上述方法，可将第一次变换分解得到的四个n 4 点子序列继续分解，通过式( 2 1 2 ) 、 ( 2 1 3 ) 和( 2 1 4 ) 所示子序列可以进一步各自分解得到四个n 1 6 点子序列。同理，通过这四 个n i l 6 点子序列的d f t 变换结果可以获得n 4 点序列的d f t 变换结果。依次类推，n = 4 m 点序列经m 1 次蝶形变换分解后，可得到n 4 个4 点子序列，而每个4 点子序列只需一个 蝶形运算即可得到其d f t 变换结果，然后再将每个4 点子序列d f t 变换结果按一定规律依 式( 2 1 2 ) 、( 2 1 3 ) 和( 2 1 4 ) 所示的方法进行逐级合并，即可得到一个n 点序列的d f t 变换 结果。 对n 点数据进行基4 f f t 运算，每级都有n 4 个蝶形单元，每个蝶形都要旋转因子玎碡， 玎铲，阿铲，因此只需要确定k 值就可以得到一组旋转因子。在第一级运算中，k 只有一个 值k - - - 0 ，旋转因子值为1 ，所以整个第一级蝶形运算只需要进行复数加法运算，第二级k 有 4 个值，第三级k 有1 6 个值，依次类推，第m 级旋转因子个数是和一1 ，直到最后一级有 n 4 个旋转因子。在固定结构的运算流图中，将0 - - n 4 一l 倒序输出后，前4 脚一1 个值即为k 值， 每进行一个蝶形运算，k 改变一次，直到和一1 个旋转因子结束再重新进行下一轮循环，直到 n ，4 个蝶形运算结束，完成一级蝶形运算。 2 3 基2 d i t 算法与基4 d i t 算法对比 基2 f f t 和基4 f f t 算法，算法应该具有最少的运算量、结构规整、易实现、可同址运 算、内部数据不需重排等特点。由于乘法运算时间和所要的硬件资源较加法器多得多，所以 6 第二章n 叩算法原理及流图分析 一般以乘法次数作为运算量的度量。比较d i t 基- 2 与d i t 基4 f f t 算法的蝶形运算单元， 同样对4 点进行处理，4 点f f t 变换采用基2 法如图2 3 所示，由此得到公式( 2 1 5 ) ，可 以知道d i t 基- 2 算法需两级进行4 次复数乘法和8 次复数加法。 采用基- 2 d i t 算法实现4 点f f t 运算如图2 3 所示： 图2 - 3 基- 2 d i t 4 点f f t 运算 a = a + b w 1 + ( c + d 形2 ) 3 b 7 = a b w 1 + ( c d w 2 ) 形七4 c = a + b w n 一( c + d w 2 ) 七3 d 7 = a - b w 射- ( c d w 2 ) 形 ( 2 1 5 ) 由公式( 2 1 4 ) 知道d i t 基_ 4 算法需3 次复数乘法与8 次复数加法，另外还需一次乘以 - i ，在电路中只需对实部与虚步进行互换即可。两种运算方法运算量7 1 如表1 所示： 表1 基2 和基4 算法运算量比较 n 基2 h 耳 基- 4 f 兀 实数乘法次数实数加法次数实数乘法次数实数加法次数 2o4| 401 6 o1 6 845 2| 1 62 81 4 82 4 1 4 4 6 43 3 29 6 42 6 49 2 0 2 5 62 3 1 65 3 8 01 8 0 0 5 0 8 0 1 0 2 41 3 3 2 42 7 6 5 21 0 2 4 8 2 5 9 4 4 4 0 9 66 9 6 4 41 3 5 1 7 25 3 2 5 6 1 2 6 9 2 9 相对来说，基2 f f r 算法结构规则，易实现，但乘法次数就多，所以速度不快；基- 4 f f t 算法虽然结构复杂，但乘法次数明显减少，因而速度有很大提高，同样时钟频率下速度是基 - 2 算法的2 倍。在那些中小型点数，实时性要求不是很高的场合，基2 算法比较适合，但 在大点数下，基- 4 f f t 算法具有明显优势。同时基_ 4 算法较d i t 基2 算法节省运算资源【l l 】， 结构更能实现低功耗。综合考虑，本文采用基- 4 f f t 算法。 7 a b c d a b c d 东南大学硕士学位论文 2 4 固定寻址的f f t 运算流图 为直观表示h 叮变换运算流程，可采用f f t 算法流图来表示每级蝶形变换中数据序列 的排列方式以及蝶形运算的数据流向。各级蝶形变换中序列数据点序号的不同排列方式及数 据蝶形运算顺序不同对应于不同的f f r 算法流图，而不同的f f t 算法流图则决定了f f t 处 理芯片设计中不同的数据存取寻址方式。常见的运算流图有两种，原位存取运算流图和固定 结构流图。 原位存取计算是指每一级蝶形变换中，当数据从存储器读出并输入到蝶形运算单元后， 蝶形运算单元输出的运算结果将存储到数据读出的同一存储单元中。与这种运算流图相对应 的f f t 变换硬件数据处理器由于每次运算为原位存取，仅使用一组大小等于输入序列数的 存储器即可完成数据读出及运算结果回存的循环操作，因此节省了存储器面积。这种运算结 构的缺点在于：每级变换中数据存取方式各不相同，增加了f f t 处理器寻址电路设计及控 制的复杂度，随着处理序列点数的增加，复杂度将显著增加，从而影响系统工作稳定性。根 据f f t 算法原理，原位存取f f t 算法流图中输入数据序列按顺序排列，输出结果为倒序排 列。 本设计中采用了一种同定寻址结构的f f t 运算方法。以“点f f t 运算为例，分析固定 寻址结构的f f r 算法流图，如图2 4 所示，其中蝶形模块如图2 - 2 所示。固定结构f f t 运 算流图中，输入序列按顺序写入r a m 中，然后每隔1 6 点从r a m 中读出四个数据到蝶形 单元中进行运算，运算结果按顺序写入另一片黜蝴中。最后整个f f r 运算结果按倒序输出。 图2 - 4 固定寻址结构的“点f f t 算法流图 由图2 - 4 所示的固定寻址结构f f t 算法流图可见： 1 ) 该结构运算流图中每级蝶形变换数据存取方式相同，降低了寻址复杂度，提高了f f t 处 理器系统稳定性；同时由于蝶形单元的输入、输出不是存储在同一存储空间中，比原位 存取算法使用了更多的r a m 。 2 ) 旋转因子的寻址非常简单。第一级，只有一个旋转因子k - - 0 ，不需要复数乘法运算，只 8 第二章f f t 算法原理及流图分析 需复数加法运算即可；第二级，有4 个不同的旋转因子，为o 1 5 倒序输出的前4 个， 在进行蝶形运算时，按照顺序循环使用；第l 级，有4 工一1 个旋转因子。 9 第三章f f t 实现方案 第三章f f t 实现方案 3 1 通用数字处理器架构 现代集成电路规模、复杂度的急剧增加，使得设计面临巨大挑战。如何将设计映射到硬 件芯片上，很大程度上取决于功能本身，功能的变化性，使得设计思路的多样性。经过长期 经验总结，一个基本数字系统 1 2 , 1 3