（电路与系统专业论文）快速小波配置方法在大规模集成电路中的应用.pdf

硕二l 二论文快速小波配置方法在大规模集成电路中的应用1 l _ g2461l 摘要 随着高速大规模集成电路( v l s i ) 发展，对电路模拟方法的计算速度和稳 定性提出了新的挑战，采用传统时间步进的积分方法求解大规模电路时，积分误 差随模拟对问增加逐渐积累，误差分布不均匀，并且很难处理电路信号的奇异性， 为此本文提出了快速小波配置方法( f a s tw a v e l e tc o l l o c a t i o nm e t h o d ) 求解电路 的微分方程。通过研究完善了算法理论，并实现了算法的自适应，最后将f w c m 方法用到大规模电路的仿真中。众所周知，大规模集成电路的发展趋势使得智能 芯片的尺寸越来越小，信号频率越来越商，造成互连线对电路的影响越来越大。 因此互连线的时域响应分析成了保证电路正常工作的必要环节。本文在对时域 f w c m 方法阐述之后，提出了在频域中使用该方法的思想，并通过对各种传输 线问题的数值求解方法的研究，提出了一种新的传输线的频域数值算法。即通过 f w c m 方法求解频域电报方程，再通过数值反拉氏变换( n i l t ) 获得电路的时 域响应。仿真结果表明，这种方法具有很高的速度和精度，与传统的频域方法相 比效率更高。 关键词：f w c m ，自适应算法，大规模集成电路。传输线，n i l t 第1 页 硕士论文快速小波配置方法在大规模集成电路中的应用 a b s t r a c t t h ea d v a n c e m e n to fv e r yl a r g es c a l ei n t e g r a t e dc i r c u i ts y s t e m s ( v l s t ) h a s b e e n c o n t i n u o u s l yc h a l l e n g i n gt o d a y s c i r c u i ts i m u l a t i o nm e t h o di nb o t h c o m p u t a t i o n a ls p e e da n ds t a b i l i t y t h ee r r o ro f t h et r a d i t i o n a lt i m e m a r c h i n gm e t h o d a c c u m u l a t e sa st h et i m ei n c r e a s e s ；a n da ts a l t l et i m e ，t h em e t h o ds u f f e r sf r o m i n e f f i c i e n c yi nt r e a t i n gs i n g u l a r i t i e s ，w h i c hi sn o r m a l t ov l s i i ta l s oh a st h ep r o b l e m o fn o n u n i f o r me r r o rd i s t r i b u t i o n t h e r e f o r e ，t h ef a s tw a v e l e tc o l l o c a t i o nm e t h o di s b r o u g h t f o r w a r di nt h i sp a p e rt os o l v et h eo r d i n a r yd i f f e r e n t i a le q u a t i o n so f t h ec i r c u i t t h e nw er e v i s ea n do p t i m i z et h i sm e t h o d ，a n da c h i e v et h ea d a p t i v et e c h n i q u e so f i t ，a t l a s tw ea p p l yi ti nv l s is i m u l a t i o n w i t ht h ed e v e l o p m e n to fv l s i ，t h es i z eo f i n t e l l i g e n tc h i pr e d u c e sw h i l et h es p e e do fs i g n a l i se n h a n c e d ，w h i c hc a u s e st h e i n t e r c o n n e c t sp r o d u c ea ni n c r e a s i n g l yi n f l u e n c et oc i r c u i t s ot h ea n a l y s i so ft h e t i m e d o m a i nr e s p o n s eo fi n t e r c o n n e c t sb e c o m e sn e c e s s a r yt oe n s u r ep r o p e rw o r k i n g o ft h ec i r c u i t d e s i g n e d a f t e rs p e c i 母i n g w h a tt i m e - d o m a i nf w c mi s ，a f r e q u e n c y d o m a i nf w c m ( f f w c m ) i s s e t f o r t h b yi n v e s t i g a t i n ge a c hk i n do f n u m e r i c a lc a l c u l a t i n gm e t h o d sd e a l i n g 、v i t ht r a n s m i s s i o nl i n e w ep u tf o r w a r dan e w f r e q u e n c y d o m a i nn u m e r i c a lm e t h o d ，w h i c h i st ou s ef f w c mt os o l v et o l e g r a p h e r e q u a t i o n si nf r e q u e n c yd o m a i n ，a n dt h e ng e tt h et i m ed o m a i nr e s p o n s eb yn u m e r i c a l i n v e r s el a p l a c et r a n s f o r mr n i l t ) t h er e s u l t ss h o wi t sa c c u r a c ya n de f f i c i e n c ya s w e l 】 k e yw o r d s ：f w c m ，a d a p t i v et e c h n i q u e s ，v l s i ，t r a n s m i s s i o n ，n i l t 第1 i 页 硕士论文快速小波配置方法在大规模集成电路中的应用 1 1 背景介绍 第一章绪论 集成电路工艺水平已步入超亚米，向电路模拟提出了新的挑战，一方面， 电路的规模越来越大，从布图或封装中提取的电路模型的元件个数已达到 1 0 4 1 0 5 量级，另一方面，电路中信号频率越来越高，已经超过了1 g h z ，如此快 速变化的信号，造成了时域信号的奇异性。传统的s p i c e 模拟工具，采用时间步 进的积分方法求解电路的节点电压方程，积分误差随模拟时间增加逐渐积累。为 了保证较小的模拟误差，在电路模拟的初始阶段必须采用很小的积分步长从而 造成较高的计算复杂度。在模拟高速大规模互连线电路时，为处理电路信号的奇 异性，并保证较高的模拟精度，积分步长必须进一步减小，这使得s p i c e 模拟方 法不适用于求解大规模电路，为此人们正努力寻找新的方法来求解大规模电路。 1 9 9 9 年，d i a nz h o u 教授和w e ic a i 教授提出了一种新的用于求解带有边界 值的常微分方程组( o r d i n a r yd i f f e r e n t i a le q u a t i o n s ，o d e s ) 和偏微分方程组 ( p a r t i a ld i f f e r e n t i a le q u a t i o n s ，p d e s ) 的数值配置方法，这一基于小波分析的算 法就是所谓的时域快速小波配置方法( t i m e d o m a i nf a s tw a v e l e tc o l l o c a t i o n m e t h o d ，以下简称t f w c m ) 【l 】，此方法很快便被应用到电路模拟中。该算法 的优点很多，它可以有效地处理时域信号的奇异性问题。实现模拟误差在时域上 的均一分布，因雨具有较高糟度和o ( h 3 ) 的收敛速度。因此目前正在把它应用到 解决大规模电路模拟问题中。本课题就是沿此方向进行的。这种新方法开拓了电 路模拟的一个新的可行方向，具有很多优越性和良好的前景。 但是t f w c m 需要对每个状态变量进行小波展开，因此在求解大规模电路 时这算法会消耗大量的计算时间和存储空间，难以实际应用。在实际应用中， 电路设计者感兴趣的是电路的某些输出信息，并不关心电路的各状态变量的值， 而且电路的输出变量数一般也远远小于电路的状态变量数。为减少所需要求解的 未知变量数，降低计算复杂度，本文将提出频域的小波配置模拟方法 ( f r e q u e n c y - d o m a i nf a s tw a v e l e tc o l l o c a t i o nm e t h o d 了，以下简称f f w c m ) ， f f w c m 将时域状态方程转换到频域后，直接对输出变量进行小波展开，有效地 减少了所需要求解的未知变量数，使之适用于大规模电路的计算。利用小波所特 有的紧支撑性( c o m p a c ts u p p o r t ) 和多分辨率性质( m u l t i r e s o l u t i o n ) ，可以控制 在整个频域区间上误差分布，有效提高计算效率。由于小波函数及其各阶导函数 变换均具有显式解析表达式，因而电路的时域波形也可以直接从频域解析解来获 第1 页 硕士论文快速小波配置方法在大规模集成电路中的应用 得。获得频域小波近似解后，可通过数值拉氏变换得到其时域的解。 与原始f w c m 方法和其他传统电路模拟方法相比，这一方法具有下面的优 势：( a ) $ 1 j 用小波逼近和频域表示，这一方法可以很好地处理电路的奇异性。( b ) 在电路模拟过程中只需对运算电路列写电路方程，形式较为简单，并且对于所 有的小波基函数，我们可以一劳永逸的求出其各阶导数的表达式，因此对于各种 微分方程和偏微分方程可以很方便的用小波导函数展开，在求得频域解后通过时 频变换，获得电路的频域响应。( c ) 这一方法可以保证频域误差的均一分布，时域 的误差也是可以控制的。( d ) 算法的时间复杂度明显优于时域方法的复杂度0 ( l 妒) 。( e ) 基于函数小波展开的多分辨率特性，以及小波基函数的紧支撑性，算 法可以用自适应的方式实现。 通常，电路模拟问题通过两个步骤解决：第一步为建立适当形式的电路方程 描述，主要利用k i m h o f f 的两个定律以及元件电学特性；第二步是利用数值方法 或解析方法求解前面得到的电路方程。我们主要研究电路方程的数值解法。现有 的这类方法通常分为两类：时间步进方法( t i m em a r c h i n gm e t h n d s ) 和频域方法 ( f r e q u e n c yd o m a i n m e t h o d s ) 。 时间步进是v l s i 电路模拟中最为常见的数值方法，因为在时域中可以很容 易的处理电路的非线性。其基本思想如下：最基础的电路方程是依据k i r e h o f f 电 流和电压定律，以及电路元件的电流一电压关系，对电容和电感，在时间上进行 积分和微分，得到的基本方程为常微分方程( o r d i n a r yd i f f e r e n t i a le q u a t i o n s ， o d e s ) ：在通过某种刚性稳定( s t i f f - s t a b l e ) 的数值积分算法，如逆向e u l e r 方法或 者g e a r 方法，将o d e s 变换为在各个时间步长上的一系列非线性方程组：每组 非线性方程运用n e w t o n r a p h s o n 方法，通过不断迭代进行求解。最为知名的电 路模拟软件- - s p i c e 就是基于这类方法。 频域方法的先驱工作是基于p a d e 近似的a w e 方法( a s y m p t o t i cw a v e l e t e v a l u a t i o n ) 2 3 。a w e 方法用仅包含少数主极点和留数的降阶模型来逼近系统 的l a p l a c e 域传输函数，该降阶模型可用于预估线性系统的时域响应。a w e 利用 矩匹配技术( m o m e n tm a t c h i n gt e c h n i q u e ) 在频域逼近系统的t a y l o r 展开系数来匹 配原系统，它是对线性电路带有多步阶跃和斜坡输入信号及不受限的非平衡初始 条件进行逼近的一种综合方法。有关a w e 方法的文献很多 4 】【1 3 】，该方法在 理论上已经报成熟，在过去的十年中，a w e 及其变种已经成为分析大型线性网 络的主流方法。a w e 算法中矩是由频域响应在某个频率点的t a y l o r 展开得到的， 通常选择在s = 0 处。由于截断误差，依赖于单个展开点的近似只能得到少量的优 势极点，而且只是在展开点附近有较好的精度，在包含传输线模型的网络分析中， 高频的影响会很大，少量的极点不能形成精确的波形估计。为了克服这些局限性， 第2 页 硕士论文快速小波配置方法在大规模集成电路中的应用 人们引入了复频反射( c f h ) 多端口矩匹配技术 1 4 1 1 6 。针对一些重点放在电报方 程离散化上的技术缺陷，如电路矩阵阶数会很高。不能用频率参数直接处理测定 的子网络或传输线，离散化导致的g i b b s 现象等。文献 1 7 1 1 8 利用基于合同变 换的分析方法来分析包含有电报方程描述的分布参数传输线网络，并证明了含有 分布元件的降阶系统在多点和多端口情况下能保持无源性。虽然基于p a d e 逼近 的矩匹配方法已被众多研究者作过深入研究，但是关于矩匹配方法仍然存在两个 问题：第一，通常情况下p a d e 逼近不能保证模型的稳定性，而且在已发表的论 文中很少能保持系统的无源性；第二，当矩匹配阶数很高时会产生数值病态问题。 为此，人们引入了p v l ( p a d e v i al a n c z o s ) 算法而对于多输入多输出的系统，要用 m p v l 2 0 】和s y j p v l 2 1 。这些方法在处理通常的r l c 电路时，同样存在不稳定 性问题。并且在推广到分布参数的电路中时，离散化都是不理想的，因而生成的 矩匹配模型都不很精确。为了弥补这些缺陷，学术界提出了诸如移频( f r e q u e n c y s h i m n g ) 、复频跳变( c o m p l e xf r e q u e n th o p p i n g 等技术。僵正鲡文献【1 4 1 中指出 的，这些方法大多数为启发式的算法，缺乏坚实的理论基础，计算复杂性高，而 且难以自动适应。 丽与频域法对应，直接对时域法研究的文献较少，由于时域方法的种种缺陷， 它渐渐被频域方法所替代。频域方法能获得均匀的误差分布，因为频域方法不象 时间那样具有特定的方向性。但通常情况下，所要获取的是电路的时域响应，因 而频域方法得到的结果通过反变换回到时域中去，这也启发了作者的研究思路。 随着f w c m 这种新的用于求解带有边界值的常微分方程组( o d e s ) 和偏微分 方程组( p d e s ) 的数值配置方法的诞生，传统的电路模拟方法正面临着一次革命性 的冲击。该方法被用到电路模拟中后，与以往的微分数值方法相比，具备了如前 文所说的众多优点。但f w c m 具有o ( ( m x 地3 ) 的时间复杂度，计算时间将随着 j 7 、r 和m 的增大而显著增加( 是配置点的数目，m 是电路状态变量的数目) 。然 而不幸的是：为了较高的精度，通常取的很大：而随着电路规模的增长，肌也 变得非常大。这极大地限制了f w c m 在实际的大规模电路模拟软件中的应用， 所以说该方法急待改进和完善。这就是本文所要改进的地方之一。 1 2 大规模集成电路的研究现状 在早期的电子工业中，对大多数的电路系统而言，导体间的互连线尺寸远小 于信号波长，在这种情况下，由于逻辑门和晶体管所引起的信号延迟远远大于互 连线所引起的延迟，所以，互连线通常只被看作是简单的金属导体，它仅具有电 连通的意义。这时，整个电路系统的性能主裴取决于电路的逻辑设计，只需要利 用传统的电路模拟工具就可在时域内有效地分析问题。但随着半导体材料科学与 第3 页 礤士论文快速小波配置方法在大规模集成电路中的应用 信息产业的迅猛发展，大规模集成电路及多芯片组件( m c m ) 【2 6 的系统规模越 来越大，工作速度越来越高，特征尺寸日益减小，使电路中互连线的长度逐渐变 得能于信号波长相比，互连延迟在整个电路系统中的作用随之交得越来越大。在 互连线终端将会出现较为明显的信号延迟。对于现在的大多数高速集成电路系统 而吉，互连延迟在整个系统中已占主导地位。在很大程度上影响着电路的性能指 标，严重时甚至将影响电路系统的正常工作，互连效应的影响再也不容忽视。高 速集成电路系统中的互连网络的分析和研究也因此成为保证系统正常工作的必 要环节，引起人们空前的重视。 剖析l s i ( 大规模集成电路) 和v l s i ( 超大规模集成电路) ，其中除单元电 路外，有必要将芯片内各单元电路之间，芯片的f o 接口和周边电路或其它芯片 之间按拓扑性质进行连接，此即所谓互连。互连借介质基板上的导体线条完成， 低速情况只具有电连通的意义，但当电路工作速度提高，时钟频率达到几十兆赫 兹以至1 0 0 兆赫兹以上，则脉冲信号将在芯片之间的连接线上呈现波效应，对频 率在几千兆赫兹以上的超高速集成电路( v h s i c ) ，则在芯片内的连接线中亦将 呈现此种效应。 出现波效应的原因在于信号脉冲的时间参量( 如脉冲的上升、下降和持续时 间) 已缩短至和连接线上电磁波传输时间处于同一量级。随着时钟频率的不断提 高这样的问题很容易出现这样的问题。这样就会在连接线上呈现波效应，我们应 将其作为微波传输线或分布参数电路分析高速脉冲的波传输性质，由此产生所谓 的互连效应，其具体表现为； ( 1 ) 时延 即由脉冲在线上的波传输时间而产生的波形延时，该物理量和 信号脉冲的时间参量及单元电路延时量( 如门延时) 相当。 ( 2 ) 畸变 由于连接线作为波传输线存在色散、损耗、不连续性的反射及 线间互耦，使信号脉冲通过后产生波形畸变，轻者使脉冲的上升和下降时间展宽， 重者使波形严重畸变甚至使脉冲的极性反转。 ( 3 ) 回波 由于线上的不连续性及二端口负载和线上特性阻抗的失配使脉 冲产生多次反射。 ( 4 ) 相邻线间的干扰噪声因布线密度所限，相邻连接线间具有可观的分 布耦合，造成信号因线间互耦而形成的噪声，由于波传输中的迭加性质。此种干 扰有时可达到很严重的程度。 由上可知，连接线互连效应当工作速度提高后将极为明显，通常将影响电路 的性能指标，严重时甚至导致电路不能正常工作，故需要对其给予足够的重视， 有必要探究互连效应的内在规律，并建立一套分析和计算方法，将其和l s i 及 v l s i 的总体设计裾结合，以保证电路的总体性能。 第4 页 硕士论文快速小波配置方法在大规模集成电路中的应用 在对v l s i 连接线系统进行研究和设计时已不能用常规的集成电路理论及 c a d 方法解决，而必须针对其波效应运用电磁场及微波的理论和方法。一般可 将其分为两个方面：其一为应用电磁场理论建立连接线系统的电磁模型，计算其 电磁参量以提供下一步进行电路分析时的电路基本参数；其- - a 0 用微波网络理论 ( 或分布参数电路理论) 计算连接线系统对高速脉冲信号的传输特性( 或时域响 应) 。由此而得出连接线系统的互连参量。进而和单元电路相结合进行电路系统 的设计与分析。 随着电路规模及速度的不断提高，连接线的互连效应也逐渐增强。互连效应 明显地影响电路整体的性能，目前发展硅高速电路还是砷化镓高速电路之争亦涉 及互连效应对电路速度限制这一因素。因此无论从何种角度来看，开展对互连效 应地研究对发展高速大规模集成电路级数及其实际应用都具有重要意义。作为微 波和电磁场科学，在过去较长的时期内基本上和信息系统的高频通道部分相联 系，并建立起一套频域分析体系。随着近年来信号的高速化和信号电路载体规模 的庞大化，微波和电磁场学科逐渐开始进入信号领域，连接线的互连效应即是其 体现。尽管在解决信号电路分析过程中，基本理论并未脱离出麦克斯韦的电磁理 论体系，但在发展过程中必然建立一些新的概念，并产生新的分析计算方法，使 这一相对成熟的学科产生新的活力。 综上所述，互连问题成为了大规模集成电路分析与研究的一个极其重要的方 向，它影响和制约着电路的性能。在某种意义上说互连线的研究甚至成为了高速 集成电路发展战略的一种考虑。本课题将沿着这个方向，用新的方法去探讨和研 究互连线的问题。 1 3 本文的主要工作及章节的安排 在本文中作者要作多个方面的工作，首先必须对f w c m ( 快速小波配置方 法) 进行研究，寻找时域f w c m 求解一般微分方程的算法，并在此基础上解决 实际的电路问题，即求解实际的电路方程。然后在此基础上对该算法进行改进， 实现算法的自适应，并提出所谓的频域f w c m 算法，即在频域中利用f w c m 的 方法，这也是本课题所提出的一种新的算法。其次，就是对大规模集成电路中传 输线问题的研究方法作探讨，研究时域和频域的各种算法，找到更加适合实际情 况的计算方法，由于无论频域还是时域的方法在用数值方法计算传输线问题时， 都有一个共同的思路，那就是把无法解析的电报方程进行变换。使得原来无法计 算的时空二变量的偏微分方程( p d e s ) 转换为可以用计算机求解的常微分方程 ( o d e s ) 。作者将对这些方法一一进行研究，找到传输线时域方法及频域方法与 小波算法的结合点，充分发挥f w c m 算法的优越性。最后确定一种适用的，快 第5 页 硕士论文快速小波配置方法在大规模集成电路中的应用 速的、高效的、准确的计算方法。在得出运用该频域方法求解传输线的频域解后， 需要对得到的频域解作反变换，从而得到其时域解。作者对不同的n i l t ( 数值 反拉氏变换) 进行研究，提出了一种新的所谓的基于c h e b y s h e v 展开的n i l t 变 换，该课题是国家九五的一个重点攻关项目。作者实现了该算法，并比较了他与 一般的n i l t 方法之间的优、缺点。 本文具体章节安排如下：第二章将对小波理论作简要的介绍，并对f w c m 的理论作一个系统的阐述，探讨了如何用其求解微分方程( 组) ，及其自适应算 法的实现。并结合实际电路的例子说明该方法解此类问题的优点。第三章阐述了 大规模集成电路中传输线的基本理论，探讨了求解电报方程的思路，和在时域和 频域中各类研究方法，以及如何使用f w c m 方法对传输线进行分析。第四章讨 论了n i l t 变换，提出了一种基于c h e b y s h e v 展开的新的n i l t 变换方法。通过 实例比较了各种方法的优劣，说明了该方法的有效、快速。第五章给出了本方法 的一些应用实例，并给出仿真结果；第六章得出了结论，对所作的工作进行了归 纳、总结，并指出了些不足的地方。在附录a 中提供所有小波基函数的详细 表达式。 第6 页 碾士论文快速小波配置方法在大撬辏舞成电箍中的廉用 第二章求解常微分方程的小波技术 2 1 傅立叶变换和小波变换在信号分析中的应用 现在，信号处理已经成为了当代科学技术发展的重要部分。信号处理已广泛 使用于通信( 电话与电视，数据传送) ，卫星图像的发射与分析，医学成像( b 超、c t 、核磁共振) ，等等。所有这些都涉及复杂的时问序列的分析与说明。在 应用中信号总是数字的序列，这些数值能够由测量得到，典型的方法是使用一 些记录的手段。总的来说，信号归根到底是时间的函数。信号处理的目标是准确 的分析，有效的编码，快速的传递。之后是重构信号。 为了得到最适合于给定信号的研究方法，通常把信号分为稳定的与非稳定 的。研究稳定信号的理想工具是f o u r i e r 变换，换句话说，稳定信号可分解为正 弦波的线性组合。以同样的方法，非稳定信号可以分解为小波的线性组合。非稳 定信号的研究，其中瞬变事件不能事先知道发生，需要不同于f o u d e r 分析的技 术，特别适用于非稳定信号的技术就是小波分析。它既适用于大多数具体的非稳 定信号的分析，也适用于具有分形结构的信号。 傅立叶变换一直统治着线性时不变信号处理，最主要的原因是傅立叶基所用 的正弦波e 埘是所有线性时不变算子的特征向量。若我们用来表示一个线性时 不变算子，r 为全体实数集。则该算予完全由其特征j 6 ( 妫值刻画： v o j er ，l e j “= _ j ；( 奶e 。“ ( 2 1 1 ) 设厂是系统的输入，要计算输出五 首先将，分解成正弦波( e “ 。之和： 邝) = 去f = 夕( 州“d 国 ( 2 1 2 ) 若，是能量有限信号，则由傅立叶积分理论可以证明每个正弦波e 的振幅 夕( 国) 是厂的傅立叶变换： 夕( 动= r ，( ，) e 州d t( 2 i 3 ) 若我们将上作用于式( 2 1 2 ) 中的，并利用式( 2 1 1 ) 可得： l f ( t ) = 去彤( ) ；( 咖“d ( 2 1 4 ) 第7 页 硕士论文快速小波配置方法在大规模集成电路中的应用 算子将，_ 的正弦波分量e 埘放大或缩小反奶倍，这一过程看作是，的频率滤波。 假如我们只是研究线性时不变算子，那么傅立叶变换足以处理大多数问题。 然而对瞬变信号而言，傅立叶变换便不会那么有效。在式( 2 1 3 ) 中，我们计算信 号f 与正弦波e 的内积而得到傅立叶系数。由于e “的支集为整个实轴，因此在 做内积时，积分范围是对应于时间变量的整个实轴。这使得从傅立叶变换，分析 信号厂的局部变化时很不方便。这就需要局部的时频交换，此时将用到一系列时 间与频率局部性都很好的波形对信号进行展开。不仅如此，传统的信号处理一直 特别关注时域不变算子和空间域不变算子的设计，这些算子改进了平稳信号的性 质，但对于那些瞬变信号而言。由于其信号范围比平稳信号大的多，也更加复杂， 因而寻找类似傅立叶变换的基来简化信号处理问题是毫无希望的。近些年来，不 同的变换和基一直不断地涌现出来，小波变换应运而生。 小波分析是自1 9 8 6 年以来由y m e y e r 、s m a u a t 及i d a u b e e h i e s 等的奠基工 作而迅速发展起来的一门新兴学科，它是函数逼近论中函数表示理论的突破，是 f o u r i e r 分析划时代的发展结果。它的发展历史可以追溯到1 9 0 9 年h a r r 的工作。 从现代小波分析的观点来看，在1 9 3 0 年后有许多与小波有关的新方向出现，其中 有l e v y ，l i t t l e w o o d 与p a l e y ，f r a n k l i n 及l u s i n 的工作。此后，由于第二次世界 大战的影响，没有出现什么进展性的工作。与现在的小波分析有关的主要工作是 1 9 6 0 年c a l d e r o l l 及2 0 年后1 9 8 0 年g r o s s m a r m 与m o r l e t 的研究，特别是1 9 8 6 年以后的工作，后人称为“原子分解”。就小波分析对信号的分析与再造的算法 来说，算法本身就是一种快速算法。它的计算复杂度不超过o ( n l o g n ) ，与f f t 算法快慢相当，但可以得到更多有用的信息，且精度高 2 9 】。 2 2 小波变换的基本思想 测不准原理说明函数与其傅立叶变换的能量跨度不可能同时任意小。受量子 力学启发，物理学家g a b o r 在1 9 4 6 年把基本的时频原子定义为在时频面上有最 小跨度的波形函数【2 9 。为了测量时频信息成分，他提出将信号在这些基本的波 形原子下进行分解，而且他证明这种分解密切地联系到我们对声音的敏感度。并 展示了音乐唱片的结构。g a b o r 所做的这一切充分说明了局部化时频信号处理的 重要性。也是基于此，有了窗口傅立叶变换和小波变换。 g a b o r 原子是在时间轴和频率轴同时平移一个窗口函数g 而得到： g 蚶( r ) = g ( t u ) e ” ( 2 2 1 ) 第8 甄 硕士论文快速小波配置方法在大规模集成电路中的应用 g a b o r 原孑g “的能量在时间轴上集中在以“为中心、宽度为盯，的区间上。其宽 度由度量l9 1 2 的标准偏差而得。它的傅立叶变换是将窗函数g 的傅立叶变换宫做 平移而得到，即： 。 童。f ( f ) = 謇( & ，一手) e 。”( 2 2 2 ) 因此，色f 的能量集中在以孝为中心、宽度为o a d 的区间上，吒度量了雪( 国) 的较 大值区域的大小。在时频平面( f ，国) 上。原子誊“的能量分布通常以h e i s e n b e r g 长方形表示。此长方形的中心在( “，掌) ，时间宽度为q ，而频率宽度为仃。根据 测不准原理，该长方形面积满足：仃，仃。= 1 ，当g 是高斯函数时，该长方形的 面积为最小，这时称原子謇“为g a b o r 函数。函数，的窗口傅立叶变换s 把函数 ，与每个原子空瞄联系起来： s f ( u , 善) = e f ( t ) g ：g ( f ) d f = d ( f ) g ( f 一“) e w d t ( 2 2 3 ) 这是一个类似于傅立叶积分的式子，然而所得值则是，在以“为中心的邻域的局 部值。根据p a r s e v a l 等式，我们将时间轴上的积分变成频率轴上的积分： s f ( u , 沪去e 椭喜：i ( o j ) d o j ( 2 2 4 ) 影像地震学中在探测高频信号时，假如送到地下的可调脉冲波持续时间太 长，便不能用来分辩密聚的地层结构。因此，m o r l e t 认为不能始终发送相同波长 的波，在探测高频时应该发送更短的波，这种由单个函数的伸缩得到的波叫做小 波。同窗口傅立叶变换一样，小波变换也可以度景谱成分的变化，然而这两种方 法在时频平面上的分辨率并不相同。这也是引入小波变换的目的所在。 小波函数妒是一个积分为零的函数： e g ( t ) d t = 0 ( 2 2 5 ) 对函数伸缩及平移后可得： 帆。( f ) ： y ( 三竺) ( 2 2 6 ) 函数厂在尺度s 、位置“的小波变换定义可以写成： w f ( u , s ) = d 去5 c ，+ ( 半) d ，= 去彤( 卅o ( 州曲 ( 2 2 7 ) 第9 页 硕士论文快速小波配置方法在大规模集成电路中的应用 因此，小揪w f ( u ，s ) 依赖于，( f ) 和于( ) 在帆。和驴。能量集中的时频区域上 的值。从大幅值的小波系数的位置和尺度可以很好探测到时频变化。 在时域上，眠，集中在以“为中心、宽度与s 成正比的区域内，其傅立叶变 换由式( 2 2 6 ) 来计算：矿。) = e 以驴0 国) 。其中驴为妒的傅立叶变换。为了 分析信号的相位信息，需要利用复解析小波。我们说小波式解析的，指的是在 0 时谚( 国) = 0 。 通过尺度变化，小波变换能有效地检测瞬变信号。假设小波咿是实函数，因 为小波的积分为0 ，所以小波系数w f ( u ，s ) 度量的是以”为中心、半径大小与s 成正比的任何邻域内信号，的局部变化。 2 3 小波基 我们可以构造一个小波函数y ，通过对其伸缩、平移得到函数族 卜2 古y ( 号铣梢：肌2 舻组规范正交基，其中z 为整数集 按2 伸缩的正交小波承载了信号在分辨率2 。上的变化。因而这些基的构造可与 多分辨率信号逼近联系起来。遵循这种联系，我们能导出小波基与共轭镜像滤波 器( 它用于离散多速率滤波器组中) 之间的等价性。这些滤波器组实现了一种快 速正交小波变换。对于长度为n 的信号，该交换的运算次数仅为0 ( 奶次。设计 共轭镜像滤波器还可以给出新的小波正交基类，其中包括紧支集的正则小波。在 多维情5 a - f ，l 2 ( 哟的小波基i m i ：- t 单变量函数的可分离乘积来构造。任意能量有 雕号厂在这组基 1 歹矿( 号孔m 下展开可得： ，= ( f ) ( 2 3 1 ) 我们从多分辨率逼近出发来寻找正交小波。对f l 2 ( 矗) ，小波系数的部分 和d ( ，) = y 。其实可以理解成厂在2 和2 4 上的两个逼近之差。 硕士论文快速小渡配置方法在大规模集成电路中的应用 通过在不同空间 。上的正交投影，多分辨率逼近计算出信号在不同分辨率 上的逼近。多分辨率逼近完全由一个特殊的离散滤波器所刻画，该滤波器控制着 跨分辨率的信息丢失。这些离散滤波器提供一个设计和合成正交小波基的简单过 程。在分辩率2 7 上的逼近定义为它在巧上的正交投影玮，f ，也称昂，f 为尺度 2 ，上的一个逼近。为了计算这个投影，我们必须找到 的一组规范正交基。通过 对一个称为尺度函数的单个函数做伸缩和平移来构造每个空间 的正交基。 m e y e r 与m a l l a t 系统研究了小波基的所谓多分辨率分析一般方法，并给出了 构造一个正交小波的充要条件。这些规范正交小波携幸侉着改善信号逼近的分辨率 所需要的细节。，在尺度2 ，和2 j 1 上的比逼近分另1 j 等于它们在v j 和v j 一1 上的正交 投影。我们知道，v j i 包含于v j 中。令彬是屹在蟛一1 中的正交补： = v j 1o ( 2 3 2 ) 厂在巧上的正交投影可分解为它在吩一i 和彬上的正交投影之和： ，。厂+ f ( 2 3 3 ) 补集昂。，提供了，的细节，这些细节出现在尺度2 ，上，而不出现在尺度2 ，一1 上。 由m a l l a t - m e y e r 定理可知，通过伸缩和平移小波矿来构造形的一组规范正交基。 则对于所有尺度2 ， 妒，) t 是工2 ( r ) 的一组规范正交基。 小波基的应用大多数是挖掘其可以用很少的非零小波系数去有效逼近特殊 函数类的能力。图像压缩如此，噪声去除和快速计算也是这样，故必需最优化地 进行矿的设计，以产生最多的接近零的小波系数 。如果大多数细尺度 ( 高分辨率) 的小波系数小，则函数厂不可忽略的小波系数就小。这个性质主要 依赖于，的正则性，妒的消失矩阶数和y 的支集的大小。 如果r f 。y ( f ) d f = 0 ，( o k 4 ，我们首先定义s o b o l e v 空间序( d 中的一个子空间集合。 = 编o ) ，蹿2 ( f ) ，r 1 2 ( 三一f ) ，r l ( 工一f ) )( 2 4 1 ) = s p a n o o 一l ( ，) ，( f ) ，l 一3 ( l 一，) ) 0 k s 三一4 ( 2 4 2 ) 阿0 = s p a n 妒 k q ) ，一1 s 七s ，l j 一2 ) 0 s j j 一1 ( 2 4 3 ) = o o 暇o o 一 ( 2 4 4 ) = k u ( 2 4 5 ) 第1 2 页 硕： ：论文 快速小波配鼍方法在大规模集成电路中的应用 n e e 矿o w 表示两空间的直和，s p a n 们，五，五) 表示由函数，五， 所有的线性组合构成的函数集合。其中h ，= 2 s l 。称为基插值空间( b a s e i n t e r p o l a t i o ns p a c e ) ，称为逼近空问( 印p r o x i m a t i o ns p a c e ) 。 中的函数用于处理边界值的不均匀性，即边界函数： r i ( f ) = ( 1 一f ) ：( 2 4 6 ) ，7 ：( ，) = 2 t + - 3 t + 2 + 吾。3 了4 “_ 1 ) ：+ i 1 ( ，- 2 ) ： ( 2 4 - 7 ) 吼( f ) = _ 2 ( l f )( 2 4 8 ) r 4 ( ，) = r l ( 一f )( 2 4 9 ) 其中，f ：= 夏，f - 0 。被称为截幂函数。 式( 2 4 2 ) 出现的尺度函数( s c a l i n gf u n c t i o n ) 集合中， 卧一( f ) - 钆( f ) - 2 一西1 1 f ：+ 3j 3 ( h ) ：一号( ) ：+ i 1 ( ) ： ( 2 4 1 。) 卜3 ( f ) = 钆( 一，)( 2 4 1 1 ) 被称为边界尺度函数( b o u n d a r ys c a l i n gf u n c t i o n ) 用来处理边界非均匀性。 9 0 t ( 1 ) = 9 ( f 一是) ，0 s 七s l 一4 ( 2 4 1 2 ) 称为内部尺度函数( i n t e r i o rs e a l i n gf u n c t i o n ) 。 其中：妒c d = 。o ，= 丢害( ； c t ，o d ： c z 。， 4 ( 0 称为4 阶b 样条函数( 4 t ho r d e r b - s p l i n e ) 。 边g - 子波函数包括： y p i ( f ) 2 妒( 2 。f ) ，。( f ) = l ( 2 r ) ( 2 4 1 4 ) q s n , - 3 ( f ) 2 i ( 27 ( 一f ) ) ，y j , n 1 - 2 0 ) = 0 ( 2 ( 一f ) )( 2 4 1 5 ) 其中， ( f ) 一嚣( 1 4 一f ) + - j ( ，) ) ( 2 4 1 6 ) l ( f ) = 面1 8 2 t 刚) + 去( ( f ) + ( f ) ) ) ( 2 4 1 7 ) 妒o ，一l ( r ) = 妒o + i kv o q o ) = 缈( f + 2 )( 2 4 1 8 ) 第1 3 页 硕士论文快速小波配置方法在大规模集成电路中的应用 内部子波函数为： v j , k ( f ) = 妒( 2 。，一) ， 1 s r ，一4( 2 4 1 9 ) y ( f ) = 一号妒( 2 f ) + 争p ( 2 t - 1 ) 一号伊( 2 f 一2 ) ( 2 4 2 0 ) 除此之外，将在附录a 中给出了上面介绍的所有函数的详细展开表达式。 由d a u b e c h i e s 提出的正交小波基为函数集合2 ( 曩) ，r 是整个实轴，因此对 于任意函数x ( t ) h 2 ( j ) 都可以进行一系列在逼近空间虼，上基函数的展开，且 满足k ，ch2 ( ，) 。根据以上述的小波集，我们可以得到以下结论： ( i ) v