（信号与信息处理专业论文）一种基于pi技术的并行自适应滤波算法.pdf

同济人学硕士论文摘要 摘要 自适应滤波作为数字信号处理的一个重要内容，具有自适应调节滤波器权值 的优点，能够适应相对复杂的信号环境，从而被广泛地应用于各种信号处理领域。 特别是在近十五年来发展迅速，受到国内外学者极大重视，有着极其广泛的应用。 随着大规模集成电路的发展，越来越多的计算机及信息处理系统采用了并行处理 的体系结构，以提高运算速度、满足人们对处理能力的高效、实时的要求。因此 关于各种高速自适应滤波算法的研究已逐渐成为一个研究热点。 本论文在自适应滤波技术的基础上，提出了一种基于p i 技术 ( p i p e l i n i n g i n t e r l e a v i n g ) 的自适应滤波器结构，并导出了相应的并行自适 应l m s 算法，这种滤波器并行度高，结构简单。对一n 阶的串行滤波器而言，本 文提出的并行自适应滤波采用k 个长度均为n k 的f i r 滤波器就可实现k 输入k 输出的自适应处理，与串行处理( 单入单出) 的滤波结构相当，并且其结构的的 复杂程度远远低于其它并行结构，所以在保证较高的数据通过率和较低的系统功 耗的同时，因为结构简单而更易于实现。 p i 技术即p i p e l i n i n g i n t e r l e a v i n g 。它综合了流水线( p i p e l i n i n g ) 技术和交叉 存取( i n t e r l e a v i n g ) 技术的特点，它能针对速度和性能的要求，提供更有效的数字 滤波器结构。于是本论文以f i r 滤波器为原型，在分析了基于多项式并行表示的 并行l m s 算法结构基础上，提出了基于p i ( p i p e l i n i n g i n t e r l e a v i n g ) 技术的 一种新的自适应滤波并行算法结构，并在此基础上提出了相应的并行自适应l m s 算法。借助m a t l a b 实验仿真，与普通串行自适应滤波结构以及基于多项式表示 的并行滤波结构进行了比较，实验仿真运行结果表明新结构算法在收敛速度上明 显优于前两者，从而为并行自适应实时处理提供了现实的可行性。 同济大学硕：l - 论文a b s t r a c t a b s t r a c t b e i n gc a p a b l eo fa d j u s t i n gt h ew e i g h t sa d a p t i v e l ya n da d a p t i n gc o m p l e x e x t e r n a le n v i r o n m e n t ，a d a p t i v ef i l t e ri sw i d e l yu s e di nv a r i o u ss i g n a l p r o c e s s i n g f i e l d s i ti saf o c u si nt h er e s e a r c ho nh i g h s p e e dr e a l - t i m es i g n a lp r o c e s s i n g p a r a l l e l p r o c e s s i n gi so n eo f t h em a i nt e c h n i q u e si nt h ef i e l d so fh i g h s p e e dr e a l t i m es i g n a l p r o c e s s i n g ，r e s e a r c h e r sp a ym o r ea t t e n t i o nt oi t f i r s t l y , t h i sp a p e ra n a l y s e st h ep e r f o r m a n c eo fl e a s tm e a ns q u a r ea l g o r i t h m ， p o i n t so u ti t sf a u l ta n dd i s c u s s e ss e v e r a li m p r o v e m e n t so nt h el m sa l g o r i t h m ，s u c h a sap a r a l l e l a d a p t i v e l m sa l g o r i t h m b ye x p r e s s i n g t h ed i g i t a l s i g n a l i n p o l y n o m i a l sp a r a l l e l f o r m b u ti t sf i l t e rs t r u c t u r ei sn o ts u i t a b l ef o rt h e i m p l e m e n t a t i o n s e c o n d l y , t a k i n gt h ea d a p t i v ef i rf i l t e rf o re x a m p l e ，an e wp a r a l l e l a d a p t i v ea l g o r i t h mb a s e do np i p e l i n i n g i n t e r l e a v i n g ( p i ) t e c h n i q u ei sp r e s e n t e d a p i p e l i n i n g i n t e r l e a v i n g ( p i ) t e c h n i q u ed e v e l o p e df o re f f i c i e n td i g i t a lf i l t e r i n gp r o v i d e s e f f i c i e n td i g i t a lf i l t e rs t r u c t u r ef o rv a r i o u ss p e e da n dp e r f o r m a n c er e q u i r e m e n t s c o m p a r e dw i t ht h eo r i g i n a l ，t h en e wa l g o r i t h mn o to n l yh a sf a s t e rc o n v e r g e n c e s p e e d ，b u ta l s oh a sh i g h e rt h r o u g h p u tr a t ea n dl o w e rp o w e rc o n s u m p t i o n f i n a l l yt h en e wp a r a l l e ll m sa l g o r i t h ma n di t sp e r f o r m a n c e sa r ed i s c u s s e d c o m p u t a t i o n a ls i m u l a t i o n si nm a t l a b s i m u l i n ks h o w st h ep e r f o r m a n c eo ft h en e w a l g o r i t h mi sb e t t e rt h a nt h a to ff o r m e ra l g o r i t h m 声明 本人郑重声明：本人在导师的指导下，独立进行研究工作所取得 的成果，撰写成硕士学位论文“一种基于p i 技术的并行自适应滤波 算法 。除论文中已经注明引用的内容外，对本文的研究做出重要贡 献的个人和集体，均己在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开或未公开发表的成果。 本声明的法律责任由本人承担。 学位论文作者签名：当刍荚 - 0 1 7 垆年够月y 日 同济大学硕：i ：论文 第一章绪论 第一章绪论 1 1 自适应滤波技术的发展及应用 滤波是现代数字信号处理的重要研究内容。特别是自适应滤波，因其具 有可随信号传送环境和要求的变化而自动( 即“自适应”) 调整系统参数的特 性，在近十五年来发展迅速，受到国内外学者极大重视，有着极其广泛的应用。 自适应滤波技术最早始于2 0 世纪中叶。1 9 5 7 年至1 9 6 0 年间美国通用电 气公司的豪厄尔斯( p h o w e l l s ) 和阿普尔鲍姆( p a p p l e b a u m ) 及其同事们就 已经开始了简单自适应滤波器的研究，并将其用于消除混杂在有用信号中的噪 声和干扰。1 9 5 9 年，美国斯坦福大学的维德罗( b w i d r o w ) 和霍夫( m h o f f ) 开始了结构更为复杂的自适应滤波器的研究工作，此间他们发明了最小均方 ( l m s ) 自适应算法，并提出了一种采用被称为“自适应线性门限逻辑单元” 的模式识别方案，在自适应理论方面作出了巨大的贡献。同时，原苏联莫斯科 自动学和遥控力学研究所的艾f 1 曼( a i z e r m a n n ) 及其同事们，也研制出一种 自动梯度搜索机器。还有英国的加布尔( d g a b o r ) 和他的助手们则研制出了 自适应滤波器，他们的工作都是独立进行的。 到2 0 世纪6 0 年代初期和中期，在自适应信号处理的理论研究和实践、应 用方面的工作进一步加强，研究范围己发展到自适应、自适应控制、自适应滤 波( 包括时域和空域) 及其他方面。美国贝尔实验室的勒凯( r l u c k y ) 首先 将自适应滤波应用于商用数字通信中。1 9 6 5 年，自适应噪声对消系统在斯坦福 大学建成，并成功的应用于医学中，主要用于对消心电放大器和记录仪输出端 的6 0 h z 干扰。此后，瑞格勒( r r i e g l e r ) 和康普顿( r t c o m p t o n ) 推广了由 豪厄尔斯和阿普尔鲍姆所做的工作。 随着自适应空域滤波的概念的不断完善，一类由维德罗、格罩菲斯 ( l j g r i f f i t h s ) 等人研制出来的基于“引导信号”算法的自适应波束形成器应 用于自适应阵列信号处理。1 9 6 9 年至1 9 7 2 年i 日j ，由格里菲斯和弗罗斯特 ( o l f r o s t ) 等人发明了又一类和“引导算法”相似的“线性约束”自适应天 线算法。 同济大学硕二卜论文第一章绪论 自适应滤波技术可以用来检测平稳和非平稳的随机信号。由于自适应数字 系统具有很强的自学习、自跟踪能力和算法的简单易实现性，它在噪化信号的 检测增强、噪声干扰的抵消、波形编码的线性预测、雷达声纳系统的阵列处理 和波束形成、通信系统的自适应均衡、图像自适应压缩编码、图像的自适应增 强复原、图像识别的自适应分割，以及未知系统的自适应参数辨识等方面获得 了广泛的应用。数字集成电路和微电子技术的迅速发展也给自适应信号处理的 应用提供了十分优越的条件。目前自适应信号处理技术在通讯、雷达、声纳、 图像处理、计算机视觉、地震学、导航系统、生物医学电子学和工业控制等领 域有着及其重要的应用和发展自玎景。 同济大学硕j l ：论文第一章绪论 1 2 自适应滤波 1 2 1 自适应fir 滤波器 f i r 滤波器即有限长单位冲激响应滤波器自适应滤波领域所用的f i r 滤 波器一般为横向滤波器，图1 2 1 1 所示为自适应横向滤波器的结构，其功能描 述如下： ( 1 ) 具有可调节抽头权系数的横向滤波器，权系数h ，( 门) ，h ：( 门) ，( 打) 表示 在行时刻的值。 ( 2 ) 是能在自适应状态下调节这些权系数的机理过程。这个过程首先自动 调节滤波器系数的白适应训练步骤，然后利用滤波系数加权延迟线抽 头上的信号来产生输出信号，将输出信号与期望信号进行对比，所得 的误差值通过一定的自适应控制算法再来调整权值以保证滤波器处在 最佳状态，达到实现滤波的目的。 图1 2 1 1 中x ( n ) 表示输入随机信号序列，y ( n ) 表示输出序列，d ( n ) 是 期望得到的序列，虚线箭头表示通过自适应算法调整滤波器权值l ( n ) 。由此可见， 自适应滤波通常是由两个不同部分构成，即滤波器部分和自适应算法部分。 同济大学硕：j ：论文第一章绪论 设自适应f i r 滤波器抽头输入信号z ( 力) = k ( 刀) x ( n 一1 ) x ( n 一所) 】1 ，其滤波 系数矢量即权值厅( 刀) = 阮( 门) 红( 盯) 研) t ，则输出信号，( ，z ) 可以写成如下的 卷积形式： m y ( ，z ) = 办，( 以) x ( 舱一f + 1 ) = h r ( 玎) x ( ，2 ) 式中上标“t ”表示转置。 根据图中输出信号少( 胛) 与期望信号d ( 以) 之间的关系误差序列p ( 门) 应为 e ( n ) = d ( n ) 一y ( 刀) 很显然，自适应滤波器的控制原理是用误差序列e ( n ) 按照某种准则和算法对其权 值以( 门) ，i = l ，2 ，m 进行调节的，最终使自适应滤波的目标函数最小化，从而 达到最佳滤波状态。 根据自适应均方误差( m s e 即m e a ns q u a r ee r r o r ) 准则可推导得到目标函 数最小的最佳滤波系数( 即最佳权向量) 删为 j l l ，。= r p ( 1 2 1 3 ) 其中，r = k ( ，z ) x t ( 刀) j 是输入信号的自相关矩阵； p = e p 0 ) x ( 门) 】是期望信号与输入信号的互相关矢量 1 2 2 最小均方( l m s ) 算法 上一节给出了自适应f i r 滤波器的w i e n e r 解形式，但是在应用时，必须要 知道所求信号的和观测信号之l 日j 的互相关矢量凡在一般情况下，它很难从观测 信号中估计出来，为此，i d r o w 等人提出了一种非常巧妙的方法，即最小均方 误差( l m s ) 自适应算法。 l m s 自适应算法的思路是这样的：假设给出了和原始信号相关的参考信号 d ( n ) ，那么首先对f i r 滤波器的权任意设定一组初始值；然后根据滤波器的输 同济人学硕士论文第一章绪论 出值与参考信号之间的误差p ( 胛) 对各权值进行调节，使下一次的输出误差能有所 减小；这样重复下去，直到滤波器的权收敛到最佳值。l m s 自适应算法流程可用 图1 2 2 1 来描述。 讲，z ) 十 图1 2 2 1白适应滤波框图 可以看出l m s 自适应滤波的关键就是如何根据误差e ( n ) 来调节滤波器的权 值，使其收敛到最佳值。其权向量调整满足下列迭代公式 h ( n + 1 ) = j | l ( ，z ) + 2 p ( 刀) x ( 刀)( 1 2 2 1 ) 该式给出了一种非常简单的权向量的递推算法，即最小均方( l m s ) 自适应算法。 该算法由美国斯坦福大学w i d r o w 和h o f f 于1 9 6 0 年提出。这种自适应滤波方法 可以根据信号的变化自动调节权向量以获得最佳的输出。 1 2 3l m s 算法的收敛性 上一节给出的l m s 自适应算法在求滤波器的权向量时非常简单、快捷。它 既不要计算输入信号的相关函数，又不要求矩阵的逆，因此得到了广泛的应用。 但是，由此算法得到的权值能否收敛于最佳值，还是一个问题。假设输入信号向 量x ( 玎) 和x ( 门+ 1 ) 互不相关，由式( 1 2 2 1 ) 知权向量h ( n ) 仅与以前门一1 次输入信 号数据x ( n 1 ) ，x ( n 一2 ) ，相关，和x ( n ) 不相关，可分析得到算法收敛的充分条 件是 i 卜2 肼。i ( 1 ( 1 2 3 1 ) 同济大学硕士论文第一帚绪论 由此可解得的取值范围 吣( 亡 这里为一个控制自适应速度和稳定性的增益常数，通常称之为自适应收敛系数 或步长因子。由于 m 名m 。、( 九= t r r 】 丘= o 故的取值范围可近似地表示成 。 - j 曲线收敛的快慢。 实际上，由于l m s 算法在每步迭代过程中梯度估值是带噪的，这就意味着 滤波均方误差f ( 胛) 随着迭代次数门的增加而出现小波动地减少，最后4 ( n ) 不是 等于最小均方误差孝m 。( 丹) 而是略大于该值，但如果步长因子选用的合适将可减 少这种波动，通常选用的越小，这种噪化指数衰减曲线上的波动幅度越小，即 学习曲线的平滑度越好，通常采用计算机仿真所得的总体平均学习曲线( 即平均 m s e ) 来反映和描述自适应算法的收敛情况，它是由5 0 到2 0 0 个独立运行的结 果加以平均而得到的。 1 2 5 失调 从上面的结果可以知道，理想的自适应滤波算法应使权向量收敛于最佳值。 但是在l m s 算法中，由于用梯度的近似值9 。= 一2 e ( n ) x ( n ) 代替了精确值v 。， 这样所求出的权向量和最佳权向量之间就存在一定的误差。 所以在实际应用中我们常用失调m ( m i s a d j u s t m e n t ) 来对自适应滤波的误差 偏移程度进行描述，其定义为 同济大学硕士论文 第一章绪论 m ：垒匿盟二红剑 孝。i 。( 门) 其中，孝。i 。( 行) 为最小均方误差，e 眵( ”) 一孝。i 。( ”) 】为超量均方误差。 失调又可以写成 m 2 芒脚。， f 。，为算法学习曲线的平均时间常数，m 为自适应滤波器权的个数。 由于在实际应用中失调量往往是事先已给定，一般取1 0 左右，因此可利 用上式和自适应滤波器权的个数肘，来计算出学习曲线的平均延时时间。 上面诸式表明： ( 1 ) 失调为自适应l m s 算法提供了一个很有用的测度，比如，1 0 的失调 意味着自适应算法所产生的总体平均m s e 高于最小均方误差的增量值 为1 0 ： ( 2 ) 失调是随着滤波系数( 权向量) 的数目线性增加的： ( 3 ) 失调可以做得任意小，只要选用大的时f 日j 常数2 w ，也即选用小的步长 值。但是，滤波器自适应收敛过程需要长的时间，影响了滤波器自学 习、自训练的速度，所以，自适应滤波器l m s 算法的失调与自适应收 敛过程之问存在着矛盾，如何缩短收敛过程，而且有很小的失调，这 是值得研究的问题。 1 2 6l m s 自适应算法的发展与局限 以瞬时值表示梯度信息的l m s 算法由于采用权值递推更新技术，计算复杂度 低，结构简单，易于实现，因此在工程上得到了广泛的应用。特别在通信工程中 的均衡和回波抵消方面广泛应用。但它收敛过程相对较慢，收敛速度与自适应步 长因子和失调之间存在着矛盾，针对这个问题人们对基本算法做了许多改进，研 究出了许多自适应l m s 算法类算法，以缩短算法的收敛过程，加快收敛速度。如 解相关l m s 算法，变换域l m s 算法，b l m s ( b l o c k l m s ) 算法等。 同济大学硕士论文第一章绪论 根据l m s 自适应滤波算法权值的调整规律，其迭代公式为 矗( 门+ 1 ) = | l ( n ) + 丢 - 亏( 玎) 】 = h ( n ) + e ( n ) x ( n ) 为了缩短收敛过程，提高收敛速度，基于该算法的改进算法主要从以下三方面展 开： ( 1 ) 采用不同的梯度估值寺( 船) ，如解相关l m s 类算法，又即l m s 牛顿算法， 它估计亏时采用了输入矢量相关函数的估值，使得收敛速度大大快于 基本的l m s 算法，因为它在迭代过程中采用了更多的有关输入信号矢 量的信息。 ( 2 ) 对收敛因子即步长因子的选用采取不同方法。步长因子的大小决 定着算法的收敛速度和达到稳态的失调量的大小。对于常数的值( 即 采用固定步长) 来说，收敛速度和失调量是一对矛盾，要想得到较快 的收敛速度可选用大的t 值，这将导致大的失调量；如果要满足失调 量的要求，则收敛速度势必受到制约。因此，人们研究了采用变步长 的方法来克服这一矛盾。自适应过程丌始时，选取较大的值以保证 较快的收敛速度，然后使值逐渐减小，以保证收敛后得到较小的失 调量。现在变步长的一类l m s 算法有很多，通过采用不同准则方法末 实现步长因子的调整，如归一化l m s 算法( n l m s ) 、时域正交化l m s 算 法等。 ( 3 ) 采用变换域分块处理技术心1 。对由滤波器权系数矢量调整的修正项中的 乘积用变换域快速算法与分块处理技术可以大大减小计算量，且能改 善收敛特性如变换域l i d s 算法( 频域l m s 算法) 、b l m s ( 分块l m s ) 算法 等。 上述提到的各种l m s 改进算法中，当输入信号具有高度相关性时，多数自适 应滤波算法的收敛速度都要下降，但l m s 牛顿算法利用与输入信号估值有关的相 关矩阵来加快收敛速度从而很好的解决了这一问题。n l m s 算法、时域f 交i 。m s 9 同济大学硕士论文第一章绪论 算法都是以输入信号功率控制变步长的l m s 算法，自适应过程较快，性能有很大 改善，但n l m s 算法的计算量较之l m s 算法计算量稍有增加。另外当输入信号具 有高度相关性时，也可采用变换域算法( t r l m s ) 增加l m s 算法的收敛速度。 它的基本思路是先对输入信号进行一次正交变换以去其相关性或衰减其相关性， 然后将变换后的信号加到自适应滤波器实现滤波处理，从而改善了相应相关矩阵 的条件数。 除了时域l m s 自适应滤波器算法，还有频域自适应滤波器算法。该算法在自 适应滤波之前先把输入信号变换到频域，然后在频域上实现自适应滤波处理，仍 采用梯度下降法调整权系数。这样作主要有以下三方面优点： ( 1 ) 与时域相比较，所需数据处理的计算量可以大大的减少。因为频域变 换都有快速算法，利用变换相乘来代替卷积运算，特别是对长序列的 卷积运算加快了收敛过程。 ( 2 ) 与经典梯度下降法相比较，自适应过程的收敛特性有所改善。因为在 梯度下降法中各个权系数作为指数和收敛到最佳解，而每个指数与自 适应过程的固有模式有关，这些模式的时间常数与输入信号自相关矩 阵的特征值成反比，其特征值可近似的等于输入信号功率谱间隔均匀 的样本，由于输入功率谱随频率有很大的变化会导致特征值有极大的 不同，从而使时间常数也大不相同。频域法容易使自适应过程各个模 式的收敛性更加均匀，改善了较缓慢的模式的收敛速率。 ( 3 ) 频域法容易进行信号分块处理。分块l m s ( b l m s ) 自适应滤波器通过频域 快速算法来实现时域分块l m s 算法，要求在同一块中滤波器权系数保 持不变，用整块数据来估计梯度，每次修正时可以更高的精度来调整 滤波器权系数。 上面介绍了基于l m s 的一些改进算法，从一定程度上加快了收敛速度，然 而大多数自适应算法因为运算量大或算法本身不易并行、流水线处理而很难用于 高速数据处理。而现在在实际工程中，需要对大数掘量进行高速处理的情况却越 来越多，因此关于各种高速自适应滤波算法的研究己逐渐成为一个研究热点。在 并行处理技术作为高速实时信号处理领域的主要技术越来越受到重视的背景下， 人们对高速、性能稳定的自适应滤波器实现结构进行了大量的研究，取得了一定 l o 同济大学硕士论文第一章绪论 的进展睁7 1 。 1 3 本课题的研究内容和主要结论 自适应滤波技术是现代信号处理技术的重要研究领域之一，具有自适应调节 滤波器权值的优点，能够适应相对复杂的信号环境，从而被广泛地应用于各种信 号处理领域【8 - 9 1 。 长期以来，人们对各种自适应滤波算法都有深入地研究。在众多的自适应算 法中，受到人们广泛关注的一类算法是基于数据递推的算法，其中最具有代表性 的是最小均方误差( l m s ) 算法。这种算法由于采用权值递推更新技术，易于实 现，因此在工程上得到广泛的应用。当然它也存在不少缺点，如它的收敛速度慢 等。为了克服这些缺点，人们对基本算法作了许多改进，得到了一些改进的算法， 如解相关l m s 算法，变换域l m s 算法，b l m s ( b l o c k - l m s ) 算法n 0 1 等。 然而大多数自适应算法因为运算量大或算法本身不易并行、流水线处理而很 难用于高速数据处理。而现在需要对大数据量进行高速处理的情况却越来越多， 因此关于各种高速自适应滤波算法的研究己逐渐成为一个研究热点。在并行处理 技术作为高速实时信号处理领域的主要技术越来越受到重视的背景下，将并行技 术应用于自适应滤波中有一定意义。 目前并行处理技术用于自适应滤波器( 如f i r ) 已引起专业人士的注意聃吲。 如基于流水线技术的d l m s 算法、基于多项式表示的并行算法等。但相应的讨论 主要集中在如何构造并行滤波器结构方面，对具体实现方面却讨论得不多，特别 是对并行自适应f i r 滤波器更鲜有讨论。此外，这些算法都以结构的复杂度为代 价获得并行操作。 于是本论文以f i r 滤波器为原型，在分析了基于多项式并行表示的并行l m s 算法结构基础上，提出了基于p i ( p i p e l i n i n g i n t e r l e a v i n g ) 技术的一种新的 自适应滤波器并行算法结构，并在此基础上提出了相应的并行自适应l m s 算法。 这种新结构的复杂程度远远低于原基于多项式表示的并行结构，与串行处理( 单 入单出) 的滤波结构相当。本文对这种自适应并行滤波方法的性能进行了分析， 同济大学硕i ：论文第一章绪论 并借助了m a t l a b 进行了仿真，理论分析和仿真的结果表明，在保持与普通串行 自适应滤波器复杂度相当的前提下，其收敛速度比普通串行自适应滤波器以及基 于多项式的并行滤波器有明显的改善，从而为并行自适应实时信号处理提供了现 实的可行性。 同济大学硕十论文第二章并行处理技术用于白适心滤波的町行性分析 第二章并行处理技术用于自适应滤波的可行性分析 2 1 并行处理技术与实时信号处理 并行处理技术始于计算机领域。自1 9 4 6 年第一台电子数字计算机问世以 来，6 0 多年来计算机的处理能力已经增长了十万倍以上，特别是近十余年，超 大规模集成电路( v l s i ) 和计算机体系结构的更新使得单机处理能力以1 0 年 1 0 0 倍的速度增长。然而，现有性能最高的计算机的计算能力仍远远不能满足 人类对计算速度无止境的追求l 。 虽然传统单处理机系统的性能有定的迅速提高，但受到v l s i 器件开关 速度、连线延迟以及v l s i 理论特征尺寸的限制，运算速度的进一步提高变得 越来越困难。因此如何满足对运算速度的巨大需求成为计算机系统发展的新目 标。 1 9 8 2 年诞生了按用户要求设计的第一台用于卫星图像处理的大规模并行处 理机( m p p ) 。自此，具有高度数据处理吞吐率的并行计算机发展了起来。它 所采用的技术就是并行处理技术。相对传统的单机处理系统，并行计算机运用 了先进的流水线、并发等手段，使计算机的运算速度大大提高，顺应了人们对 计算机处理速度日益增长的迫切需求。经过几十年的不断发展，特别是得益于 v l s i 技术的飞跃和并行处理理论的成熟化，现代通用并行计算机的峰值速度已 经达到每秒千亿次运算，这包括了采用大规模并行处理( m p p ) 技术设计的多 种通用并行计算机型：c m 一5 e ( 峰值速度2 6 2 g f l o p s ，g f l o p s - 每秒1 0 亿 次浮点运算) 、p a r a g o n x r s ( 1 5 3 g f l o p s ) 和s p 2 ( 1 3 6 g f l o p s ) 等。同 时，并行处理技术在多年的发展中扩展到了众多领域，如科学计算、地质分 析、气象预测、仿真模拟、图像处理及实时信号处理领域，并在结构、算法、 运行方式、应用等方面形成了各自的特色。 数字信号处理相对模拟信号处理，具有精度高，灵活性大，可靠性好，易 于大规模集成等优点。随着大规模集成电路技术的发展，数字信号处理技术也 发生着r 新月异的变革。实时数字信号处理成为当前信号处理的研究热点。虽 同济大学硕： 二论文第- 二章并行处理技术用于自适膨滤波的吖行件分析 然不同的数字信号处理领域，对数据处理的速度有不同的要求。但总得趋势是 一致的：那就是在复杂坏境中对信号处理的实时性和高效性；不仅有运算速度 的要求，还有单位时问数据处理能力的要求。例如：通信和语音信号处理中需 要每秒几千万到几亿次运算；在视频信号和图像处理中，每秒需要几亿到几十 亿次运算：而几十个通道阵元的雷达系统必须具备每秒百亿次的运算才能在复 杂环境中实时检测出目标。 而并行处理作为一种有效的信息处理形式，它着重于发掘计算过程中的并 发事件。并发性包含并行性、同时性及流水线处理。并行事件可在同时间间 隔内在多个资源里发生；同时，事件可在同一时刻上发生，流水线事件可在部 分重叠的时间内出现。在一个计算机系统的各种处理级别上，都可获得这些并 发事件。并行处理要求在计算机中并发地运行许多程序。它和顺序处理是相对 立的。它是通过计算机中的并发活动，改进系统性能以获得好的性能价格比的 一种手段【l2 1 。所以可使得大吞吐量的复杂运算在合理的时问内高效的完成。 因此，将并行处理技术用于实时信号处理势在必行。目前针对实时数字信 号处理，在数字信号处理机方面已引入了并行处理技术。如用于雷达信号处理 以实现自适应波束合成和方向估计的脉动波前阵列处理机，其数据吞吐率可高 达2 m h z 。 2 2 并行处理技术应用于自适应滤波的可行性分析 上述实时信号处理领域中引入的并行处理技术，大多是基于计算机系统硬 件结构实现方面的并行处理。而在滤波方面鲜有研究。但滤波技术作为信号处 理内容之一，它的功能是从受到干扰或噪声污染的环境中将有用信号提取出 来。同样它也面临着在处理速度和实效性方面的挑战。 而自适应滤波系统，由于能够通过自身与外界环境的接触来改善自身对信 号处理的性能，即具有自动适应信号传送变化的环境和要求的能力，所以广泛 地应用于诸如通信、雷达、声纳、工业控制、地震勘探及生物医学、电子学等 领域【l 引。随着人们对实时信号处理要求的不断提高和大规模集成电路技术的迅 速发展，如何提高自适应滤波系统的处理速度，满足现在对大数据量进行高速 1 4 同济人学硕= i ：论文第- 二章并行处理技术用于自适心滤波的a ，行住分析 实时处理的要求，已越来越引起人们关注。因此关于各种高速自适应滤波算法 的研究已逐渐成为一个研究热点。并行处理技术的研究目的是采用多个处理单 元同时对任务处理而减小任务的执行时间，如何以最短的时间完成任务是并行 处理技术所关心的核心问题。这与追求高速、实时的理念不谋而和。因此将并 行处理技术用于自适应滤波是可行的。 在自适应滤波技术中，广泛应用的是一类基于f i r 的自适应滤波器。因为 其设计方法和结构简单，而且相应的最小均方误差( l m s ) 算法易于理解，计 算量小，易于实现，所以在实际工程中有相当多的应用。但原有的基于l m s 的 自适应f i r 滤波器是一种串行的滤波器结构，在处理速度上不能满足现在高速 实时信号处理的要求。所以如何提高f i r 滤波器的设计质量是数字信号处理领 域的重要问题：为了提高f i r 滤波器的处理速度，引入并行处理技术不失为一 条可行的途径。 周济大学硕_ j ：论文第二三章皋十p l 技术的并行白适心滤波算泫 第三章基于pl 技术的并行自适应滤波算法 在并行处理技术作为高速实时信号处理领域的主要技术越来越受到重视的 背景下，人们对基于l m s 算法的高速、性能稳定的自适应滤波器f i r 实现结构 进行了大量的研究，取得了一定的进展。例如第一章提到的b l m s 算法。下面 将要提到的是对自适应f i r 滤波器权值调整延迟取样的d l m s 们算法，以及基于 多项式表示的并行算法。而本论文则在后者即基于多项式表示的并行算法基础 上借助p i 钾( p i p i n g i n t e r l e a v i n g ) 技术提出了一种新的算法结构，为了比 较说明新算法在性能和实现方面的优势，先将前两种并行算法做一介绍。 3 1 延迟l m s 算法( d l m s ) 自适应f i r 滤波器是以w i n d r o w 和h o f f 提出的最小均方( l m s ) 即梯度搜 索算法为基础的。按其迭代公式 h ，+ i = h ，+ 2 ze i x j = h j + 2 z ( d ，一工。，h ，) x j 进行滤波器权系数的调整。可见，在自适应滤波器实现中，滤波器系数的调节 按照算法的约定必须在下一个信号样本输入之前完成。换句话说，自适应算法 规定滤波器的执行时间不能超过数字信号的取样周期，这正是自适应f i r 滤波 器并行和流水线结构实现的最基本问题之一。 图3 1 1 白适膨l m s 算法信号流图 1 6 同济大学硕士论文第三幸幕十p i 技术的并行臼适心滤波算法 图3 1 1 为自适应l m s 算法信号流图。可以看出，l m s 算法迭代公式只能 依次按照： ( 1 ) 计算滤波器输出y ： ( 2 ) 计算误差e ； ( 3 ) 再计算权系数的增量a h i ； ( 4 ) 完成权系数的调节办，+ l = h ，4 - a h ， 四个步骤完成，不允许交换顺序，亦无法并行完成。因此权系数根据输出进行 调节或者说输出反馈的存在导致了l m s 算法较差的计算并行度。 为了改善l m s 算法的并行或流水线的计算性能，于是人们提出了有引入延 迟调整的修正以增加算法内在的流水线( 并行) 处理能力的方法，即d l m s ( d e l a yl m s ) 算法。该算法的权系数迭代按照流水线处理方式延迟n 个 取样周期。即在权系数矢量进行迭代更新的计算期问，同时( 并行地) 以 原来的权系数矢量对新的信号矢量进行内积( 滤波) 计算。图3 1 2 给出了 d l m s 算法延迟一个取样周期的信号流图，这里有两个子系统( 以虚线框图表 图3 1 2d l m s ( n = ”臼适j 、证滤波器信号流图 示) 以流水线方式工作，其迭代公式可表示为 办j + l2 办j + 2 ( d j i x 1 ，一i 厅，一1 ) 工 ( 3 1 1 ) = h j4 - 2 z e , _ l x1 1 同理，当对权系数矢量的调整进行两次延迟( 即延迟两个取样周期) ，于 是就有三个子系统出于流水线工作状态，参见图3 1 3 。这种修萨算法可以表 示为： 同济人学硕：t 论文第三章幂十p i 披术的并行白适心滤波算法 厅+ l = 矗，+ 2 ( d ，- 2 一x 。，一2 厅，一2 ) x j 一2 ( 3 1 2 ) = h j + 2 , u e 卜2 xi 2 图3 1 3d l m s ( n - - - - 2 ) 自适心滤波器信号流图 2 h j 办x j _ 2 d l m s 算法虽在保证原有的收敛特性的基础上改善了l i d s 算法的计算并行 度，并据此得到了一些高度流水的自适应滤波结构。但随延迟次数的增加，特 别是在以3 时( 这里刀表示延迟次数) ，该算法的收敛速度明显比原l m s 算法收 敛速度慢，失调也明显加大，所以这一类算法是以牺牲算法性能为代价的，并 且算法性能的损失与滤波器的长度成f 比。在滤波器长度较长的情况下，限制 了高速自适应滤波器结构的使用。与此同时，如何进一步提高滤波器滤波速度 和自适应收敛速度，也是一个需要考虑的问题。 3 。2 基于多项式表示的并行算法 3 2 1 数字信号的多项式并行表示 针对上述问题，又有一种基于对数字信号进行多项式表示的并行结构【1 6 j 被 提出。 一般数字信号皆可表示成多项式乘积的形式： 彳( x ) = b ( x ) xd ( x ) 这里么( x ) ，b ( x ) ，d ( x ) 均为多项式，假设它们均为负指数多项式。 同济人学硕士论文 第三帝皋十p i 技术的并行臼适戍滤波算法 可将( 3 2 1 1 ) 重写为： 一ll ll - l 彳，( x 。) x = b 。( x ) x 一”d ，( x ) x 叫 j = om = o= 0 这里x 为自变量，可重记为x 彳，( x ) = ：口。l + ，x 一”， i ：= 0 ，1 ，l - 1 n = 0 召。( x ) = 6 以+ 。x 1 ， 肌= 0 ，1 ，上一l 4 ( x ) = + ，工， ，= 0 ，1 ，一1 在式( 3 2 1 3 ) 中l 为常数，它规定了信号爿( x ) 的并行程度。利用式( 3 2 1 2 ) 和( 3 2 1 3 ) 可得到多项式信号的并行实现。 为分析快速傅立叶变换( f f t ) 与( 3 。2 1 2 ) 式的关系，做如下假设： 设爿( x ) ，b ( x ) ，d ( x ) 均为有限长( 长度设为n ) ， 令：( 这里j 为复数符号) 。l lm = 0 f ，2 7 r 足、 晚2 托册“肛叫二铲j 重写式( 3 2 1 1 ) 为 令孵一p ( 一，等 ， 将上式按l = 2 分解得 砸) = 艺d f e x p ( - 1 = 0 - 等) 么( 尼) = 口e x - 等 v 4 ( 七) = d ? + 畋d p 其中d 5 1 为d ( x ) 的偶数项，d f l ) 为d ( x ) 的奇数项：再用同样的方法将硝按奇 偶项分解得 d 牡d 乳暖硝2 1 9 同济大学硕： 论文第三幸摹于p i 技术的并行白适应滤波算法 其中d o ( z ) 为硝1 的偶数项，d ；2 为磁1 的奇数项；对d p 的分解同上：继续这样 的分解直到l - n ， 有 d j 叫= d j + ( ：) d 彤) 2 对d ( g = 1 ，n 一1 ) 进行同样的处理，可见这些分解恰好完成了对d ( x ) 的快 速傅立叶变换f f t 。通过上面的分析可见，f f t 实际上是一种高度并行的信号 处理方法。 3 2 2 基于多项式表示的并行结构 我们再将( 3 2 1 2 ) 式中的多项式关系引入到f i r 滤波器系统中，很显然也 能构造出类似的并行处理结构。 设其单位冲激响应为h ( n ) ，0 刀n 一1 。则其基本的输入输出关系为： 对等式两边取z 变换， 有： 其中： y ( n ) = 办( 即) ：l ：x ( 以) ( 3 2 2 1 ) j ，( z ) = h ( z ) x ( z ) n l 】，( z ) = y 。z ” n = o n 一1 何( z ) = h 。z ” n l 彳( z ) = l z ” 月= 0 间济大学硕士论文 第三帝甚于p i 技术的并行臼适成滤波算法 由( 3 2 2 2 ) 式知，信号r ( z ) 也可表示成两个多项式乘积的形式，且 y ( z ) ，日( z ) ，x ( z ) 也均为负指数多项式。 同样，这罩我们引入一个表示信号j ，例并行程度的常数k ，来重写 ( 3 2 2 2 ) 式得 其中( 4 2 2 3 ) 式相应为： 下面以二输入二输出( k = 2 ) 为例， 由式( 3 2 2 4 ) 知 即 i = 0 ，1 ，k 1 ( 3 2 2 4 ) j = 0 ，1 ，- o k 一1 ( 3 2 2 5 ) ，= 0 ，1 ，k 一1 】，= + z x = ( x 。+ z 一i ) ( 片。+ z - h i ) ( 3 2 2 6 ) = x o 日o + z - 2 x 1 日l 】+ z - i ( x o 日i + x i h o ) y o = x o h o + z 一x h k = x o 日l + x i h o 因此根据公式( 3 2 2 6 ) 我们得出了图3 2 2 1 所表示的并行结构。 假设f i r 滤波器为6 阶( n = 6 ) ， 则有 日o = h o + z - j h 2 + z - 2 h 4 h l = h i + z 一1 以+ z - 2 h 5 ( 3 2 2 7 ) 2 l ， 一 声 h 间 = 一z y 1 瑚 打一 z +ry 脚 | i 、， z j i 、l 叫 z 吖 k 川脚 = 、， z ， 叫 z “kk 川 i l 、， z ，l 一 同济大学硕i i ：论文第三帚基于p l 技术的并行白适心滤波算法 图3 2 2 1 所示并行结构采用4 个长度为3 ( n = 3 ) 的f i r 滤波器，其运算 量为4 ( n 2 ) 次乘，4 ( n 2 - - 1 ) 次加。输入序列分为奇偶序列从两路分别输 入，输出亦分为奇偶两路。 i 7 7 ，r l y l l。呆l i 7 u 一， ， l 亡习 图3 2 2 1f i r 滤波器的并行结构( 两入两出) 3 2 3 并行算法实现 针对上述两输入两输出的并行结构，设法引入自适应技术来构建其并行算 法。以l m s 算法为基础可构造出三神自适应并行算法实现。 方法一：任选其中一输出支路作自适应，而另一路权系数随之作相应变化即 可。 以图3 2 2 1 为例，选y 支路做自适应，设h 。表示h 。的系数：啊表示 h 。的系数。按分块矩阵方式表示l m s 算法有 h + ，= k 町+ 。ih d + lj = k 。，ih , j + 2 2e jb ，ix o jj = h ，+ 2 , ue x p ，= d ，- h7 o x l ，一办7 l ，石叮 其中( ) 7 表示矢量的转置，h o ，、h i ，分别为第，步迭代对应的h 。、h ，值，而 x 。，、x 。，分别为第- ，步迭代对应的、x 。值，i t 、p 、d j 分别为控制收敛因 子、第步迭代