（电路与系统专业论文）基于FPGA的32位浮点数据FFT及IFFT的设计与实现[电路与系统专业优秀论文].pdf

中山大学硕士学位论文 基于f p g a 的3 2 位浮点数据f f t i f f t 的 设计与实现 专业：电路与系统 硕士生：宋军江 指导教师：黄以华副教授 摘要 f f t i f f t 是时域信号与频域信号之间转换的基本运算，是数字信号处理的 核心工具之一，因此，它广泛地应用于许多领域。在数字化的今天，不论是在通 信领域还是在图像处理领域，对数字信号处理的速度、精度和实时性要求不断提 高。为满足不断提高的要求，国内外不断地推出各种f f t i f f t 处理器，主要处 理器有a s i c 、d s p 芯片、f p g a 等。由于f p g a 具有可反复编程的特点及丰富资源， 所以它受到广泛的关注。 本论文就是一种基于f p g a 实现浮点型数据的f f t 及i f f t 处理器，该处理 器使用a l t e r a 公司的s t r a t i xi i 系列的f p g a 芯片。它主要采用流水线结构， 这种结构可以使各级运算并行处理，对输入进来的数据进行连续处理，提高了运 算速度，满足了系统的实时性要求；另外处理器所处理的数据是3 2 位浮点型的， 因此它同时提高了运算的精度。 关键词：f i 丌，i f f t ，f p g a ，流水线，浮点型数据。 中山大学硕士学位论文 d e s i g na n di m p l e m e n t a t i o nf o r3 2 - b i tf l o a t i n g - p o i n t f f t i f f tb a s e do nf p g a m a j o r ：c i r c u i t sa n ds y s t e m s n a m e ： s o n gj u nj i a n g s u p e r v i s o r ：h u a n gy il h aa s s o c i a t ep r o f e s s o r f 】同f f tp r o c e s s o r sa r et h eb a s i co p e r a t i o n so f t h et r a n s f o r m i n gb e t w e e n s i g n a l so ft i m ef i e l da n df r e q u e n c yf i e l d a n di ti so n eo ft h em a i nt o o l sf o rd i 舀m l s i g n a lp r o c e s s i n g a sar e s u i t , i ti sw i d e l yu s e db ym a n yf i e l d s b u ti nn o w a d a y s ，t h e d e m a n d so fs p e e da n dp r e c i s i o na n dr e a lt i m eb e c o m em o r ea n dm o r eh e a v i e rn o t o n l yi nc o m m u n i c a t i o nb u ta l s oi m a g ep r o c e s s i n ga n ds oo n t os a t i s f yt h eh e a v y d e m a n d 。m a n yf n n 叩p r o c e s s o r sh a v eb e e ni n v e n t e dc o n s t a n t l ya th o m ea n d a b r o a d i tc o n c l u d e sa s i cp r o c e s s o r ，d s pc h i p s e t , f p g aa n ds oo n b u tf p g ah a s b e e nw i d e l yu s e df o ri t sf l e x i b l ep r o g r a m m a b l el o g i ca n dp l e n t yo fs o u r c e s t h i st h e s i ss t u d yak i n do fh i g l ls p e e df f l w p r o c e s s o rb a s e do nf p g a o f s t r a t i xi is e to fa l t e r ac o m p a n y i ta d o p t sp i p e l i n et or e a l i z et h ep r o c e s s o rs ot h a tt h e o p e r a t i o n so fe v e r ys t a g er u na tt h es a m et i m e t h a n k st ot h a tt h ep r o c e s s o rc a nd e a l w i t ht h ei n p u td a t ac o n t i n u o u s l ya n ds a t i s f yt h er e a lt i m ed e m a n d i na d d i t i o n ，t h ed a t a p r o c e s s e di s3 2b i t sf l o a t i n g - p o i n tt y p ea n di ti m p r o v e st h ep r e c i s i o no fp r o c e s s i n g r e s u l t k e yw o r d ：f f 嘎i f f t , f p g a , p i p e l i n e ，f l o a t i n g - p o i n t 中山大学硕士学位论文 第1 章绪论 1 1研究的背景与意义 快速傅里叶变换，反变换( 阡t 腰f r ) 是d f t i d f t 的快速算法，是把数据 从时域到频域从频域到时域变换的基本运算它是数字谱分析的必要前提，是 数字信号处理的核心工具之一因此它在通信等数字信号处理领域乃至其他众多 学科领域中都有着广泛的应用。i t 】 随着计算机科学的高速发展，很多领域对f f t i f f r 运算速度、精度及实时 性的要求越来越高。如数字语音编码、雷达信号处理、声纳信号分析、数字滤波、 射电干涉等应用领域。传统的f f r i f f r 运算已不能满足系统的更高要求：由软 件实现的f f t i f f r 运算速度慢，不能满足实时高速的系统性能要求，而专用的 d s p 芯片由于处理速度慢也不能满足某些更高速的要求，如a d 公司的2 1 0 6 x 系列d s p 实现1 0 2 4 点基2 复数f f r 运算大约需时0 s i n s ，已不能满足高速的要 求。 因此必须开发出能够实现高速f f t i f f r 的专用硬件，以满足不断提高的系 统要求。而现在高速发展的现场可编程逻辑阵列器件( f p g a ) ，使得硬件实现 f f r i f f t 运算变为可能。 本论文研究一种f f r i f f r 专用硬件的具体实现方法，并设计一个硬件系统， 即f f t i f f f 处理器。该f f r i f f r 处理器整体结构采用流水线型，进行3 2 位浮 点型数据的复数运算。采用流水线结构可以提高运算速度，3 2 位的浮点型复数 运算可以提高运算的精度，从而满足系统要求。 1 2国内外的研究现状 中山大学硕士学位论文 自从2 0 世纪6 0 年代c o o l e y - t u k e y 快速傅里叶变换( f f t ) 算法发表以来， 国际上对数字信号处理理论的研究已经非常成熟，但实现的方法多是以软件为 主；而到了2 0 世纪7 0 、踯年代，随着集成电路和计算机科学技术的发展，使数 字信号处理的硬件实现变为可能，从而使数字信号处理有了更快的发展 目前国际上，以f p g a 芯片生产商为主的公司在基于f p g a 设计f f t 的综 合研究方面处于领先地位。如x i l i n x 公司推出了1 4 0 m h z 时钟频率下处理速度 达到1 u s 的1 0 2 4 点f f t 处理模块，采用8 0 0 万门v h - t e xi i 器件实现；a l t e r a 公 司2 0 0 5 年推出了f f t 的坤核，使用此口核计算1 6 位1 0 2 4 点的f f t 仅需要 6 6 3 u s 。嘲但是这些口核售价很高，还不能在我国得到广泛应用 而我国的f p g a 起步较晚，和国外相比有一定差距，但进入2 1 世纪以来， 发展也非常迅速。我国的科研人员通过对先进的d s p 芯片的研究，已经研制出 一些高性能处理设备的解决方案，并在板级p c b 设计方面取得一定的成果，积 累了宝贵的经验如我国某电子技术研究所研制的d s p 雷达数字信号处理通用 模块，是采用6 片a d s f 2 1 0 6 0 和大规模可编程器件构成通用处理模块l 国内某 所大学所研制的基于t m s 3 2 0 c 强2 0 1 的高速实时数字信号处理平台，实现了基2 的复数f f t ，允许输入数据的动态范围1 6 - b i t , 可以实现5 9 u s 内完成5 1 2 点的f f t ， 1 3 0 u s 内可以完成1 0 2 4 点的f f r 随着集成电路和计算机科学技术的不断发展，对数字信号处理系统的要求也 会不断的提高，因此，作为数字信号处理核心工具之一的f f t i f f r 也会不断地 向前发展。 1 3本论文的研究内容 本论文主要研究基2 浮点型数据f f f i f f t 的f p g a 实现，包括浮点型数据 运算标准与运算实现，f f r i f f r 设计与实现，以及c + + 语言的实现及验证。 各章内容分别为： 第一章概论 第二章f p g a 技术概述； 2 中山大学硕士学位论文 第三章快速傅里叶变换的算法研究 第四章浮点运算标准及实现 第五章n 啊唧整体结构设计 第六章f f t i f f t 的f p g a 设计与实现 1 4 本章小结 本章从研究快速傅里叶变换的背景及国内外研究现状来提出本论文的实际 意义。随着计算机科学及信息化的高速发展，在数字化的今天，对信号处理的要 求不断提高，尤其是对数字信号处理的要求，更是如此为满足这些不断提高的 要求，国内外都不断地研究实现数字信号处理的新方法，本论文试图利用f p g a 实现f f r a f f r 。 3 中山大学硕士学位论文 第2 章f p g a 技术概述 f p g a 是现场可编程逻辑门阵列( f i e l dp r o g r a m m a b l eg a t ea 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 r o ) 。 i l d 是一种专用的集成电路，内部有大量的门电路，可以通过软件编程来实 现内部门电路的不同连接，从而整个p l d 对外就可以实现一定的功能，而且还 可以通过软件编程来改变内部门电路的连接关系而改变p l d 的功能。使用p l d 来进行数字电路的开发，不仅可以大大缩短设计的开发周期，减少p c b 的面积， 而且还可提高系统的可靠性。因此，p l d 是电子设计领域里最有发展前途的一 项技术。 2 2f p g a c p l d 的发展历程 当今社会是数字化的社会，是数字集成电路广泛应用的社会。而数字集成电 路本身也在随着社会的不断发展而不断的更新换代，已由早期的电子管、晶体管、 小中规模集成电路，发展到现在的超大规模集成电路( v l s i c ，v e r yl a r g e s c a l e i n t e g r a t e dc i r c u i t ，几万门以上) 以及许多具有特定功能的专用集成电路。但是随 着微电子技术的发展，设计与制造集成电路的任务已不完全由半导体厂商独立承 担。而系统设计师们更愿意自己设计专用集成电路( a s i c ) 芯片，而且希望a i s c 的设计周期尽可能短，最好是在实验室里就能设计出合适的a i s c 芯片，并且立 即投入实际应用之中，因而出现了现场可编程逻辑器件( f p l d ) ，其中应用最广 4 中山大学硕士学位论文 泛的当是现场可编程门阵列( f p g a ) 和复杂可编程逻辑器件( c p l d ) 。 早期的可编程逻辑器件可分为三种：可编程只读存贮器( p r o m ) 、紫外线 可擦除只读存贮器( e p r o m ) 和电可擦除只读存贮器( e e p r o m ) 。由于它们结 构上的限制，它们只能完成简单的数字逻辑功能。 随后，开始出现了结构上稍复杂的可编程芯片，即可编程逻辑器件( p l d ) ， 它可以完成各种逻辑功能这种可编程逻辑器件主要有可编程阵列逻辑( p a l ) 和通用阵列逻辑( g a l ) 。它们都是由“与”门和“或”门阵列组成，任意组合 逻辑都可以用“与一或”表达式来描述，所以p l d 可以以“积一和”的形式完 成大量的组合逻辑功能。这个时期的p l d 器件有一个共同的特点，就是可以实 现速度特性较好的逻辑功能，但其过于简单的结构使它们也只能实现规模较小的 电路 为了弥补这一缺陷，2 0 世纪年代中期，a l t e r a 和x i n l i n x 分别推出了类 似于p a l 结构的扩展型c p l d ( c o m p l e xp r o g r a m m a b l ei j o g i cd e v i c e ) 和与标准 门阵列类似的f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) ，它们都具有体系结构和 逻辑单元灵活、集成度高以及适用范围宽等特点。这两种器件兼容了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 c ) 相比，它们又具有设计开发周期短、设计制造成本低、 开发工具先进、标准产品无需测试、质量稳定以及可实时在线检验等优点，因 此被广泛应用于产品的原型设计和产品生产( 一般在1 0 0 0 0 件以下) 之中。几乎 所有应用门阵列、p l d 和中小规模通用数字集成电路的场合均可应用f p g a 和 c p l d 器件。 4 - 7 1 2 3f p g a c p l d 的概述锐，嘲 f p g a 和c p l d 都是可编程逻辑器件，它们是p a l 和g a l 等逻辑器件的基础上 发展起来的，同以往的p a l 和g a l 等相比较，f p g a c p l d 的规模比较大，它可以 替代几十甚至几千块通用i c 芯片，因此它受到广泛的关注和普遍的欢迎。在全 球范围内有很多公司开发生产f p g 和c p l d ，但主要的有a i t e r a 和x i l i n x 公司， 5 中山大学硕士学位论文 此外还有l a t t i c e ，a c t e l ，q u i c k l o g i c 等。 尽管f p g a 和c p l d 和其他类型的p l d 的结构各有其特点和长处，但它们主要 都是由三大部分组成： 1 )一个二维的逻辑块阵列，构成了p l d 器件的逻辑组成核心。 2 )输入输出模块； 3 )连接逻辑块的互连资源。边线资源：由各种长度的边线线段组成， 其中也有一些可编程的连接开关，它们用于逻辑块之间、逻辑块输入输出之 间的连接。 典型的p l d 的框图如图2 - 1 示 图2 - 1 典型p l d 的框图 f p g a c p l d 都是特殊的a s i c 芯片，除了具有a s i c 的特点外，还有以下的优 点： 1 )随着v l s i ( v e r yl a r g es c a l ei c ，超大规模集成电路) 工艺的不断提 高，单一芯片内部可以容纳上百万个晶体管，f p g a c p l d 芯片的规模也越来越大， 其单片逻辑门数已达上百万门，它所能实现的功能也越来越强，同时也可以实现 系统集成。 2 )f p g a c p l d 的资金投入小，节省了许多潜在的花费。 6 中山大学硕士学位论文 3 )用户可以反复地编程、擦除、使用，或者在外围电路不动的情况下用 不同软件就可实现不同的功能。 2 4f p g a c p l d 的内部结构矧 2 4 1 基于乘积项( p r o d u c t - t e r m ) 的p l d 结构 c p l d 主要采用这种结构，它的内部结构主要可分为三部分：宏单元 ( m a c r o c e l l ) ，可编程连线( p i a ) 和i o 控制块。宏单元是p l d 的基本结构， 由它来实现基本的逻辑功能。如图2 - 2 中蓝色的多个宏单元的集合。可编程连线 负责信号传递，连接所有的宏单元；i o 控制块负责输入输出的电气特性控制。 图2 - 2 基于乘积项的p l d 内部结构 而宏单元的结构如图2 - 3 所示，其左侧是乘积项阵列，实际就是一个与或阵 列，每一个交叉点都是一个可编程熔丝，如果导通就是实现“与”逻辑，后面的 乘积项选择矩阵是一个“或”阵列。两者一起完成组合逻辑。图的右侧是一个可 7 中山大学硕士学位论文 编程d 触发器，它的时钟、清零输入都可以编程选择，可以使用专用的全局清零 和全局时钟，也可以使用内部逻辑产生的时钟和清零。如果不需要触发器，也可 以将此触发器旁路，信号直接输给p i a 或输出到i o 脚。 h 。 i7 p 蛔h l o 出 ： 自晴m 相瞎 rn l 阳m 甜l 向d 口，n _ 柚 龟叫iz m n 矧b l 蟛鲥 j 1 一 釉 广- 、 卜一 铆p 讳 u i ：拱乃n 汗如 u ，溉厂#奄 广- 、秉蹶 垌 盥曼j l ，选择 矩阵 可捕程 n u1 必l 删姨墨 f广、 a 彭 l u ”。 s 棚 1 冷一 _ f j l 。 、z 。枷b 幽 絮 w p l a 一 一v s 枷1 0 卧d m 蛔 嘲n p “嘶峨砸糟 图2 - 3 宏单元的内部结构图 2 4 2 乘积项结构p l d 的逻辑实现原理 _ o c 删 蛳吐 我们以图2 - 4 中所示的电路为例具体说明p l d 是如何利用乘积项结构实现逻 辑的，电路如下： o 2 a 日 c d c u 图2 - 4 示例电路 假设组合逻辑的输出( a n d 3 的输出) 为f ，则： 8 中山大学硕士学位论文 f ：( a + b ) 粑宰( ! d ) = a 托奉! d + b 粑木! d ( 我们以! d 表示d 的“非”) p l d 将以图2 - 5 中所示的方式来实现组合逻辑f ： 、r 、，一 、 ，旷 、，一 一一 五 暑bcc 卫面 ， 、月 砬。 图2 - 5 实现逻辑功能的电路 a ，b ，c ，d 都是由p l d 芯片的管脚输入后进入可编程边线阵列( p i a ) ，在 内部会产生a ，( 1a ) ，b ，( 1b ) ，c ，( 1c ) ，d ，( 1d ) 8 个输出。图中每一个 叉表示相连( 可编程熔丝导通) ，所以得到：f = f l + f 2 = ( a 托奉ld ) + ( b 托奉! d ) 。 这样逻辑功能就实现了。而图2 3 中的触发器的实现比较简单，直接利用宏 单元中的可编程d 触发器来实现。时钟信号c l k 由i o 脚输入后进入芯片内部的 全局时钟专用通道，直接连接到可编程触发器的时钟端。可编程触发器的输出与 i o 引脚相连，把结果直接输出到芯片的管脚。从而实现了图2 - 3 中的电路所示 的功能。 上例中所示的电路是一个简单电路，因此所需要的内部单元也不多。但是对 于一个复杂的逻辑电路，简单的内部电路是不能实现的，因此需要通过将多个宏 单元相连来实现复杂的功能。 2 4 3 查找表( l o o k - l i i ，- t a b l e ) 的原理与结构 f p g 是采用这种结构的p l d 芯片，如a l t e r a 的a c e x ，a p 既，s t r a t i xi i 系列，x i l i n x 的s p a r t a n ，v i r t e x 系列等。 查找表( l o o k - u p - t a b l e ) 简称为l u t ，l u t 本质上就是一个r a i l i 目前f p g a 中多使用4 输入的l u t ，所以每一个l u t 可以看成一个有4 位地址线的1 6 x1 的 r a m ，当用户通过原理图或h d l 语言描述了一个逻辑电路后，p l d f p 6 a 开发软件 9 中山大学硕士学位论文 会自动计算逻辑电路的所有可能的结果，并把结果事先写入r a g 。这样，每输入 一个信号进行逻辑运算就等于输入一个地址线进行查表，找出地址对应的内容， 然后再输出。 我们举一个4 输入的与门的例子来说明以上的所介绍的工作原理： 实际逻辑电路l l r r 的实现方式 b = 卜f 、 5 习兰：i c 亡= 叫， 一 d = ) _ - j 逻辑输r a m 中存储的内 a ，b ，c ，d 输入地址 出容 0 0 0 000 0 0 0o 0 0 0 100 0 0 1o 0 0 1 l l ll1 1 1 1l 1 、a l t e r a 公司的f p g a 的内部结构 a l t e r a 公司的f p g a 都采用基于s r a m 的查找表结构形式，主要由嵌入式 阵列块( e m b e d d e d a r r a y ，e a b ) 、逻辑阵列块( l o g i c a r r a y ，l a b ) 、快通道互 连( f a s t t r a c k ，f t ) 、i ，o 单元( i n p u t o u t p u tc e l l ，i o c ) 四部分组成，其结构如 图2 - 6 所示。 中山大学硕士学位论文 嵌入式阵列 i o e1 0 e 图2 - 6a c f x1 k 器件的内部结构框图 ( 1 ) 嵌入式阵列块e a b 嵌入式阵列块e a b 是在输入输出口上的r a m 块，在实现存储功能时每个 e a b 可以提供2 0 4 8 位，可单独使用或组合使用 ( 2 ) 逻辑阵列块l a b 逻辑阵列块是f p g a 内部的主要组成部分，l a b 通过快通道互连f r 相互 连接，典型结构如图2 - 7 所示。 l a b 是由若干个逻辑单元再加上相连的进位链和级联链输入输出及l a b 控制信号、l a b 局部互连等构成。 逻辑单元l e 是f p g a 的基本结构单元，主要由一个4 输入l u t 、一个进 位链( c a r r y - m ) 、一个级联链( c a s c a d e - i n ) 和一个带同步使能的触发器组成， 可编程实现各种逻辑功能。每个l e 有两个输出，分别驱动局部互连和快通道互 连 逻辑单元l e 的l u t 用于组合逻辑，实现逻辑函数。逻辑单元l e 中的可编 1 1 中山大学硕士学位论文 程触发器用于时序逻辑，可通过编程配置为带可编程时钟的d 、t 、j k 、s r 触发 器或被旁路实现组合逻辑。寄存器的时钟清0 、置位可由全局信号、通用i 0 引 脚或任何内部逻辑驱动。 图2 7a c e x l k l a b 结构图 进位链和级联链是专用高速数据通道，用于不通过局部互连的通路，连接相 邻的l e 。进位链用于支持高速计数器和加法器，提供l e 之间快速向前进位功能， 可使f p g a 适用于高速计数器、加法器；级联链用于实现多输入逻辑函数。 ( 3 ) 快通道互连f t 快通道互连f t 用于l e 和器件i 0 引脚间的连接，快通道互连是一系列水 平( f f 互连) 和垂直( 列互连) 走向的连续式布线通道。行互连可以驱动i 0 引脚，或馈送到其它l a b ，列互连接各行，也能驱动i 0 引脚。 ( 4 ) i o 单元1 0 c f p g a 的i o 引脚由i 0 单元驱动，u o 单元位于快通道的行或列的末端，由 一个双向三态缓冲器和一个寄存器组成，可编程配置成输入、输出或输入输出双 向口 i o 单元的清0 、时钟、时钟使能和输出使能控制均由i o 控制信号网络采 用高速驱动。 中山大学硕士学位论文 2 、x i l i n x 公司的f p g a 的基本结构 x i l i n x 公司的f p g a 产品结构与a l t e r a 公司的f p g a 有较大的差异，其内 部结构为逻辑单元阵列( l o g i cc e l la r r a y ，l c a ) ，主要由可配置逻辑块 ( c o n f i g u r a b l el o g i cb l o c k ，c l b ) 或可配置逻辑单元( c o n f i g u r a b l el o g i c c e l ! ) 、各模块互连资源( p r o g r a m m a b l ei n t e r c o n n e c t ) 和输入输出模块 ( i n p u t o u t p u tb l o c k ，l o b ) 组成。x i l i n x 公司的f p g a 内部的结构如图2 8 所示。 可配置逻辑 图2 - 8x c 3 0 0 0 系列f p g a 内部结构图 1 ) 可配置逻辑块( c l b ) c l b 主要由组合逻辑功能发生器、d 触发器( 2 个) 和内部控制部分组成。 组合逻辑功能发生器有5 个逻辑变量输入端和两个反馈输入端，可以作为查找表 的地址输入，两个输出端。因此逻辑功能发生器可以配置成3 2 1 或1 6 x 2 的查 1 3 中山大学硕士学位论文 找表。c l b 的两个d 触发器共享一个时钟信号，d 触发器的复位由全局复位信号 或r d 输入信号驱动。 2 ) 输入输出模块l o b 输入输出模块i o b 为外部封装引脚与内部逻辑之间提供一个可编程的接 口。 3 ) 配置存储单元 基本的存储单元由2 个c m o s 反相器和一个用于读写数据的开关晶体管组 成。该存储单元具有高可靠性和抗干扰能力。 4 ) 可编程互连 可编程互连是连接各模块的通道，将c l b 、1 0 b 连接起来形成功能电路。 2 5 本章小结 本章回顾了c p l d 与f p g a 的发展历程、并介绍了主要生产商生产的f p g a 的 内部结构及工作原理等，主要有a l t e r a 公司和x i l i n x 公司，它们的内部结构有 不少的差异，但它们都是基于查找表的p l d 。 1 4 中山大学硕士学位论文 第3 章快速傅里叶变换及反变换的算法研究 3 1 离散傅里叶变换的原理嘲 信号的傅里叶变换建立了信号的时域与频域之间的一一对应关系，拓展了 信号的表达空间，为信号与系统的频域分析奠定了理论基础。从而使我们在分析 信号与系统时，既可以对信号的时域进行分析也可以对信号的频域进行分析，而 且信号的频域分析具有更清晰的物理概念和深刻含义，因此在信息领域有了广泛 的应用。 对信号进行频域的分析，首先要对时域的信号进行傅里叶变换得到对应的 频谱函数。而在数字信号处理中，我们考虑对时域中有限长度的离散信号进行傅 里叶变换得到频域有限长度的离散信号，即离散傅里叶变换。离散傅里叶变换的 定义如下： 对时域的有限长序列x ( n ) - 毒o )( o o n s n 一1 ) 的傅里叶变换对定义 为： x ) 一d f r ( x ( n ) ) 一2 x ( n ) 嘴0 sk n 一1 ( 3 1 ) u 一i d f t ( x ( k ) ) a 专薹x 肘s n 一1 ) 一r 啊 其中昭1 e ，由式中可以看出傅里叶变换与反变换都是旋转因子 赠或降i h 的线性组合，因此时域离散信号有限长度序列石o ) 与频域的离散 信号z ) 唯一确定的对应关系。在时域里确定了的离散信号，也就确定了它在 频域里对应的频谱函数，从而使我们能够对其频谱函数进行分析。 中山大学硕士学位论文 3 2 快速傅里叶变换及反变换的原理f 1 叫【9 1 2 ，毖捌 3 2 1 快速傅里叶交换算法的提出 若直接按照式( 3 一1 ) 和式( 3 2 ) 求长度为的时域信号的傅里叶变换，那么， 对每一频率分t x ( t 1 ，都需要进行次复数乘法运算和一1 次复数加法运算。 因此计算个不同频率分量x ( t ) 共需要2 次复数运算，( 一i ) 次复数加法运 算。而进行傅里叶变换的反变换具有相同的运算量。显然，随着信号的长度的不 断增加，则进行变换的运算量将是成级数倍的增加。因此，虽然傅里叶变换在信 号与系统的分析中具有非常重要的作用，但由于它的巨大的运算量，使它在一段 时间内不能得到广泛的应用。 直到1 9 6 5 年c o o l e y 和t u k e y 提出了一种快速运算的算法，即c o o l e y - t u k e y 算法，才使得傅里叶变换的运算量大大的降低，在很大程度上提高了运算效率， 从而使傅里叶变换得到广泛应用。 3 2 2 按时域抽取的基2 快速傅里叶变换的算法原理 我们以长度为- 2 u ( m 为正整数) 的时间序列x o ) 的基2 d f t 为例，推 导说明快速傅里叶变换的算法原理。 c o o l e y - t u k e y 快速算法是利用旋转因子嘴的特殊性质通过在时域内将 序列逐次分解为一组子序列进行运算的。 2 x 旋转因子f 哮e 一7 可h 具有周期性，对称性及可约性。 1 )旋转因子以n 为周期，即： 中山大学硕士学位论文 唠= 蝶肌4 = 睇仲圳 咛+ 了一一时，( 吩) = 陈h 陟方= 仰篇，仰穸= _ i ，t ，z k n ，。m ( n m 为正整数) 首先把序列工0 ) 分解为两组，偶数项为一组，奇数项为一组，可得到两个 x i ( r ) = x ( 2 r ) ，k ( r ) ，x ( 2 ，+ 1 ) ，o ，1 要一1 墨 ) 一胛“( r ) ) 一墨( ，) 形移，( 3 - 3 ) - 7 2 筋 x z ( k ) = d f t ( x 2 ( r ) ) = x 2 ( r ) w 毳，p4)2 筋 、7 石 ) 一d f t ( x ( n ) ) 一工 渺方 n - 一1 一1 = x 哪( 。为+ z o 肘( n 为删 以- 1噘一1 2 荟z ( 2 r ) 孵打+ 荟z ( 2 ，+ 1 ) 磁犯h 。 n 一1n z 。1 2 磊x ( ，) 咙+ 昧乏x z ( ，) 吃 其中o s k 墨要一1 。由旋转因子的特性可得 。 1 7 中山大学硕士学位论文 x ( k ) = x 1 ) + 噼x 2 ) ，( 3 - 6 ) x ( k + n 一五 ) 一嘭x ： ) ( 3 7 ) 其中七一o ，1 ，等一1 ，式( 3 6 ) 表示了前半部分( 。七s 等一1 ) z ) 的组 合方式，式( 3 7 ) 表法了后半部分( 鲁七墨一1 ) x 僻) 的组合方式，信号流图 如图3 - 1 示。 ：二瑟= 二二力 图3 一l 蝶形运算削 由于信号流图形如蝴蝶，因此称为蝶形运算由蝶形运算图可以看出，每一 个蝶形运算需要一次复数乘法，两次复数加减法运算。因此前半部分的组合共需 要竺次复数乘法，后半部分也需要旦次复数乘法运算，所以两个掣点的dft442 共需譬次复数相乘运算。而组合运算共需等次蝶形运算，需等次复数相乘运 算，因而共需里2 + 丝2 搿n f 2 次复数相乘，与直接运算相比节省了近一半运算。 由于等= 2 u - 1 仍然是偶数，可依此推理得继续分解为等个点的序列，依此 分解下去，直到最后是二点的d f t 运算为止，两点的d f t 同样可以用一个蝶形运 算表示，例长度为8 点的时间序列最后可以分解到x ( o ) 和x ( 4 ) 为一组，x ( 2 ) 和 x ( 6 ) 为一组蝶形运算。 由于这种算法是在时域上按偶数和奇数抽取的，且每一次是一分为二的，所 以称为按时域抽取的基2 算法。长度为8 点的时间序列的蝶形运算数据流图如图 3 2 所示。 x 0 一 一+ ，- - x 0 x l 二 一- w 0 - ，- w 。- -x4 二一w；：、x2 一。_ x 2 x 3 1 一o j 一17 、 1w 2 - 一一x 6 x 4 黔j i ，l ，x l x 5。- w i ii t , + 0 i 一：7 ， w 1 _x 5 】6w 。j o 。| w ：2 i 7 - _ 一，x 3 x 7 _ 7 、o _ w 3 一- x 7 图3 2n = 8 按时域抽取的蝶形流程图 3 , 2 3 按时间抽取的基4 算法的数学推论 基4 算法与基2 算法的基本原理大致相同，都是将长序列的d f t 分解为短序 列的d f t ，然后再根据短序列的d f t 表示长序列对应的d f t 。它们都利用了旋转 原子陟穷的特性，使d f t 的运算结构简单化。按时域抽取的基4 算法是将长度 为n ( 。4 琳) 的序列x 0 ) 分解为学个短序列，即 4 而0 ) = x ( 4 n ) ， 工2 0 ) = x ( 4 n + 1 ) ， 而0 ) = x ( 4 n + 2 ) ， x 4 ) = x ( 4 n + 3 ) 剃_ o ，1 ，等- 1 0 下面推导由短序列的d f t 表示长序列的d f t 。长度为n 的序列x o ) 的d f t 可以稀到： 中山大学硕士学位论文 ；警1 z ( 4 ，) 暇庸+ 警1 z ( 4 厂+ 1 ) 哦m2 薹坩，) 暇薹水，+ 1 ) 哦和+ 1 冲 一1n 4 - 1 + 罗x ( 4 r + 2 ) w x t 4 ”2 弘+ x ( 4 r + 3 ) 嘴”3 冲 劁岗 l n 4 - 1 五( ，) 暇砖+ 孵乏z z ( ，) 崂砖 一-一t + 睇x 3 ( r ) 暇睹+ 孵x 4 ( ，) 孵埔 ( 3 - 8 ) 筋筋 、7 由于昨砖。p 一，警打，e 一，南h 。略。，所以式可以表示为 以一1一1 z ) 。荟_ ( ，) 嚼+ 聪荟z z ( ，) 略 以一-一1 + 孵zx 3 ( ，- ) 嚼。+ 暇芝x 4 ( r ) 嘴。 ( 3 9 ) 箭衢 、 进一步整理得 x ( k ) = x 。( 七) + w 公x ：( 七) + 蝶七x 3 ) + 嵋七x 4 ) ( 3 1 0 ) 其中五 ) 、x ： ) 、墨 ) 、蜀 ) 分别是 ) 、x 2 ( n ) 、屯o ) x 4 ( n ) 对应的鲁点。f t ，频率变量的七的取值为七一o ，1 ，等一1 。 f l q 式( 3 一l o ) 可知，长度为n 的序列x 0 ) 的d f t x ( k ) 可由而0 ) 、x 2 ) 、 加 嘴o x v 知 昌 ” r卯 暑 x 中山大学硕士学位论文 毛o ) 、砀0 ) 对应的d f t x 。 ) 、x ：( 七) 、x ， ) 、x 。( 七) 来表示， 由于_ o ) 、x 2 ( n ) 、屯o ) 、_ ) 都是长度为等的序列，因此，x d k ) 、 x 2 ) 、邑 ) 、x 4 ( 七) 也都是长度为芸的序列。所以，要想全部的表达 x ( 七) ，就要利用互 ) 、x 2 ) 、z 3 ) 、x 4 ( 七) 和矽# 4 的特性， 即满足：。 x 。( 七+ ) - x 。( 七) ， x ：( “2 ) x 2 ( 七) ， x 3 ( 七+ 3 ) 一x 3 ( 七) ， x 。( 七+ 4 ) - x ( 七) ， 其中七地1 ，等- 1 0 而旋转因子咛存在性质： 嘭+ ；e 一，瞄：一_ 噼， 咙+ 2 ：e 一加孵；一1 噼， 嘭+ 3 ；p ，瞄；j 碟， 形：+ 4 ；形? ：1 形茹。 因此，由式( 3 1 0 ) 可得： x ) 一五 ) + 嘭z ： ) + 嚼x 3 ) + 嘴z 。 ) ，( 3 1 1 ) x ( k + 仫) - 五 ) 一蛾五 ) 一略鼍 ) + j w y x 4 ( k ) ，( 3 - 1 2 ) x + 吆) - 五 ) 一嘭五 ) + 畔墨 ) 一嘴墨 ) ，( 3 - 1 3 ) x + 3 ) - 墨 ) + j 碟五 ) 一畔五 ) 一j 孵邑 ) ( 3 - 1 4 ) 中山大学硕士学位论文 中七一o ，1 ，。i n 一1 。式( 3 一1 1 ) ，( 3 1 2 ) ，( 3 - 1 3 ) ，( 3 1 4 ) 是按照基4 分解的子序 列对应的d f t 来合成原序列x 0 ) d f t 计算公式，其实现过程可用信号流程图3 - 3 表示 x l ( k ) x 2 ( k ) x 3 ( k ) x 4 ( k ) x ( k ) x 时2 n 4 ) x ( k + 3 n 4 ) 图3 3 按时间抽取的基4 f f t 蝶形运算图 3 3f f t 算法的规律 对于长度为一矿的基2 算法，我们可以从中了解它的规律。 第一，蝶形运算的规律。整个流图都是由蝶形运算单元组成，因此，蝶形运 算是f f t 及i f f t 运算的核心，是最基本的运算。1 ) - 矿点序列共需要m 级 蝶形运算，每级都有冬个蝶形运算；2 ) 第l 级的要个蝶形运算中，共有2 工n 个 不同的蝶形运算组，即旋转因子不相同；3 ) 每个蝶形运算组中有矿_ 工个蝶形运 算；4 ) 蝶距，第l 级的运算中，参加每个蝶形运算的两个数相距矿4 。 第二，顺序与倒序。按时间顺序输入的序列，输出时为倒序。按时间输入 倒序的序列，输出为顺序。也可以对蝶形运算进行变形，使得输入和输出都为顺 序，但它的控制结构不易实现。倒序的规律可以由( 肼一1 ) 位的二进制数加1 再 倒序的输出结果的次序来定。例如，当n = 8 时，n = l 的二进制数为0 0 1 ，倒序结 果为1 0 0 ，对应的十进制数为4 。依此类推，其他的倒序数都可一一求出。 中山大学硕士学位论文 第三，同址存储。由蝶形运算流图可以看出，参加蝶形运算的两个数，在 运算结束后就不再参加下一次的运算，即不需要再保存，而蝶形运算后的结果可 以分别存放在存储原来两个数据的存储单元中。这样可以节省硬件资源，降低成 本。 第四，旋转因子的规律。由第一个规律可得，在第级运算中，共有2 工- 1 个 不同的蝶形组，因此有4 个不同的旋转因子，即矸孽( k o 1 2 l - 1 1 ) ，且 每级中的旋转因子都是从孵开始的，k 依次加l ，即为下一个蝶形组的旋转因 子，周期为矿4 。 3 4 算法的选择 由前面的推导可知，基2 和基4 算法都大大的降低了运算量，从而很大程度 上提高了傅里叶变换的运算速度。相比较基2 算法和基4 算法，基2 算法的蝶形 运算需要一次复数乘法和两次复数加法，而基4 算法的蝶形运算需要三次复数乘 法和十二次复数加法由于在硬件实现时，乘法器所需的资源比加法运算所消耗 的资源多，大大的增加了成本，因此，在实现f f t 时我们采用基2 算法。 3 5 本章小结 由于快速傅里叶变换的算法原理是实现f f t 的前提，因此，必须对快速傅里 叶变换的算法要有非常的了解本章就是针对快速傅里叶变换的基2 算法和基4 算法原理进行了研究，并得出了一些算法的规律，这些规律在实现的过程有很大 的帮助。最后，根据实际的需要及对比两个算法优缺点的比较，我们选择其中的 基2 算法作为本论文的算法依据，在后面章节的实现过程中都是基于这种基2 算法原理的。 中山大学硕士学位论文 第4 章浮点处理器的硬件电路的设计与实现 4 1 定点、浮点数据n 钉 在数字系统中表示数据的方法主要有两种：定点型和浮点型。 定点型数据是小数点位置固定不变的数，小数点的位置按照约定可以在数的 最高有效位的左边或最低有效位的右边，即化为纯小数或纯整数。 在计算机中一般采用纯小数的表示方法，纯小数表示是小数点按约定在符号 位之后，在最高数值位之前，它表示格式为： 其中最高位是符号位，即x o 是符号位，x 0 为l 时为表示数值为负，为0 时表示 数值为正；其它为数值部分，即尾数部分，小数点在x 0 与x 1 之间。 浮点型数据是由两部分组成：e ( 阶码) 和m ( 尾数) 。其表示格式为： 其中m s 是尾数的符号位，也是整个浮点数的符号位，表示该浮点数的正负， 当m s 是1 时，表示浮点数为负；当m s 为0 时，表示该浮点数为正。e s ，e 1 ，e 2 e n 为阶码e ( e x p o n e n t ) ，即指数部分，e s 是阶码的符号位，即指数部分的符号位。 当e s 是1 时，则阶码为负，当e s 是0 时，则阶码为正。m 1 ，姚为尾数部 分m ( m a n t i s s a ) ，是有效数字，通