关闭

关闭

关闭

封号提示

内容

首页 信号子空间分解的FPGA实现.pdf

信号子空间分解的FPGA实现.pdf

信号子空间分解的FPGA实现.pdf

上传者: xl46512 2012-05-08 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《信号子空间分解的FPGA实现pdf》,可适用于IT/计算机领域,主题内容包含电子科技大学硕士学位论文信号子空间分解的FPGA实现姓名:张乐申请学位级别:硕士专业:通信与信息系统指导教师:魏平摘要摘要阵列测向在移动通信、电子对符等。

电子科技大学硕士学位论文信号子空间分解的FPGA实现姓名:张乐申请学位级别:硕士专业:通信与信息系统指导教师:魏平摘要摘要阵列测向在移动通信、电子对抗、参数估计、信号识别等领域有着广泛的应用前景。信号子空间方法是阵列测向方法中重要的一种经过多年的发展已经产生了大量性能优异的测向算法典型的有MUSIC(MultipleSignalClassification)、ESPRIT(EstimationofSignalParametersviaRotationalInvarianceTechnique)等。在基于信号子空间的各种算法中由R.O.Schrnidt提出的MUSIC算法具有高精度和高分辨率的特性但因为运算量大至今无法应用在实时场合。因此研究MUSIC算法的实时实现有着十分重要的意义。本文主要研究MUSIC算法在一个四阵元的均匀线阵的测向系统上的FPGA实现问题:()本文针对现有基于FPGA实现特征值分解(EVD)的算法的不足提出更适合FPGA实现特征值分解的MCJacobi算法。MC.Jacobi算法增加了特征值分解的并行性因此特征值分解的时间只有原算法的/。()本文给出基于MC。Jacobi算法的EVD模块框图采用VHDL语言进行RTL级描述并进行功能仿真和时序仿真在建立FPGA硬件测试模型后在开发板上进行硬件测试。()本文给出MUSIC算法中协方差模块和谱峰搜索模块的FPGA解决方案给出了硬件实现框图用VHDL进行RTL级描述进行了软件仿真、硬件测试。()本文对MUSIC算法的各模块进行了互连调试工作。当采用了Altera公司Cyclone系列的FPGA实现MUSIC算法时单次运算时间在us以内。与基于PDSP设计的MUSIC专用处理器相比时间减少个数量级.与国外基于FPGA设计的MUSIC专用处理器相比在使用相同器件时时间减少一半。关键词:MUSICFPGAEVDJacobiCORDIC塑!型曼!ABSTRACTArrayprocessingplaysaveryimportantroleinmanyfieldssuchasmobilecomunicationelectronicreconnaissanceparameterestimationsignaldiscriminationandsooil.Subspacebasedmethodisoneoftheimportantmethodsofarrayprocessingandhasproductedplentyofhighperformancealgorithmsthroughyearsofdevelopment.ThetypicalODeSareMUSIC(MultipleSignalClassification)ESPRIT(EstimationofSignalParametersviaRotationalInvarianceTechnique).AmongallthealgorithmsbasedonsubspacebasedmethodMUSICproposedbyR.O.SchmidtishighpreciseandlaJ曲resolution.Neverthelessitneedshugequantityofcomputationwhichbafflesits如rlherapplicationinreahimeprocessing.Thereforeitisverynecessarytostudyitshighspeedimplementmethods.ThisdissertationstudiesthehighspeedwaytoapplyMUSICalgorithminanfoursensoruniformlineararray(ULA)system.()AnalyzingthedisadvantagesofthepmsemalgorithmbasednFPGAforeigendecompositionthedissertationproposestheMCJacobialgorithmwhichisbetterforeigendecompositionwhenusingFPGA.MCJacobiaddstheparallofcomputationsothetimewillbeshortenby/comparing、Ⅳitlltheoldalgorithm.()BasingonMCJacobialgorithmthedissertationdesignsEVDhardwarediagram.ThedissertationdoesfunctionsimulationandtimingsimulationaftercodingbyVHDLwhichisoneofdescriptionlanguageforRTL.MakingamodelforrealtestingthedissertationapplysMCJacobialgorithmintoFPGAonthedemoboard.()ThedissertationdesignsthehardwarediagramsofComlationMatrixModuleandSpectrtmaPeakFindingModule.AccrodingtothehardwarediagramsthedissertationcodesbyVHDLanddofunctionsimulationandtimingsimulatioil.垒曼!!堡垒竺!()ThedissertationconnectsanddebugsallmoduleswhichwedesignWhenchoosedAlteraCompany’sproductionCyclone,thetotalprocessingUmeislessthanus.TheprocessingtimeoftheMUSICchipwhichthedissertationdesignandtheprocessingtimeoftheMUSICprocessorwhichdesignedbasedonPDSPdifferbytwoordersofmagnimdeandwhichthedissertationdesignaslocuttimeinhalfwiththeMUSICchipwhichisbasedonFPGAinforeigndesigning.Keyword:MUSICFPGAEVDJacobiCORDICin独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知除了文中特别加以标注和致谢的地方外论文中不包含其他人已经发表或撰写过的研究成果也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名:丛堡日期:年月Et关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定有权保留并向国家有关部门或机构送交论文的复印件和磁盘允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后应遵守此规定)签名:承禾导师签名:主垦至El期:年月日第一章绪论第一章绪论.阵列测向与信号子空间方法阵列信号处理是信号处理的一个年轻分支属于现代信号处理的重要研究内容在移动通信、电子对抗、参数估计、信号识别等领域有着广泛的应用前景。一般来讲阵列信号处理是将多个传感器设置在空间的不同位置来组成传感器阵列通过对多通道接收机输出的数据进行处理利用各个信号在空间位置上的差异最大程度增强所需要的信号抑制干扰和噪声最终提取空间信号源的特征信息。这些特征信息包括:空间信号源的方向、数目、频率、相位、调制形式等。其中估计空间信号源的方向是即阵列测向人们广泛研究的内容之一迄今为止阵列测向已有大量的研究成果见于各种文献和报道。信号子空间方法是阵列测向方法中重要的一种它将N维观测空间划分为D维信号子空间和由噪声引入的(ND)维噪声子空间(D<N)子空间的分解依靠协方差矩阵的特征允解或数据矩阵的奇异值分解而获得。在所有利用利用信号子空间方法来实现阵列测向的方法中以R.O.Schmidt提出的MUSIC算法【l】【】最为经典且最有代表性理论与实践均已证明此算法具有高精度(其估计精度接近CramerRao方差下限)和高分辨的性能而且为一维的空间谱搜索其计算量比多维搜索的最大似然法小得多。MUSIC算法的核心思想是对阵列输出的协方差矩阵做特征值分解把整个特征空间分成信号子空间和噪声子空间。利用阵列方向矢量和噪声子空间互相正交定义一个MUSIC伪谱搜索谱峰谱峰对应的角度既是入射信号的波达方向【。.研究背景与现状关于实际的阵列系统国内外均有大量的文献报道f】【”。在已报道的MUSIC算法在阵列测向的相关应用中大多数还是一些对实时性要求不太严格的应用如对雷雨天气的研究和对速度较慢的船舶的定位等方面。但是在移动通信、电子侦察以及电子对抗等对实时性要求严格的领域中的应用还比较少究其原因主要电子奉耳技大学硕士学位论文是因为MUSIC算法具有非常大的计算量现有的系统处理速度难以满足实际应用的需要。对于高速实现MUSIC算法目前很多研究工作正在进行并且已经提出了很多方案来解决这个问题:()国内目前大多采用并行PDSPl对于八元阵而言能够把MUSIC算法的计算时间由单片处理的.ms降低到片处理器并行处理的.ms虽然加速比达到了.但是在很多实际场合仍难达到要求。为此国内对于MUSIC算法中的计算协方差和谱峰搜索两个步骤采用FPGA实现【】【。对于计算八元阵协方差而言使用目前器件可以在us内完成运算任务对于计算八元阵谱蜂搜索而言使用目前器件可以在us内完成运算任务。这两个步骤基于FPGA实现时间明显少于使用并行PDSP实现时间但目前国内对MusIc特征值分解步骤还不能用FPGA实现。一方面导致了整个MUSIC算法计算时间还不得不停留在ms量级另一方面导致整个系统涉及到FPGA和PDSP的互连互接问题涉及到FPGA的定点运算与DSP浮点运算的相互转换增加了设计难度。()国外已经采用FPGA来实现整个MUSIC算法Lgl其运算速度相对于PDSP而言已经有了很大提高。国外设计对于MUSIC算法中的特征值分解步骤采用了Jacobi算法对Jacobi算法中的非线性运算如反正切、坐标旋转采用了cORDIc算法来实现。在保证整个运算一定精确度的条件下可以仅用加法和移位就能实现并且计算速度大大增加:完成四元阵的MUSIC算法只需要.us使用逻辑资源是个LE完成八元阵的MusIc算法只需要.us使用逻辑资源是个LE。但是从另外的方面来看国外基于FPGA实现MusIC时特别是在特征值分解步骤时并行性不高还有可以改进的地方。.FPGA实现阵列测向算法的优点在阵列测向的许多应用场合中如移动通信中的空分多址的应用在复杂、密集的实际信号环境中电子侦察和对抗的应用等都面临着高速实现、小型化、低成本的要求。因此研究阵列测向算法的高速实现对于促进应用有着十分重要的意义。要高速实现阵列测向算法可以考虑采用适合算法的器件。目前实现阵列第一章鳍论测向算法的数字处理器件主要有三类:ASlC(ApplicationSpecificIntegratedCircuit)PDSP(PromgrammableDigitalSignalProcessor)FPGA(FieldProgrammableGateArray)。ASIC称为专用集成电路是为实现某种特定算法而定制的集成电路芯片。其主要由两类一类由门海构成一类由标准单元构成。它具有高集成度、高计算速度和高计算效率的优点但其硬件结构固定不具备通用性灵活性差成本较高实现复杂。PDSP是基于一种精简指令集的计算机专门为实现数字信号处理而设计可以在一个时钟周期内完成乘累加运算并具备独特的循环寻址和倒序寻址能力因而它获得了极广泛的应用在语音、图像、通讯、雷达、电子对抗、仪表仪器等各个领域均起着重要作用。采用PDSP器件能够很好的胜任条件进程特别是较复杂的多算法任务但在运算上受制于时钟速率和串行指令流的限制而且每个时钟内的有用操作受到限制。FPGA结构是由基于半定制门阵列的设计思想而得到的具有专用集成电路的特点可以在FPGA内部资源许可的条件下进行自由设计。FPGA能合理实现算法需要的各个处理单元并通过状态机(StateMachine)对算法进行控制从而可以按照算法需要将各个处理单元按照一定的结构映射到FPGA上。因为FPGA内部的结构是为算法专门设计的因此FPGA与PDSP相比最大优势是FPGA将不受到运算单元数量(如乘法累加器数量)的影响可以用最恰当、最高效的硬件结构实现算法提供更多的带宽运算速度相对于PDSP而言有较大提高。但同时FPGA实现阵列测向算法也有很多的不足和难点。FPGA实现浮点运算需要占用很多资源所以目前FPGA主要还是基于定点运算进行设计在一些对精确度要求很高的场合就无法使用FPGA:FPGA对实现复杂的不规则算法比较困难相比PDSP实现非线性运算也比较困难。在进行FPGA设计时候必须要考虑这些不足和设计困难。.本文的主要内容及章节安排本文所研究的信号子空间算法是MUSIC算法针对的阵列测向系统为四阵元的均匀线阵。本文所包括的主要内容有:()本文针对现有基于FPGA实现EVD的算法的不足提出更适合FPGA第一章绪论测向算法的数字处理器件主要有三类:ASIC(ApplieafionSpecificIntegratedCircuit)PDSP(PromgrammableDistalSignalProcessor)FPGA(FieldProgrammableGateArray)ASIC称为专用集成电路是为实现某种特定算法而定制的集成电路芯片。其主要由两类一类由门海构成一类由标准单元构成。它具有高集成度、高计算速度和高计算效率的优点但其硬件结构固定不具备通用性灵活性差成本较高实现复杂。PDSP是基于一种精简指令集的计算机专门为实现数字信号处理而设计可以在一个时钟周期内完成乘累加运算并具备独特的循环寻址和倒序寻址能力囚而它获得r极广泛的应用在语音、图像、通讯、雷达、电子对抗、仪表仪器等各个领域均起着重要作用。采用PDSP器件能够很好的胜任条件进程特别是较复杂的多算法任务但在运算上受制于时钟速率和串行指令流的限制而且每个时钟内的有用操作受到限制。FPGA结构是由基于半定制门阵列的设计思想而得到的具有专用集成电路的特点可以在FPGA内部资源许可的条件下进行自由设计。FPGA能合理实现算法需要的各个处理单元并通过状态机(StateMachine)对算法进行控制从而可以按照算法需要将各个处理单元按照一定的结构映射到FPGA上。因为FPGA内部的结构是为算法专门设计的因此FPGA与PDSP相比最大优势是FPGA将不受到运算单元数量(如乘法累加器数量)的影响可以用是恰当、最高效的硬件结构实现算法提供更多的带宽运算速度相对于PDSP而言有较大提高。但同时FPGA实现阵列测向算法也有很多的不足和难点。FPGA实现浮点运算需要占用很多资源所|三【目前FPGA主要还是基于定点运算进行设计在一些对精确度要求很高的场合就无法使用FPGAFPGA剐实现复杂的不规则算法比较困难相比PDSP实现非线性运算也比较困难。在进行FPGA设计时候必须要考虑这些不足和设计困难。.本文的主要内容及章节安排本文所研究的信号子空间算法是MUSIC算法针对的阵列测向系统为四阵元的均匀线阵。本文所包括的主要内容有:()本文针对现有基于FPGA实现EVD的算法的不足提出更适合FPGA(”本文针对现有基于FPGA实现EVD的算法的不足提出更适合FPGA电子科技大学硕士学位论文实现特征值分解的MCJacobi算法。MCJacobi算法增加了特征值分解的并行性因此特征值分解的时间只有原算法的/。()本文给出基于MC.Jacobi算法的EVD模块框图采用VHDL语言进行RTL级描述并进行功能仿真和时序仿真在建立FPGA硬件测试模型后在开发板上进行硬件测试。()本文给出MUSIC算法中协方差模块和谱峰搜索模块的FPGA解决方案给出了硬件实现框图用VHDL进行RTL级描述进行了软件仿真、硬件测试。()本文对MUSIC算法的各模块进行了互连调试工作。本文各章节的安排为:第一章是绪论:第二章介绍MUSIC算法基本原理介绍了MUSIC算法的预处理方法同时基于MUSIC算法的运算步骤划分FPGA设计模块:第三章针对现有特征值分解算法的不足提出FPGA可实现的MC.Jacobi算法分析了MC.Jacobi算法的运算量统计MC.Jacobi算法的误差第四章介绍基于MC.Jacobi算法的EVD模块框图基于VHDL语言进行了软件仿真基于本文设计的硬件测试方案进行FPGA硬件测试第五章介绍MUSIC算法中协方差模块和谱峰搜索模块的硬件结构框图利用VHDL语言进行了时序仿真并互连MUSIC算法的各个模块第六章是全文总结和后续工作。第二章基于FPGA实现MUSIC算法的基本方案第二章基于FPGA实现MUSIC算法的基本方案MUSIC算法是基于特征结构分析的信号子空间方法是信号子空间方法的典型代表。其测向原理是根据矩阵特征分解的理论对阵列输出的协方差矩阵进行特征值分解(EVD)将信号空间分解为噪声子空间和信号子空间利用噪声子空间与阵列的方向矢量正交的性质构造MUSIC伪谱函数户(曰)并进行谱峰搜索从而估计出波达方向信息。基于FPGA实现MUSIC算法时候从宏观方面需要解决两个问题:一方面需要把MUSIC算法的复数运算转换到实数运算本章第节介绍的预处理可以解决这个问题另一方面要进行FPGA模块划分设计各个模块的基本架构分析各个模块设计的重点和难点规划模块间的数据接口这将在本章第节中阐述。.MUSIC算法设空间有D个互不相关的信号分别以方位角靠从远场(信号源与阵列天线距离大于信号源信号的波长倍以上)入射到阵列时可以近似认为该信号到各天线阵元的方向角一致。如果入射信号的数目D小于阵列的阵元数N则阵列的输出矢量如式():X(t)=AS(t)N(t)()其中x(f)=h(f)X:(})X。(r)为阵列接收信号s(t)=S。(f)S(f)SO(f)为辐射源入射信号A=陋(最)日(吼)口()。。。是阵列的方向矩阵其中a(k)是方向矢量与阵列流型有关是个复数矩阵:N(t)='tI(f)n(f)nⅣ(f)为噪声矩阵。那么阵列输出矢量x(t)的协方差矩阵:R=eXX“】彳BA”盯()其中Rs=ESS“】为信号协方差矩阵盯=ENN“电子科技大学硕士学位论文方向矩阵各列相互独立在入射信号都不相关的情况下Rs为非奇异阵所以有:Rank(ARsA“)=D由于R。是正定阵则矩阵彳爱。彳”是非负定的共有D个正的实特征值和(ND)个零特征值。将这N个实特征值按照降序排列记为^如“分别对应N个特征向量vvvⅣ。协方差矩阵中与信号相关的特征值有D个分别等于矩阵ARsA”的各特征值和口之和协方差矩阵中其余的(ND)个特征值则为盯于是R的特征值可以分为信号特征值和噪声特征值两个子集对于特征向量也可以分为信号特征向量和噪声特征向量。这样就把整个特征向量空间分为信号子空间风和噪声子空间Eu。其中信号子空间Es=IVIv:v。】噪声子空间日=lk。vD.v。】。可以证明噪声予空间和方向矢量彼此正交于是构造MUSIC伪谱函数P(口)并进行谱峰搜索:联垆面薪幢。’这样P(O)中D个最大值对应的D个目就是待求的信号源的方向。对于四阵元的均匀线阵N是等于从而阵列的方向矩阵A可以如下:A=【口(岛)口(包)口(如)】。。其中:()D<:()d(只)=P一。耐锄品“e』耐“““ejndsin靠】(.)其中d是阵元间隔五是信号波长。.预处理实现从式(.)可以知道阵列的方向矩降A为一个复矩阵那么由式(.)可推导出阵列的输出矢量X(t也是一个复矢量。因此在应用MUSIC算法时各种计算都是复数运算。然而可以证明对于一个偶数阵元的对称阵列可以通过一种简单有效的预处理方法【l将复数矩阵彳转换为实数矩阵把复矢量z(f)用~个实矢量来代替从而将各种复数运算转换为实数运算。由于一次复数乘法相当于次实数乘法和次实数加法一次复数加法相当于次实数加法。因此通过预处理兰三童苎三!里垒窒堡!型!笙簦垦塑苎查查薹可以大大的减少算法的计算量从而达到加快MUSIC算法处理速度的目的。本文所针对的四阵元均匀线阵显然是个偶数阵元的对称阵列所以可以采用该方法。将元均匀线阵如图.所示分成两个子阵SublSub预处理方法可以简要说明如下:SubSub:q图元均匀线阵设SublSub方向矩阵分别为Ai、A,于是有:Xl(f)=AlS(t)Na(t)x(f)=As(t)N(t)其中X。(f)X:O)分别为子阵Subl和Sub的输出向量阵Ⅳ。(r)Ⅳ:(r)为噪声向量。方向矩阵A、A:具体形式如下:A。=k。(岛)a(吼)口(%)】其中al(目女)=【P“Ok“口td”以“A:=k(日:(敬)a(%)】其中a(幺)=P一““。“口卅““。“ns(o为信号矩(.)(.)从()和()可以看出两个子阵的方向矩阵爿。、A是互为共轭对称的即有A=A:’。于是构造~个线性变换矩阵T:T=土。土o三o!土。一上ojZjjjo土。一上下面对x(t)作线性变换设作线性变换后得到y(f)那么电子科技大学硕士学位论文】p)=TX(t)=TLI础XI(t!)J呜s。)Ⅲ(f)其中l主lk(B)吒(幺)口(铭)】()姒最):fcos(nds丁in~Ok)c。s(rMsin叫k.sin(华nL,戒/sin一kJ.。几^^从式()可知道此时方向矩阵是一个实矢量当S(t)为实信号时则r(t)是一个实矩阵用y(f)代替J()于是协方差矩阵月=EⅣ”】变成了一个实对称矩阵。这样就可将MUSIC算法的计算由复数域转到了实数域。图、显示了未用预处理和使用预处理后的MUSIC伪谱图可以证实预处理方法是有效且可行的.图未做预处理的MUSIC算法仿真图第二章基于FPGA实现MUSIC算法的基本方案例做过预处理的MUSIC算法仿真图因此针对四阵元均匀线阵该预处理方法的应用可以通过如下方式来进行:用第Subl阵元接收机输出的实部作为接收数据用Sub阵元接收机输出的虚部作为接收数据。这样就完成了预处理操作而不增加额外的计算量。.MUSIC算法的FPGA模块划分完成预处理后MUSIC运算从复数运算转化为实数运算。一般对MUSIC算法的运算划分为以下三个步骤:()计算协方差矩阵()特征值分解()谱峰搜索。可以看出MUSIC三个步骤为顺序执行有明显的串行性。在进行FPGA模块划分时可以对应MUSIC算法三个步骤设计三个模块来分别实现它们再通过模块间的互连实现整个MUSIC算法。图给出了经过预处理之后MUSIC算法的模块划分本文所有设计将按此进行模块设计。电子科技大学硕士学位论文预曩方VD:|||}}}嚣i处理叫差卜一鬈广模模模i磊i块块{j块{{筷i图MUSIC算法的FPGA模块下面分析三个模块基本组成:对于协方羞模块其功能是根据NM的数据矩阵(N对应阵元阶数M对应采样点数)得到协方差矩阵。从本质讲该模块是计算一个NM矩阵与其自身转置(MN矩阵)相乘从而得到一个ⅣⅣ的对称协方差矩阵。分析矩阵乘法的过程协方差模块核心结构是乘法累加器。对于阶对称协方差矩阵而言需要求出的协方差矩阵的元素是个主对角元素和个上三角元素所以可以设计个并行的乘法累加器从而每个时钟都可以同时进行次相乘累加。另外考虑到数据矩阵在读入该模块前已经保存在RAM中该部分处理需要高数据吞吐量设计合理的流水线是设计本模块需要重点考虑的。对于EVD模块应该是FPGA实现MUSIC算法的难点其功能是根据协方差矩阵计算出特征值和特征向量。该模块首先需要确定特征值分解算法。考虑到MUSIC算法进行特征值分解的目的是得到精确特征向量可以在Jacobi算法和QR算法中间选择。其次无论选择何种特征值分解算法中间一定包含大量的乘法和非线性运算如何合理的实现这些运算是用FPGA进行设计时候必须考虑问题。最后因为本模块处在三个模块中间设计与前后模块的数据接口、控制接口也是必须要考虑的。对于谱峰搜索模块其功能是根据EVD模块输出的特征值和特征向量构造噪声矩阵然后按照式()进行计算。在设计本模块时首先可以把式(。)中计算MUSIC伪谱函数最大值的问题等价转化为直接计算JJE若d(臼)虻最小值问题。其次对于方向矢量可以参照式(.)通过个ROM表把a(目)()的值进行存储运算过程中只需要从表中读出方向矢量值即可这样计算忙:口(曰)虻可以IIZ等效为计算内积后做平方和运算。最后需要设计比较单元根据计算忙盘徊)IIZ出的值找出其D个波谷。该部分模块也需要高数据吞吐量设计合理的流水线将会使本模块的速度大大提高。第二章基于FPGA实现MUSIC算法的基本方案在实际设计过程中本文采用了定点运算所以还需要保证模块间的数据位数一致:即每个模块输入与上级模块输出的数据位数保持一致同时其输出与下级模块输入的数据位数保持一致。否则必须进行移位来保证模块间的数据位数一致。本文在数据位数采用下述规定:协方差模块输入端的数据位数是bitEVD模块输入端的数据位数是bit谱峰搜索模块输入端的数据位数是bit。考虑到MUSIC算法中EVD步骤的运算量最大同时在上述三个模块中EVD模块的设计难度最大本文将首先设计EVD模块。第三章将提出实现EVD模块的MC.Jacobi算法在第四章将基于MC.Jacobi进行EVD模块设计第五章将设计MUSIC算法中的协方差模块和谱峰搜索模块并把这两个模块和EVD模块进行相连从而可以完成MUSIC算法三个模块以实现MUSIC算法。电子科技大学硕士学位论文.引言第三章MCJacobi算法EVD步骤的计算量大概占到了整个MUSIC方法计算量%提高该步骤的速度将对减少MUSIC算法计算时间起到重要作用。其次基于信号子空间方法的各种算法(如ESPRIT等)都有特征值分解的运算步骤所以特征值分解的高速实现又可以做为一个相对独立部分应用在基于信号子空间的各种算法中去因此在实际中将会有广泛的应用。EVD步骤主要是计算实对称的协方差矩阵的特征值和特征向量。目前计算对称矩阵全部特征值和特征向量一般采用正交变化法。它的理论依据是将实对称矩阵R的特征值问题转化成计算其相似矩阵的特征值问题而转化过程是采用正交相似变换。根据所采用的分解矩阵又分为Jacobi算法与QR算法。Jacobi所采用的分解矩阵是平面旋转矩阵直接将R化为对角矩阵:而QR算法采用的Householder矩阵先将R化为对称三对角矩阵然后再用QR法求对称三角矩阵的特征值。QR算法收敛速度要比Jacobi算法快但在使用FPGA实现特征值分解时候往往采用Jaeobi。因为Jacobi具有高度的并行性和易于FPGA实现的特性。本文选择的进行特征值分解的算法是Jacobi算法并且是Jacobi算法的改良方法顺序Jacobi算法后文为叙述方便都以Jacobi算法代替顺序Jacobi算法。本章节主要介绍的是国外设计的EVD处理器J中使用的两个算法在第节分析上述算法不足后在本章节提出自己的两点改进:()改进了Jacobi算法迭代结构:()创新提出改进CORIDC坐标旋转该算法能高速并行实现Jacobi算法中的反正切步骤和坐标旋转步骤。本章第节主要根据第两节提出的两点改进给出FPGA可实现特征值分解的算法MC.Jacobi算法(基于改进CORDIC的Jacobi算法)。第节介绍MCJacobi算法运算量第节统计定点MC.Jacobi算法的误差。第三章MC.Jacobi算法.Jacobi算法Jacobi算法是计算实对称矩阵特征值的算法之一【。它使用一系列实平面旋转把实对称矩阵化为对角矩阵。在acobi算法中对N阶对称矩阵足的上三角元素按算法依次置反复迭代后矩阵R收敛成对角矩阵此时可得到矩阵R的特征值和特征向量。如果令P=q=那么Jacobi算法单次迭代步骤如下:()计算反正切:驴一去。根据pg值从对称矩阵R中$一r。、%和‰计算反正切得到旋转角%:()计算次坐标旋转:OCOS‰sin%一sin%COS%()R’=%R陟()在第()步计算得到旋转角%后按照()构造旋转矩阵‰然后按照()算出矩阵月’。式()运算等效于做次坐标旋转。()判断:如果R’已经转化为对角矩阵则跳出迭代此时R’即为所求否则令R:Rr按照n寸一Ⅳ斗斗斗Ⅳ一r(Nm)的顺序选择下一次“扫描”对象r。(Pq值改变)返回第()步重新计算。上述就是Jacobi算法单次迭代过程。在单次迭代后矩阵只的上三兔元素r~约等于O从而在一定的迭代次数后对称矩阵冗转换为对角矩阵。因此后文对元素‰的单次迭代也称为“扫描”元素~。电子科技大学硕士学位论文当用Jacobi算法确定特征向量时只需要初始特征向量矩阵为N阶单位阵V当“扫描”元素‰时特征向量矩阵y将只有第pq列元素变化设变化后的特征向量矩阵是V’则变化公式如下:=,矩阵阶数Ⅳ特征向量矩阵计算本质就是做次坐标旋转。当Jacobi算法进行下次迭代时只需要令矿=矿’即可。从Jacobi算法单次迭代来看需要解决的运算是第()步的反正切计算和第()步的坐标旋转计算。CORDIC算法可以仅用加法和移位就实现这两种运算非常适合FPGA实现。下节对CORDIC算法进行介绍。.CORDIC算法CORDIC(CoordinateRotationalDigitalComputer坐标旋转计算机)算法【l驯是Voider等人于年在美国航空控制系统的设计中提出来的它是~种用于计算~些常用的基本运算函数和算术操作的循环迭代算法。其基本思想是用一系列与运算基数相关的角度逼近所需旋转的角度。在传统的硬件算法设计中乘、除等基本数学函数运算是一种既耗时又占用面积大的运算甚至有时是难以实现的CORDIC算法正是为解决这种问题而产生的。它从算法本身人手将其分解成为一些简单的且在硬件中容易实现的基本算法如加法、移位等因此使得这些算法在硬件上可以得到较好的实现。又由于该算法是一种规则化的算法它满足了硬件对算法的模块化、规则化的要求因此CORDIC算法可以充分发挥硬件的优势利用硬件的资源从而实现硬件与算法相结合的一种优化方案‘j。下面介绍CORDIC实现坐标旋转的原理和基本步骤反正切运算与此类似不再赘述。r坐标旋转数学描述方式如下:已知初坐标fi和旋转角%需要求出旋转后Loj的坐标fy:l其中ly:}满足式():啊啊丌ii儿跏蹦姐一C叫叫目护菪.蛐............L=lJ.妒月py............L第三章MC.Jacobi算法计隧螂sin讣Oop,y。使用CORDIC算法解决坐标旋转时候定义CORDIC的基本角度集口和CORDIC符号集孝具体形式如下:a=妇lqat}={arct~arct~arct“)孝={掌。氧善)={掌=l或一i=,k)其中k称做CORDIC阶数可以根据精度进行选择。CORDIC算法实现过程就是确定符号集毒中毒(f,.k}的值使之满足:lzt={al即对于:旋转角%用:旋转角站逼近。而坐标:旋转角‰等价于IyI旋转CORDIC基本角{岛q缶%磊吼)所以式(.)可以近似等效成:yxjz『L。s。inG亭}a口,女sinG。口a。‘一。C。iOnS苣孝I口(Zsin掌,ctcoscos夤(z。‘Lyxcs.sl以jLsin掌t%。J』实现式()需要解决两个方面问题:()如何根据屯去确定符号集毒中专(fl女)的值()如何用加法和移位实现旋转一个基本角盘。。先看第()个方面首先定义pr%一岛a只一.在可以理解为转过(i)个CORDIC基本角后与实际需要旋转角。的误差它越小说明误差越小越逼近角度移。。所以当B一。大于要想逼近opt下次旋转必然是顺时针旋转则令鲁=那么臼=i一一口反之若只一小于要想逼近口。下次旋转必然是逆时针旋转则令茧=一那么=。口。这样就可以根据%的值确定符号集孝中皇(f,尼)的值(点直接根据%的正负判定)。再来看第()ff'b面设坐标fLyx。,JI是坐标LI靠X,JLx/l旋转口中一个基本角q后得到即满足式():皇王型苎查堂堡圭兰竺堡奎一x=L咄sin亭鲁ia仉,螂sin驰善,a‘他XjI仔。因为苣=或一:所以上式等效ft一量tgtx门fyHl“qk姚l儿H一又因为d。=arct~即培口=~则y:l:coso,b黧:jcs上式中的COSOE。可以认为是常数(因为口是CORDIC基本角)在迭代过程中不需要处理只需要在迭代完所有coRDIc基本角乘以固定常数co删=lICOSt:Z做模值修正即可。在简化cos瑾处理后式()可以只用加法和移位就能实现。i=,Order是cORDIC阶数初始坐标是f:J旋转角是%归纳coRDIc实现坐标旋转步骤描述如下:()根据屯正负判断专的符号。()计算%‘。%。’=‰一善呸(口为固定常数arct“)()计算b’x’r。即计算:黔品一矧圈()如果forder输出砂’工T那么constLy‘x‘r(模值修正)就是所求否则令f=i后口。=口。’【yxr=【y’x‘r后回到第()步进行.改进思路国外设计的EVD处理器就是基于本章第节介绍的Jacobi算法对于Jacobi算法中的反正切和坐标旋转两种运算采用第节介绍的CORDIC算法来实现。结合本章第节介绍的Jacobi单次迭代步骤EVD处理器流程图如图所示:只一口裟一%mc岳IIyX第三章MCJacobi算法协方差矩阵R:特征向量矩阵V(N阶单位阵)尺=R矿=y计算CORI)IC反正切次CORDIC坐标旋转CORDIC模值修正J判断R’输出月’.t图基于CORDIC的Jaeobi算法因为CORDIC算法可以用加法和移位就实现这样EVD模块也可以仅用加法和移位实现。该设计非常适合在FPGA中实现。但在Jacobi算法的单次迭代过程中必须按照{反正切运算一坐标旋转运算斗坐标旋转运算}顺序串行运算单次迭代的并行性【】相对很差。考虑到当用同样阶数的CORDIC实现坐标旋转和反正切两种运算时运算时间基本~致即实现上述Jacobi单次迭代需要fc。m时间(tcoRDfc表示单次CORDIC运算时间)。单次迭代的并行性很差这是国外设计的主要不足。本文提出的两点改进方案正是解决Jacobi荜次迭代中存在的不是:()改进Jacobi算法迭代结构在采用此改进后单次迭代过程变为:f反正切运算寸坐标旋转运算单次查表乘法J因为单次查表乘法运算时间明显少于rc。舳c所以此改进下的Jacobi单次迭代时间降为tcDRDc。()本文提出的改进cORDIC坐标旋转。在使用该算法后单次迭代过程变电子科技大学硕士学位论文为:钽殳进coRDIc坐标旋转岭坐标旋转运算使用改进坐标旋转算法可以在不使用反正切计算出旋转角的情况下实现坐标旋转从而可以简化掉反正切运算因为改进CORDIC坐标旋转运算时间也基本是‘(蚴c所以此改进下单次迭代时间也降为tc。在综合使用上述两点改进后本文提出了MC.Jacobi算法(基于改进CORDIC的Jacobi算法)该算法单次迭代过程是:{改进coRDIC坐标旋转单次查表乘法}MCJacobi算法单次迭代时间仅略多于fcⅢc时间仅为原来的单次迭代的/左右所以特征值分解的时间也降为IN夕I"设计/左右。下面节将分别叙述两个改进和MC.Jacobi算法。.改进Jacobi算法迭代结构在Jacobi算法单次迭代中当通过反正切模块计算出旋转角瓦。后对公式()展开可以得到:第一类:第二类:第三类:口=r一roge叫rqqrqqrAm‘=rqrCOSO叩l一目sinoopi‘=osin掣‘cos叫(』p、g)()()()对比本章第节叙述的lacobi算法单次迭代的三个步骤此时Jacobi算法单次迭代的步骤变为以下步:()计算反正切:利用CORDIC算法近似求出旋转角只。()CORDIC坐标旋转实现求出R。中‘和‘(/P、q)与此同时可以根据()把步骤()中求出的。叫经过从%映射喀%查表和乘法运算后求出R’中的‘‘而对‘采取直接置的方式上述完成了对称矩阵R到胄r的迭代。第三章MC.Jacobi算法()判断发现改进后虽然用到了查表和乘法等非线性运算但是Jacobi单次迭代步骤()的两次坐标旋转运算转化为一次坐标旋转和一次查表乘法并行运算因为单次查表乘法运算时间明显少于f。。Ⅲc步骤()的运算时间从f。Ⅲ。降为rcan一而Jacobi单次迭代总时间从r。眦降为fⅢc。使用FPGA实现查表和单个乘法器时可以充分利用FPGA中的RAM资源和硬件乘法器从而这种改进在硬件实现上也是有效可行的。.改进CORDIC坐标旋转参照本章第节介绍的旋转一个CORDIC基本角口的方法当把Jacobi算法单次迭代第()步求出的耽。作为已知值送入到CORDIC坐标旋转后可由P。产生符号集碍岛磊)(k是CORDIC阶数)。符号集{轰舌:蟊)的产生过程是由%g最。分剐与。比较注意到在Iacobi算法中{%l<%因此同样可以根据留‰ttk一的正负确定符号集{氧孝:氕)因此如果已经知道僖口。tlI.tt,一。的分子和分母的正负也就同样能确定符号集{点岛氕)。S(t,兹(f.卜)o令Jacobi算、法中喀p的分子分母分别是脚步根据公式()则有y=‰和=。一从而可以确定点e假设能通过N弋,gOa饥届)坎屈}执。层一。)那么符号集{岛彘)就能确定。假设留%一筹已知那么根据n。和屈一的正负可以确定符号位苣是还是.那么有如下推导:留毋瓮tg(统r舌隅):堡!坠二圭擅!竺亭tgJta。一(卜I)又因为有tga=I百那么有象=等高嚣畿pⅢ(一一n)卢卜l孝叫卜”y一。。电子科技大学硕士学位论文根据式(.)可以看出改进CORDIC坐标旋转与普通CORIDC坐标旋转一样也可以使用加法和移位来实现具体框图如图.:Ai模块广一一一f’一一减法器孝寄存器位移(i)矸tj:减i瓦H鎏女Ⅱ馕法嚣lLJ’I一一一一一一~一.}=一I图改进CORDIC坐标旋转的符号集迭代发现在使用改进坐标旋转后可以不用计算曰。而在只知道姆眈的分子分母的情况下计算坐标旋转。更具体的对于Jacobi算法可以直接从矩阵中提取矩阵元素rpq、~及‰后计算出‰和%一‰的值后作为改进CORDIC坐标旋转的初值进而产生符号集{卣岛磊)从而可以直接做坐标变换。而国外设计的计算皖。反正切步骤可以直接省略这样将大大减少单次迭代时间。因为坐标变换往往都是用较高阶的CORDIC来实现因此使用改进后的CORDIC坐标变换等价于月高阶的CORDIC反正切求出口。。后做CORDtC坐标变换这样在减少时间的情况下整个运算的精确度不会受任何影响。.MC.Jacobi算法本章第、两节提出的改进方法彼此独立它们都可以使单次迭代时间从ICORDI。降为f。。。。。本节讨论的问题是如何综合使用这两种改进从而最大限度缩短单次迭代时间。在同时使用两个改进时必须要解决它们之间存在冲突:因为改进CORDIC坐标旋转不用反正切计算出眈直接计算坐标旋转而在改进Jacobi算法迭代结构中计算第一类矩阵元素变化时候必须要知道矽。后查表得到喀。。那么如何在使用改进CORDIC坐标旋转的同时(未知眈。)也能使用改进Jacobi算法迭代结构(要求已知瑶。.)。o第三章MCJacobi算法在实际处理过程中根据CORDIC算法原理CORDIC坐标旋转的实际旋转角屯=艺毒嘶。因为“=argt是己知角所以实际的旋转角屯可以由确定符号集毒唯一确定留屯又可以由屯唯一确定。所以一个确定符号集毒可以确定一tgOo,所以可以建立从符号集善映射到喀屯固定表来取代从屯映射到培站固定表从而解决两个改进的冲突。另外对于CORDIC的模值修正在改进CORDIC算法中也存在该运算。const=兀COSa。在女lo时consl近似等于常数.从而可以采用固定的移拉位和加法组合来近似实现常数乘法即consfz兰兰三一三一三一!l一:.'x()下面归纳本文提出的MCJacobi算法如下:()计算r=m‰、参=~一%q()把y、和需要旋转的坐标作为改进CORDIC坐标旋转的初值计算坐标旋转()在第()步中确定符号集孝后通过查表和乘法器后可求出~’、‰’对‰’直接置。()判断。MC.Jacobi算法流程图如图.所表示:图MC.Jacobi算法流程图电子科技大学硕士学位论文.运算量分析下面对MC.Jaeobi算法的运算量进行分析。假定矩阵的阶数为N利用CORDIC算法实现坐标旋转的阶数为Order。MC.Jaeobi算法为一个循环迭代、并且把初始对称矩阵变换为对角形矩阵的过程弹次迭代运算量固定。下面先分析单次迭代运算量:()MCJacobi算法步骤()中对应次移位操作和次Add/Sub操作:()MCJacobi算法步骤()会将步骤()计算出的、送入到Order个如图结构中单个结构的运算量为次移位操作和次Add/Sub操作所以该部分运算量=Order(ShiftsAdd/Sub):矩阵阶数为N时有(N.)对的对称矩阵元素和N对特征向量矩阵元素需要做坐标旋转所以总的坐标旋转次数是(N.)次。次坐标

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/13
仅支持在线阅读

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部