您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 重汇聚扇出 >

对数字电路扇出的影响与造成困难的分析

发布时间:2019-06-15 22:15 来源:未知 编辑:admin

  30对数字电路扇出的影响和造成困难的分析 粱业伟杨志娟 (北京工业大学计算机学院 北京lo0044) (中国科学院计算技术研究所cAD开放实验室北京100080)摘要文中提出一种在Benchmark电路中存在的隐式扇出和描述实际组合电路中扇出 的一种方法。从D传送、赋值和冗余、难测故障等方面,对扇出的影响造成的困难进 行了分析,并叙述了其影响的范围和程度。 关键词扇出,数字电路,隐式扇出 分类号TP 331.2 Analyzing DigitalCircuits LIANG Yewei YANG Zhijuan (Computer Institute BeijingP01ytechnic University,Beijing 100044) SHI Yin WEI Daojheng (CAD Lab, Institute ComputingTechnology Academia Sinica, Beijing lO0080) ^hstrct In paperwe present akind implicitfan—out existing Benchmarkcircuits describefan—out practicalcombinational circuits. We analyze fan—out from aspects D—Drive,assignment value redundant,hard—test faults, extensions,levels influence.Key-ords fau out, digital circuits, iplicit fan—out 本课题得到国家自然科学基金资助 1.引言 扇出对测试码产生带来巨大的影响,而测试码产生的困难又是重汇聚的扇出带来 的。因为重汇聚的扇出可能造成冗余故障、恒值点、难测故障、……等;若是无扇出, 电路中任何~点都可以按照要求赋值;无论是用面向整个电路的(如:临界路径法), 或用面向故障的(如:单路径敏化法)任何测试码产生方法,都不会有任何困难。可以 说许多测试码产生方法都是为了解决重汇聚扇出的困难而提出来的。如:多路敏化,D 算法,PODEM,FAN算法,九值、十一值、十六值算法,……等。 虽然如此,但就我们所知:至今还没有人对扇出问题、重汇聚扇出问题作过比较系 统的专文分析,因此也没有较系统地提出一些措施来减少扇出带来的影响和困难。经过 多年研究,本文提出我们的一些看法。限于篇幅,减少扇出影响和困难的措施将由以后 的文章来叙说。 下面第二节先介绍一些本文要用到的有关术语和定义。第三节提出一种描述实际组 合电路中扇出的方法。第四节从几方面来分析扇出造成的影响和困难。擐后是结束语。 2.术语和定义 为了清晰起见,将以后要用到的术语和定义先说明一下。 定义1:多输入门:输入端数大于等于2的门。 定义2:单输入门:除非门外,仅单个输入端的门。 定义3:扇出树:具有唯一的根,至少有一片叶,且其中不含多输入门的树。 按此定义,扇出树除了其根可能为多输入门的输出外,树中只可能含扇出分支、单 输入门和非门;而且,~棵扇出树中可以有多个扇出源,即经过非门或单输入门再扇 出。少数情况下可以不含扇出源,只有一片叶子,称为“单叶树”。 扇出树的树根,除了可以为多输入门的输出外,还可能为PI(Primary Input): 如为PI,它可能由PI直接扇出,或经非门、单输入门再扇出。树根不可能为非门或单输 入门的输出.因为它们只可能在树中,这时只有它们的输入才可能是树根。 扇出树的叶片简称为“扇叶”,可能是扇出分支、非门或单输入门的输出。扇叶又 同时是多输入门的输入或P0(Primary output),而不可能是非门或单输入门的输入, 因为后者也只可能在树中。 有些扇出树除了根和扇叶外,还有内部点。但扇出树和外界的联系只经过根和扇 以后谈到的扇出都是指扇出树对外的扇出。我们规定;一个门的输出与其输入为父子关系:前者为后者的父辈。并以此定义电 路中一点(线)的先辈和后代。所以,一棵扇出树的扇叶是其根的先辈。 定义4:电路中一点的锥,由该点及其所有后代组成。 按照定义,可以对电路中各点来划分锥。各锥之间的关系除了包含和被包含外,还 有部份重叠和完全断开。“包含”和“被包含”是先辈和后代关系的一种表现。“部份 重叠”表示锥之间有公共的扇出树,“完全断开”则没有。 定义5:对多输出电路,按其各个PO来划分锥,称为PO自然分锥。 3l 32 一电路中的各Po自然分锥之间没有包含、被包含的关系;而只有部分重叠和完全断 开的关系。这是因为电路中的各个Po都是单独分别和外界连接的。 一棵扇出树的重汇聚情况,必定处于下面三种状态之一:全汇聚、部分汇聚和无汇 定义6:在整个电路中一棵扇出树的全汇聚点的条件是:该树的所有扇叶或其先辈均在该点或其后代中汇聚。 定义7:在整个电路中一棵扇出树的都份汇聚点的条件是:至少有该树的西片扇叶 或其先辈在该点汇聚。 上面的全汇聚点和部份汇聚点是对整个电路定义的,对电路中一Po自然分锥的定义 则如下: 定义8:在一P0自然分锥中一棵扇出树的全汇聚点的条件是:该树在此锥中的所有 扇叶(至少有两片)或其先辈都在该点汇聚。 定义9;在一Po自然分锥中一棵扇出树的部份汇聚点的条件是:该树在此锥中至少 有两片扇叶或其先辈在该点汇聚。 按以上定义,对多输出电路来说,一棵扇出树在整个电路有全汇聚点是很少的;而 只要该扇出树在一P0自然分锥中不是单叶树,则必有全汇聚点。 汇聚点又按汇聚的诸扇叶或其先辈至汇聚点所经路径的反相奇偶次数是否相同,分 成同极性和异极性。 定义10:一汇聚点称为某棵扇出树的同极性汇聚点,是指在该点汇聚的所有扇叶或 其先辈,从该扇出树树根到汇聚点所有路径上的奇偶极性都相同。否则,为异极性汇聚 3.一种描述实际组合电路中扇出的方法电路中除了扇出树外,余下的是“块”。 定义11;块:其输出是P0或除单叶树外扇出树的根(它也是块的根),其输入是无 扇出PI或扇叶。块内主要是多输入门;块中无扇出。 这样,块和扇出树是交替连接的。即,块的下代若还有块的话,中间必定经过扇出 树;扇出树的下代若还有扇出树的话,中间也必定经过块。块和下代块之间的关系,用 层来描述。 其输出是Po的块简称为Po块。多输出电路有n个Po,则块数n。每块有两个层号; (最小层号,最大层号)。Po块定为(o,O)层。 一块根的扇出只要有一片扇叶是最小层号为0块的输入,则该块的最小层号为1。一 般,若一块根的扇出定有一片扇叶是最小层号为i块的输入,而且它没有扇叶是最小层 号<i块的输入,则该块的最小层号为i+l。若一块根的扇出只要有一片扇叶是最大层号 为j块的输入,而且它没有扇叶是最大层号>j块的输入,则该块的最大层号为j+l。 块的最小层号说明:从该块到Po最少要经过的块数;最大层号则说明从该块到P0最 只有PI输入的块,称为“底层块”。由于实际电路中扇出的复杂性.块之间的最小层号、最大层号之间的关系也比较复 杂。图1显示的仅是比较简单的一种情况,其中(1,3)块是“底层块”。设一Po自然 分锥中有A、B两块,它们的层号分别是: (A的最小层号,A的最大层号)和(B的最小 层号,B的最大层号)。如A的最小层号<B的最小层号,A的最大层号和B的最大层号之间 的关系可以是<、=、和>。同一块的最大层号和最小层号之差的最大值,只受实际电 路特性的限制。 由于除Po块外,块根即是扇出树的根,所以,上面对块间层的描述对扇出树也适 用。即树也分层,也有相应的最小、最大层号。 应注意的是:由于电路按Po自然分锥后,有些扇出树会蜕化为单叶树,所以原来电 路中的块会被上一层的块吸收进去。 4.扇出造成的影响和困难 下面将讨论扇出影响的方面、范围、它造成影响大小的程度作一些分析。影响的方 面有:D传送;赋值;冗余故障;难测故障。扇出除显式的外,还有隐式的。显式的指 的是它有显而易见的扇出树;隐式的是说一个电路中有一条以上其逻辑功能完全相同的 线,实质上存在扇出关系但表面上看不出来。这种隐式的扇出造成的影响和困难,比显 式的大许多,所以下面要专门分析。 4.1扇出对D传送的影响 扇出对D传送的影响有两方面: 一是遇到重汇聚的扇出时,如果是同极性汇聚,可能需要多通路同时敏化;如果是 异极性汇聚,可能会相互抵消,堵塞D传送。 另一是D传送到一棵扇出树的树根时,若该树有M片扇叶,则这时D传送可能的选择就 有M种,而且这是对九值和九值以上的算法而言,否则有2。一r种。如果其扇叶经过块后 又遇到扇出树,后一棵扇出树有P片扇叶,这时D传送可能的选择数是多少?与M,P有什 么关系? Po 我们先用图1为例来说明。设原始 D在(1,3)块中,这时在该Po自然 分锥中,D传送总的所有可能选择情况 如图2所示。因为扇叶所输入的非PO块, 不论是否汇聚都是一种不同的选择,所 以可以想象成此扇叶连到所在块的块根 长出相应的扇出树。总的所有可能的选 择是按上述构成的森林的扇叶数。因此 与M,P的精确关系要用图2的方法给出。 其上限,是M,P的相乘关系。当然,这 样的上限是比较偏大的。如图2实际是 11种选择;而按上限估计应是相继块 3334 再看扇出对D传送范围的影响;仅对单棵扇出树来说,粗略地可分成从狭义和广义来看的两种。狭义地看,范围仅涉及该扇出树所到达的边。广义地看,还要从该树边的 先辈扩展开去,一直到其所有先辈的PO块,所以会穿过若干层树,层之间的扇叶数是 上限相乘关系;因此,最大层号的扇出PI,其影响也比较大;这时在每一PO自然分锥 中是否该树只有一片扇叶,是否己全汇聚?都意义不大。 如果看所有扇出对整个电路影响的范围,则除了无扇出块(块中所有输入全是无扇 出PI)和块中的无扇出锥(该锥中所有输入也全是无扇出PI)外,都是。 4.2隐式的扇出 为了进一步说明什么是隐式的扇出,下面对两种扇出情况作一比较:一种是电路中 只有以PI为根的扇出:另一种是一般的实际电路,即还有块根的扇出。 为比较起见,我们将一般实际电路转换成只有以PI为撮扇出的电路。不失一般性, 以一个PO自然分锥为例。从PO块开始,将块中非PI的扇叶全用相应扇出树根所在的块 代入,扩大了的PO块称为P0块,这样在PO“)中已没有最小层为l的块的扇叶。尤 其(1,1)块的扇叶已全部代入。再将PO块非H的扇叶全用相应扇出树根所在的块 代入,扩大了的PO(块称为PO(:)块;在PO(2)块中已没有最小层为2的块的扇 叶。……这样一直到P0(。)块为止,如这时PO(。)块中只有以Pl为根的扇出,PO(q)电 路已比原来的PO自然分锥扩大了很多。每一块根的扇出有i片扇叶,该块即有i个复制 品。这里每个复制品如有k个非PI输入,它又有k个复制品,……。所以,这里i和k之间 也是相乘关系。 图l经上述转换后如图3所示。图3中的电路虽然只有PI为根的扇出,但显然比图l耗 费器材多多了。因为它是按照层之间扇叶相乘关系展开的。问题是:这样转换后,扇出 的影响是否减少了?对测试码产生是否有利?答案是否定的。因为,除了原来(O,o) 块中的无扇出外,其它块中的无扇出现在都变成有扇出了,尤其是底层块中的扇叶数增 加得很快。再者,在非(o,o)块中原来已全汇聚的扇出树,本来其扇出有的己不应再 影响上层,而现在则不再局限于局部了。但是从图3中可以看出:Al~A2;B1~B5;Cl~CI 1分别都是逻辑功能相同的点,表面上它们之间并没有扇出树,但实质上存在扇 出关系,这就是“隐式扇出”的一种表现。从图3还町以看出:并不 定要将扇出全推 导到PI,只要局部将扇出推向PI就会有隐式的扇出。 要强调的是:这种隐式的扇出不仅仅是理论上的分析,我们考察了85Benchmark电 路,其中确实存在,而且不是个别的。它己实际上造成了测试码产生的团难。因此我们 提出:电路逻辑设计上首先就不要让它出现,如避免不了,则至少在测试码产生预处理 阶段要将它们尽可能识别出来,标志出电路中哪些线的逻辑功能是相同的。 4.3扇出对赋o、1值的影响 如果没有扇出,对一条线赋O、l值只会影响该线本身和有关的电路。有扇出后,对 扇出树中任一条线赋o、l值,首先使整棵树中的每一条线都有确定值,无论这树有多 大;其次,它还会扩展到树外,使树外的某些线也有确定值,有时甚至扩展到很大。 为了便于说明,先要介绍控制值、脱开值、选一值和全选值的概念。 对与、与非门来说,只要任一输入端赋以“o”值,其输出的值就确定了。因此, “O”值称为与、与非门的“控制值”:“l”值为它们的“脱开值”。对或、或非门来 当与、与非、或、或非门的输入端之一取“控制值”时,其输出端必须取的值称为“选一值”。当其所有输入端均取“脱开值”时,其输出端必须取的值称为“全选 有了这些概念下面讨论中便不必区分这四种门中的哪一种了。对异或、异或非门,则没有上述概念。 上面谈到,扇出树的叶必定是多输入门的输入或P0。为下面叙述方便,有: 定义12:至少有一扇出树的叶作为其输入的多输入门,称为该扇出树的“边”。 当对一扇出树先后分别赋以0和l值时,除了这些边是异或(异或非)门外,必有一 值在其输入为“控制值”,因而其输出为“选一值”。这样,对该扇出树的赋值至少在 其边的输出扩展了一步。与此相类似,对扇出树的赋值可以向外扩展到很大。为此,给 定义13:当给一扇出树赋o(1)值时,从其边开始向外,所有具有确定值的线)值的“延伸”。 所以,当对一扇出树赋o(1)值时: 一、具有“选一值”的边是延伸; 二、如“延伸”又成为下一个门的“控制值”,因而其输出为“选一值”,则又是 “延伸”; 三、如下一个多输入门的所有输入都由该树的延伸组成,而且对该门全取“脱开 值”、且输出叉取。全选值”,则它又是延伸: 四、如延伸又成为另一扇出树的根,则后一整棵树及其延伸,又是原扇出树的延 延伸除了终止在Po外,必定终止在这样一种多输入门:它的输入中至少有一个取“脱开值”,而没有一个取“控制值”;并且至少有另一输入的值未确定。 对扇出树赋o、1值时,其影响大小的基数虽然是扇出树的叶数,但其延伸和叶数并 不存在比例关系,如c7552中6线,内部线,加上根,整 裸扇出树有346条线。赋。值时,其延伸仅仅是具有选一值的边,有138条线;赋l值时, 具有选一值的边有96条线条线条线线,但赋O值时,延伸却达514条线,它连续穿过了六层树(块),一直到 PO:面赋l值时,延伸为o,即连具有选一值的边也没有。所以,延伸的多少和电路的结 构、功能有关,而与扇出树本身的大小无关。一般.电路中的控制线,尤其是总控制 线的某一个值时,延伸可能会比较大。 所以,单棵扇出树其赋o,1值时影响的范围由该树大小和延伸数决定,虽然一棵树 的延伸可能穿越若干层扇出树,但其延伸总线数,一般均远小于层之间扇叶相乘关系。 又由于最大层大的PI扇出树,其延伸穿透多层树的可能性大些,所以,一般其影响也大 从电路中所有扇出看,赋值时对整个电路影响的范围和D传送时一样,即除了无扇出块和块中的无扇出锥外,都受其赋值的影响。 4.4重汇聚的扇出导致冗余故障和难测故障 4.4.1冗余故障 可以从不同角度对冗余故障分类。冗余故障中有的要确定它很困难,有的则比 较容易。我们希望通过分类的讨论,找出哪些冗余故障溯试起来可能很困难。~个故障 要能检测出来,要满足三个条件: 1.在故障处能置成与故障相反的值: 2.从故障处到P0要形成一条能传送故障到P0的路径: 3.上面两条件能通过PI赋值得到满足。 按这三个条件可对冗余故障分类: 一、在故障处不能置成与故障相反的值;是冗余故障中一种很特殊的情况.该处 布尔值恒定,是恒值点。照理,实用电路中不应该有,但Benchmark电路却有少量出 现。它又分为下列几种: 1.A AB}AB+AB+AB型由多个门构成 4.其它原因导致布尔值恒定。 二、从故障处到Po的D传送通路被堵塞。它又分为下列几种: 三、故障能检测出的前两个条件至少表面上似乎都可满足,但实际上不能由PI赋值来满足。这种称为“综合型”。比起前面两种来,综合型难确定的可能性比较大。 此外,还有~类,如:“异或”或“异或非”门中有一组或一组以上的测试不 可能形成所导致的冗余故障。其原因可能有:其输入电路不可能形成那些测试.或虽然 能形成那些测试,但造成D传送通路堵塞。 由上述还可看出:冗余故障还可按由单个和多个扇出源造成的来分类。一般多 个扇出源的较难确定。 上述一些类型出现时,有隐式和显式两种,它们分别由隐式和显式扇出造成。 显式的由于逻辑关系表现得比较明显,如二中的几类,所以较容易判定为冗余故障。隐 式的没有像二中的明显逻辑关系,所以一般较难确定。 如果冗余故障仅涉及很少一部分电路,则成局部型的:如涉及的电路面比较 广,则称为全局型的。一般全局型的冗余故障比较难以确定。隐式的多为全局型的。多 扇出源的,其全局型的可能性较大。 冗余故障又可以按其出现位置的不同来分类。如可分成在块中和扇出树中的两 大类。每大类又可细分为三种,如:在块中的可细分为在块根、块输入和块内部三种; 扇出树中的也可分为在树根、树叶和树内三种。由于块和扇出树是交替连接的,使得除 Po块外,块根也是扇出树的根,以及块的有扇出的输入均为扇出树的叶片。这样,导致 有些冗余故障既可分类成块中,又可分类成扇出树中。而由块较易确定其为冗余故障, 我们将它都分类为块中的。这样一来,扇出树中的一大类只剩下树内的一种,其数量较 少。扇出树内冗余故障的特点是:由它扇出的所有扇支均为冗余故障。 恒值点一般出现在多输入门的输出,它可能出现在块根或内部。如出现在块内 部,且该恒定值是其上~个门的控制值,则它使上一个门的输出也为冗余故障,如它又 是它的上一个门的控制值,则……,这样直到它是其上一个门的脱开值为止,或到块 根。到达块根的和恒值点在块根的一样,如同对扇出树赋值的情况,不但整棵扇出树赋 了确定值,相应的所有延伸都有确定值。这些有确定值的线也全为恒值点。恒值点还堵 塞其它故障信号的传送,所以块中以恒值点为顶的锥内的相应故障也是冗余故障。因此 恒值点造成的冗余故障,往往不止一个。 一般同时具有多个扇出源、全局型、综台型、隐式的冗余故障,是最难确定 4.4.2难测的故障对整个电路列出它的联立布尔方程组,冗余故障是联立方程对它无解。难测故 障是联立方程组对它有唯一解或个别解。因此,从这一角度看,难测故障和冗余故障有 一定关系。难测故障也可作类似分类,即:单纯D传送困难和综合型:单扇出源和多扇 出源;局部和全局型;显式和隐式的。最难测的故障一般也同时具有多扇出源、综合 型、全局型和隐式的特征。 冗余故障和难测故障出现的范围比D传送和赋0、1值都小。它只出现在有重汇 聚的扇出处,而且一般在全汇聚点之内,所以如果某一扇出树仅有单个扇叶进入一个P0 自然分锥中,则该树的扇出不会成为这分锥中冗余故障和难测故障的原因。因为这时, 该扇叶在这分锥中已退化成为无扇出。从整个电路看,只有恒值点才有可能延伸到扇出 全汇聚点之外。冗余故障和难测故障出现的地方和导致这些故障的扇出树之间的远近, 对这些故障确定的难易程度会有一定影响,即相隔层次愈大的一般更难确定。 最后再来看一下隐式扇出造成的影响和困难。由于4.2节中所叙述的块复制, 不仅使电路中的冗余故障、难测故障等依然存在,而且使其数量和D传送、扇叶、延伸 中的边等一起按相乘关系迅速增加。所以隐式扇出造成的影响和困难要大得多。 5.结语 上面分析了扇出对D传送、赋值和冗余、难溯故障等三方面的影响和造成的困难。 影响的因素有三:单棵扇出树的叶数、相继层扇出树扇叶的乘积和扇出树的延伸数。从 中可以看出,扇出对它们所影响的范围和程度是不同的。为了便于分析,文中提出了一 种描述实际组合电路中扇出的方法,利用它较容易解释隐式扇出.对时序电路,只要切 断了反馈线,仍可以用它描述。 为了减少扇出造成的影响,可以采取许多措施,如:至少采用十值以上的算法来进 行D传送,充分发挥单个无扇出PI及扇出重汇聚的作用,预处理时对扇出树分别赋o、1 值找出其延伸,并将隐式扇出实际上变成显式的……等等。这些以后将专文探讨. 由于这是首次较系统地对扇出进行分析,所以不足之处不可避免,写出来想起抛砖 引玉的作用。 1.扬志娟,梁业伟。数字电路中的主要结构——扇出树的特点及利用。计算机辅助设计与图形学学报,1998,10(增刊):126~131。 BreuerM.A, et a1. Digital Systes Testing&Testable Design. New York:Computer Science Press, 1990. Logiccircuits under classification undetectablefaults. In: Proc. Interation8l symp.FTC,1992,263~270. IyerM.A, Abramovici Low—costredundancy identification cobinationalcircuits. In 7th international conf. 0n VLSI design,1994, 315~318.

  对数字电路扇出的影响与造成困难的分析,扇入扇出,扇出系数,bga扇出,重汇聚扇出,pads扇出,空调扇出风口,扇出限制,扇出模块,高扇入低扇出

http://womensarab.com/zhonghuijushanchu/57.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有