（水声工程专业论文）基于fpga的快速傅立叶变换.pdf

哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h e d e v e l o p m e n to fd i g i t a l e l e c t r o n i c t e c h n o l o g y ，d i g i t a ls i g n a l p r o c e s s i n gi sw i d e l yu s e di nm a n yf i e l d s ，s u c ha ss o n a r ，r a d a r ，t e l e c o m m u n i c a t i o n ， s p e e c ha n di m a g ep r o c e s s i n ga n ds oo n t h ef a s tf o u r i e rt r a n s f o r m ( f f t ) a l g o r i t h mp l a y sa ni m p o r t a n tr o l ei nt h ei m p l e m e n t a t i o no fd i g i t a lp r o c e s s i n g a l g o r i t h m sa n ds y s t e m s ，w h i c hi m p r o v e st h ee f f i c i e n c yo ft h ec o m p u t a t i o no ft h e 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 r a m a t i c a l l y t h ep r o c e s s o ri sr e q u i r e dt oh a v et h ec a p a b i l i t yo f h i g h - s p e e d ，h i g h - p r e c i s i o n , l a r g e - c a p a c i t ya n dr e a l - t i m ep r o c e s s i n g f i e l dp r o g r a m m a b l eg a t ea r r a y ( f p g a ) ，w h i c h h a s d e v e l o p e dr a p i d l y i nr e c e n ty e a r s ，h a s g r e a ta d v a n t a g e i np r o c e s s i n g l a r g e s c a l ed a t a s o ，as c h e m ew h i c hi m p l e m e n t st h ef f ta l g o r i t h mo nf p g ai s a d o p t e di nt h ep a p e r t h eh a r d w a r ed e s i g no ft h ed i g i t a l s i g n a lp r o c e s s i n gb o a r di s o n eo ft h e i m p o r t a n tp a r t si nt h ep a p e r a tf i r s tt h ep r i n c i p l ea n dt h em e t h o do ft h eb e a m f o r m i n ga n df f ta l g o r i t h ma r ei n t r o d u c e db r i e f l y ，t h e na c c o r d i n gt or e a l - t i m e p r o c e s s i n gr e q u i r e m e n t ，t h eh a r d w a r ec i r c u i ti sd e s i g n e da n dt h er e a l i z a t i o no ft h e h a r d w a r ei sa n a l y z e d a c c o r d i n gt o t h ed e s i g nm e t h o do fd i g i t a ls y s t e m ，10 2 4 - p o i n tf f ti s i m p l e m e n t e di nv h s i ch a r d w a r ed e s c r i p t i o nl a n g u a g e ( v h d l ) u s i n gt h r e e m e t h o d s ，r a d i x - 2d e c i m a t i o n - i n t i m e ( d i t ) f f t ，r a d i x 4d i tf f ta n df f t m e g ac o r ef u n c t i o n t h e nt h ec o m p a r i s o no ft h et h r e em e t h o d si sg i v e n w ec a n c o n c l u d et h a tf p g am e e tt h er e a l t i m ep r o c e s s i n gr e q u i r e m e n to fb e a mf o r m e r t h e na c c o r d i n gt ot h ep r o t o c o lo ft h eu n i v e r s i a ls e r i a lb u s ( u s b ) ，t h ef i r m w a r eo f t h ei s p15 81i sp r o g r a m m e di nv h d l ，a n dt h ee n u m e r a t i v ep r o c e s so ft h ed e v i c e i si m p l e m e n t e d k e yw o r d s ：f p g a ；f f ta l g o r i t h m ；u s b ；f i r m w a r ep r o g r a m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：生釜1 区 日期：加。子年弓月f9 e l 哈尔滨下程大学硕士学位论文 第1 章绪论 1 1 课题的提出 随着信息学科和计算机学科的发展，数字信号处理的重要性日益在各个 领域的应用中表现出来。数字信号处理基本上从两个方面来解决信号的处理 问题：一是时域方法，即数字滤波；二是频域方法，即频谱分析。处理的任 务大致分为三类：卷积：用于各种滤波器，对给定频率范围的原始信号进行 加工来提高信噪比；相关：用于信号比较，分析随机信号的功率谱密度；变 换：用于分析信号的频率组成，对信号进行识别。其中，d f t 和卷积是信号 处理中两个最基本也是最常用的运算，它们涉及到信号与系统的分析与综合 这一广泛的信号处理领域。由数字信号处理的基本理论可知，卷积、相关、 谱分析等都可以转化为d f t 来实现；此外，各种系统的分析、设计和实现都 会用到d f t 的计算问题。所以，d f t 在各种数字信号处理中起着核心作用， 而d f t 的快速算法快速傅立叶变换就成为了数字信号处理的最基本技术之 一，对f f t 算法及其实现方式的研究是很有意义的【1 1 。 目前，f f t 己广泛应用在频谱分析、匹配滤波、数字通信、图像处理、 语音识别、雷达处理、遥感遥测、地质勘探和无线保密通讯等众多领域。在 水声领域的应用中，应用f f t 可以提高波束形成的工作效率，由于声纳换能 器及其基阵所接收的是全方位多波束回波信号，数字信号处理器必须对多路 信号进行实时处理，这就要求f f t 处理器具有高速度、高精度、大容量和实 时处理的性能瞄1 。因此，如何更快速、更灵活地实现f f t 是提高数字信号处 理器性能的关键。 面对当今迅速变化的数字信号处理应用市场，特别是面对现代通信技术 的发展，数字信号处理器( d i g i t a ls i g n a lp r o c e s s o r ，d s p ) 在处理速度上早已力 不从心。面向数字信号处理的各类专用集成电路( a p p l i c a t i o ns p e c i f i c i n t e g r a t e dc i r c u i t ，a s i c ) 芯片虽然可以解决并行性和速度的问题，但其高昂 的开发费用、耗时的设计周期和不灵活的纯硬件结构，使得数字信号处理的 a s i c 解决方案日益失去其实用型3 1 。 近几年，随着f p g a 技术的迅速发展，采用并行度更大、速度更快的f p g a 1 哈尔滨t 程大学硕士学位论文 芯片来实现f f t 己成为必然趋势。f p g a 技术的关键就是利用强有力的设计 工具来缩短开发周期，提供元器件的优质利用性，降低设计成本，并能够并 行处理数据，容易实现流水线结构，在处理大规模数据方面，有极大的优势。 且升级简便，提高设计的灵活性1 ，这些都非常适合实现f f t 算法。所以作 者将基于f p g a 的快速傅立叶变换作为了研究课题。 1 2f f t 处理技术的现状 自从1 9 6 5 年图基( t w t u k y ) 和库n ( t w c o o l y ) 发表了著名的机器计算 傅立叶级数的一种算法论文后，桑德( g s a n d ) 图基等快速算法相继出现， 又经人们进行改进，很快形成一套高效运算方法，这就是现在的快速傅立叶 变换。这种算法使d f t 的运算效率提高1 2 个数量级，为数字信号处理技术 应用于各种信号的实时处理创造了良好的条件，大大推动了数字信号处理技 术的发展1 。 科学的发展是永无止境的，多年来，人们继续寻求更快，更灵活的好算 法。19 8 4 年，杜哈梅尔( p d o h a m e l ) 和霍尔曼( h h o l h n a n n ) 提出了更有效的分 裂基快速算法，使运算效率进一步提高。 f f t 算法本身己经相当成熟，很多领域对其高速实时运算的要求却不断 提高，实现f f t 算法的硬件方法也在不断地优化。目前主要有三种硬件实现 方式：通用数字信号处理芯片、专用集成电路及可编程逻辑器件。选择哪种 方法实现f f t 算法，必须综合考虑f f t 算法、系统的要求及实现方法的特点。 通用数字信号处理芯片是一种适合于进行数字信号处理的微处理器，其 主要应用是实时快速地实现各种数字信号处理算、法【5 1 。 目前国际市场采用单片通用数字信号处理芯片实现1 0 2 4 点1 6 位字长、 定点、块浮点或浮点运算的f f t 处理的速度达到几十到数百微秒量级。 专用集成电路具有运算速度快，可靠性高的特点，非常适合实时和对可 靠性要求较高的信号处理系统，但它不可重构，可编程能力有限。在产品发 展过程中，它的功能无法任意修改或改进。因此，任何的线路改版都需要重 新设计并且重新制造，这不仅增加开发成本，而且造成产品快速上市的障碍， 不太适合处理算法和参数经常改变的场合1 。 可编程逻辑器件目前正朝着更高速、更高集成度、更强功能和更灵活的 2 哈尔滨t 程大学硕十学位论文 方向发展，它不仅已成为标准逻辑器件的一个强有力的竞争对手，也成为掩 膜式专用集成电路的竞争者。由于超大规模集成电路技术的高速发展，数字 设计技术和方法的进一步成熟，为新一代高速实时的f f t ，滤波专用芯片或 其他专门用途的信号处理芯片提供了很好的基础。大规模可编程技术的发展， 都使得专用处理器的实现越来越有效和实用。同时，知识产权( i n t e l l e c t u a l p r o p e r t y ，i p ) 内核的出现使硬件设计可以在模块或部件级基础上进行复用， 提高了设计生产效率和避免了错误的发生p 1 。 可编程逻辑器件的厂商x i l i n x ，a l t e r a 公司都为数字信号处理提供了宏功 能模块或i p 内核，如高速乘法器、浮点算法功能、f f t 、滤波器等，可以直 接调用。这些功能的内核大都是根据各种f p g a 芯片的结构进行布局和布线 优化过的，其资源利用率得到了较大的提高。在大容量f p g a 设计中采用i p 模块可以缩短设计周期和上市时间，降低风险，提高系统的性能和可靠性。 采用x i l i n x 公司的f f ti p 内核处理1 6 位1 0 2 4 点数据，在v i r t e xi i 系列 基二结构、2 4 6 m h z 系统时钟下，速度达到2 5 4 9 岬量级哺1 ；a l t e r a 公司 2 0 0 6 年4 月推出的f f ti p 核，全面支持a l t e r a 公司的最新器件，使用此f f t i p 核计算1 6 位1 0 2 4 点数据，在3 3 2 m h z 系统时钟下仅需要6 3 肛s 1 9 of f ti p 核通常专为要求高可靠性的应用场合而设计，如雷达、地面和高空通信、声 学、石油和医疗信号处理等，且价格十分昂贵，难以在基层应用领域普及。 国内外学者在用f p g a 实现f f t 处理器方面做了大量的工作，并取得了 良好的效益芦10 1 1 1 2 1 3 1 。我国的f p g a 技术起步相对较晚，但进入2 1 世纪后， 发展非常迅速。目前不少大学及研究所都使用f p g a 设计开发具有自主知识 产权的f f t 。 1 3f p g a 技术的介绍 1 3 1f p g a 技术的发展 随着微电子设计技术与工艺的发展，数字集成电路从电子管、晶体管、 中小规模集成电路、超大规模集成电路逐步发展到今天的a s i c 。a s i c 的出 现降低了产品的生产成本，提高了系统的可靠性，缩小了设计的物理尺寸， 推动了社会的数字化进程。但是因a s i c 设计周期长，改版投资大，灵活性 差等缺陷制约着它的应用范围。硬件工程师希望有一种更灵活的设计方法， 3 哈尔滨t 程大学硕+ 学位论文 在实验室就能设计、更改大规模数字逻辑，研制自己的a s i c 并马上投入使 用，这是提出可编程逻辑器件的基本思想。 可编程逻辑器件随着微电子制造工艺的发展取得了长足的进步。从早期 的只能存储少量数据，完成简单逻辑功能的可编程只读存储器、紫外线可擦 除只读存储器和电可擦除只读存储器，发展到能完成中大规模的数字逻辑功 能的可编程阵列逻辑和通用阵列逻辑，今天已经发展成为可完成超大规模复 杂组合逻辑与时序逻辑的复杂可编程逻辑器件( c o m p l e xp r o g r a m a b l el o g i c d e v i c e ，c p l d ) 和f p g a 。随着工艺技术的发展与市场需要，超大规模、高速、 低功耗的新型f p g a c p l d 不断推陈出新。新一代的f p g a 甚至集成了中央 处理器或d s p 内核，在一片f p g a 上进行软硬件协同设计，为实现片上可编 程系统( s y s t e mo nap r o g r a m m a b l ec h i p ，s o p c ) 提供了强大的硬件支持。目 前，f p g a 已广泛应用于数字信号处理、图象处理、高速网络互连、总线协 议、微处理器和微控制器等各个领蜊1 4 1 。 1 3 2 利用f p g a 实现数字信号处理 当前许多通讯、视频和图像系统已无法简单地利用d s p 来实现，基于 f p g a 的信号处理器己广泛应用于各种信号处理领域。f p g a 所固有的灵活 性和性能可让设计者紧跟新标准的变化，并能提供可行的方法来满足不断变 化的标准要求p 1 。 f p g a 与d s p 相比的主要优越性有： ( 1 ) f p g a 实现数字信号处理最显著的特点就是高速性能好。f p g a 有内 置的高速乘法器和加法器，尤其适合于乘法和累加等重复性的数字信号处理 任务。d s p 处理速度比较慢的瓶颈来自于基于c p u 的指令顺序执行的基本工 作模式，以及通常使用的多片d s p 组合电路和过多的外部接口电路导致的信 号通道过长、过复杂。 ( 2 ) f p g a 的存储量大。d s p 内部一般没有大容量的存储器，但是f f t 实时处理运算需要存储大量的数据，只能外接存储器，这样往往会使运算速 度下降，同时电路也会更复杂和不稳定。目前，高档的f p g a 中有大量的高 速存储器，不用外接存储器便可实现f f t 实时处理运算，其速度更快，电路 更简单，集成度和可靠性也大幅度提高。 4 哈尔滨t 程大学硕十学位论文 ( 3 ) f p g a 是可重构的。仅仅通过对d s p 加载不同的程序代码，并不能有 效地改变d s p 系统的诸如吞吐量、数据总线宽度、d s p 加速模块的数量与功 能、调制模式、实时加密算法、模块d s p 系统、处理频段带宽、通信协议、 动态范围、制式等技术参数和技术方案。这是因为这一切必须完全改变硬件 结构、硬件功能和硬件组成才能实现。也就是说除非d s p 系统具有硬件可重 构性，即结构有可重配置性才能实现上述变化。由于不同的配置文件下载到 f p g a 后，将能获得不同的硬件结构和硬件功能，因此基于f p g a 的数字信 号处理系统具有良好的系统结构可重配置特性。 ( 5 ) 在比较f p g a 和d s p 时，一个重要的参数是输7 , 输( i n o u t ，i 0 ) 带宽。除了些专用引脚外，f p g a 上通用引脚均可供用户使用，这使得f p g a 信号处理方案具有非常高性能的i o 带宽。大量的i o 引脚和多块存储器可 让系统在设计中获得优越的并行处理性能。 ( 6 ) 二者系统知识产权自主性不同由于基于f p g a 的d s p 系统主要是纯 硬件系统设计，可选的硬件实现方式很多，因此系统具有较好的自主知识产 权属性。基于d s p 的系统则没有这种属性。 ( 7 ) 掌握开发技术的难易程度不同。掌握d s p 技术的困难主要来自以下 几个方面： 1 ) 不同的开发目标需要选择不同的d s p ，详细了解d s p 器件的结构对 正确地设计d s p 硬件系统至关重要，特别需要多片d s p 联用时更是如此。 对器件硬件结构的熟悉和关注能力需要相当的硬件开发经验，这显然增加了 学习的难度。 2 ) 不同的d s p 结构将对应不同的汇编语言，以及不同的编程方法和编 程技巧。语言与结构的密切相关性在明显增加学习难度的同时，缩短了新的 计算机语言的可用性周期，即学会的软硬件知识容易过时。 3 ) 不同的d s p 结构、不同的汇编语言及其对应的不同的d s p 系统结构， 都将对应不同的仿真开发工具以及编译软件。 4 ) 由于必须直接使用计算机语言来描述和实现复杂的算法，且描述的方 法与d s p 结构相关，因而设计过程缺乏直观性和一般性。 5 ) 由于系统的低速性，为了了解和实现典型的d s p 功能，需将大量的 精力花在本应由计算机就能实现的软硬件结构技巧上。而f p g a 系统的一切 5 哈尔滨t 程大学硕十学位论文 设计操作都可以在同一环境中完成，整个设计流程中几乎可以不必了解 f p g a 的结构和v h d l 硬件描述语言，从而最大程度地发挥了计算机自动化 设计的优势。设计者所有的任务都集中在系统行为和功能的描述，以及系统 性能的优化上。 ( 8 ) 二者系统成本、功耗、集成度与可靠性不同。实用系统中往往需要 尽可能高速、高性能的d s p ，而且多片d s p 连用的情况也十分普遍。在这种 多片d s p 系统中，每一片d s p 都必须配置完整的辅助器件才能正常工作， 其中包括诸如各种存储器以及f p g a c p l d 等辅助接口器件等等。这种系统 的成本将成倍提高自不必说，功耗、集成度与可靠性等性能指标也都将不同 程度地下降。而基于f p g a 的d s p 系统的优势主要源于可以形成单片系统。 目前拥有大规模逻辑资源的f p g a 完全能容纳本来必须由多片d s p 构成的系 统，从而使得单片d s p 系统在各项技术指标大幅度提高的前提下，成本和功 耗大幅度下降，集成度与可靠性则大幅度提高。 ( 9 ) f p g a 还具有可扩展的优点，f p g a 本身复杂性的提高远远超过最终 产品要求的复杂性。目前的市场采用的是用f p g a 内嵌d s p 内核模块的形式 来抢夺d s p 市场的。事实上，内嵌强大d s p 内核的f p g a 正逐步向传统d s p 市场渗透，d s p 作为i p 内核的模块嵌入到f p g a 芯片内。i p 内核的使用也 促进了设计再利用，这在生产周期中可节约大量的时间。目前，将f p g a 引 入d s p 硬件的设计在呈指数增长。这一爆炸性增长的原因是，所有主要的 f p g a 供应商和第三方i p 设计商都在提供越来越多的f p g ai p 内核。利用这 些资源，系统设计者就能将精力集中在设计上，而无需关心滤波器和转换等 底层模块的细节。f p g a 和a s i c 制造商正在密切协作，使设计再利用变的 更为容易。 1 4 论文的主要工作 论文的主要工作可归纳为两部分：一是硬件平台的设计，包括f p g a ， 静态存储器，f p g a 和t m s 3 2 0 c 5 5 0 9d s p ( 简称d s p 5 5 0 9 ) 之间的数据交互 接口，两路u s b 接口，以及两套l v d s 数据传输等电路的设计；二是软件部 分的设计，包括f f t 算法的实现，u s b 接口芯片固件程序的编写，l v d s 传 输电路控制程序的编写以及静态存储器读写控制时序代码的编写。 6 哈尔滨工程大学硕士学位论文 论文内容安排如下： 1 探讨了f f t 的基本原理，基本算法，详细介绍了基二时间抽取f f t 算法和基四时间抽取算法的原理，然后简单介绍了波束形成的基本 原理基本方法以及d f t 波束形成算法。 2 对数字信号处理部分的硬件系统各接口电路进行了详细介绍。 3 对系统软件进行了详细设计，包括基二时间抽取f f t 算法、基四时 间抽取f f t 算法的实现以及知识产权内核实现f f t ，并对三种算法 进行了比较。 4 对各模块电路的逻辑控制进行了详细设计，包括i s p l 5 8 1 接口芯片 的固件编程实现以及简单的u s b 驱动程序和应用软件的开发，还包 括系统之间的低压差分信号传输模块的设计，对静态存储器的读写 控制等。另外对d s p 5 5 0 9 的u s b 模块进行调试。 5 在文章中对系统的软硬件设计中碰到的问题进行了分析，然后给出 了解决方案。 7 哈尔滨工程大学硕十学位论文 第2 章f f t 算法基本原理 2 1f f t 的基本原理 长度为的x ( n ) 的d f t 为 】 x ( 后) = x ( 圳嗲，k = o ，1 ，n - 1 ( 2 - 1 ) n = 0 式( 2 1 ) 中 2 盯 嘭= p 吖百腑( 2 2 ) 考虑x ( n ) 为复数序列的一般情况，对某一个后值，直接按式( 2 1 ) 计算 x ( k ) 值需要次复数乘法、一1 次复数加法。因此对于个k 值，共需要2 次复数乘法和( 一1 ) 复数加法。实现一次复数乘法需要4 次实数乘法和2 次实数加法，一次复数加法需要两次实数加法。因此直接计算全部x ( 七) 需要 4 n 2 次实数乘法和2 n ( n 一1 ) 次实数加法。当较大时，对实时信号处理来 说，对处理器计算速度有十分苛刻的要求，于是如何减少计算离散傅立叶变 换的运算量变的至关重要。 为减少运算量，提高运算速度，就必须改进算法。利用系数嘭以下固 有特性，就可以减小d f t 的运算量。 ( 1 ) 阿, r n k 的对称性： 咿= ( 嚼) = 昭脚 ( 2 3 ) ( 2 ) 1 7 v z n k 的周期性： 嘭= 嘴州= 蝶“ ( 2 4 ) ( 3 ) f v n k 的可约性： 嘭= 孵眩= 嚼，嘴坨= - 1 ，嘴州陀= 一蝶 ( 2 5 ) 利用嘭的上述特性，可以将长序列的d f t 分解为短序列的d f t ，这样 可以避免大量的重复运算，提高d f t 的运算速度1 。 快速傅立叶变换算法正是基于上述的基本思路而发展起来的。它的算法 8 哈尔滨工程大学硕十学位论文 基本上分成两大类按时间抽取和按频率抽取法。作者采用的是按时i 、日j 抽取的 f f t 算法。 2 2 基二时间抽取f f t 算法 基二时间抽取法f f t 的基本原理是将一个点的计算分解为两个n 2 点的d f t 计算，每n 2 点的计算再进一步分解为n 4 点计算，依次类推。 信号x ( n ) 根据采样信号分解为奇采样点和偶采样点5 1 。设偶采样序列为 x ( n ) = x ( 2 n ) ，奇采样序列为x ( n ) = x ( 2 n + 1 ) 。 - l譬1譬1 x ( 后) = x ( 刀) 嘴= x ( 2 n ) w l ；时+ x ( 2 n + 1 ) 嘴”d n = on = on = 0 掣1 笪1 ， = x ( 2 n ) w 嚣, * z + 蝶x ( 2 n + 1 ) w 茄： ( 2 6 ) 崂t ：口一等驰：p 一- 。此2 xk ：蝶，： ( 2 7 ) 型一1 令 g ( 尼) = x 、，2 n k ，七= o ，1 ，n 2 - 1 ( 2 8 ) 里一1 2 日( 后) = x ( 2 咒+ 1 ) 嘴，后= o 1 n 2 - 1 n = 0 贝i j ， x ( 后) = g ( 后) + r e h ( k ) ，k = o ，1 ，n 2 1 x ( k + n 2 ) = g ( k + n 2 ) + 眩+ n 1 2 h ( k + n 2 ) 式( 2 1 1 ) 中 ( 2 - 9 ) ( 2 1 0 ) = g ( k ) - 昭日( 尼) ，k = o 1 n 2 - 1 ( 2 1 1 ) 噼“彪= ( p 川州1 ) “删2 = 一( p 掣州) = 一嘭( 2 1 2 ) 式( 2 一1 0 ) 和式( 2 1 1 ) 结合在一起，将点的d f t 分解成了两个n 2 点的 d f t 。同理将每个n 2 点在分解成奇偶两部分，则n 2 点的d f t 可以由两 个n 4 点的d f t 求得，依次类推，一直分解到n 2 个2 点的d f t 。例如可 以把一个8 点的d f t 分解为四个2 点的d f t ，如图2 1 所示。 9 哈尔滨工程大学硕士学位论文 图2 1n = 8 的基二时间抽取法f f t 运算流图 对于点的d f t ，每一个点要计算次复数乘法和一1 次复数加法， 要完成全部运算的工作量与2 成正比，对于点的d f t 来说，共有l o g ，n 级，每级有n 2 次复数乘法和次复数加法，因此完成全部运算的工作量与 ( n 2 ) * l 0 9 2n 成正比。以n = 1 0 2 4 的复数乘法为例，用按时间抽取法d f t 计算速度比直接计算d f t 速度快2 0 0 多倍。 2 3 基四时间抽取f f t 算法 基四f f t 算法和基二f f t 算法原理相似，只是将分解的基数改为4 ，使 得在增加单个蝶形运算单元复杂度的情况下，减少了蝶形单元的个数列。 m 等争争 等t 娴= 嘭= 删咿+ 枇+ 1 ) 咿冲+ e x ( 4 n + 2 ) g x f f + 2 m + e x ( 4 n + 3 ) g x f f + 3 ) k n = 0n = 0n = 0n = 0n = 0 型1盟1丝1翌i 4正d4 = x ( 4 n ) w 嬲 m 4 + 蝶x ( 锄+ 1 ) 嘱+ 磉枘+ 2 ) 哦+ 磁x ( 锄+ 3 ) 畴( 2 1 3 ) 令 旦1 4 g l ( 后) = x ( 4 刚璐。 n = o 型一1 4 g 2 ( 后) = x ( 4 n + 1 ) w 茄4 n = 0 1 0 ( 2 1 4 ) ( 2 1 5 ) 蝌 刑 删 删 删 荆 俐 聊 蚴 缈 傅 瓣 谚 谚 仍 卿 蝴 哟 删 卿 卿 删 婀 哈尔滨工程大学硕士学何论文 旦l d g 3 ( 尼) = x ( 4 ，z + 2 ) 嚼。 ( 2 - 1 6 ) 生l j g j ( 后) = e x ( 4 ，z + 3 ) 阿篇4 ( 2 - 1 7 ) 其中 ，2 = 0 ，1 ，i n 一1 ；七= 0 1 一l 则， 彳( 后) = g 1 ( 忌) + 乃葛g 2 ( 七) + 陟焉。g 3 ( 尼) + 乃贯g 4 ( 尼) ( 2 - 1 8 ) x ( k + 百n ) = g l ( 尼) + ( 一j ) w i ：g 2 ( k ) + ( 一1 ) 啄。g 3 ( k ) + ( 歹) 时g 4 ( k ) ( 2 - 1 9 ) x ( k + i n ) ：g l ( 后) + ( 一1 ) 孵g 2 ( j i ) + ( 1 ) 啄t 岛( 尼) + ( 一1 ) 眩g 4 ( 后) ( 2 - 2 0 ) x ( k + 等) = g l ( 尼) + ( ) 嘭g 2 ( 后) + ( 一1 ) 呒g 3 ( 尼) + ( 一) 暇。g 4 ( 七) ( 2 - 2 1 ) 由式( 2 1 8 ) 到式( 2 2 1 ) 可以得到基四的蝶形运算单元，如图2 2 所示 一 曰 c 刀 a a ；4 + 占矽茹+ e 酽萨+ d 矽秽 b 雪= a 一口阡茹一e 阡铲+ j d 蹄铲 c c - 。且一b 阿茹+ c 矽舻一d 矽秽 d d = a + j b 嘴一c w 2 9 3 i t , 图2 2 基四蝶形运算单元 对于n = 4 m 点d f t ，按4 玎、4 玎+ 1 、4 玎+ 2 、4 玎+ 3 = 0 ，1 ，( 4 ) 一1 ) 进行分解，逐级分解直到n 4 个4 点的d f t ，这样全部d f t 可分解为l o g 。n 级蝶形运算，每一级有n 4 个蝶形单元。对于点的d f t 来说，共有l o g 。n 级，每级有3 n 4 次复数乘法和2 n 次复数加法，因此完成全部运算的工作量 与( 3 n l o g 。n ) 4 成正比。同样点数的d f t ，基四算法运算量为基二算法的 7 5 。 2 4 波束形成的基本原理及基本方法 波束形成是声纳信号处理的主要组成部分，无论是被动声纳还是主动声 1 1 哈尔滨t 程大学硕+ 学位论文 纳都要有波束形成系统。其根本意义就是要在特定的方向形成一个波束图， 对于基阵预采样传来的信号进行空域滤波，确定信号传来的方向，判断目标 方位。这一方面是为了获得足够大的信噪比，另一方面也是为了得到高精度 的目标分辨率。所以，波束形成系统是现代声纳的核心部分，是声纳具有良 好战术、技术性能的基础6 1 。 2 4 1 波束形成的基本原理 波束形成的最重要的目的是定向。要完成这个任务，只有一个水听器是 不够的，通常要将很多水听器按一定的几何规则排成一个阵，这样的水下接 收系统称为基阵，构成基阵的各水听器叫做基元。当信号传播到各基元时， 由于声程差的缘故，每个基元的输出的信号是有差异的。如果我们能把这种 差异进行人为的适当补偿，那么补偿后的信号就都一样了，然后再进行其他 处理。这就是普通波束形成或常规波束形成的基本思想7 1 。 我们知道，由个无方向性阵元组成的接收换能器阵，将所有阵元的信 号相加得到的输出，就形成了基阵的自然指向性。当信号源从不同方向入射 时，由于各阵元接收信号与参考信号的相位差不同，所以输出和的幅度也不 同，也就是阵的响应不同，这就是基阵具有指向性的基本原理。 对一元线阵而言，设其间距为d ，各阵元接收灵敏度相同，平面波入 射方向为臼，如图2 3 所示。设各阵元信号输出为： 图2 3 等间距线阵 f o ( t ) = wo o s ( c o o t ) r o ) = w c o s ( c o o t + 刀缈) = wr e ( e 一归”e 一血妒)( 2 2 2 ) 1 2 哈尔滨。t ：程大学硕士学位论文 其中形表示信号幅度，为信号角频率，缈为相邻阵元接收信号问的相 位差。可知： 伊：2 z c f r ：2 ，r f ds i n 8 ( 2 2 3 ) r e ( ) 为取实部的记号。阵输出为 j ( 秒，f ) = r ( r ) = 么r e p 积p 咖伊l ( 2 - 2 4 ) 化简为 s ( 秒，f ) ：彳兰尝c 。s c o t + ( 一1 ) 伊2 ( 2 2 5 )、 s i n ( ( o 2 1 、 将式( 2 2 5 ) 的幅度归一化，就得到波束主瓣指向阵法线方向的输出幅度 为： s i n ( - 挈) s i n ( 丝坦s i n 9 ) 尉六幺0 。卜一n s i n ( 罟) 2 忑盈面 q 2 6 当8 = 0 ，域d = 1 时，实现同相相加。 此时只要补偿适当的相移或者时间延迟，就可以将波束主瓣指向o o 方 向，不难得到， s i n n z c f d ( s i n 0 一s i n 岛) 】 烈 见印5 忑蕾商 仁2 7 一般来说，只有直线阵或空间平面阵才会在阵的法线方向形成同相相加， 得到最大输出。然而，任意阵形的阵经过适当处理，可在预定方向岛形成同 相相加，得到最大输出，从而有效地输出该方向的信号n 引。 因此波束形成的基本原理可叙述为：对多元阵阵元接收信号进行时延或 相移补偿使对预定方向的入射信号形成同相相加。 2 4 2 波束形成的基本方法 波束形成有许多种方法，可以按照不同的标准对它们进行分类。例如： 1 3 哈尔滨丁程大学硕十学位论文 根据采用的权值是否时变可分为常规波束形成和自适应波束形成；根据是否 对信号采用限幅方法压缩动态范围可分为限幅波束形成和线性波束形成；根 据波束形成在时域完成还是在频域完成可分为时域波束形成和频域波束形 成；根据信号频谱的宽窄可分为宽带波束形成和窄波束形成等。根据下图给 出的常规波束形成方法的分类情况，可以看到，常规的方法还包括了其它分 类方法中的波束形成方法h 明，如图2 4 所示。 时域波束形成技术主要通过两种方法来实现：相移波束形成；时延波束 形成。由于相移是频率的函数，而时延可以做到与频率无关，所以窄带应用 ( 一般在主动声纳) 时，常用相移波束形成；在宽带应用( 一般在被动声纳) 中，则用时延波束形成。 常规波束形成 时域波束形成 f 延迟求和波束形成 宽带波束形成 降采样波束形成 l 内插波束形成 f 正交波束形成( 基带波束形成) 窄带波束形成 荔蓉辇霆鬃襞束形成 i 升采样波束形成 频域波束形成 耄蓁薹蓁蓁主 图2 4 常规波束形成方法 2 4 3d f t 波束形成 d f t 波束形成的优点是可以利用f f t 算法在数字信号处理器中实现。如 图2 3 所示，一个元等问距直线阵第后个阵元接收的信号用复数表示为： 讫( f ) = 色p 7 姗柳= 反e 国。p 业矿 ( 2 2 8 ) 其中境为第七号阵元的接收灵敏度，坳是第后号阵元接收信号超前第0 号阵元信号的相位，相邻阵元件的相位差为： 矽：2 万_ z ds i n p( 2 2 9 ) 1 4 哈尔滨工程大学硕士学位论文 若在相邻阵元之间插入相移屈，则各阵元对应的输出为： 乩( f ) = b k e j 耐e 肚9 一屏1 忽略时间因子，记未经补偿的阵元信号为： x k = b k e 肚 ( 2 - 3 0 ) ( 2 3 1 ) 则求和后阵的输出为： 一1 4 = x k e 一粥，厂= o 1 n - 1 ( 2 3 2 ) k = 0 如果取补偿的相位为： 屏= 等r 则有 4 ：芝x k e 争产1 n - 14 = 。矿，= o 。 ( 2 3 3 ) ( 2 - 3 4 ) 由上式不难看出，这时一个离散傅立叶变换的形式，不过这里的样本黾 取自空间不同阵元，而不是时间序列，因而是空间傅立叶变换。式( 2 3 4 ) 表示 当阵元间插入相移屈时，由( 2 2 9 ) 式不难得到，主极大方向被控制到 s i i l 晓：盟：丝小土：三，( 2 3 5 ) ? h dn2 x dh d 如果信号方向s i n 0 = s i n q ，此时1 4 i 值最大，达到同相相加。式( 2 3 4 ) 中，彳，表示阵元间补偿相移屏时，第，号波束的输出。因此，当s i n 0 s i n o r 时，4 表示指向o r 的波束对入射角为矽的信号的输出，此时i 彳，i 值不是最大。 在s i n 0 轴上，第，号波束和，+ 1 号波束的间隔记为a ( s i no r ) ，由式( 2 3 5 ) 得： ( s i n p ) _ s i n o r rs i n o r2 意( h 1 ) 一南忙啬( 2 - 3 6 ) j， o r + l - - b = a r c s l n ( 意( ，+ 1 ”一a r c s i n 兰n d 厂( 2 - 3 7 ) 由式( 2 3 6 ) 和( 2 3 7 ) 得，在s i n 0 轴上两个相邻波束的间隔是一个与具体控 制角p 或波束指向无关的常数。但是在汐轴上，两个相邻波束的角度间隔与 具体波束控制角有关，而且随控制角偏离阵法线角度越大，波束的角度间隔 越大，波束宽度也越大。 1 5 哈尔滨工程大学硕士学位论文 由式( 2 3 4 ) 得，在对阵元同时采样时，= 0 4 + ：岩x k e 一净( 舢) = 4 ( 2 - 3 8 ) 可知它以，= n 为周期在s i n 0 轴上重复排列，因此个波束在中心非模 糊扇面s i n o f _ 2 2 d ，2 2 d 1 内从中心到右，再从左到中心顺序排列。这里， 形成的个波束是相互独立的。 原则上，在阵元数为时，d f t 波束形成的方法只能形成个独立波束， 但这并不意味着只能形成个波束。利用补零的方法可以形成更多的波束。 当补m 个零后，构成序列如下： = 罄冀知? 叠- 1 + m 一1 ( 2 - 3 9 ) 这样，对儿进行d f t 运算，有： 4 ：羔1 稚p 南打：芝故p 南打，：0 ，1 ，+ m 一1 ( 2 - 4 0 ) k = 0 k = o 现在，利用个阵元形成了+ m 个波束，在s i n 0 轴上相邻波束的间隔 由一2 n d 变为2 ( n + m ) d 。此时，波束加密了，但是波束的宽度并未改变， 实质上，独立波束数仍是个，只不过利用补零的方法又内插了若干波刺1 8 1 。 2 5 本章小结 论文的主要目的是在f p g a 中采用f f t 算法实现相移波束形成，故在本 章中首先探讨了f f t 算法的基本原理，并重点对基二时间抽取算法和基四时 间抽取算法的公式进行了详细推导，为本设计的软件实现提供了理论依据。 然后对波束形成的基本原理和基本方法进行了概述，并对相移波束形成中的 d f t 波束形成实现算法作了重点讨论。 1 6 哈尔滨工稃火学硕十学位论文 第3 章数字信号处理系统硬件设计 3 1 系统硬件设计概述 正是因为第一章提到的f p g a 处理数据的高速性，本设计才把f p g a 技 术应用到f f t 技术的实现中来。本章的主要工作是对数字信号处理板硬件的 设计。系统框图如图3 1 所示。 静惫钉铭器s r a m l d t 7 l v 4 1 6 p 墩卜 氮f k 罄分 臻收- -叫嘞i s 拱p i 艇s g 捌l 。产主 铸 j 伎输 ，7f p ( j a l v d s s t r a t i xh 一_ 托选 e p 2 s 3 0 f 4 9 4 c 5 叫雠p 机 图3 1 系统硬件结构框图 这部分的主要功能介绍如下： 数字信号处理板上的通过低压差分信号模块接收模拟接收板的数据，把 数据送到f p g a 内部进行f f t 处理，然后把处理结果通过u s b 接口送给主 机，进一步处理。 数字信号处理板还可以通过u s b 接口接收主机仿真数据，并把这些数据 存储到电路板上的静态存储器中，然后f p g a 读取存储器中的数据并进行处 理，对f f t 算法进行验证。 本设计在硬件电路中采用了两条和主机进行通信的通道：一是电路板通 过u s b 接口芯片i s p l 5 8 1 和主机建立连接，该芯片符合u s b2 0 规范；二是 利用d s p 5 5 0 9 芯片中内嵌的u s b 模块建立数字处理板和主机之间的连接， 该模块符合u s b1 1 规范。 数字信号处理板上除了d s p 5 5 0 9 中的u s b 模块数据传输部分由d s p 实 现，其他包括f f t 算法的实现、各接口电路的逻辑控制、驱动编写都是在 1 7 哈尔滨工程大学硕十学位论文 f p g a 中实现的，故f p g a 是整个系统的核心。 本设计的硬件电路板实体照片请参见附录。 3 2f p g a 电路设计 3 2 1a l t e r af p g a c p l d 的结构 目前，各种设计所包含的功能越来越复杂，性能要求也越来越高，这就 要求我们充分了解所用的f p g a c p l d 器件的结构特点，合理地使用其内部 的功能模块和布线资源。 如今的f p g a 早已不仅仅是传统意义上的通用可