关闭

关闭

关闭

封号提示

内容

首页 基于FPGA的特征子空间目标识别法的关键技术研究.pdf

基于FPGA的特征子空间目标识别法的关键技术研究.pdf

基于FPGA的特征子空间目标识别法的关键技术研究.pdf

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

简介:本文档为《基于FPGA的特征子空间目标识别法的关键技术研究pdf》,可适用于IT/计算机领域,主题内容包含电子科技大学硕士学位论文基于FPGA的特征子空间目标识别法的关键技术研究姓名:杨垒申请学位级别:硕士专业:信息与通信工程指导教师:窦衡摘要摘要雷达目符等。

电子科技大学硕士学位论文基于FPGA的特征子空间目标识别法的关键技术研究姓名:杨垒申请学位级别:硕士专业:信息与通信工程指导教师:窦衡摘要摘要雷达目标识别是现代雷达技术的一个重要发展方向雷达技术的日趋成熟使雷达目标识别逐步走向实用。本文对基于FPGA的特征子空间雷达目标一维距离像识别法的关键技术单精度浮点SVD处理器的实现进行了研究。论文研究了在FPGA资源有限的前提下实现对高阶矩阵奇异值分解的高速度和高精度处理要求。论文给出了几种处理器核心运算单元的结构并改进了基本矩阵运算单元设计和元素调度方法对这些结构在速度、资源占用和数值精度上进行了详细的比较和分析。最后对这几种结构在各方面性能和优化上的考虑给出了单精度浮点SVD处理器的整体设计方案并对其性能进行了测试分析。论文的主要内容为:、介绍了基于奇异值分解的特征子空间目标识别法并研究了用于FPGA实现奇异值分解的双边雅克比算法、BLV阵列结构和雅克比算法的并行调度规则、为了实现SVD处理器高速度和高精度的要求研究了CORDIC的两种算法的FPGA实现方式传统的CORDIC算法和基于GA算法的改进型CORDIC算法对改进型CORDIC算法的补偿因子为不定值的设计上给出了相应的设计方案并设计完成了CORDIC基本计算单元单精度浮点加/减法器、在资源、速度和精度上的考虑完成了SVD处理器的两个关键计算单元的设计角度计算单元和旋转计算单元。对角度计算单元通过查找表的设计改善求解角度的运算速度对旋转计算单元设计以双平面旋转(TwoPlaneRotationTPR)方法为基础给出了三种设计方案并对其结构进行了比较和分析、给出了单精度浮点SVD处理器的整体结构对其各个模块的设计给出了详细的说明。设计改进了矩阵的并行调度方式采取分组分类的方法完成矩阵元素的调度。对矩阵核心运算单元利用以上结构组合采用通用并行方式完成设计。通过对x矩阵仿真详细比较了各个结构的资源、速度和数值精度情况、为了进一步改善SVD处理器的性能减少结构中由于角度计算单元造成的资源消耗并提高处理器时钟优化性能在保证数值精度的前提下利用阶差估计sin/cos的方式和FPGA的资源整合并采用上述处理器的结构方法完成SVD处理器的整体设计并通过仿真测试验证和分析了这种结构的性能。关键词:特征子空间法SVD处理器雅克比算法CORDICTPRABSTRACTABSTRACTRadartargetrecognitionisailimportantdevelopingfieldofmodemradartechnology.Radartechnologyisbeingmaturewhichmakesittobepractical.InthedissertationFPGAimplementationofasinglefloatpointSVDprocessorisresearched,whichisakeydesignfortheeigensubspaceextractionalgorithmusingSingularValueDecomposition(SVD).InthelimitationofresourcesonFPGAthedissertationresearchstheinplementationofprocessorbyhi曲一speedandexactnumericalprecision.theservalarchitecturesofkeycomputationunitalepresentedandthebasiccomputationunitandtransmissionruleofmatrixareimproved.Thesearchitecturesarecomparedandanalyzedindetailintermsofspeed,areaandnumericalprecisionbysimulation.Finallythearchitectureofprocessorwhichisconsidedbyitsperformanceandoptimizationdesignispresented,andtheperformanceofthisSVDprocessorisvalidatedbysimulation.nemaincontributionsofthisdissertationaleasfollows:.TheeigensubspaceextractionalgorithmusingSingularValueDecompositionisdiseased.ThreemethodswhichcomputeSVDonFPGAarestudiedincludingTwosidedJacobiAlgorithmthearrayarchitecturecalledBLVandtheparalleltransmissionruleofmatrix.Inordertosatisfytheperformanceofarea,highspeedandexactnumericalprecision,twoalgorithmscalledconventionalCORDICalgorithmandmodifiedCORDICalgorithmbasedGreedyAgorithm(GA)arediscussed.ThescalefactorofmodifiedCORDICalgorithmisvariablethedesignsolvestheproblem.Meanwhileasinglefloatpointadder/subtracterisimplementedinthedesign.Thedesignsoftwokeycomputationunitsarepresentedinthisdissertation.Intheangleunit,thedesignimprovestheperformancebyLookUpTable(LUT).IntherotationuinttheTwoPlaneRotationmethodisusedtodesignit.Inthedisseration,servaldesignsfortherotationuintarepresentedtoimplementonFPGAindetail.mentirearchitectureofasinglefloatpo砬SVDprocessorispresentedinthisdissertation.ThedisserationintroducesthedesignsofallofmodlIlesinSVDprocessorindetail.nledesigninthisdissertationimprovestheparalleltransmissionruleofTI竺婴盟m咖xtoⅡl仃duceallefficientmethodtoachievetheelementtransmission.ForthekevcompⅡ铷onunit,thedesignsmakeuseoftheabovearchitecturesaIldp删leIbasicmodulestoimplementTheperformancesofmatrixusedabovearchitecturesarecomparedandanalyzedintermsofspeedareaandnumericalprecisionAne伍cientmethodcalledallestimatedsin/cosmethodisimroducedtoachievethesvDprocessordesigntodecreasetheareasandimprovethepe墒珊ancenFPGA.Thedesignofasinglefloat。pointSVDprocessorisachievedbythismethodandtheresoWCesaIldspeedareoptimizedandaboveentirearchitecture.ThesimulationvalidatestheperformanceofthisSVDprocessor.K铡ords:Eigen。subspacemethodSVDprocessor,JacobiCORDICTPRIII独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知除了文中特别加以标注和致谢的地方外论文中不包含其他人已经发表或撰写过的研究成果也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。签名:鸟垒日期:硼年¥月尹日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定有权保留并向国家有关部门或机构送交论文的复印件和磁盘允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后应遵守此规定)签名:扬垒导师签名:塞堡呈日期:研年妒月如日第一章绪论.研究背景及意义第一章绪论雷达目标识别(RadarTargetRecognitionRTR)指用雷达设备获取目标的特征信息回波并利用已掌握的各种目标的先验知识判别未知目标的类别属性fl】。它根据目标的后向电磁散射来鉴别目标是电磁散射的逆问题。年美国人D.K.Barton就曾通过精密跟踪雷达的回波信号分析出前苏联人造卫星的外形和简单结构如果以之作为RTR研究的起点RTR至今已走过五十多年的历程在目标特征信号的分析和测量、雷达目标成像与特征提取、特征空间变换、目标模式分类、目标识别算法的实现技术等方面都取得了不同程度的突破这些成果的取得使人们相信RTR是未来新体制雷达的一项必备功能。雷达目标识别是根据雷达目标回波进行的一种模式识别因而也遵循模式识别的一般步骤即包括信息获取、预处理、模式特征提取及模式分类决策。根据雷达的探测手段以及应用背景的不同出现了多种识别方法其中雷达成像识别技术作为雷达目标识别的一种新技术正在日趋成熟。当雷达发射并接收窄脉冲或宽带信号其径向距离分辨率远小于目标尺寸目标可以模型化为各自独立的散射中心的集合这些散射中心在雷达径向距离上的分布情况便成为一维距离像。利用距离.多普勒联合成像处理技术可获得目标各散射中心散射强度在一个二维平面上的投影即二维像。而与二维成像雷达(SAR、ISAR无线电摄像机等)造价高和技术难度大相比易于实现的一维成像雷达在目标识别方面则有着广阔的前景。目前对基于一维距离像的子空间方法已进行了广泛而深入的研究在普通特征子空间法的基础上提出了正则子空间法、修正特征子空间法、综合子空间法、子空间串法等多种子空间方法【。在仿真与实测数据的识别中均取得了较好的效果。特征子空间的建立是这些算法的核心部分可以通过奇异值分解的方法来建立特征子空间。奇异值分解是一个在上个世纪初就已在线性代数中出现的古老概念自上世纪年代以来它成了线性代数中~个最热门的研究专题。奇异值分解作为矩阵计算、分析的强大工具之一在统计分析、信号与图像处理、系统理论和控制中被广泛地应用。在本论文中利用奇异值分解良好的性质通过其建立特征子空电子科技大学硕士学位论文问同时由于雷达目标一维距离像识别法过程中需要将采集到的样本加入目标库并使用奇异值分解实时更新目标特征因此需要很高的奇异值分解的数值精度和运算速度这就需要研究建立一种高效的SVD处理器本论文的主要工作正是研究基于奇异值分解的特征子空间目标识别法的FPGA实现的关键技术单精度浮点SVD处理器的实现。此外FPGA中资源的局限性也是本论文设计的一个难点所以在FPGA中使单精度浮点SVD处理器的占用面积、运算速度和数值精度上都到达一个很好的效果实现对高阶矩阵的高速和高精度处理的要求是本论文的另一意义所在。.研究现状在模式识别中良好的特征提取有益于识别率的提高在各种特征类别中代数特征反映了图像的内在属性是一种本质特征而奇异值特征正是一种性质良好的代数特征。正是由于有着这种良好的性质奇异值分解被广泛应用于信号处理中例如:图像压缩、方位估计、频谱分析和模式识别等。随着应用的提高许多方式中对于奇异值分解的实时性提出了很高的要求这就需要设计一种高性能系统用于满足算法应用中对于计算速度的高要求。FPGA是一种十分高效的器件它丰富的内部资源使设计者可以随心所欲的设计自己的方案其并行性的特点也使得它在算法设计上具有相当好的速度上的优势。随着可编程逻辑设计技术的高速发展新型的FPGA/CPLD的规模越来越大成本也越来越低。高性价比使可编程逻辑器件在硬件设计领域扮演着日益重要的角色。低端CPLD已经逐步取代了系列等传统的数字原件高端的FPGA也在不断地夺取ASIC的市场份额特别是新一代的FPGA中集成了中央处理器(CPU)或数字处理器(DSP)可以在一片FPGA上进行软硬件协同设计为实现片上编程系统(SystemOnProgrammableChipSOPC)提供了强大的硬件支划。】【引。这些高性能的FPGA为本课题设计实现单精度浮点SVD处理器创造了非常好的硬件平厶:o国内外的广大学者对利用FPGA实现SVD算法的处理器设计进行了深入的深究和探讨很多有效的算法和结构被给予。Cavallaro和Luk【】通过直接使用CORDIC的两种计算模式矢量模式和旋转模式分别完成角度和旋转的计算。Yang和BohrneEl为了进一步的减少实现SVD算法时的计算量应用了一种有效的方法一一双平面旋转(TwoPlaneRotationTPR)。这种方法通过两个并行矩阵的并行计第~章绪论算实现奇异值分解被认作是一种十分高效的CORDIC.SVD实现方式。Brent、Luk和VanLoaIl【】提出了一种用于计算刀/,/实矩阵奇异值分解的一种阵列结构一BLV阵列这种结构很好的实现了矩阵SVD的运算充分体现了FPGA硬件的并行性的特点是一种经典的阵列结构。在这些算法和结构的基础上许多研究设计中为了体现FPGA实现SVD算法的高效性设计及改进了用于FPGA实现的SVD算法及其阵列结构完成了多种SVD处理器的设计【】【J。同时结合应用和资源考虑Z。Liu等【】利用CORDIC算法采取浮点设计的方式给出了一种用于SVD算法的浮点FPGA实现设计。Sau.GeeChen和Chin.ChinChang”J为了减少CORDIC算法计算的复杂性提高设计的性能提出了一种新的有效的SVD算法这种方法充分利用FPGA中乘法器资源实现了高效的设计。WeiweiMa等【l】在FPGA资源有限的情况下给出了用于CORDIC实现的结构。对于图像处理方面的应用A.Ahmedsaid等【lJ利用CORDIC算法和改进的Systolic阵列结构完成了SVD算法应用设计。目前随着各项数学工具的发展使得FPGA硬件设计变得越来越简单Altera和Xilinx两大FPGA行业的巨头都推出了各自的IPCore使得设计者在进行硬件设计时不需要在一步步的设计每个模块Altem公司的DSPBuilder和Xilinx公司的SystemGenerator更是使得设计者只需要通过图形化的设计完成工作这使得设计变的简单。M商shRahmati等IlJ就直接通过Xilinx公司的SystemGenerator图形化设计并利用FPGA内部丰富的乘法单元和存储单元评估和设计完成了SVD算法的定点设计。近几年Xilinx公司还推出自己的数学设计工具一一赛灵思AccelDSPSynthesis综合工具该综合工具利用FPGA中的DSP内核等单元通过基于Matlab的FPGA设计流程简化设计者在设计时的程序编写并充分利用FPGA器件的内部资源使设计到达最好的效果。利用它基于Matlab的设计方法也可以很好的完成SVD算法设计并利用此工具能实现定点和浮点之间的转换。这些算法和结构上的设计在某些应用方面都很好的改善设计的性能为以后的设计提供了很好的方法基础。.论文的主要内容及组织安排基于奇异值分解的特征子空间目标识别法的FPGA实现是本论文的重点由于特征子空间的建立是通过求解奇异值分解完成的所以FPGA设计时的核心问题就是研究单精度浮点SVD处理器的实现。论文中介绍了FPGA实现奇异值分电子科技大学硕士学位论文解的算法一双边雅克比算法(Two.sidedJacobiAlgorithm)并研究了其实现SVD的阵列结构BLV阵列结构。为了满足高速度和高精度的要求研究了利用传统CORDIC(CoordmmeRomtionalDigitalCompmer坐标旋转计算机)算法和基于GA(GreedyAlgorithm贪婪算法)算法的改进型CORDIC算法的矢量模式和旋转模式分别实现SVD处理器角度计算单元和旋转计算单元对这两种实现方式从FPGA实现的面积、速度和数值精度上进行了详细的比较同时给出了实现CORDIC算法基本模块单精度浮点an/减法器的设计和时序仿真然后研究分析了用于实现高阶矩阵浮点运算的结构并详细说明了各个控制单元和存储单元的设计同时由于并行调度较大矩阵元素比较复杂改进了调度方式并将实现结构各个基本单元的资源进行了整合给出了相应的结构和设计方法最后研究比较了实现处理器核心运算单元的几种结构通过仿真进行了详细的比较和分析给出了单精度浮点SVD处理器的实现方案。论文的组织安排为:第一章是绪论部分主要介绍了研究背景及意义然后介绍了研究现状最后给出了论文的主要工作及组织安排第二章主要介绍了特征子空间目标识别法原理以及基于SVD的特征子空间目标识别法引出本论文核心问题单精度浮点SVD处理器的FPGA实现并研究了用于FPGA实现SVD的算法一双边雅可比算法以及实现SVD的BLV阵列结构和雅克比算法的并行调度规则第三章介绍了传统CORDIC算法以及基于GA算法的改进型CORDIC算法基本原理给出了FPGA实现浮点CORDIC算法基本单元模块浮点加/减法器的实现方法并给出了FPGA实现两种CORDIC算法的两种模式矢量模式和旋转模式的具体步骤和仿真结果对这两种FPGA实现方式的优劣性进行了比较第四章首先给出了实现单精度浮点SVD处理器的两个计算单元角度计算单元和旋转计算单元的几种设计方法并通过仿真设计比较了这几种FPGA实现方式的性能然后给出了单精度浮点SVD处理器的FPGA实现结构对控制单元和存储单元的设计给出了相应的方法并改进了结构中的矩阵元素调度方式采用分组分类的方式完成矩阵元素的调度。同时对于其核心运算单元X基本矩阵运算单元以TPR方法为基础利用上述两个计算单元几种方案的组合设计并设计为通用并行单元完成其核心运算单元的设计通过矩阵仿真测试详细分析比较了这几种结构的性能给出了速度、资源和运算的数值精度的比较和分析。为了进一步减少处理器面积和改善处理器FPGA实现时时钟优化性能最后第一章绪论论文采用阶差估计sin/cos的设计方式并直接利用FPGA中的DSP内核单元和浮点加/减法器通过资源整合完成单精度浮点SVD处理器的设计论文通过仿真在速度、资源占用和数值计算精度上给出了设计实现这种SVD处理器结构性能的详细比较和分析第五章给出了单精度浮点SVD处理器整体实现的仿真测试和分析对各个矩阵的资源占用、速度和数值精度给出了详细的说明:第六章对全文进行了总结及其后续工作的展望。电子科技大学硕士学位论文第二章基于奇异值分解的特征子空间目标识别法子空间方法进行目标识别是在线形变换的基础上将不同类别的目标各自用一个线性子空间或者是一个共同子空间中的不同区域来表示以提取各类目标最典型的特征信息进行分类或者是抽取对于提高同类聚合性和异类可分离性能有用的信息。特征子空间方法是一种传统而稳定的模式识别手段在特征提取、数据压缩和快速分类方面都有比较广泛的应用。刘本永对雷达目标一维距离像的子空间方法的广泛而深入研究改进出了正则子空间方法、修正特征子空间方法、综合子空间方法、子空间串法等多种子空间方法在对仿真数据以及实测数据的实验中都取得了比较好的效果【刮。本章主要对特征子空间算法的实现进行研究。建立特征子空间可以通过对模式矢量的相关矩阵或自协方差矩阵进行特征分解求得还可以利用奇异值各种良好的性质根据奇异值分解的方法直接对矩阵运算求得本课题正是根据奇异值分解建立特征子空间。在应用FPGA实现奇异值分解并建立特征子空间时本论文设计选用双边雅克比算法(TwosidedJacobiAlgorithm)来FPGA实现之。下面将介绍特征子空间目标法的原理以及FPGA实现SVD的具体算法及其阵列结构和并行调度方式。.特征子空间目标识别法..特征子空间一个子空间可以用一组正交归一的(即标准的)基矢量来完全表达。设聆维Helbert空间H中一任意以维矢量xH的标准基为缸。“:‰)则x的某一展开为:z=口“。()i=l当展开式中第P项以后截断得Pi=掣=l()第二章基于奇异值分解的特征子空间识别法设V=Span(ul“甜)当且仅当展开系数为口f=(x“)(f,p)时有^x。P。工。在统计学上需要根据一定的准则确定上述’里所有P个标准矢量组中最佳的一组以建立相应的子空间。不同的准则对应不同的子空间下面讨论在最小均方误差准则下确定的特征子空间。最小均方误差准则为:E啦一邓】=min()以公式()和()代入并注意到口=瓴蚝)(i=l,,,p)及(影跖)={三二i:上式等价于:ulEl=’h=材j=rain()即甜j纰=maxQ=Exxr】()由于Q是对称正定矩阵所以式子()等价于:UQu』=丑扛,一P()故(.)式等价于求相关矩阵的P个大的特征值所对应的单位特征矢量这样就可以使得式(.)中的误差最小是nP个最小特征值的总和。这就是KL变换也称为主成分分析的原因。主成分分析是通过对矩阵作特征分解后选取P个大的特征值所对应的特征矢量来张成子空间所确定的子空间称为特征子空间。..特征子空间目标识别方法简述z维模式空间的P维普通子空间由P个矢量张成:s=跏巾:一=卜=酗p口f}弘其中缶厶彭(p<z)为常数。由上节可知当P维子空间的s的P个正交基矢量通过对模式矢量的相关矩阵或自协方差矩阵进行特征分解求得时该子空电子科技大学硕士学位论文间即特征子空间特征子空间还可以用奇异值分解法建立【】【】。模式识别中特征子空间法能有效提取模式主要特征即本征特征。设刀维空间中任意矢量x经矩阵A线性变换的结果为Y=Ax如图所示。图矢量的线性变换h是对x在其原方向或反方向进行的展缩其中k为常数而彳(h)=七(出)=砂是对Y在其原方向或反方向的相应展缩。对门维空间存在门个基本的方向使得沿这些方向的矢量经过变换后长度保持不变或只是受到展缩而方向不变即有:Ax=缸()这iv/个基本方向即该空间的特征方向(本征方向或惯性主轴)。模式矢量在这些方向上的投影就算其基本征特征以所有特征方向为基矢方向的空间为特征空间而以其中一部分特征方向的空间即为特征子空间。上述特征子空间目标识别方法未考虑噪声的影响实验证明随着输入输出矢量之信噪比的降低这种方法的正确识别率也相应的降低通过修正特征子空间法可以依据噪声功率来自动修正上述特征子空间以达到降低噪声的影响。在考虑到反映目标类别主要特性的信息未必正好就是对于区别不同目标类别最为有用的信息时正则子空间方法利用正则变换的非正交特性在突出异类目标的差异性的同时增强同类目标的聚合性为所有感兴趣目标类建立公共子空间以提取对于区别这些目标类最为有用的信息的正则子空间法等‘】【。这些方法都是以特征子空间法为基础的应用特征子空法进行目标识别的过程如图所示。由上可知特征子空间可以通过对模式矢量的相关矩阵或自协方差矩阵进行特征分解求得但是在形成相关矩阵或自协方差矩阵时可能会导致信息的损失【。特征子空间还能够通过奇异值分解的方法建立用奇异值分解方法直接对矩阵运算无须对模式矢量求相关矩阵或自协方差矩阵可以避免因此而人为地引入误第二章基于奇异值分解的特征子空间识别法差另外奇异值符合模式识别中特征所要求的稳定性及旋转、比例不变性是一个有效的模式特征f。因此本课题中在研究算法实现时主要考虑采用SVD方法来建立特征子空间。图.特征子空间法目标识别过程.基于奇异值分解的特征子空间目标识别法..奇异值分解及其性质定理(奇异值分解(SVD))设彳是实m”矩阵则必存在正交阵U=【U“U。】R”。朋和V=VVV。】R“”使得UAV=旃昭(以万口)RmxnP=min{m疗}其中磊磊万。。待,P为矩阵彳的奇异值是似胃或彳Ⅳ彳的特征值以的算术根即反=五。定理(奇异值的稳定性)设么彳ER眦”它们的奇异值分别为岛以f。fzo则h一l,<E)=IIEII:。此定理的意义是:当矩阵有微小振动时它的奇异值改变不会大于振动矩阵的.范数。定理(奇异值的比例不变性)设么默”的奇异值为最瓯aA的奇异值为西西瓯则I(训)(鲥)日‘=即I州H’I/atlo上式中为单位阵故H(嘎瓯)=(并西《)即经过归一化处理后可实现奇异值的比例不变性。定理(奇异值的旋转不变性)矩阵彳做旋转变换相当于彳左乘一个酉阵尸旋转后么变为刚显然朋与彳具有相同的奇异值。电子科技大学硕士学位论文根据上述SVD的性质【】【】本文选择奇异值分解作为目标子空间的建立方法进行研究。..基于SVD的特征子空间目标识别法简述设X盯(甩维列矢量)表示第f类目标的第j『个训练姿态角的一维距离像(江,gJ=,ⅣJⅣ=NlⅣNg其中g为目标类别数Ⅳj为第f类目标的训练样本数Ⅳ为训练样本总数)训练样本集的总平均矢量为【】:X一=而南喜善X()=一夕.。IZylNLNNl乞葛‘、其中i为训练样本集的总平均矢量。训练一维距离像减去总平均矢量%=X{『一X一()按列组成如下矩阵X=hSJglSJ珧一J珧】()对矩阵X(刀N维)作奇异值分解X=UAVr(.)其中U和矿分别为左、右奇异矩阵人为奇异值对角矩阵其对角元素按大到小的顺序排列。U和y满足嚣二箍p阿r=矿ry:E。。、取人中前P(P聆PⅣ)个值所对应的左奇异矢量为列构成特征子空间。特征子空间的维数P可以由对数据的压缩比七确定其确定方式为式()所示其中最为奇异值聊为矩阵奇异值的总个数。瓯Lk佗.)加、p确立后建立特征子空间A。lgfg=【UlU/,/p】()第二章基于奇异值分解的特征子空间识别法其中材为左奇异矢量。%在特征子空间A。嘧中投影为:乃=彳孟sFf=,gJ=,M()其中Y盯(P维列矢量)为一维距离像h对应的子像即为特征子像。每类目标的平均训练子像作为对应库目标的模板矢量则譬类目标总模板为:识歹咒j()其中只为第f类目标的平均训练子像。设输入目标的一维距离像为x哪则其在特征子空间A。fg中的子像为y唧计算其与库目标模板矢量之间的距离则分类规则为z=y删一硎i=,g()矿dt>dffo.allkithenx咖fclassi().基于FPGA实现的SVD算法奇异值分解(SingleValueDecompositionSVD)是一种被广泛应用于数字信号处理的重要技术例如目标识别、图像压缩、频谱分析等本课题中将利用奇异值分解建立特征子空间。对于SVD的实现两种雅克比算法一单边雅克比算法(One.sidedJacobiAlgorithm)和双边雅克比算法(Two.sidedJacobiAlgorithm)一直被人们所关注单边雅克比算法是一种利用一系列Jacobi平面旋转实现数据矩阵的单边正交化方法而双边雅克比算法是通过对矩阵进行一系列正交相似变换不断校正使得每个新的A比前一个更加对角化最终非对角线元素都小到几乎为零。因为双边雅克比算法是一种十分适合FPGA实现的、高效的、并行的方法所以本文选择其作为SVD处理器实现用的基本算法。..双边雅克比算法双边雅克比算法【】【(Two.sidedJacobiAlgorithm)是一种在难易性、规律性和实现性方面都非常适宜于FPGA实现奇异值分解(SVD)的方法。双边雅克比算法作法是进行一系列的正交相似变换不断校正使得每个新的A比前一个更加对角化最终使非对角元素都减小到几乎为零。Brent、Luk和VanLoan已电子科技大学硕士学位论文经显示了【并行的双边雅克比算法能够在D(zlog聍)时间内计算厅刀矩阵的奇异值分解。对于一个矩阵AR“”其SVD因式分解形式为A=UAV’。在这里U和矿矩阵是正交的即UrU=矿ry=且UR“”VR“”人R””为对角化矩阵对角元素为谚f=,k。其中元素巧为彳的奇异值。双边雅克比算法通过一系列的正交双边旋转来对角化一个矩阵如下式:AⅢ=A()其中和是左、右雅克比旋转矩阵其形式d(pq印为:j沪J垮=cos/Jqp=。sinO。血护峋删:Jqq=cosl一。以=IiPq山=其他其中P<gC=cosOs=sinO。OOcsO一JcOpq()每次计算中新的矩阵AⅢ总比前一次矩阵要更加对角化一些。通过"次迭代计算最后输入矩阵彳被转化为对角化矩阵彳。:An=J:Ji』JlJ:AJoJ:J.'iJ:()此时人=AnU=n以y=兀。在每一次的迭代中左、右雅克比旋转矩阵中的左、右旋转角度有选择的减少矩阵彳元素口胛和a驴到零。因此矩阵彳左乘以左雅克比旋转矩阵影响到的仅仅是矩阵的f.两行矩阵么右乘以右雅克比旋转矩阵影响到的仅仅是矩阵的f『两列。双边雅克比算法中当所有P、q的行和列都被包含计算后称之为一次清扫当重复所需要的清扫次数后就完成了矩阵的奇异值分解运算。Forsythe和Henrici提出刀职矩阵能够通过求解一个合适次序的X矩阵的SVD完成其矩阵的对角化。一个X矩阵的SVD算法如下式子(.)所示。如.g嘶洲C一洫篇第二章基于奇异值分解的特征子空间识别法其中abcd为矩阵元素秒和矽分别为左、右旋转矩阵的角度其关系式如下所示。通过将矩阵划分为n/Xn/个的矩阵并行的处理这些矩阵并通过适当的调度方式完成矩阵的奇异值分解。日:口tan掣矽一目:atan掣()d~口口a..Brent、Luk和VanLoan方法Brent、Luk和VanLoan提出了~种用于计算甩X刀实矩阵奇异值分解的一种阵列结构(BLV)fl。BLV阵列是一种十分适合用于计算并行雅可比算法Systolic阵列结构。对于一个矩阵R~可划分为厅/XH/个X的子矩阵。在BLV阵列结构中每一个处理单元(ProcessingElementPE)被提供给每一个X的子矩阵。PE结构如图.所示。同时在阵列结构中处理单元PE被划分为对角处理单元和非对角处理单元。每个处理单元都包含了旋转角度秒、矽和矩阵元素口、b、c、d。对角处理单元通过上式(.)用以计算旋转角度伊和矽然后将计算所得角度传递到邻近的非对角处理单元。利用此时的旋转角度和矽对角处理单元通过公式(.)计算下一次迭代用的矩阵元素。同时各个非对角处理单元分别接收左、右旋转角度和痧同对角处理单元一样应用公式(.)计算下一次迭代时的子矩阵。在计算完成后此PE存储计算后的新矩阵元素同时PE中的左、右旋转角度传递到下一个行或列的PE单元中然后进行相同的运算。依照这种方法旋转角度逐步地传递到所有非对角线PE单元中并完成运算。当所有的PE完成运算后相邻PE单元交换彼此矩阵元素的位置在如上步骤进行矩阵运算。对于求解并行雅可比算法阵列完成一次清扫需要刀一步当完成奇异值分解需要清扫次数为O(n)时这个阵列能够在O(nlogn)时间内完成矩阵的奇异值分解【】【】。out口irl矽utout矽out目out占图对角处理单元饱“和非对角处理单元鸭电子科技大学硕士学位论文下图.为一个X矩阵求解SVD时的BLV阵列结构。PEtl卜叫PElHPElHPElPEHPEHPEHPEPEalHPEHPEHPEPEHPEHPE“图.X矩阵BLV阵列结构..雅克比算法的并行调度规则由上述双边雅克比算法的介绍可知当矩阵的阶数n为一偶数的时候那么矩阵可划分为n/个子问题并行的处理。例如矩阵AR“”且"=则完成一次清扫需要通过个子问题来解决:Setl:{()())Set:{()()}Set:{()())。三个子问题中的行和列元素在每一步中均是不相互冲突的。如Setl中子问题()和()能并行处理这是由于每个子问题仅影响到其所选的行和列如子问题()影响的是行和列而()子问题影响的是行和列。Set和Set中的子问题也能并行的完成处理。这种处理方式称之为雅克比算法的并行调度规则【】【刀。Brent和Luk给出了并行排序的规则如图.所示。图中每一列即为一个子问题沿着箭头移动一次后形成的所有子问题都可以并行处理。完成一次清扫需要厅一l步每一步中的所有子问题都是并行的。当刀为奇数时可在矩阵的边上增加一行和N零元素在求解添加的零元素时小心处理就行。按照这样的排序就可以完成矩阵的SVD运算这种方式不但具有并行性的特点而且在每一步之间的数据交换仅发生在相邻的单元之间每一个子问题所完第二章基于奇异值分解的特征子空间识别法成的操作都是相同的因此很容易利用一定的阵列结构来实现之。.本章总结上上卜一卜}一图.Jacobi算法的并行调度规则本章研究了基于奇异值分解的特征子空间目标识别法的原理并且研究了应用双边雅克比算法计算SVD的方法及其相应的矩阵结构BLV阵列结构同时研究了雅可比算法的并行调度规则。下一章节中将讨论FPGA实现SVD中关键模块的设计介绍CORDIC算法及其FPGA实现方法。。In...一.......一.).一.广介m(...一。.......一......彳..电子科技大学硕士学位论文第三章CORDlC算法及其FPGA实现CORDIC算法是Volder等人四】于年在美国航空控制系统的设计中提出来的它是一种用于计算一些常用的基本运算函数和算术操作的循环迭代算法其基本思想是用一系列与运算基数相关的角度的不断偏摆从而逼近所需的旋转角度。从广义上讲它是一个数值性计算逼近的方法由于这些固定的角度与计算基数有关运算只有移位和加减硬件操作起来简便易行又由于该算法是一种规则化的算法它满足了硬件对算法的模块化规则化的要求因此COImIC算法可以充分发挥硬件的优势利用硬件的资源从而实现硬件与算法相结合的一种优化方案。可用该算法来计算的函数包括乘、除、平方根、正弦、余弦、反正切、向量旋转(即复数乘法)以及指数运算等。年J.S.Walther提出了统一的CORDIC算法形式J把圆周旋转、双曲线旋转和直线旋转统一到同一个CORDIC迭代方程里为统一硬件实现多功能提供了前提。随着对CORDIC算法的不断深入研究提出了各种改进算法和优化方案以适应各种不同的需求。贪婪算法【(GreedyAlgorithmGA)即为其中一种比较好的改进算法其通过事先判断出要求的最佳旋转角度和旋转方向从而大大减少计算过程中的迭代次数提高了硬件计算速度文中就将会以这种改进的算法完成CORDIC的模块设计。本章将介绍CORDIC算法的原理、操作模式及其改进型的GA.CORDIC算法并详细介绍传统COImIC算法和改进型CORDIC算法的FPGA实现。.CORDIC算法的原理BLV阵列中求解矩阵奇异值分解时的基本矩阵为的矩阵对其X基本矩阵的求解成为了求解刀X甩矩阵时的关键。设计中可以采用CORDIC算法的两种模式旋转模式和矢量模式来实现其求解过程。下面将介绍CORDIC算法的基本理论和过程【。对于一个P点坐标(而Y。)经过逆时针旋转口角成为Q点其坐标为(xY)如图.所示。第三章CORDIC算法及其硬件实现则有:即为:O)图向量逆时针旋转坐标图fx、fCOSlI=ltyJ(sinsisn坝O(yxo。)仔()假定将分解为一组固定的基本角度口的线性组合即:O=aI疋口名口。谚=()式中代表每次基本角度的方向可得到如下递推公式即:经i一次旋转后的第f次旋转前的角度()只一=万l口l口万j一口f一()令z。为要求的转角曰与包一.之差则有由式(.)可知若取口。=atan(。)则zf=秒一只一zi“zi一万i口()()()伊p.口咖DOyX一口秒{啷OO工y==XyJ、L口口毋坑h.a剐Sy工一十口口瓯毋哪哪儿==件Zy、L哆%咖伽籼%一口.口OOCC==口口觚伽只一口口谚OOCC==Z少L电子科技大学硕士学位论文把一l=COSO!(戈一巧一Yj)Yfl=COSf(Jfx)zf=zj一ate(“)xi一一YtYf薯Zl一iai()()称为CORDIC算法的基本旋转公式。可以看出CORDIC算法实际上只是由一系列简单的移位和加法操作组成。原矢量p(x。Y。)经过刀次基本旋转公式循环后结果为工’Y。原矢量精确旋转口角度后新矢量为Q(xY)则有r”一月一llx=xt兀口爿Ⅱ(’』)=K(n)x’{葛I=O()nI月一\lY=y。兀口刊’兀(‘丁“=K(n)y’K(n的出现说明了基本旋转对矢量来说并非完美的旋转它改变了矢量的模长因而CORDIC循环完成后矢量还需要进行一个模长的校正过程才能保持原矢量模值不变。由于CORDIC计算时的角度覆盖范围为一..所以为使CORDIC算法适应与全平面的旋转问题需要在进行计算之前对其做预处理以使得CORDIC算法能完成对平面矢量进行从一~的旋转运算。下面小节的FPGA预处理部分将介绍其具体的方法。.CORDlC算法的两种模式及其统一形式..旋转模式旋转模式(Rt撕onMode):是将给定的矢量圪=(‰Y。)r进行要求角度的旋转计算新矢量巧的坐标值。其旋转过程如图.所示。矗兀矗(【一\、l川兀瑚=船/K中式第三章CORDIC算法及其硬件实现设初始旋转角度z。=秒在每~步的迭代过程中逐步地使其减少当z。=时CORDIC就完成了所需旋转的角度其图.中所示矢量旋转过程为%一K砭寸巧。旋转的方向由每一步迭代过后剩余角度的大小来决定。图.CORDIC旋转过程CORDIC算法旋转模式的差分方程可以写做:其中tl=X一一YfYfYf,~Xfz『l=乙一,atan(一)弘{:z其t他<因此旋转模式的最终结果为:()()其中K()为补偿因子。应用该模式选择不同的输入就可以完成基本的向量旋转计算、极坐标系到直角坐标系的变换以及sin、COS计算等。本课题中将利用旋转模式进行向量运算。在一般FPGA设计过程中CORDIC实现向量旋转运算的方式比起利用查找表和乘法器直接实现起来其实现数值精度要高一些且不必占用大量的FPGA存储单元。由于本课题涉及到单精度浮点数的计算同时结合具体FPGA的资源以及实现的数值精度和运算速度情况在力功KK.璺.吕%‰如叫=。%%z哪螂而%“==Xy电子科技大学硕士学位论文实现具体向量旋转时应用不同的方式并对其做了相应的比较这些将在下面文中给出。..矢量模式矢量模式(VectoringMode)是将给定矢量(XY。)向工轴旋转以求得原矢量的模长和幅角。将角度初始化为然后通过旋转使得J值为当Y为零时x即为向量的模z.即为其幅角值。矢量模式的差分方程为:x,Ⅲ=xtf一'YYi::l:鼽谚啦姿嚣Bfl=。x其中谚={I’:二。()zfl=zl一fatan(“)。因此矢量模式的最终结果为:Ix.:厮/敏功{儿=o(.)Iz。=zoatan(yoIxo)应用矢量模式可以完成向量的模运算、反正弦、反余弦、反正切函数的计算等。在本课题中可以利用矢量模式完成反正切函数的计算用以达到求解旋转角度的目的。..CORDlC算法统一形式为了能计算更多的基本函数年J.S.Walther提出了统一的CORDIC算法形式【把圆周旋转、双曲线旋转和直线旋转统一到同一个CORDIC迭代方程里:其中m代表工作模式m=l为圆周系统m=为线性系统m=一I为双曲线系统表给出了CORDIC算法对应模式的角度只取值情况。表.给出了在相应的工作模式下分别采用旋转模式和矢量模式的情况其结果是差不多所有的超越函数都可以利用CORDIC算法进行计算。正确的选择初始值以及各种操作模式间的结合就可以实现多种函数的运算。表.中酌y叫掣olⅣ饵所瞑一一t儿毛=II=K儿钆第三章CORDIC算法及其硬件实现表.CORDIC算法模式m工作模式伊ll圆周坐标atan(。)O线性坐标fl.双曲线坐标atanh()..表.CORDIC算法的操作模式m旋转模式=sign(z)矢量模式=sign(y)Xn=(xoCOSZoYosinzo)/Kcx。=x。y。/K。儿=(YoCOSZ而sinzo)/Kcz月=zo口tan(yo/xo)X一=XO石^=Xoynyxo‘zqz一.zoYo/Xox。=(Xocoshzo%sinhzo)/KhI=、/X一YY/AhlYn=(Jocosh

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/16
仅支持在线阅读

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部