（微电子学与固体电子学专业论文）高速电路时域和频域分析的小波方法.pdf

摘要 l f 随着集成电路技术的飞速发展，电路分析领域正面临着前所未有的挑战。电路的 规模越来越大，分布式互连电路阶数通常在1 0 4 量级。信号速度越来越快，微处理器 芯片的时钟信号上升时间已降到p s 量级。如此大规模的电路和如此高速变化的信号造 成了电路在频域和时域极强的奇异性。传统的频域及时域模拟技术在处理强奇异性电 路时遇到收敛性及计算效率上的困难。丫 、 小波分析理论在近二十年中得到了突破性的发展，并已被广泛应用于数据压缩、 信号处理、数值分析等各个领域。本文将小波分析的方法引入到高速电路的时域和频 域分析中，利用小波所特有的紧支撑性和多分辨率特性，来有效处理电路在时域和频 域的奇异性。本文的主要创新包括：( 1 ) 提出了高速电路频域分析的小波配置方法。利 用小波所特有的自适应算法，实现频域的变步长采样。与s p i c ea c 分析等频域定步 长采样方法相比，我们的方法可以有效处理频域波形的奇异性，提高了计算效率。( 2 ) 实现了原有时域快速小波配置方法中的希尔维斯特方程的有效求解，使这一时域小波 分析方法能够应用于较大规模电路模拟。与传统时域的t i m e m a r c h i n g 方法相比，我 们的时域小波分析方法在模拟在时域具有强奇异性的高速电路时，有更高的计算效率 和稳定性。与传递函数法相比，时域小波方法有更快的收敛速度和计算速度。 关键词：电路模拟，小波分析，时域分析，频域分析，状态方程 l l ， l ?l v ? a b s t r a c t a b s t r a c t t h er e m a r k a b l ee v o l u t i o no fv l s it e c h n o l o g yc h a l l e n g e sn o w a d a y sc i r c u i ta n a l y s i s t o o l s t h ec i r c u i ts c a l ei sb e c o m i n gl a r g e ra n dl a r g e r t h eo r d e ro ft h ed i s t r i b u t e d i n t e r c o n n e c tc i r c u i t si sa b o u t1 0 4 o nt h eo t h e rh a n d ，t h es i g n a ls p e e di sr e a c h i n gg h z r a n g e t h ec l o c kr i s e - t i m eo ft h em i c r o p r o c e s s o rh a sr e d u c e dt op i c o s e c o n do r d e r t h el a r g es c a l e c i r c u i ta n dt h ef a s t c h a n g i n gs i g n a ll e a dt og r e a ts i n g u l a r i t i e si nt h et i m ea n df r e q u e n c y d o m a i n t r a d i t i o n a lf r e q u e n c ya n dt i m ea n a l y s i st e c h n i q u e ss u f f e rf r o mt h ec o n v e r g e n c ea n d e f f i c i e n c yp r o b l e m sw h e nh a n d l i n gt h ec i r c u i tw i mg r e a ts i n g u l a r i t i e s r e c e n t l y ，t h ew a v e l e tt h e o r yh a sb e e nw e l ld e v e l o p e da n dw i d e l yu s e di nm a n y a p p l i c a t i o n s ，s u c ha sd a t ac o m p r e s s i o n ，s i g n a lp r o c e s s i n g ，n u m e r i c a la n a l y s i s ，e t c i nt h i s t h e s i s ，w ea p p l yt h ew a v e l e tm e t h o dt ot i m ed o m a i na n df r e q u e n c yd o m a i na n a l y s i so ft h e h i g h s p e e dc i r c u i t s t a k i n ga d v a n t a g eo ft h ec o m p a c ts u p p o r ta n dm u l t i - r e s o l u t i o no f w a v e l e t ，w ec a nh a n d l et h es i n g u l a r i t i e so ft h eh i g l l s p e e dc i r c u i t se f f i c i e n t l yi nb o t ht i m e d o m a i na n df r e q u e n c yd o m a i n t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ( 1 ) a f r e q u e n c yd o m a i nw a v e l e tc o l l o c a t i o nm e t h o di sp r o p o s e df o rh i 曲- s p e e dc i r c u i ts i m u l a t i o n t a k i n ga d v a n t a g eo ft h em u l t i r e s o l u t i o na n a l y s i so fw a v e l e tm e t h o d ，t h ec o l l o c a t i o np o i n t s ， i e t h es a m p l i n gp o i n t si nf r e q u e n c yd o m a i na r ea d a p t i v e l yc h o s e na c c o r d i n gt ot h e s i n g u l a r i t yo ft h ef r e q u e n c yr e s p o n s e i ns u c haw a y , f r e q u e n c yd o m a i nm u l t i r a t es a m p l i n g i sa c h i e v e db yw a v e l e t c o m p a r e dw i t ht h es p i c ea ca n a l y s i s ，o n rm e t h o dc a ne f f e c t i v e l y h a n d l et h es i n g u l a r i t i e si nt h ef r e q u e n c yd o m a i na n di m p r o v et h ec a l c u l a t i o ne f f i c i e n c y ( 2 ) a f a s ta l g o r i t h mf o rs o l v i n gt h es y l v e s t e re q u a t i o ni sp r o p o s e dt oe f f e c t i v e l ys i m u l a t el a r g e s c a l ec i r c u i t si nt i m ed o m a i nb yw a v e l e t s c o m p a r e dw i t ht h eo r i 百n a lf w c mm e t h o d ，t h e p r o p o s e da l g o r i t h mc a nh a n d l el a r g e - s c a l ec i r c u i t c o m p a r e dw i t ht 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 ，t h ep r o p o s e dw a v e l e tm e t h o dc a nd e a lw i t ht i m ed o m a i ns i n g u l a r i t i e s m o r ee f f i c i e n t l ya n ds t a b l y c o m p a r e dw i t ht h et r a n s f e rf u n c t i o nm e t h o d ，t h ew a v e l e tm e t h o d h a sf a s t e rc o n v e r g e n c er a t e k e y w o r d ： c i r c u i ts i m u l a t i o n ，w a v e l e ta n a l y s i s ，t i m ed o m a i na n a l y s i s ，f r e q u e n c y d o m a i na n a l y s i s ，s t a t ee q u a t i o n 第一章 绪论 第一章绪论 1 1现代集成电路技术的发展 自六十年代初第一块集成电路诞生到现在，集成电路技术已从初期的几十个元 件，很快跨越了中小规模，大规模和超大规模，直到今天g i g a s c a l e 的阶段。近二十 年来，集成电路技术的高速发展主要表现在以下三个方面： ( 1 ) 电路规模日益增大。根据m o o r e 定律，数字集成电路的规模以每1 8 个月翻一番 的速度持续增长。六十年代初期，一片集成电路只能集成几个晶体管。而现在的 奔腾m 处理器中，晶体管数就已达到2 8 0 0 万个。1 g ( 千兆) 位存储器已经问世。 目前的工艺水平与器件的基本物理极限还有相当的距离，因此可以预测芯片的集 成度仍有很大的增长空间。 ( 2 ) 工作速度不断提高。根据有关报道，八十年代初期微处理器芯片的工作频率一般 为1 m h z 左右，而当今的微处理器芯片其时钟频率可高达几个g h z 。例如，a m d 公司最近推出时钟主频1 8 g h z 的芯片，i n t e l 公司也已推出主频超过1 6 g h z 的产 品，同时i n t e l 正在研究主频约为1 0 g h z 的新一代数字芯片。 ( 3 ) 特征尺寸持续减小。近十年来，集成电路的最小特征尺寸经历了0 8 l am 、o 3 5u m 、0 1 81 - 1 n l 等一系列变化。目前，n e c 公司和t i 公司分别推出了o 1 3 u m 和0 1 u m 的工艺技术。 表1 1 给出了n a t i o n a lt e c h n o l o g y r o a d m a p t l l 在1 9 9 7 年对半导体业未来所作出的预测。 而当今集成电路的实际发展状况有些已超过了当初的预测，这充分说明集成电路技术 发展的曰新月异。 表1 - 1 国家技术指1 9 9 7 年对半导体业未来所作出的预测 y e r1 9 9 71 9 9 9 2 0 0 12 0 0 32 0 0 62 0 0 9 t e c h n o l o g y ( 啪) o 2 5o 1 8 o 1 5o 1 3o 1 00 0 7 t r a n s i s t o r s 1 1 m2 1 m4 0 m7 6 m2 0 0 m5 2 0 m o n - c h i pc l o c k ( m h z ) 7 5 01 2 0 01 4 0 01 6 0 02 0 0 02 5 0 0 a r e a ( m m 2 ) 3 0 03 4 03 8 54 3 05 2 06 2 0 w i r i n gl e v e l s 66 7777 88 9 1 2计算机辅助电路分析技术的发展 从六十年代以来，人们开始进行计算机辅助电路分析研究。现在较为常用电路分 析工具主要是建立在第二、三和四代电路分析技术基础上的。 第二代电路分析技术是基于数值积分( 或称为t i m e - m a r c h i n g ) 的方法，这类方法的 第一章绪论 基本特点是： 1 ) 根据电路拓扑结构，以节点电压方法为基础，构成描述电路特性的代数一微分 方程组。 2 ) 采用刚性稳定的隐式数值积分方法 2 1 1 3 1 ，将描述电路的代数一微分方程转化为 非线性代数方程。 3 ) 以牛顿一莱夫森方法为基础，将非线性代数方程转化为线性代数方程叫3 1 。 4 ) 采用稀疏矩阵技术，并用高斯消元，l u 分解等方法求解线性代数方程o 】【4 】。 当今仍被普遍使用的s p i c e 电路分析工具正是这一代电路分析技术的典型代表，它可 用来分析电路的直流，交流和瞬态特性。 但是，采用隐式数值积分方法的电路分析技术面临两个问题：一是其运行时间与 电路规模成超线性关系，其所能应用的电路规模一般只限于1 0 3 量级。二是其计算误 差在整个模拟过程中会不断积累，需要很小的迭代步长才能保证算法的收敛性f 5 】 6 】 7 1 。 第三代电路分析技术是八十年代提出了以松弛法为基础的电路分析技术嗍【9 】，其 基本思想是把一个大的n 维方程组( 线性代数方程组，非线性代数方程组和微分方程组) 解耦成几个方程，而每个方程只包含一个未知变量。松弛法将所能解决的电路规模扩 大到l o 量级。但是，由于解耦的过程必然包含了近似，所以最终的精确解要通过反 复迭代得到，而迭代的收敛性取决于初始解与真实解的接近程度。而且，松弛法在遇 到有反馈回路和寄生元件的电路时，计算速度会受到很大影响口1 。 第四代电路分析技术起源于九十年代。随着集成电路的进一步发展，电路规模的 进一步扩大，超过了1 0 5 量级。如此大规模的电路，已经无法使用原有的电路分析技 术进行直接模拟。于是，模型降阶的想法被提出，其基本思路是： 假设一个线性系统由方程( 1 - 1 ) 和( 1 2 ) 描述。 j ( f ) = 础) + b u ( t j ( 1 1 ) y ( f ) = c k 【f ) + d “o ) ( 1 2 ) 其中f 代表时间，在每一时间点t 上“o ) c ”，x ( f ) c 4 ，y o ) c 分别是输入向量，状 态变量和输出向量。矩阵彳c ”“，b c “，c c 一4 和d c ”4 为常数。系统传递函 数为： g ( s ) = d + c ( s z 一4 ) “b ( 1 3 ) 如果一个系统是极小的，则它具有数值为刀的m c m i l l a nd e g r e e 。模型降阶方法 是找到一个降阶系统使它的传递函数向0 ) 具有七 n 的m c m i l l a nd e g r e e ，同时使它保 持原系统的基本特性，即在适当意义下逼近原系统，例如保留原系统的几个主极点或 是保留原系统的几个主要特征向量或特征值。 1 9 9 0 年，采用矩匹配( m o m e n t - m a t c h i n g ) 技术，基于p a d e 近似的a w e 方法【1 0 1 被 提出。其在频域匹配被近似系统的t a y l o r 展开系数，以仅包含相当少数量主极点和 第一章绪论 留数的降阶模型来逼近线性系统的l a p l a c e 域传递函数。但是，a w e 中最初用到的 数值方法在求解高级近似时遇到了严重的数值稳定性问题，后被l a n c z o s 算法懈决， l a n c z o s 方法将原系统方程投影到两组k r y l o v 子空间上，然后进行l a n c z o s 迭代，由 于迭代包含了正交化过程，保证了数值稳定性。随着对这一技术的不断研究”2 】- 【“】，基 于矩匹配的方法相继解决了p a d e 7 近似方法产生的其他数值问题，如无源性和互易性 等，产生了较为成熟的处理大规模电路的模型降阶方法，如p v l t “】、p r i m a t “1 、e n o r 【1 q 等。这些方法被提出后，对于大规模线性电路的模拟，一般先将其降阶致1 0 3 量级以 内，然后再采用积分方法或是松弛法进行求解。 1 3高速、超深亚微米集成电路计算机模拟面临的挑战 随着集成电路工作速度不断提高，特征尺寸不断减小，对高速集成电路中半导体 互连线电路的模拟已成为一类特殊的电路模拟问题。在集成电路发展的初级阶段，互 连线仅仅起着简单的电连通作用。然而，当今集成电路生成工艺的最小尺寸已达到0 1 微米，微处理器芯片的信号上升时间已降到p s 量级，单片芯片上晶体管数目已超过4 0 0 0 万只。对于如此高速度、高集成度的晶体管进行布线连接，互连线的性能主宰着整个 芯片的性能。研究表明，高速脉冲信号由这些互连线传输时具有电磁波传输的特性， 其自身将受到一定程度的退化和变质，严重时会影响高速集成电路系统的正常工作。 因此，为了精确模拟互连线的传输线行为，必须采用分布式r l c m ( 电阻、电感、电 容、互感) 电路模型。一方面，由于芯片中互连线数目多，长度长，且互连线间相互 耦合，因此分布式互连电路规模相当庞大，电路阶数通常在1 0 4 量级，而如此大规模 的电路在频域存在极多的零点和极点，造成电路的频域波形在某些区域变化极其剧 烈，我们通常称之为奇异性。另一方面，电路内状态的快速变化造成了电路中信号的 时域波形也呈现出很大的奇异性【1 1 。在1 9 9 9 年于美国加州硅谷召开的a c m 物理设计 国际会议上，超深亚微米互连设计被列为2 1 世纪集成电路物理设计的十大前沿问题 之一。 对大规模电路的模拟和有效处理电路的奇异性是当今集成电路计算机模拟的两大 难题。p v l t ”】、p r i m a t “】、e n o r t “1 等模型降阶方法，基本解决由于电路方程规模太 大，无法直接求解的问题。但是降阶以后的电路，仍需使用第一代或是第二代电路分 析技术进行模拟。由于降阶后的电路保持着原电路的主要特性，其在时域与频域存在 的奇异性在降阶后仍然存在。 在频域分析中，s p i c ea c 分析，离散傅立叶变换( i d f t ：i n v e r s ed i s c r e t ef o u r i e r t r a n s f o r m ) 等方法在计算电路的频域响应时，使用的是频域采样的方法，计算每个采 样点上的频响值。对于频域奇异性很强的电路，s p i c ea c 分析必须取足够多的采样 点，来捕获电路的频域波形，这将极其耗费时间。 第一章绪论 在时域分析中，时域积分方法的计算误差在整个模拟过程中会不断积累，需要很 小的迭代步长才能保证算法的收敛性，在处理时域奇异性很强的电路时，必须把时问 步长取得很小才能得到较高的计算精度，这就会耗费大量的计算时间，而且在有些情 况下，算法可能不收敛。 本文的工作就是研究高效的数值算法，解决强奇异性的高速电路的频域和时域的 快速高精度分析问题。由于小波函数具有紧支撑性和多分辨率特点，我们将小波分析 方法应用到对高速电路的时域和频域分析上来。 1 4本文研究内容 高速集成电路通常包括线性电路( 例如互连线电路等) 及非线性电路( 例如缓冲器 晶体管电路等) ，以下我们给出线性与非线性电路的基本方程。 对线性电路而言，其状态方程与输出方程为： 蔓掣：出( f ) + b ( f )( 1 4 ) a 1 y ( f ) = c x ( t ) + d u ( t )( 1 5 ) x ( o ) = x 。( 1 6 ) 其中x ( t ) = 【x 1 ( f ) ，i f 2 ( f ) x ( f ) 】7 是维状态变量，u ( t ) = “l ( f ) ，“2 0 ) “x ( f ) 】7 是k 维激励向量，y ( t ) = 队( f ) ，y ：o ) y ，o ) r 为p 维输出变量，4 为n x n 系数矩阵，曰为 n x k 系数矩阵，c 为p x n 系数矩阵，d 为p x k 系数矩阵。工( o ) 为电路初始条件。 为便于说明，本文只限于考察单输入单输出系统，即k = p = 1 。 对非线性电路，其状态方程形如： a x ，c t _ _ _ a ) ；厂( x ( f ) ) + s u ( t ) ( 1 7 ) 其中厂( ) 是光滑的平衡的非线性函数。不失一般性，我们假设平衡点在0 ，即 ，( 0 ) = 0 。我们可以将系统在平衡点附近进行线性化处理呻1 。，( 功在0 点附近的幂级 数展开为： f ( x ) = a l z + a 2 ( j 圆功+ 4 ( x 0 x 0 x ) + ( 1 8 ) 其中a t 为厂( x ) 的j a c o b i a n 矩阵获一阶导数，a 2 为二阶导数，以此类推。圆代表k r o n e c h e r 乘。我们只取( 1 8 ) 式展开项中的第一项，则原系统就被线性化为： 皇掣：4 。x ( f ) + b “o ) ( 1 9 ) 其形式与( 1 4 ) 完全相同。 可见，对于非线性电路一般可通过线性化方法，将问题归结为线性问题来求解。 因此本文从线性方程出发，利用小波进行时域和频域分析的研究，所得到的快速算法 4 第一章 绪论 将可以应用于线性电路和非线性电路的求解，具有较广泛的应用价值。 1 5本文主要贡献 本文的主要贡献在于：( 1 ) 提出了高速电路频域分析的小波配置方法。利用小波 所特有的自适应算法，实现频域的变步长采样。与s p i c ea c 分析等频域定步长采样 方法，我们的方法可以有效处理频域波形的奇异性，提高了计算效率。( 2 ) 实现了原有 时域快速小波配置方法中的希尔维斯特方程的有效求解，使时域小波分析方法能够处 理较大规模的电路。与传统时域的t i m e m a r c h i n g 方法相比，我们的时域小波分析方 法在模拟时域上具有强奇异性的高速电路时，有更高的计算效率和稳定性。与传递函 数法相比，时域小波方法有更快的收敛速度和计算效率。 本文第二章简要介绍小波理论和在本文中将要用到的两种小波基函数。在第三章 中，我们将介绍频域的小波模拟方法，并与经典的s p i c ea c 分析及i d f t 方法进行 比较。本文第四章给出时域的小波模拟方法，并将其与s p i c e 和传递函数法进行比较。 最后，在第五章，我们给出全文工作的结论。 5 第二章小波简介 第二章小波简介 2 1小波分析简介 小波分析方法的提出，可以追溯到1 9 1 0 年h a a r 提出的小波规范正交基。1 9 8 1 年s t r o m b e r g 对h a a r 系正交基函数进行了改进，证明了小波函数的存在性。1 9 8 4 年法国地球物理学家m o r l e t 和g r o s s m a n n 在分析地震波的局部性质时，发现传 统的f o u r i e r 变换难以达到要求，因此他将小波的概念引入到信号分析中，并实 现了信号的小波分解，同时引进了以他们名字命名的g r o s s m a n n - m o r l e t 小波。 随后，理论物理学家g r o s s m a n 对m o r l e t 的这种信号按一个确定函数进行伸缩、 平移展开的可行性进行了研究，这无疑为小波分析的形成开了先河。真正的小 波热开始于1 9 8 6 年，当时m e y e r 创造性的构造出了具有一定衰减性的光滑函 数r ( x ) ，其二进尺度伸缩与二进整倍数平移构成函数空间r 伍) 的标准正交基。 继m e y e r 提出小波变换之后，l e m a r i e 和b a t t l e 又分别独立的给出了具有指数衰 减的小波函数。1 9 8 7 年，m a l l a t 巧妙的将计算机视觉领域内的多尺度分析思想 引入至0 1 j , 波分析中，提出了小波函数的构造及信号按小波变换的分解和重构。 这一研究成果成功的统一了在此之前s t r o m b e r g 、m e y e r 、l e m a r i e 和b a t t l e 提出 的具体小波函数的构造。后来，m a l l a t 又继续研究了小波变换的离散化情形， 并将相应的算法( 现今称之为m a l l a t 算法) 有效的应用于图象分解与重构。与 此同时，d a u b e c h i e s 构造了具有有限支集的正交小波基。这样，小波分析的系 统理论初步得到建立。从本质上讲，小波是构成数据集合的基本块。它的基本 特性容许我们更有效的表示数据和更快速地计算数据。简单的说，小波的有效 性体现在用少量的小波系数就能获取数据集合中的一些本质特征，因为大多数 的数据集在时间( 空间) 上和频率上具有很强的相关性，而小波具有时间一频 率局部化特性。目前，小波分析在信号处理、语音识别、地震勘测、计算机视 觉等方面都得到了广泛的应用口o l t 2 ”。 2 1 1 小波变换 小波分析是将信号投影到一组代表不同尺度和平移的正交基上，正交基的 形式为： ，。= 2 j 7 2 甲( 2 ，一k l 工后= ”，一i 01 ( 2 1 ) 并且甲g ) 满足下列条件： ( 1 ) c v = d c o o ( 2 2 ) 第二章小波简介 ( 2 ) e 甲g ) d x = 0 ( 其中、i ，0 ) 为甲g ) 傅立叶变换。对于任意厂g ) r 陋) ，i ( x ) 可以展开成为小波 基函数的线性组合 ，g ) = c 肼、l ，x ) j ，k = - - 2 3 1 ( 2 4 ) 其中小波系数q ，。由函数厂g ) 与小波基函数，。g ) 在r ) 中的内积给出，即 q 广d g ) 巧：翮d x ( 2 5 ) 小波分析的优越性来自于它的基函数具有紧支。i 生( c o m p a c ts u p p o r t ) ，而传 统的f o u r i e r 分析的基函数是全局支撑( g l o b a ls u p p o r t ) 的。在许多实际信号分析 问题中，我们所关心的是信号在局部范围中的特征。例如，图形识别中的边缘 检测关心的是信号突变部分的位置，对地震波的记录人们关心的是什么位置出 现什么样的反射波。可见，这些任务的完成不是f o u r i e r 分析力所能及的，因此 就需要借助小波分析的紧支性特点才能加以解决。 2 1 2 多分辨率分析 多分辨率分析o 讧u l t i r e s 0 1 u t i o na i l a l y s i s ) 是指将空间伍) 分解为一系列闭子 空间帆，一1 ，0 ，1 ， 直和的形式，这些子空间满足 ( 1 ) 彬n ，= o ) ；i ， ( 2 ) u = 【o ，】 ，o ( 3 ) 厂g ) 厂( 2 x ) 。 ( 2 6 ) ( 2 7 ) ( 2 8 ) 等价的，空间r 似) 亦可以分解为闭子空间e ，一，1 ，0 ，1 ，j 和的形 式，这些子空间满足 ( 1 ) 单调性：c 圪。c c 巧c ( 2 9 ) ( 2 ) 唯一性：n 巧= 0 j ；一 ( 3 ) 稠密性：u = r o ，l 】 j - 啪 ( 4 ) 可分解性：0 = 巧一，o ( 5 ) 伸缩性：，g ) f ( 2 x ) 巧。 其中，符号。代表直和。与子空间形；不同， ( 2 1 0 ) ( 2 1 1 ) r 2 1 2 ) ( 2 1 3 ) 子空间的序列是嵌套的。根据 第二章小波简介 性质( 2 6 2 1 3 ) ，r 伍) 中的每一个函数厂g ) 能够用它在中的投影p ( 厂) 非常 接近希望的逼近。但另一方面，通过减d , j ，投影只( ，) 能够具有任意小的能量。 多分辨率分析最重要的实质是当，不断减小时，只( 厂) 更大的“变化”被除去。 事实上，这些变化是逐层剥离，即按频率成分减小顺序剥离，并且存放在补子 空间中。 从以上介绍可知，小波基函数与其它函数最大的不同是具有紧支撑性和多 分辨率特性，而本文的工作就是想利用小波的这两个特性，处理高速电路频域 和时域分析中遇到的奇异性问题。以下介绍两个将在后文中用到的小波基函数 的空间构成及定义。 2 2 样条小波函数 1 9 9 6 年，美国北卡大学的w c a i 博士提出了一类收敛速度为o ( h 4 ) 的高效 样条小波基函数口2 1 。基于这类小波基函数，北卡大学的d z h o u 博士于1 9 9 9 年 成功地构造了相应的电路仿真快速算法i ”】 2 ”。 考虑s o b o l e v 空问h 2 i o ，l l ，定义以下函数子空间 ，f r 1 ( ，) ，r ：( f ) ，1 。乜一班叩：仁- 1 ) ，伊。，一( ，) _ i 砷册k 。( f ) ，。( f ) ，一c p o 一。( f ) ，。g 一讲 降j = s p a n 妒。x p ) ，一1 k 2 。一2 ，j 0 ( 2 1 4 ) r ，= r ，一l + 形，j 0 其中，函数叩。( f ) ，叩：( ，) ，i p o , - t ( ，) ，概。( ，) ，o k l - 4 j ，q o o 卜，亿一，) 和 妒眦( f ) ，- 1 k 2 。一2 ，j 0 j 的具体定义将在下文给出。符号 s p a n ，厂2 ， 表示由函数z ， ， 张成的线性子空间。 式( 2 1 4 ) q b ，函数编o ) 和玎：( ，) 用于处理边界数据的非齐次性。 r l ( ，) = ( 1 一戎 瑁：( ，) = 2 ，+ 一2 e + 吾e 一詈( 一1 x + 丢( ，一2 x 2 j 5 弘协篡= 。 亿峋 边界尺度函数为 ( f ) = 仇( ，) = 三2 一，1 ：1 1 ，3 + 詈( f 一x 一号( 一2 ) ：+ 丢( 一s x( 2 1 ，) 妒。，o ) = 仁一，) 内部尺度函数为 ( ) = 伊( ，一k ) ，0 k g l - 4 ( 2 1 8 ) 8 兰三兰 ! ：垫笪! ! 一 一 边界小波函数为 内部小波函数为 妒o ) = 吉口3 一詈( f t x + ( f 一2 r 一詈( f s ) ：+ 吉( f 一4 ) ： ( z ，) 佗2 0 ) o ) = 一蔫【1 4 妒( f + 2 ) + y o + 1 ) 】 ( f ) = 一瓢) 专) + 扣2 ) q 2 u y ，、。( ，) = y ( 2 7 ，一髟) ，1 足2 7 4 ( ，) = 一号妒眺孚妒) 一号妒( 2 t z ) ( 2 2 2 ) f 2 2 3 ) 根据以上描述，子空间巧中所有的基函数个数为n = 2 s + 1 l + 3 。 另外，对于和慨。j o 中的每一个基函数，有如下的配置点( c o l l o c a t i o n p o i n t ) 与其对应。 扣r 旷1 f o r w j f 2 2 4 ) 2 3h a a r 小波函数 h a a r 小波函数是最早提出的小波函数，也是形式最为简单的小波函数，我 们在此给出它的定义【2 0 】【2 l 】。 设l 2 是定义在区间r = 0 ，剀上的平方可积函数空间，定义以下函数子空 间： 以： 妒，。i ( ，) = 妒( 2 ，一k ) j = 0 , 1 ，2 ： i f j , k ( ，) = y ( 2 j - i ，一k ) ) j = 1 , 2 3 其中k = o ，l ，2 ，m 一1 ，m = 2 j l ，妒( ，) 为h a a r 小波尺度函数， 波函数，定义如下： r 10 蔓f 1 伊( ，) 2t o o t l l e r w i s e f 1 妒“) = - 1 【0 o s l 0 5 0 5 l o ) ，必定存在某一 q 使得信号能量在区间盼。】上满足：口y ( a + j c o ) 1 2 d c o o ) ，假设。川为空间小波基函数y 川( x ) 的系数， 如果式 c ，p 占( 3 2 5 ) 成立，则表示在小波基函数| f ，。( x ) 所覆盖的区域内，使用j 阶小波进行逼近还不能达 到误差边界要求，必须继续增j n d 波阶数；否则，表示在小波基函数y ( x ) 所覆盖的 区域内，阶小波已经能使小波逼近误差控制在误差边界之内，不必继续增加小波阶 数。 i i ) h a a r 小波 对于h a a r 小波，我们可以使用与样条小波同样的方法，来判定小波逼近的阶数 是否已达到精度要求。但是，由于在计算e 空间的小波系数时，我们采用了第二种函 数组成方式。因此，阢空间的小波系数并未直接获得。但我们可以通过已获得的y ： 空间的小波系数计算出形，空间的小波系数。 假设采用了第二种函数组成方式的y ，空间的小波系数已求得，需要求解形空间的 函数y ( ，) 的系数o y 坩，则： ，一c o r p ，2 f c o t p ，2 “l ，2 旦严 r 3 2 6 ) 其中c o 口) j , 2 t 和c b 仍，分别为巧空间的小波妒”f ( ，) 和纺，2 i + 。( ，) 的系数。具体证明，见 附录b 。 3 3误差分析 f f w c m 方法的误差来源有两种，其一是由于小波只在区间【o ，q 】上逼近 y 似+ j w ) ，将区间【q ，0 0 上的解截断造成的截断误差。二是在区间【o ，o 上进行小波 逼近所造成的逼近误差。 在实际互连电路应用中，当信号通过线性互连电路后，其频率响应在频率足够高 时会趋近于o ，因此，截断误差满足： b = 【i ( 口+ j t o ) 2 d w ( 3 2 7 ) 其中q + j w ) 为截断误差函数，s ，为某一常数。很明显，若q 寸o o ，则 第三章频域小波分析算法 以- - - ) 0 。 对于小波逼近误差，正如文献【2 2 】中所说，小波阶数越高，则逼近误差越小。而 且通过自适应算法，我们可以在整个逼近频带上保证误差的有界性。因此，逼近误差 可被限制在式( 3 2 8 ) 给出的范围内： e 。= f i k 十j , o ) 1 2 d c o s 。 ( 3 2 8 ) 其中y 茹 + ，m ) 为逼近误差函数，s 。为某一常数。根据小波理论m 1 ：若，- - - ) o o ， 则专0 。 由此可见，f f w c m 方法在整个频域上的误差为e ，+ e 。，。由帕塞瓦尔定理可 知，f f w c m 在时域的误差为： = a r i a y ( t ) 1 2d t = , f f l a r ( a + j c ) 1 2 d t o9 1 = x ( e + f 印畔) 五( s + 占q 叩，) 其中a y ( t ) 为时域误差函数，a 为某一常数。式( 3 2 9 ) 说明f f w c m 的模拟误差在时域 和频域均为可控。 3 4算法复杂度分析 由于，f f w c m 在计算小波系数时存在快速算法，其复杂度约为d ( m ) 。因此， 由3 2 1 可知，f f w c m 方法的主要计算量在于需要将m 个配置点上代a ( 3 6 ) ，对 一彳】- l b u ( s ) + x 。】进行求解，以解出原系统在这些配置点上的频域值。若采用标准 的l u 分解计算，其时间复杂度约为o ( m n 3 ) ，空间复杂度约为o ( n 2 ) 。然而，当 电路规模很大时，矩阵a 将非常稀疏( 零元的个数往往占9 0 以上) 。因此，我们可以 采用一些稀疏矩阵算法，降低复杂度。另外，配置点的个数也会影响到积分反变换的 速度。由于每个时间点上的值都需经过( 3 1 9 ) 求出，因此，假设有k 个时间点需要求 解，则从频域解获得时域解的复杂度约为o ( k m ) 。 3 5实验结果 3 5 1 与s p i c ea c 分析相比较 图3 3 是一个匹层r l c 树电路，其中包括1 8 9 个元件，状态变量个数为1 2 0 。我 们使用基于样条小波函数的f f w c m 和s p i c e 的交流小信号分析模拟这一电路的传 递函数在频域的波形。图3 4 给出了理想情况下的传递函数频域幅值波形。图3 5 和 图3 6 分别为f f w c m 方法和s p i c e 方法的模拟结果的绝对误差1 日( s ) 一磨( s ) i ( 何0 ) 为理想值，疗( s ) 为模拟值) 。其中，f f w c m 共取了4 3 5 个采样点，计算时间为1 8 2 秒，而s p i c e 算法取了6 0 0 0 个等间隔采样点，其计算时间为6 2 8 秒。图3 7 给出了 匕空间( 即旺。o w o o 彬。职0 空间) 所用到的小波配置点位置，图3 8 - - 3 1 0 给出 1 7 第三章频域小波分析算法 了、和哌空间所用到的小波配置点位置。 s e g m e n t s e g m e n tc i r c u i t o l e v e l4 二= 二二二二 p 以 fk ) (u r s 2 上l 堪、 l l 址、 l 0心g心| ： ； 图3 1 1 并行总线等效电路 我们在第一根数据线上加冲击信号作为激励，以第一根数据线输出端c o u t l 的电 压为输出变量。我们分别采用基于h a a r 小波的f f w c m 、基于样条小波的f f w c m 方法和离散傅立叶反变换方法t 2 r l ( i d f t ：i n v e r s ed i s c r e t ef o u r i e rt r a n s f o r m ) 对其进行模 拟。为了考查三种方法在处理不同规模电路时的效率，我们取了几个不同的段( s e g m e n t l 数，在模拟过程中，前两种方法在频域的误差边界相同，离散傅立叶反变换方法在频 域取了等间隔的2 0 0 0 个点。表3 1 给出了模拟结果，其中“求解时间”为获得时域解 所花的时间，“频域域模拟误差”定义为：f 1 y i ( j _ = w ) - y ( j _ c o 一) l d 。o ( 】，u ) 为理想值， fi y ( ，国) i d c o ，( _ ，) 为模拟值) ，。时域模拟误差，定义为：f ( y f ( t ) - y - ( t ) 一) 2 d t ( y ( f ) 为理想值， 【y ( f ) 2 d t y ( t ) 为模拟值) ，计算精度是以m a t l a b 精确结果作为参考。所有程序均在c p u 为p i i i 9 3 3 ，内存为5 1 2 m 的p c 机上运行。 表3 1f f w c m 模拟结果 段数 状态变 小波基采样点数求解时间频域模拟时域模拟 量数实部虚部 ( 秒)误差误差 h rf f w c m 6 8 47 6 l2 1 64 8 4 3 7 2 2 e 5o 9 5 4 0 8 0 e 3 81 5 3 样条f f w c m 3 2 73 3 52 4 74 9 1 8 4 4 3 e 一50 9 6 8 8 7 7 e 3 离散i d f f 2 0 0 02 0 0 04 9 55 0 8 5 7 7 1 e 51 0 0 1 7 5 7 e 一3 h a 盯f f w c m6 7 26 7 63 7 55 _ 3 1 2 4 6 7 e 51 0 4 6 4 1 0 e - 3 1 22 2 5 样条f f w c m 3 2 53 3 53 35 2 0 8 2 3 4 e 51 0 2 5 8 7 9 e 3 离散i d f t 2 0 0 02 0 0 09 5 95 5 4 9 9 1 7 e 51 0 9 3 1 8 1 e 3 h a a rf f w c m 6 4 4 6 3 65 6 76 4 8 8 4 6 9 e 一51 2 7 8 0 5 0 e 3 1 62 9 7 样条f f w c m 3 2 13 2 34 4 6 7 5 3 5 9 8 7 e 51 4 8 4 2 2 7 e 一3 离散i d f t 2 0 0 02 0 0 01 6 3 37 1 2 7 6 8 5 e 51 4 0 3 2 9 4 e 一3 h a a rf f w c m 6 4 4 6 7 48 4 31 0 1 2 2 4 4 e - 41 9 9 3 3 1 3 e 3 2 0 3 6 9样条f f 、w m 3 2 73 2 75 8 65 1 4 5 3 8 8 e 一51 0 1 3 5 8 7 e 3 离散i d f t 2 0 0 02 0 0 02 3 9 98 9 6 5 5 7 2 e 一51 7 6 6 0 3 5 e 3 h a a l r f c m6 4 46 5 41 1 49 7 1 2 0 5 4 e 51 9 1 2 5 5 l e 一3 2 44 4 1 样条f f w c m 3 1 1