一种基于马尔可夫转移矩阵库的寄生电容提取方法

技术领域

本发明设计一种寄生参数提取方法，尤其是设计一种基于马尔可夫转移矩 阵库的寄生电容提取方法。

背景技术

互联线寄生参数提取是当今集成电路设计中非常重要的一个环节。集成电 路设计者通过寄生参数提取工具软件得到集成电路中互联线上的电阻、电容等 寄生参数，再以此来得到该集成电路的时延和功耗，来判断其设计是否在功能、 频率和功耗方面达到要求，是否需要对原设计进行改动和优化。事实上，当今 的集成电路设计需要多次的设计或设计优化，其寄生参数提取和时延功耗分析 才能达到最初的标准，开始进行流片即芯片生产。

22纳米甚至更先进的芯片工艺流程给互联线寄生参数提取带来了巨大的挑 战，使集成电路设计者更难设计出更快速，更低功耗的芯片。这个挑战的根源 在于寄生参数提取的EDA软件：22纳米工艺流程中的硅片上的各种效应，更高 的时钟频率，更大的电路版图和三维集成电路使寄生参数提取软件在精确度、 可靠度和运行时间上都有巨大的麻烦。集成电路设计者不得不通过增加其设计 的冗余度来应对以上的问题，以保证其设计的可靠性，但这样就降低了设计出 的芯片的时钟频率，增加了芯片的功耗。

寄生参数提取的技术可大致分为两类：

1、基于场解气的技术：前者从麦克斯韦方程的某种变体形式出发来求解电 路中的电磁场，直接从中得到电路的寄生参数(电阻、电容等)，其理论清晰， 从而精确可靠，但因求解实际集成电路版图上的麦克斯韦方程需要的计算量巨 大，使其无法运用到真实的集成电路设计上；

2、基于模型匹配的技术：对预先定义的一些电路模型建立寄生参数库，然 后通过对实际的电路与模型的匹配来取得寄生参数，在实际版图的提取中有较 高的效率，从而在今工业界得到广泛的应用，但是因不可能预先定义电路版图 中所有可能出现的模型，故在新的工艺下基于模型匹配的寄生参数提取精确度 与可靠性不足。国内外占寄生参数提取市场主导地位的是Synopsys的StarRC， Cadence的QRC和Mentor的Calibre XRC，它们都是基于模型匹配提取技术的， 共占有整个寄生参数提取市场份额的95％。这些软件工具基本能够满足以前的 集成电路工艺制程下寄生参数提取的要求，但是由于22纳米或更新的工艺制程 的新的特点，其精确度、可靠性和运行效率在新的工艺制程下都不够理想。

发明内容

针对现有技术之不足，本发明提出一种基于马尔可夫转移矩阵库的寄生电 容提取方法，以提高新工艺制程下的精确度和可靠性，满足目前集成电路设计 所面临的更高要求。

本发明的基于马尔可夫转移矩阵库的寄生电容提取方法，该方法包括以下 步骤：

由模型模板和工艺参数文件构造电路模型；

由电路模型生成马尔可夫转移矩阵；

存储同一工艺制程下的各个模型的马尔可夫转移矩阵至马尔可夫转移矩阵 库中；和

利用马尔可夫转移矩阵库提取该工艺制程下的集成电路设计中的寄生电容。

其中，电路模型生成马尔可夫转移矩阵的步骤包括：

将指定的电路模型的边界划分为若干边界元，并将所有边界元离散化；

将每一个边界元都可被看作一个单独的导体，计算出由所述边界元的总电 容和该边界元与其他边界元之间的耦合电容组成的边界电容矩阵；和

转换所述边界电容矩阵为马尔可夫转移矩阵。其中，边界元包括介质边界 元和导体边界元。

其中，转换边界电容矩阵为马尔可夫转移矩阵的步骤包括：

利用公式转换边界电容矩阵为马尔可夫转移矩阵，其 中M是马尔可夫转移矩阵，是边界电容矩阵，I是与边界电容矩阵同维的单位 矩阵，是对矩阵取对角运算，是对边界电容矩阵取对角运算 后求逆。

其中，马尔可夫转移矩阵满足的充分必要条件为：所有元素都是非负的， 并且每行元素之和为1，对角元为0。

其中，利用马尔可夫转移矩阵库提取该工艺制程下的集成电路设计中的寄 生电容的步骤包括：

读入相应工艺制程的马尔可夫转移矩阵库；

读入及翻译集成电路版图并将其划分为若干个子区域；

读入相应工艺制程下每个子区域的电路模型的马尔可夫转移矩阵；和

由每个子区域的电路模型的马尔可夫转移矩阵计算出导体间的寄生电容。

其中，读入相应工艺制程下每个子区域的电路模型的马尔可夫转移矩阵的 步骤包括：

读入每个子区域的电路模型的寄生参数映射表；

读入与每个子区域的电路模型在同一工艺制程下相对应的模型介质区域的 马尔可夫转移矩阵M₀电路；和

利用模型介质区域的马尔可夫转移矩阵的微分方程，计算同一工艺制程下 任一子区域的电路模型的马尔可夫转移矩阵，

$M_1\approx M_0+\mathrm{\Delta x}\frac{{\partial M}_0}{\partial x}+\mathrm{\Delta y}\frac{{\partial M}_0}{\partial y}+\mathrm{\Delta x\Delta y}\frac{{\partial }^2{M}_0}{\partial x\partial y}+\frac{1}{2}{\mathrm{\Delta x}}^2\frac{{\partial }^2{M}_0}{{\partial x}^2}+\frac{1}{2}{\mathrm{\Delta y}}^2\frac{{\partial }^2{M}_0}{{\partial y}^2}$

其中，M₁为任一子区域的电路模型在相应工艺制程下的马尔可夫转移矩阵， M₀为与每个子区域在同一工艺制程下相对应的模型介质区域的马尔可夫转移矩 阵，x、y为相应工艺制程的寄生参数，Δx、Δy为任一子区域的电路模型在相应 工艺制程下的寄生参数变化量。

其中，由每个子区域的电路模型的马尔可夫转移矩阵计算出导体间的寄生 电容的步骤包括：

设定任意一个导体i的电位为1V，设定导体j及其它导体的电位为0V，其 中j≠i；与导体j相邻的多个边界元中的一个边界元为始发边界元；

由导体所在子区域的电路模型对应的马尔科夫转移矩阵得到始发边界元直 接或间接跳转至相邻边界元或导体的转移概率；

以足够多的次数由始发边界元出发并按照随机漫步法跳转至已知电位的边 界元或导体；

对最终跳转至导体的电位以跳转至该导体的转移概率为权重进行加权平均 从而得到始发边界元的电位；

重复上述步骤得到所有与导体j相邻的边界元的电位；

根据的原理，按照等式得到导体 j的总电荷；

当导体电位为1V时，该导体的总电荷在数值上等于该导体的总电容，或该 导体电位为0V时，该导体的总电荷在数值上等于与电位设为1V的导体之间的 耦合电容。

其中，读入及翻译集成电路版图的步骤中包括：转化集成电路版图为内部 按空间区域索引的数据格式。

其中，读入及翻译集成电路版图并将其划分为若干个子区域的步骤包括： 由集成电路设计版图和对应工艺制程下的工艺参数文件共同得到实际硅片上的 电路板图。

其中，集成电路板图为标准格式的集成电路版图。

本发明的技术效果

本发明中建立马尔可夫转移矩阵库和运用随机漫步法进行寄生参数提取的 方法都是严格基于麦克斯韦方程的变体形式，可以完全控制计算过程中的误差， 保证了精度与可靠性。本发明中一个工艺流程只建立一次马尔可夫转移矩阵库， 绝大部分的计算过程在建库时进行，而不是在使用随机漫步法计算并提取寄生 参数时进行，故能达到非常高的效率。本发明的马尔可夫转移矩阵库与模型匹 配法里面的寄生参数库不同，本发明的模型为基本的导体、介质或二者边界， 能够覆盖电路中所有可能出现的情况；而模型匹配法必须要考虑多个导体之间 的耦合关系，模型的组合复杂，无法以可实际接受的数量的模型来覆盖所有可 能出现的电路版图情况。

附图说明

图1是基于马尔可夫转移矩阵库的寄生电容提取方法的流程图；

图2是二维相邻子区域交界线上的边界元的示意图；和

图3是三维相邻子区域交界面上的边界元的示意图。

具体实施方式

下面结合附图进行详细说明。

结合图1所示的基于马尔可夫转移矩阵库的寄生电容提取方法的流程图， 本发明的基本原理是：

1、建库：将模型模板和工艺参数文件读入或输入计算机中构造成包含若干 层电介质、若干个导体的电路模型并划分指定的模型边界为若干边界元。将所 有边界元离散化，将每一个边界元视作一个单独的导体，并根据介质区域的电 磁场的线性与狄里赫利边界条件，计算出由所述边界元的总电容和该边界元与 其他边界元之间的耦合电容组成的边界电容矩阵；在得到边界电容矩阵后，按 照公式转化边界电容矩阵为马尔可夫转移矩阵，其中M是 马尔可夫转移矩阵，是边界电容矩阵，I是与边界电容矩阵同维的单位矩阵， 是对矩阵取对角运算，是对边界电容矩阵取对角运算后求逆， 并且马尔可夫转移矩阵满足的充分必要条件为：所有元素都是非负的，并且每 行元素之和为1，对角元为0；将计算所得同一工艺制程下的各个电路模型的马 尔可夫转移矩阵存储至对应该工艺制程下的马尔可夫转移矩阵库之中，并且每 一个不同的集成电路工艺只需建立一次马尔可夫转移矩阵库。

2、提取电容：读入某一工艺制程下的马尔可夫转移矩阵库，并翻译集成电 路版图为内部数据格式，并将对应的集成电路版图划分为若干个子区域，通过 读入的每个子区域的电路模型的寄生参数映射表，根据马尔可夫矩阵的微分方 程，计算出与模型介质区域相对应的子区域的马尔克夫矩阵；设定任意一个导 体i的电位为1V，设定导体j及其它导体的电位为0V，其中j≠i；与导体j相 邻的多个边界元中的一个边界元为始发边界元；由导体所在子区域的电路模型 对应的马尔科夫转移矩阵得到始发边界元直接或间接跳转至相邻边界元或导体 的转移概率；以足够多的次数由始发边界元出发并按照随机漫步法跳转至已知 电位的边界元或导体；对最终跳转至导体的电位以跳转至该导体的转移概率为 权重进行加权平均从而得到始发边界元的电位；重复上述步骤得到所有与导体j 相邻的边界元的电位；根据的原理，按照等式得到导体j的总电荷；当导体电位为1V时，该导体的总电荷在数值上 等于该导体的总电容，或该导体电位为0V时，该导体的总电荷在数值上等于与 电位设为1V的导体之间的耦合电容。

下面，详细叙述本发明的基于马尔可夫转移矩阵库的寄生电容提取方法。

由模型模板和工艺参数文件构造电路模型

将集成电路版图的模型模板和工艺参数文件的工艺特征尺寸的数据读入或 输入计算机，然后构造成包含若干层电介质，若干个导体的电路模型。

在本发明中，工艺参数文件一般由集成电路生产商提供，其是描述某个集 成电路工艺制程下导体、介质的几何与物理特征等相关参数的文件。每一个集 成电路工艺制程对应一个工艺参数文件。集成电路工艺制程是指集成电路的精 细度。精度越高，生产工艺越先进，例如28纳米工艺制程、22纳米工艺制程。 工艺制程的纳米是指IC内电路与电路之间的距离，密度愈高的IC电路设计，意 味着在同样大小面积的IC中，可以拥有密度更高、功能更复杂的电路设计。电 路模型是集成电路中的一小部分，若干电路模型可以组成整个集成电路板图。 一个电路板图包含若干层电介质和若干个导体，导体的数量一般较少。

由电路模型生成马尔可夫转移矩阵

将某个均匀或非均匀的介质区域的边界离散化，得到一组边界元。边界元 包括介质边界元和导体边界元。介质边界元分布在介质区域外围，导体边界元 即狄里赫利边界分布在区域内部或边界上。

本发明与其它寄生参数提取方法中使用的电路模型的不同之处在于，本发 明中电路模型的全部或部分边界被划分成若干边界元，作为后来在电容提取中 的转移节点。

标记介质边界元和导体边界元上的平均电势和激化电荷电量或电场强度在 边界元上的积分分别为u_d，q_d和u_m，q_m。由于电磁场的线性，无论是在均匀介 质还是非均匀介质中，[u_d u_m]和[q_d q_m]都存在线性关系，即

$\left(\begin{array}{cc}{\tilde{A}}_{\mathrm{dd}}& {\tilde{A}}_{\mathrm{dm}}\\ {\tilde{A}}_{\mathrm{md}}& {\tilde{A}}_{\mathrm{mm}}\end{array}\right)\left(\begin{array}{c}{u}_d\\ u_m\end{array}\right)=\left(\begin{array}{c}{q}_d\\ q_m\end{array}\right)---\left(1\right)$

根据狄里赫利边界条件，每个导体为等势体，导体边界元的平均电势u_d和 (激化电荷)电量q_d可由其对应导体的电势U_d与总电量Q_d替代，用高斯消元法 或类似的方法可以减小方程系数矩阵维度，得到

$\left(\begin{array}{cc}{A}_{\mathrm{dd}}& A_{\mathrm{dm}}\\ A_{\mathrm{md}}& A_{\mathrm{mm}}\end{array}\right)\left(\begin{array}{c}{U}_d\\ u_m\end{array}\right)=\left(\begin{array}{c}{Q}_d\\ q_m\end{array}\right)---\left(2\right)$

方程(2)的系数矩阵可被称为“边界电容矩阵”(Boundary capacitance matrix, BCM)，并被简记为：

边界电容矩阵就是反映导体与区域介质边界元之间相互作用的电容矩阵，其中 矩阵的对角元为总电容，矩阵的非对角元为耦合电容取相反数。对角元C_ii等于 导体i的总电容，非对角元C_ij和C_ji等于导体i和导体j的耦合电容取相反数，本发 明中导体可被看做导体的边界元。例如，假设模型中有两个导体，导体1的总 电容为C_t1，导体2的总电容为C_t2，二者的耦合电容为C_c。则此模型的边界电容 矩阵$\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)=\left(\begin{array}{cc}{C}_{t1}& -C_c\\ {-C}_c& C_{t2}\end{array}\right),$从而得到由总电容和/或耦合电容组成的边界电容矩 阵。

在物理上，每一个边界元都可被看作一个单独的导体。若边界电容矩阵中 采用常数边界元，边界电容矩阵与普通的电容矩阵在数学上具有相同的形式， 普通的电容矩阵仅表示真正导体之间电容的矩阵。先用独立的导体替换每一个 区域介质边界元，用传统的电容矩阵计算方法得到对应导体系统中的(普通) 电容矩阵C，从而得到该区域的边界电容矩阵

利用等式转换所得到的边界电容矩阵为马尔可夫转移 矩阵，其中M是马尔可夫转移矩阵，是边界电容矩阵，I是与边界电容矩阵同 维的单位矩阵，是对矩阵取对角运算，是对边界电容矩阵取 对角运算后求逆。马尔可夫转移矩阵M中的元素M_ij代表从节点i跳到节点j的概 率。

一般情况下，马尔科夫转移矩阵需要满足的充分必要条件条件为：矩阵所 有元素都是非负的，并且各行元素之和等于1，各元素用概率表示，在一定条件 下是互相转移的。而在本发明中，马尔可夫转移矩阵还必须满足的充分必要条 件为:矩阵的对角元为0。由电荷守恒可知，的每一行元素之和为0即空间中的 总电荷为0，且的对角元为正。在确定无穷远为参考0电位的情况下，激化电 荷的符号与其电位的符号相同，的非对角元为负数或0。因此，根据等式 得到的马尔可夫转移矩阵M满足本发明的三个充分必要 条件。

利用马尔可夫转移矩阵及其微分计算同一工艺制程下不同寄生参数的电 路模型生的马尔可夫转移矩阵

对于均匀的介质区域，存在边界积分方程

将介质区域的边界划分成边界元，方程(14)可离散化为

Hu＝Gq                 (5)

对边界元上的电势u取0或1，其对应的边界元电量q就是该区域电容矩阵的一 列。选取适当的边界元电势矩阵U代入方程(15)中，通过计算对应的边界元 电势Q得到该区域的边界电容矩阵即

HU＝GQ                (6)

对方程(16)两边都取变量x的偏微分，变量x是介质区域的某个参数，例如介 质的介电常数，区域内导体的长度、宽度或高度，区域本身的长度、宽度或高 度,得到

$\frac{\partial H}{\partial x}U=\frac{\partial G}{\partial x}Q+G\frac{\partial Q}{\partial x}---\left(7\right)$

在方程(17)中，和都可以通过对每一个元素求微分得到，于是也 就可以计算出来。在此基础上，通过马尔可夫转移矩阵计算模型中边界元各自 的总电容和/或耦合电容，将总电容和耦合电容组成的边界电容矩阵的类似过程， 得到边界电容矩阵的微分和马尔可夫转移矩阵的微分具体详细过程在此 不在赘述。

利用模型介质区域之间的马尔可夫转移矩阵的微分方程计算同一工艺制程 下的其他介质区域的马尔可夫转移矩阵。具体计算方法为：

若一介质区域N₀有参数x＝x₀，y＝y₀，其对应的马尔可夫转移矩阵是M₀； 另一介质区域N₁与N₀相同，除其参数x＝x₀+Δx，y＝y₀+Δy与N₀的参数x₀， y₀略有差别外。则区域N₁对应的马尔可夫转移矩阵M₁可近似为

$M_1\approx M_0+\mathrm{\Delta x}\frac{{\partial M}_0}{\partial x}+\mathrm{\Delta y}\frac{{\partial M}_0}{\partial y}+\mathrm{\Delta x\Delta y}\frac{{\partial }^2{M}_0}{\partial x\partial y}+\frac{1}{2}{\mathrm{\Delta x}}^2\frac{{\partial }^2{M}_0}{{\partial x}^2}+\frac{1}{2}{\mathrm{\Delta y}}^2\frac{{\partial }^2{M}_0}{{\partial y}^2}---\left(8\right)$

于是，本发明仅预先计算少数的介质区域模型的马尔可夫转移矩阵及其微 分，而在实际电容提取时通过公式(10)和模型介质区域N₀的马尔可夫转移矩 阵及其微分来得到实际的介质区域N₁的马尔可夫转移矩阵。

当介质区域交界面上边界元吻合时，利用马尔可夫转移矩阵提取总电容和 /或耦合电容的计算方法

假定在一个介质区域N₁中，U_j为其中导体的电势或区域边界元的电势。假 设导体i上电势为0，即U_i＝0，且导体i的边界元编号为i。那么导体i上的电量可 表示为

利用等式(4)，把通过区域边界元电势U_j为在U_i＝0时的导体i上的电量Q_i估值看 作马尔可夫随机过程中的一步。在U_i＝0时,运用随机漫步法计算导体i上的电量 Q_i，从而得到导体i到j的耦合电容，即

其中n为从导体i开始的总行走次数，而n_j为终止于导体j的次数。

使U_i＝1，U_j＝0(j≠i)，从方程(3)可以推出

即Q_i可通过上述随机过程来计算。由于其他导体电势均为0，只有跳回导体i的 行走对计算Q_i有贡献，即

其中n_i为起始于导体i且终止于导体i的随机行走次数。由此得到导体i的总电容 C_ii。

当介质区域交界面上边界元不吻合时，利用马尔可夫转移矩阵提取二维相 邻子区域的总电容和/或耦合电容的计算方法

如图2的二维相邻子区域交界线上的边界元的示意图，其中介质区域N₁与 N₂的交界面上的边界元不吻合。根据静电场持续性方程得到，

但此时并不直接出现于N₂的边界积分方程当中，需要由与N₁中的边界 元i在N₂中对应的边界元k和l的电量和来估算使用常数边界元，得 到

$Q_i^{\left(2\right)}=\frac{s_{\mathrm{ik}}}{s_k}{Q}_k^{\left(2\right)}+\frac{s_{\mathrm{il}}}{s_l}{Q}_k^{\left(2\right)}---\left(13\right)$

根据边界元i，k和l对应的方程

得到

其中，

当介质区域交界面上边界元不吻合时，利用马尔可夫转移矩阵计算三维相 邻子区域的总电容和/或耦合电容的计算方法

如图3的三维相邻子区域交界线上的边界元的示意图，其中介质区域N₁与 N₂的交界面上的边界元不吻合，两个相邻介质子区域为N₁和N₂，S_k,S_l,S_m,S_n是 图中N₂的4个边界元的面积；S_ik,S_il,S_im,S_in是N₂的四个边界元与N₁的右上角的 边界元i所重合部分的面积。

使用常数边界元，易得

$Q_i^{\left(2\right)}=\frac{s_{\mathrm{ik}}}{s_k}{Q}_k^{\left(2\right)}+\frac{s_{\mathrm{il}}}{s_l}{Q}_k^{\left(2\right)}+-\frac{s_{\mathrm{im}}}{s_m}{Q}_m^{\left(2\right)}+-\frac{s_{\mathrm{in}}}{s_n}{Q}_n^{\left(2\right)}---\left(16\right)$

再由边界元i，k，l，m和n对应的方程

得到方程

然后根据电容矩阵的定义CU＝Q，设定U为单位矩阵或某种特殊矩阵，即 假定一系列导体上的电势为0或1，计算各导体上相应的电量Q，最终得到各 导体的总电容和各导体之间的耦合电容。其具体过程类似于在介质区域交界面 上边界元吻合时，利用马尔可夫转移矩阵提取总电容和/或耦合电容的计算过程， 在此不在赘述。

本发明计算模型中的电容能够采用传统提取寄生电容的方法提取，而真正 集成电路的电容不能实现采用传统提取寄生电容的方法提取。原因在于本发明 定义的模型规模很小，能够在有效的时间内运用传统的提取寄生电容的方法得 到寄生电容，而真实的集成电路规模太大，采用传统的电容提取方法无法得到 结果。同时本发明对一个工艺制程只需要建立一次马尔可夫转移矩阵库，绝大 部分的计算过程在建库时进行，在提取寄生电容时缩短了提取时间，能达到非 常高的效率。

由马尔可夫转移矩阵计算导体间的寄生电容的详细过程

首先，读入相应工艺制程下的马尔可夫转移矩阵库。然后，将标准格式例 如LEF/DEF格式、GDSII格式等的集成电路版图读入或输入计算机，翻译并转 化该集成电路版图为内部按空间区域索引的数据结构格式以便更有效的提取寄 生参数。但在45纳米工艺制程或更新的集成电路工艺制程下，由于受到众多硅 片生产时的物理效应影响，最终硅片上的版图与设计者设计的版图会有不同， 例如导线的宽度、厚度及形状都会有变化。因此，为了保证最终硅片上的版图 与设计的集成电路版图一致，在读入设计者的电路版图后，需要根据工艺参数 文件的工艺特征考虑硅片上的效应，由集成电路设计版图和对应工艺制程下的 工艺参数文件共同得到实际硅片上的电路板图。

在获得实际硅片上的电路板图后，将一个大的数据结构形式的集成电路版 图划分成多个子版图，让多个计算机内核或多台计算机并行对各个子版图的电 路模型提取对应工艺制程下的马尔可夫转移矩阵，以便减少提取寄生电容的总 时间。所有集成电路版图的子区域都是直接或间接通过其边界相连的，因此其 对应的马尔可夫转移矩阵都可以链接在一起。任一子区域上的边界元转移到其 余边界元或导体的概率都可以通过相应的马尔可夫转移矩阵计算出来。

设定任意一个导体i的电位为1V，设定导体j及其它导体的电位为0V，其 中j≠i。与导体j相邻的多个边界元中的一个边界元为始发边界元；与所有边 界元相邻的边界元或导体标记为S。

当导体电位为1V时，该导体的总电荷在数值上等于该导体的总电容，或该 导体电位为0V时，该导体的总电荷在数值上等于与电位设为1V的导体之间的 耦合电容。

此时的边界电容矩阵已知，由得到导体j上的总电荷Q_j为 因此，若要求导体i与导体j之间的耦合电容C_ij， 需要首先得到所有与导体j相邻的边界元的电位。

由导体所在子区域的电路模型对应的马尔科夫转移矩阵 得到，始发边界元转移到其相邻边界元或导体r的转移 概率为由于始发边界元本身是在电介质中而非导体上，故始发 边界元上的总电量为0。

可由与其相邻的边界电容和电位差表示，即

将此等式变换，得到

又进一步得到

用文字来描述此等式的原理为：一边界元的电位等于其所有相邻边界元或 导体的电位的加权平均，相应权重等于此边界元到相邻边界元或导体的马尔可 夫矩阵中的转移概率

具体地，由导体所在子区域的电路模型对应的马尔科夫转移矩阵 得到始发边界元直接或间接跳转至相邻边界元或导体的 转移概率。

以始发边界元为起点，按照马尔可夫转移矩阵中的转移概率以随机漫步法 的方式跳转到其相邻的边界元或导体。本发明中随机漫步法指由起点开始以一 定的概率跳转至临近边界元，一直持续跳转直至跳转至某一个电位已知的导体 结束的方法。由始发边界元跳转到导体r，由于此时导体的电位已知，这一 次随机跳转结束；若跳转到边界元则继续跳转，直到跳转至某一个电位已知 的导体结束。

当以始发边界元为起点的出发次数足够多时，始发边界元上的电位就无限 接近于最终跳转到的每一个导体上的电位的加权平均，此权重就是最终跳转到 该导体的概率。由于设定导体i上的电位为1V，其它所有导体的电位为0V，则 始发边界元上的电位就是最终跳转到导体i上的概率。

重复上述步骤，得到所有与导体j相邻的边界元的电位。根据的原 理，按照等式得到导体j的总电荷；

当导体电位为1V时，该导体的总电荷在数值上等于该导体的总电容，或该 导体电位为0V时，该导体的总电荷在数值上等于与电位设为1V的导体之间的 耦合电容。

计算出的导体的总电容和/或耦合电容即为集成电路版图的子区域对应的 寄生电容，寄生电容包括总电容和/或耦合电容。用户或集成电路设计者可指定 总电容和耦合电容中的两者或任意一项进行提取。本发明对一个集成电路版图 设计的寄生电容提取只需要做一次，节省了提取时间，提高了提取效率。

需要注意的是，上述具体实施例是示例性的，本领域技术人员可以在本发 明公开内容的启发下想出各种解决方案，而这些解决方案也都属于本发明的公 开范围并落入本发明的保护范围之内。本领域技术人员应该明白，本发明说明 书及其附图均为说明性而并非构成对权利要求的限制。本发明的保护范围由权 利要求及其等同物限定。