（通信与信息系统专业论文）dbf算法研究及其硬件实现.pdf

摘要 数字波束形成( d b f ) 技术是现代雷达和通信领域的研究热点。本文结合总装“十 五”预研项目“x x 雷达d b f 接收阵”，进行了数字波束形成算法的研究并在硬件系统 上实现。本文主要开展了以下几个方面的工作： 1 、对基于线性约束最小方差( l c m v ) 准则的程序进行优化，以适应系统实时 性要求。优化后运算量为优化前的4 0 4 。根据系统测试要求，对算法作适当修改。 参与完成了系统测试，测试结果与理论结果基本相符。 2 、在a d s p t s 2 0 1 s 硬件平台上实现了基于l c m v 准则的d b f 算法。完成了软 件和硬件的调试。测试结果验证了软件的正确性。 3 、针对大型阵列的特点，提出了一种新的自适应波束形成算法分块并行的 l c m v 算法。这一算法通过对输入信号和权重向量分块，降低了向量的维数，并且 各个子向量可以并行处理，克服了大型阵列数据传输和运算量的瓶颈，也大大降低了 大阵列数字波束形成系统的复杂性和成本。并且通过切比雪夫加权来降低旁瓣。本文 完成了算法的理论推导，计算复杂度分析，仿真以及与其它算法的比较，仿真结果验 证了算法的正确性及运算量上的优越性。 关键字：数字波束形成，l c m v ，d s p ，并行计算 a b s t r a c t d i g i t a lb e a mf o r m i n g ( d b f ) t e c h n i q u eh a sb e e nw i d e l yr e s e a r c h e di nm o d e r nr a d a r a n dc o m m u n i c a t i o ns y s t e m s t h i st h e s i si sf o c u s e do nt h es t u d yo f d b f a l g o r i t h m sf o rx x r a d a r t h em a i nw o r ki n c l u d e s ： 1 t h ep r o g r a mo f d i g i t a lb e a m f o r m i n g ( d b f ) a l g o r i t h mb a s e do nl i n e a r l yc o n s t r a i n e d m i n i n l u n lv a r i a n c e ( l c m v ) i so p t i m i z e dt om e e tt h er e q u i r e m e n to fr e a lt i m ep r o c e s s i n g i 刀艟c o m p u t a t i o n a ll o a di sr e d u c e dt o4 0 4 a f t e ro p t i m i z a t i o n 刀玲s o f t w a r ep r o g r a mi s m o d i f i e da c c o r d i n gt ot h er e q u i r e m e n to fs y s t e mm e a s u r e m e n t n l em e a s u r e m e n to ft h e d b fs y s t e mi sa c c o m p l i s h e d t h er e s u l t ss h o wt h ea g r e e m e n tt ot h a to f s i m u l a t i o n 2 t h ed b f a l g o r i t h mb a s e do nl c m v i sa l s oi m p l e m e n t e do nt h eh a r d w a r ep l a t f o r mo fa d s pt s 2 0 1 s t h ed e b u g g i n go ft h es o f t w a r ea n dh a r d w a r ea l ea c c o m p l i s h e d 硼1 ct e s tr e s u l t ss h o wt h ec o r r e c t i o no f t h es o f t w a r e 3 an e ws u b a r r a yp a r a l l e ll c m va l g o r i t h mi sp r e s e n t e d w i t hp a r t i t i o n i n gt h e r c c e i v e rd a t aa n dw e i g h t ，a n dc o m p u t i n gw e i g h ts u b v e c t o r si np a r a l l e l ，t h ea l g o r i t h m o v e r c o m e st h eb o t t l e n e c ki nt h ec o m p u t a t i o n a ll o a da n dv a s td a t at r a n s m i s s i o no fl a r g e a r r a y l o ws i d e l o b eo ft h eb e a mi so b t a i n e dw i t ht s c h e b y s c h e f fc o e 伍c i e n t s t h et h e o r y d e v i a t i o n , c o m p m ec o m p l e x i t ya n a l y z i n g , a n d s i m u l a t i o no ft h e a l g o r i t h m a l e a c c o m p l i s h e d s i m u l a t i o nr e s u l t sp r o v et h a tt h ep r o p o s e ds l c m v m e t h o di sc o r r e c ta n d r e q u i r e sl e s sc o m p u t a t i o n a ll o a dt h a nt h a to f o t h e rm e t h o d s k e y w o r d ：d i g i t a lb e a mf o r m i n g ，l c m va l g o f i t h r n , d s p , p a r a l l e lc o m p u t a t i o n 声明 本学位沦文足我在导师的指导下取得的研究戎粟，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何敦厶机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： 铮z 月如目 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 _ k n 公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：l 塾知叫年月蝴 劝卜沦之d b f 等吐研究砖萁诤件窑观 1 绪论 雷达和通信系统所需的信扈越复杂，对天线的性能要求就越高。数字波束形成 f d b f ) 是提高天线胜能的强有力技术。严格地讲，波束形成对应于单元信号的加权与 合成，而数字波束形成几乎包括传感器阵列的数字化信号的所有空间处理。目前，先 进的微波集成电路、信号处理和高速数字电路使微波雷达和通信系统的d b f 成为可 能，d b f 技术将越来越重要。数字波束形成赋予雷达系统诸如多波束形成、波束形成 的灵活性和方向图综合等许多优点，这些优点在原理上与射频模拟技术是共有的，而 且从理论上讲也是可以无限制的予以变控。究竟d b f 的这些属性如何的重要以及由此 是否就能判明系统的附加成本，则取决于系统的性能要求。随着现代数字技术方面的 进展、各种军用雷达设计规划对雷达接收机数字法的推动和促进，雷达d b f 技术的研 究必将取得更重大的实质性突破。 自适应波束形成技术始于二十世纪五十年代，最早应用于声纳和雷达系统【1 2 1 。 经过几十年的蓬勃发展，已经逐渐走向成熟。自适应技术由优化理论演变而来，从上 世纪初以来，各方面的研究工作促成了自适应技术的出现。二十世纪五十年代末v a n a t t a 首次提出了“自适应天线”的概念【3 i 。进入六十年代，自适应技术在许多领域 进行了开创性工作，形成了很多分支，自适应波束形成就是其中之一。最小均方算法 即l m s ( l e a s t m e a n s q u a r e ) 算法是b w i d r o w 和h o 行于六十年代末提出的 4 1 ，由于 实现简单且对信号统计特性有稳健性，l m s 算法获得了极为广泛的应用 5 1 ，其他人的 研究也奠定了这一研究方向的理论基础。七十年代随着大规模集成电路技术和计算机 技术的飞速发展，自适应技术的研究领域得到更为广泛的拓展，成为最活跃的研究领 域之一【3 1 a 1 1 国内外研究现状 从国外8 0 年代以后的报导来看，英国、美国等都分别在进行8 、2 5 、2 8 和3 2 天线 单元的d b f 系统试验。有代表性的系统英国海军部研究所和普莱塞雷达公司联合开发 的m e s a r ( 多功能电扫描自适应雷达) m e s a r 计划是由英国防御评估和研究机构 ( d e r a ) 以及早先的s i e m e n sp l e s s e y 公司联合进行的。m e s a r 技术验证计划是从1 9 8 6 年开始的，它的第一个阶段是采用1 5 6 个砷化镓发射接收模块( 每单元最大发射功率为 2 w ) 构成一个单面阵列，同时发展了实时自适应波束形成技术，通过估算协方差矩阵 来计算自适应加权系数( 即采样矩阵转置s a m p l em a t r i xi n v e r s i o n 算法) 。根据1 6 个通道 输出“快拍”所得的采样来推导协方差矩阵，算出加权系数，就获得了有1 5 个自由度 的部分自适应阵列，并有很强的自适应零控能力1 6 1 。它的第二个阶段是从1 9 9 0 年开始 的。在这个阶段增加了实进控制硬件和相应的软件，这样就使m e s a r 从实验型发展 一l 一 d b f 算哇研究段疑硅件实现硕十论丈 成为可使用的验证型设备。从1 9 9 3 年4 月至9 月，对于m e s a r 验证型设备，针对各种 有代表性的威胁进行了实战试验。2 0 0 0 年，新一代的m e s a r 2 技术验证设备已经建成， 可以用于弹道导弹防御方面的一系列试验工作【7 】。为辅助设计和测i j l m e s a r 相控阵 雷达进而开发了一些程序。在权向量计算过程中，采用了一些基于采样矩阵转置 ( s m i ) 的不同算法，包括g r a m - s c h m i d t 正交算法，高斯消去法和h e r m i t i a n 解相关算 法。 s a f r a n 演示系统【8 l 是法国国防部为未来的战场监视系统中有效的应用新的雷 达技术而进行的开发研究性工程，s a f r a n 是“运用数字波束形成的空中和地面监视 雷达”的法语的首字母缩写。信号经1 6 个通道送往信号处理系统，该系统由五个框架 组成，每个框架包含2 0 块由2 片t m s 3 2 0 c 4 0d s p 组成的板子。d b f 由信号处理器的 输入得到一个参考信号，运用最初的规则化的采样矩阵转置( s m d 算法来合成一组 1 6 4 独立的自适应波束，使其在矩阵病态时仍具有稳健性，并在参考信号中找出有用 的目标。 文献 9 】中对基本的采样矩阵转置( s m i ) 算法进行了改进，即e s m i ( e n h a n c i n g s m i ) ，并引入一种相对简单的恶化函数方法( p e n a l t yf u n c t i o nm e t h o d ) ，分别应用予 英国国防评估和研究机构d e l l a ( d e f e n s e e v a l u a t i o n a n d r e s e a r c h a g e n c y ) 研究的 m e s a r i i 和捷联式导弹制导( s t r a p d o w n m i s s i l e g u i d a n c e ) 中。 多年来，东芝公司一直致力于为日本防卫厅开发各种雷达，先期研制的是两种无 源相控阵雷达，其中之一采用的是带有自锁铁氧体移相器的波导裂缝天线：另一雷达 则是带p i n - 极管移相器的空馈阵列天线。这些新型有源相控阵雷达也采用了数字波 束形成技术。多波束形成技术应用于雷达需采用超高速电路，他们具体采用的是 s y s t o l i c 阵的方法。在s y s t o l i c 阵中，通过控制各个波束的复数加权值就可形成任意和独 立控制的多波束。数字波束形成中易于应用自适应技术，具体使用的是采用了g r a m - s c h m i d t 变换方法的s y s t o l i c 阵，该自适应电路已研制完成且在室外场地进行了测试， 施放干扰信号，然后测量自适应处理前后的天线方向m t l o 】。 自适应数字波束形成技术在调频连续波f f m c w ) 雷达中也得到了应用。文献 1 1 】 根据f m c w 雷达的距离多普勒处理方式，提出了两种不同的a d b f 系统方案。通过仿 真，证明了将a d b f 技术应用于o t h r 等f m c w 雷达是有效、可行的。它将显著改善 此类雷达的分辨力、作用距离、抗干扰能力等战术性能，具有重要的应用价值。a d b f 系统的性能很大程度上取决于自适应算法的选择，常见的算法很多，在相控阵雷达 a d b f 系统中应用较广泛的是采样矩阵求逆( s m i ) 算法。该算法收敛速度快，数值特 性稳定，干扰抑制效果好。为避免s m i 算法在采样数不足情况下引起的波束畸变问 题，对s m i 算法进行了对角加载处理【l l 】。 现代天线阵列系统，阵列规模的增大、系统功能的增加，要求波束形成算法的运 静t 论zd b f 算疰研究受廷硬件蛮观 算量要小同时还能抗强于扰，子阵处理算法是减少自适应算法的计算量，加快计算速 度相当有效的方法。但实际的系统中总有噪声存在，尤其是突发强干扰时，子阵处理 算法往往会发散，导致体统崩溃，基于稳健估计的r l s 算法近年来一直是研究的热点。 一种改时的r l s 算法稳健子阵异步r l s 算法( m s a r l s ) 保持了稳健算法和异步子 阵r l s 算法两者的优点，具有抗突发强干扰，计算量小，收敛快的特点。同时算法迭 代过程中的并行性使算法易于并行计算，在阵列规模较大时，应用并行m s a r l s 将有 明显优势【1 2 1 。文献 1 3 - 1 5 研究了了基于r l s 算法的子阵处理方法，可以通过将向量 划分成子向量来降低维数，同时这些子阵可以并行处理，可以大大提高运算速度。 近年来也有人将神经网络和遗传算法应用于数字波束形成l m l ，但实际应用不是很 多。 目前关于d b f 的理论研究较多，硬件实践较少，这是因为实现d b f 的算法运算量 过于庞大，硬件实现时难以满足系统的高实时性需求【l 刀。上海交大结合并行延时最小 均方( p a r a l l e ld e l a yl m s p d l m s ) 算法，充分利用f p g a 存储资源丰富，细颗粒易于 并行等优势，采用f p g a 单芯片来实现d b f 硬件模块。用x i l i n x 公司的s p a r t e n1 i x c 2 s 1 0 0 芯片实现了基于该算法的自适应d b f 结构【l ”。 1 2 本文的主要工作 本文结合总装“十五”预研项目“x x 雷达d b f 接收阵”，进行了数字波束形成 算法的研究并在硬件系统上实现。本文主要开展了以下几个方面的工作： 1 、对基于线性约束最小方差( l c m v ) 准则的程序进行优化，以适应系统实时 性要求。优化后运算量为优化前的4 0 4 。根据系统测试要求，对算法作适当修改。 参与完成了系统测试，测试结果与理论结果基本相符。 2 、在a d s p t s 2 0 1 s 硬件平台上实现了基于l c m v 准则的d b f 算法。完成了软 件和硬件的调试。测试结果验证了软件的正确性。 3 、针对大型阵列的特点，提出了一种新的自适应波束形成算法分块并行的 l c m v 算法。这一算法通过对输入信号和权重向量分块，降低了向量的维数，并且 各个子向量可以并行处理，克服了大型阵列数据传输和运算量的瓶颈，也大大降低了 大阵列数字波束形成系统的复杂性和成本。并且通过切比雪夫加权来降低旁瓣。本文 完成了算法的理论推导，计算复杂度分析，仿真以及与其它算法的比较，仿真结果验 证了算法的正确性及运算量上的优越性。 d b f 箅洼册究受蟪硬件实观 硕卜论文 2 数字波束形成技术 2 1 数字波束形成技术概述 波束形成是在阵列天线和信号处理基础上发展起来的一项新技术，它的基本思想 是利用天线阵的阵方向函数乘积定理，通过在天线阵元上加权以控制天线阵的方向函 数，达到控制天线阵方向图动态地在有用信号方向上产生高增益窄波束，在干扰信号 方向产生较深零陷的目的。波束形成有效地解决了传统天线的方向图难于进行变化控 制的难题，较好地实现了对有用信号的自动接收。 一、数字波束形成基本原理l 埔1 假设接收天线为元均匀直线阵，相邻阵元之间的间隔为d ，且各阵元都是各向 同性的，对备阵元的加权分别为w j ，w 2 ，w n ，信号是窄带信号，波长为k 信号的来 波方向为0 ，经加权控制的天线阵示意图如图2 1 所示： 一 图2 1 1 天线阵列波束形成示意图 对于均匀直线阵，其方向性矢量为： d ：【1 ，p 7 j 2 x i 。n n 9 ，p 7 等”1 ) 。自n 8 】 加权后天线阵的输出为： y ( t ) = w 7 x ( t ) 此时，均匀直线阵的方向函数可表述为： 刑) ：+ p 等+ + w p 们- l 睁m 8 = w j + w 2 e v 州9 + + w ”一1 烈9 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) t j d b f 锋三1 4 墁p 地叶寓观 = e w 忙1 堋9 = w 7 b 其中，p ( 咖等枷，矽= hw z ，t 一，k 】7 ，6 = 1 p 埘m ，_ i ) 删 ，。 二、数字波束形成的优越性 波束形成按照其实现方式的不同，可以分为模拟波束形成( a n a l o g o u sb e a m f o r m i n g ) 和数字波束形成( d i g i t a lb e a mf o r m i n g ) 两大类。由于阵列天线的方向图= 阵元方向图阵因子，当阵元的单元方向图、阵元数、阵元间距一定后，改变权重系 数的幅度和相位就可以改变方向图的指向及形状。 一般把在射频或中频( r f i f ) 韶分实现的波束形成称为模拟波束形成，“波束形成” 这一术语本身指的是通过器件或设备使个口径天线沿着空间指定的方向发射或辐 射信号。利用模拟波束形成实现对多个用户的波束形成时，所需的硬件结构非常复杂， 最常用的多波束形成矩阵b u t l e r 矩阵是一种较为简单有效的模拟波束形成网络，模拟 波束形成可以实现的精度不高。 而数字波束形成通过将接收信号在天线阵元上接收并进行数字化复加权处理，可 以同时实现多个不同指向的波束，由于数字波束形成是通过d s p 软件来实现的，因 此具有很高的灵活性和可扩展性，具有较高精度。与模拟波束形成相比，数字波束形 成主要有下列优点：在不降低信噪比的条件下，数字波束形成可以产生多个高增益波 束，使系统可以同时跟踪多个目标；数字波束形成可以充分利用天线阵接收的所有信 息优化系统性能；从理论上而言，数字波束形成可以实现任意算法；数字波束形成系 统能够实时地实现对天线系统的校正。 2 2 自适应波束形成的优化方法 自适应波束形成最早出现在声纳和雷达系统中，1 9 6 5 年，a p p l e b a u m 提出了完 全自适应阵列的概念，并提出了基于最大信噪比原则的自适应算法【圳；接着，w i d r o w 和h o 行提出了利用最小均方误差的算法，在一定的条件下，该算法可以获得良好的 性能1 4 】。虽然表面上看来，最大信噪比算法和最小均方误差算法是两种完全不同的方 法，但对于稳定的信号，已证明了它们均收敛于维纳解【2 ”。后来，c a p o n 提出了极大 似然方法瞄l ，r e e d 等又提出了直接对样本相关矩阵求逆的方法，该方法能够快速收 敛并克服收敛速率依赖于特征值散布的缺点，但是该方法计算量较大p l 。自适应波束 形成技术经过了几十年的发展，已经逐渐走向成熟。一个基本的自适应波束形成结构 如图2 2 1 所示，其中，自适应处理器可以依据许多不同的准则选择最佳权向量。比 较常用的准则包括：最小均方误差准则( m m s e ) ，最大信噪比准则( m s n r ) 和最 一5 一 d b f 算庄研究及疑硬件实现 硕卜沦史 小方差准则( m v ) z 4 1 。 五( f ) ： 五( r ) ： ( f ) 幽2 2 1 目适应波果形成框图 1 最小均方误差准则( m m s e ) 最小均方误差准则就是使估计误差的均方值最小化，具体地说，就是使阵列输出 _ y ( f ) = w 7 x ( t ) 与参考信号d ( t ) 的均方误差最小，均方误差为： e ( 9 2 ( f ) ) ；e d ( t ) - w 7 x ( f ) 2 ( 2 2 ，1 ) 为使式( 2 4 ) 最小化，将式( 2 ，4 ) 展歼得： e ( s 2 ( f ) ) = e ) r - 2 w 7 r + w 7 r w ( 2 2 2 ) 其中，= 昱p ( f ) x ( f ) ) ，r = ( 熠“) ，一般地，将震称为相关矩阵，r 称为互相关矩 阵。将式( 2 5 ) 对于权向量求梯度，得到梯度算子： v ，( e ( 2 ( f ) ) ) = 之r + 2 r w ( 2 卫3 ) 令梯度算子为零，得到最小均方误差准则下的最佳权向量： = r 。， ( 2 z 4 ) 此最佳权向量被称为维纳解。 2 。最大信噪比原则( m s n r ) 最大信噪比原则是基于期望信号的功率与噪声功率之比最大的准则，假设期望信 号为s ，且墨= e ( s s ”) ，是= ( “) ，其中，“表示噪声a 此时，输出的信号功率 可以写成： z = g f ：形8 s 1 2 ) = ”e 矿 ( 2 2 5 ) 输出的噪声功率可以写成： 西= e ( f 4 2 ) - w 8 毛矿 ( 2 2 ，6 ) 这时，输出的信噪比s i r 为： 一6 一 ， 母t 沦之 d b f 募，三研毫鼍疑蝗僻宴吨 s i r ：垂：鬈坚 ( 2 2 7 ) 吒rw 经计算，使得输出信噪比最大的最佳权向量是对应于矩阵r 。一r 。的最大特征值的特征 向量，也就是说如果设a 。是矩阵r 。- i r ，的最大特征值，则得到的最佳权系数满足： r = k ( 2 2 8 ) 3 最小方差准则( m y ) 在已知期待信号的来波方向和参考信号的条件下，最小方差准则是通过最小化阵 列输出的噪声方差，来取得对信号j 的较好的增益。经权重后的波束形成器的输出为： y ( t ) = w 7 x ( t ) = w 7 s + w 7 u ( 2 2 9 ) 为保证波束形成对信号5 的增益，必须对波束形成器的权向量加以限制，使其在 信号j 方向产生一定的增益，即： w 8 a 日= g ( 2 2 1 0 ) 其中，a 。为期望信号的方向矢量，则最佳权重可以表示为： = 驾浩 ( 2 2 1 2 ) a 。 虽然以上三种准则在原理上是完全不同的，事实上，它们的联系非常紧密，可以 证明，这些准则下的最佳权向量都可表示为维纳解。因此，选择不同的准则并不会影 响阵列输出的性能，但是，在实际应用中，环境是不断变化的，要求实时地更新权向 量，因此我们需要利用自适应算法来获得实时的权向量，而自适应波束形成算法则不 仅决定了算法的收敛速度，而且决定了算法硬件实现的复杂度。 2 3自适应波束形成的常用算法5 11 2 5 2 6 j 常用的自适应波束形成算法有最小均方算法，样本相关矩阵直接求逆，递归最小 二乘算法等，下面分别简单介绍： 1 最小均方算法( t a s ) 最小均方算法是应用最广的一种波束形成算法，它是在已知期望信号的参考信号 d 的条件下，利用随机梯度法最小化误差e ( 七) ： p ( 女) = d w 7 ( 七) z ( 后) ( 2 3 1 ) 从而得到权向量的迭代公式： w ( k + 1 ) = w 【七) + u x ( k ) e ( d ( 2 3 2 ) 其中，z 为步长因子，它决定了算法的收敛速度。最小均方算法的收敛性态取决于相 关矩阵r 的特征结构，当其特征值散布很大时，算法收敛速度较慢。 2 样本相关矩阵直接求逆算法( s m d 样本相关矩阵直接求逆的算法是利用某一时间段内的接收数据构造对相关矩阵 d b f 算庄研究及j 硬件宴观 硕 论文 ( 2 3 3 ) 通过接收数据和参考信号形成互相关矩阵r 的估计： = d ( 七) x ( 七) ( 2 3 4 ) f ：瓦 从而得到最佳权向量的估计： 矿= 蠢一1 声( 2 3 5 ) 自相关和互相关矩阵的估计是基于最大似然原理的，它给出了最小方差的无偏估计。 样本相关矩阵直接求逆的算法是分块迭代的，即在一段时间内，接收数据保持不变， 每隔定的时间，更新接收数据块，故称分块迭代。虽然从理论上讲，样本相关矩阵 直接求逆的算法比最小均方算法的收敛速度快，但是其最大的缺点是运算量大，计算 复杂度高。 3 递归最d 、- - - - - 乘算法( r l s ) 在样本相关矩阵直接求逆算法中，如果采用递归方法估计相关矩阵r 和互相关矩 阵，就形成了递归最小二乘算法，其权向量的递归迭代公式为： 矿( n ) = 矿( h 1 ) + g ( 月) l d 。( ，1 ) 一i f , 8 ( n 1 ) x ( ) l ( 2 3 6 ) 其中，增益向量q ( n ) 为： 咖，= 考羲器 旺。 其中的0 _ ，k = 0 , k - ， ( 4 2 9 ) d b f 算硅研究厦疑硬件实现硕卜论史 2 、解a x = b 等价于解 只只血= 只坦6 即 l u x = 6 = 只币 此时等价于求解l y = 6 ，己废= y 计算公式为 y l = 岛，咒= 白一e l , j y j ，i - - 2 ，n j = l x h = y i u m 只一u , j x j 而= = l _ 一，i = n 一1 ，l ( 4 2 1 0 ) ( 4 2 1 3 ) ( 4 2 1 4 ) ( 4 2 1 5 ) 通过以上两部分的计算，即可实现l u 分解求解线性方程组。要实现矩阵求逆，只需 要将b 换成单位矩阵b ，石向量对应x 矩阵，对于x 矩阵也分成各个向量来求解，就 等价于求解线性方程组，因此可以实现矩阵a x = b 的( ，分解求逆。 ( 三) 、三u 分解求逆矩阵的软件实现 根据三u 分解求逆矩阵的求解方法，程序实现也是分两部分实现的。分别为工u 分解和求逆矩阵。其实现的流程图分别为图4 2 2 的( a ) ( b ) 。 在程序实现过程中，为了节省空间，得到的u 和，仍然存放在矩阵4 中，由式 ( 4 2 i ) 我们可以看出，存放空间没有冲突，其中上矩阵的对角线为1 ，所以存放了 u 的对角线的值，不会影响到最终结果。 由于式( 4 2 9 ) ，求上下三角矩阵时，不需要对整个矩阵维数做循环，从流程图 中我们可以看出，两部分正好分开。但是在求上三角矩阵的最后k = _ ，时，再执行一 次循环后，k = j + l ，为了满足求下三角矩阵的条件，需要对k 重新初始化。 求逆矩阵时，先采用逐次向前带入法求y ，f 递增到n ，同样存在l u 分解时的问 题，最后一次循环后，i = n + 1 。所以在逐次向后回代法求工时，需要对i 重新初始 化，以满足递减的初始条件。 日是单位矩阵，由式( 4 2 1 3 ) 和式( 4 2 1 5 ) 我们可以看出，在向前带入求y 时 用到b ，在向后回代求工时不再需要用到，因此，我们将逆矩阵的结果肖存放在b 空 间中，节省了空间的开辟，也减少了参数的个数。因为在汇编中，参数必须使用指定 的寄存器来传输，参数个数减少，在汇编中安排寄存器时有很大的优势。 图4 2 2 所示的算法流程图，是根据l c m v 算法中，矩阵的特点简化的，去掉了 一些可以简化的环节，使程序实现更加简单，汇编更容易实现，也节省很多运算量。 简化后的程序并不是对任意矩阵都适用的，比如奇异矩阵。 谛卜论zd b f 曹三研t 冀箕硬件娄观 中 1 一 = 一詹 ”1 。 、 求。 t l - l i = t + l 三- i角 n 奈篆i - t ! ： 。孑 t y r ” !审 l k = ji ， 。f 。l ， 。 。 j 1 l 一 七 l 乞= ”1 7 f，m l 。 下： ” b k = k + 1 三“ 。p 。8角 上 矩 n 、 阵 。l 。! y l ，= ，+ 1i ； n “ n ：少 i y 厶u 矩阵申 1 f 芒 f 逐 咒2包一乞l,yjf 垮 j = l 【向 雾 | f _ f + 1 入 l法 * n 八查 ! 丫罗y ； “ i ” ” 毫 ； i t 。 f - 。 。= ! r 咒一u , j x j ； 五2 7 3 1 u l f r ” 箸 n少冬求!i-一i s 量 ： n 乏yiy l|i=七+1i 上 n ly 逆矩阵 图4 2 2 ( a ) l u 分解 图4 2 2 ( b ) 求逆矩阵 一2 1 d b f 算庄研究及兑硬件实现硕十论艾 对软件程序的优化是按蕾图4 2 3 所示的步骤来实现的，从最基本的l u 线性方 程组求解开始到实矩阵求逆，再进一步改成复数矩阵求逆，均用c 语言实现，最终 在t m s 3 2 0 c 6 7 0 1d s p 上用汇编实现，并通过软件流水进行优化，提高运算速度。 线性方程组 l u 求解 ( c 语言) l u 分解 实矩阵求逆 ( c 语言) l u 分解 复矩阵求逆 ( c 语言) l u 分解 复矩阵求逆 ( 汇编) l u 分解 复矩阵求逆 ( 汇编优化) 图4 2 3l u 分解求逆矩阵软件实现优化流程图 在实际的程序编写过程中，根据自己的算法的需要，结合算法中矩阵的特点，对 标准的l u 分解程序作了一定的修改，使之更适合算法需求，节省更多时间。 因为算法中用到的矩阵不是奇异矩阵，因此去掉了判断是否为奇异矩阵的部分程 序，省去了几个判断语句。判断语句在汇编中特别是在流水过程中，会比较麻烦，去 掉的话，可以省很多语句。c 语言环境下，从实矩阵求逆改到复数矩阵求逆，难度并 不大，只要时刻搞清楚复数运算实部和虚部的对应关系就可以了。 最后两个环节，在t m s 3 2 0 c 6 7 0 1 的d s p 上实现，有很多问题需要注意和值得探 讨的。这两部分也是工作的重点，接下来具体讲一下汇编中的一些问题。 首先要注意的就是数据类型。一开始在c 语言里面初始化的矩阵为d o u b l e 型的， 但是汇编中的l d w 的指令只能l o a d 3 2 位的数据，所以要改成f l o a t 型程序才正确传 输数据。 在汇编调试过程中，单精度浮点数是个重要的问题，汇编中显示的值不是我们可 以直接看到的。除了要了解一些常见的值的十六进制表示，必要时，需要自己做一些 转换。c 6 7 x 采用与i e e e 标准相同的浮点数表示法，有3 2 位单精度与“位双精度两 种。图4 2 4 是单精度浮点数格式【3 5 】。 ”3 0 叠露o 图4 2 4i e e e 标准单精度浮点数格式 图中各个符号的意义如下：s 代表数的符号，0 为正，1 为负；g 是指数阶码，8 位，视做无符号数( 0 e 2 5 5 ) ；厂是为数的分数部分，共2 3 位。对于规格化数，当 0 e 2 5 5 时，上述浮点数的数值为( 一1 ) 2 e - 1 2 7 ) 1 f 。 在t m s 3 2 0 c 6 7 0 1 的汇编编程中，还有个问题需要注意的是：区分浮点指令和非 浮点指令。比如，地址偏移量的乘法用m p y ，而数据的乘法，因为是浮点数的乘法， 必须用m p y s p 。两者需要严格区分，否则错误严重。同理，其他涉及到的浮点运算 砸t 论芝d b f 募上辑蔓鲢堙僻寓观 也要注意这个问题。 在汇编调试中，发现选主元耗费较多运算量，去掉选主元，程序可以达到预期的 效果，这部分修改不影响本算法的结果，不知道对于其他任意矩阵是否可行，有待进 一步研究。 对程序中的一些循环作了流水，但是不可以盲目做流水优化。因为在某些条件控 制下，有的循环只执行一次，流水了反而会增加指令周期，这就是为什么流水之后时 间还会变长的缘故。因为这个程序中每个循环中的指令不是很多，所以软件流水的效 率也不是非常高。迭代间隔不能够太短，否则数据还没有更新完就又被下一次循环用 到了。下面以一个循环为例，简单说明一下软件流水的过程。 软件流水是编排循环指令，使循环的多次迭代能够并行执行的技术。c 6 0 0 0 的并 行资源使得在前一次迭代尚未完成之前可以开始一个新的循环迭代。软件流水的目的 就是尽可能早地开始一个新的循环迭代。 我们怼e 盼解求逆矩阵的一个内循环程序片断进行了流水处理，这段程序实现 的是式( 4 2 8 ) 中的除以u 一在复数运算中，除法就相当于倒数的实部和虚部间的 乘法运算，这段程序主要实现的即是乘法的功能。因为要对所有求得的值除以“。， 所以通过循环来实现，“。在循环中不改变，可以在循环外先求得1 u 。 在复数乘法中，实部和虚部各需要两次乘法，实现一次复数乘，需要四次乘法运 算和一次加运算和一次减运算。下面介绍一下对该段程序进行软件流出处理的过程。 首先画出相关图，即数据流程图，其步骤慰3 5 1 ： i 画节点： 节点一个或多个数据通路流入和流出的点； 2 画节点间数据流向的数据通路： 3 添加指令和指令所占用的周期； 4 添加功能单元： 读取d 、乘法m 、加法l 、减法s 、跳转s ； 先为仅有一种功能单元可用的指令安排功能单元； 平衡使用a 、b 两侧的功能单元； 使交叉通道的使用最少； - 5 调整相关图中功能单元的分配，使指令并行执行。 图4 2 5 即为得到的相关图，左边所注的是所处的周期。从图中可以明显看出，a 、 b 两侧的功能单元数几乎相等，有四次用到交叉通道。功能单元两边平分，和交叉通 道尽可能少是一对矛盾，要平衡好两者之间的关系。点划线标示的路线是s t w 在d 1 单元存储前所必须等待的周期。在周期数标为8 1 2 处，意思为第8 个周期时，可以进 行m p y s p 运算，但必须要等到第1 2 个周期，b 1 4 的值计算完毕才可以进行a d d s p 运 d b f 算庄研究及冀硬件实现 确t 论丈 算。所以到达m e n l o r y 是第1 6 个周期。同理在1 2 1 6 处，在第1 2 个可以进行m p y s p 运算， 但是必须等到第1 6 个周职a l o 的值计算完毕，才可以进行s u b s p 的运算，所以到达 m e m o r y 时为第2 0 个周期。 2 0 2 1 s u b 圈4 2 5 复数乘法的自相关图 通过相关图，所用单元，所处周期一目了然，为下面的模迭代间隔编排表做了很 好的铺垫。相关图的作用之重大，之明显就不言而喻了 程序流水的实现过程如下所述f 3 5 1 ： 1 画模迭代间隔编排表 考查模迭代间隔编排表的性能是表示代码性能的一种方式。表给出了软件流水循 环的执行情况和周期跟踪所使用的资源，确保资源在任何给定的周期内不会使用2 次。 一个循环地迭代间隔是指这个循环相邻2 次迭代开始之间的周期数。 2 确定最小迭代间隔 一2 4 硕。论之 d b f 算甚研毫受奠砖仲宴吨 软件流水通过有效地利用资源柬提高代码信能，然而为了建立一个完全流水的编 排表，应首先确定最小迭代间隔。一个循环的最小迭代间隔是这个循环相邻2 次迭代 开始之问必须等待的最小机器周职数。迭代间隔越小，执行一个循环所用的周期就越 少。 循环中使用的最多的资源数和数据相关性决定着最小迭代间隔。例如，在一个循 环中有4 条指令部使用s l 单元，则最小迭代间隔至少是4 ，因为使用同一资源的4 条指 令不能并行执行，因此至少需要4 个分开的周期执行每一条指令。交叉通道不能冲突 是个很容易忽视的问题。 3 建立一个完全流水的模迭代间隔编排表 4 编制软件流水后的汇编代码 5 消除额外指令 表4 2 1 是复数乘法软件流水的模迭代间隔表。 表4 2 1 模迭代间隔编排表示例 u n i t 、c y c l e 0 6 l 尹甏 d 1 ，d 2 ； m 1四ym 口y l m p y ” 3 1 2m 咿y ，咿y m p y ” l ls u b 7 j l 2s u b 7 ； s 1 b i s 2 li l x “ j 2 x 套 u n i t 、c y c l el71 3 1 d l l d 2 l m 1 m p y 5 = m 2 m p y 5 i l l l a d d s pi l 2 s u b s p s 1 一! ； s 2 l x a d d s p 2 x s u b s p u n i t 、c y c l e 28 已。1 4 ， d b f 算往研究及萁醺件实现硕t 论史 一2 6 一 d 1 d 2 m 1m 【p y s pr 【p y s p * m 2 m 口y s p r m p y s p 者 l la d d 9a d d 9 a d d 9 + l 2 a d d 9a d d 9 a d d 9 * * s la d d 5 s 2a d d 5 l x ； 2 x ； u 1 1 i t 、c v c l e39 1 5 ； d 1l d wl d w u ) w 4 * d 2l d wl d w l d w “1 m 1 ，【p y s p l lm p y s p i * m 2m p y s p i m p y s p l + j l l a d d l ti 工2a d d 饿1 s l s u b s 2； ” l xm p y s p i m p y s p t * 2 x 伊y s p l lm p y s p i 鬈j u n i t 、c y c l e 41 0 i 1 6 1 d l l1 d 2 m 1 i n l l l l ， 1 l 2 8 1 ，。i s 2 i一。i l x # ； 2 x * u n i t 、e y e l e5l l 。1 7i d 1 s t w i d 2 s t w 一一1 m 1 m 2 l l l 1 l 2 ，。# 一。；茹 矽记之d b f 算_ 主碑定砭疑畦衅毒琨 s l a d d 7 a d d 7 +a d d 7 2 4 s 2a d d 7a d d 7 a d d 7 4 l x 2 x i ， 。 循环的最小迭代日j 隔为6 个周期。一次循环中有3 次乘法，而乘法只能用m 单 元，所以最小迭代间隔至少为3 ，因为浮点乘加减运算都需要等待3 个周期，迭代间 隔安排也不能十分紧凑。 对照上面的模迭代间隔表，写出流水后的汇编程序已经是非常简单的事了。对应 的流水后的程序如下： ：b e s l nt h es o f t w a r ep l p e l l n e0 i l 0 0 p 3 二； m p y m 1a 7 ，a 6 ，a 9 m p y m 2 b 7 ，b 6 ，b 9 n o p a d dl 1a 9 ，a 8 ，a 9 a d dl 2 b 9 ，b 8 ，b 9 l d w d 1 - + a 4 a 9 】，a 1 2 l d w d 2 。+ b 4 b 9 】，b 1 2 n o p a d ds 1 a 7 ，l ，a 7 a d d