（电气工程专业论文）集成电路多输出逻辑函数最优化技术研究.pdf

i ：海大学工程硕十学位论文 一- _ _ _ - - _ - _ _ 一 摘要 在数字集成电路设计中，逻辑综合是对逻辑函数描述的转换和优化，生成 与逻辑功能描述等价优化的逻辑结构级描述。逻辑综合的作用是在功能等价的 条件下减少电路中的元件数目，从而使电路体积减少，能耗降低，故障率下降 稳定度提高。 本文对集成电路多输出函数逻辑优化算法进行了系统深入的分析研究，研 究主要内容包含多输出逻辑函数实质蕴涵项的选取，覆盖问题的求解，以及使 覆盖无冗余。在对算法进行分析研究的基础上，对部分算法进行改进：实现了 逻辑优化结果的最小造价，降低时空复杂度。 在多输出逻辑表示的数学模型和优化策略实现的基础上，描述了怎样用 值逻辑优化软件o p l g 实现多值逻辑函数的优化方法，讨论了多输出函数的蕴涵 项扩展的实现算法，讨论了多输出函数的全域判断算法及多输出逻辑函数的无 冗余覆盖选择算法，对逻辑函数的三种求补算法进行了分析综合，并对逻辑函 数求补算法进行了部分的改进，同时对基于最小项逻辑函数优化的测试技术进 行了研究和讨论。 关键词：多输出函数、逻辑优化、算法、蕴涵项、全域、无冗余覆盖 v p 海人学工程硕上学位论文一 a b s t r a c t f o rd i g i t a li n t e g r a t ec i r c u i td e s i g n ，l o g i cs y n t h e s i si st ot r a n s f o r ma n do p t i m i z e t h el o g i cf u n c t i o n sa n dp r o d u c et h ep u r el o g i cl e v e ls t r u c t u r a l d e s c r i p t i o n i ti s a p o w e r f u lt o o lt or e d u c et h en u m b e ro fe l e m e n t so fac i r c u i tw h i l ei t sf u n c t i o n a l i t y r e m a i n sa tt h eo r i g i n a l c o n s e q u e n t l y , t h ec i r c u i tc a r lb em a d ew i t hs m a l l e rs i z ea n d w o r kw i t hl e s sp o w e rc o n s u m i n g ，l o w e rt r o u b l er a t ea n d h i g h e rs t a b i l i t y i nt h i sp a p e r ，w e s t u d yl o g i co p t i m i z a t i o na l g o r i t h mf o rm u l t i p l eo u t p u tl o g i c f u n c t i o n si ni c t os t u d ym a i nc o n t e n ti n c l u d e sc h o o s i n gt h ee s s e n t i a l i m p l i c a n to f m u l t i p l eo u t p u tl o g i cf u n c t i o n s ，a s k i n ga n ds o l v i n g t h eq u e s t i o no f l o g i cc o v e r ， a n de n a b l ec o v e r i n gi r r e d u n d a n t l y a n a l y s et h ea l g o r i t h mo fk n o w i n ga n dc a r r yo n i m p r o v e m e n tt ot h ee x i s t i n ga l g o r i t h m ；t h er e s u l tt h a tl o g i co p t i m i z e si st or e a l i z e t h em i n i m u mf a b r i c a t i o nc o s t ，r e d u c et h ec o m p l e x i t yo fs p a c e t i m e ， o nt h eb a s i so fm u l t i p l e o u t p u tm a t h e m a t i c s e sm o d e lt h a tl o g i ce x p r e s s e sa n d o p t i m i z et h et a c t i c st or e a l i z e ，w eh a v ed e s c r i b e dh o wt oo p t i m i z es o f t w a r eo p l g a n dr e a l i z et h el o g i cf u n c t i o no fm u l t i p l e v a l u ew i t lt w ov a l u el o g i co p t i m i z a t i o n m e t h o d ，d i s c u s sa l g o r i t h m so fm u l t i p l eo u t p u tf u n c t i o n si m p l i c a n th o w t oe x p a n s i o n d i s c u s s i o nj u d g et a u t o l o g ya l g o r i t h mo fm u l t i p l eo u t p u tf u n c t i o n sa n dm u l t i p l e o u t p u tf u n c t i o n si r r e d u n d a n tt o c o v e rt h ea l g o r i t h mo fc h o o s i n gw i t hm o r em o r e ， h a v eb e e na n a l y s e da n ds y n t h e s i z ea b o u tt h r e ek i n d so fa r i t h m e t i co fc o m p l e m e n ts e t f o rl o g i cf u n c t i o n ， a n dh a sc a r r i e do ns o m ei m p r o v e m e n tt ot h el o g i cf u n c t i o n c o m p l e m e n ts e ta l g o r i t h m ，t os t u d i e s i n ga n dd i s c u s s e do n t h eb a s i so ft h et e s t t e c h n o l o g yt h a tm i n i m u mi t e m so fl o g i cf u n c t i o no p t i m i z e d a tt h es a f f l et i m e k e y w o r d s ：m u l t i p l eo u t p u tf u n c t i o n ，l o g i co p t i m i z a t i o n ，a r i t h m e t i c ，i m p l i c a n t s ， t a u t o l o g y , i r r e d u n d a n tc o v e r v 海人学t 程坝卜学位论义 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 本论文使用授权说明 期：逮! ! ：! ：6 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名i 导师签名： 期：望：圭= ! ：! 上海大学工程硕士学位论文 1 1 论文背景 第一章绪论 1 1 1 课题来源 本课题是在南通大学( 原南通工学院) 自然科学基金课题“多值逻辑技术研 究”( z 2 0 0 2 1 8 ) 的基础上进行的，本课题的研究得到了江苏省自然科学基金课题 “集成电路最优化逻辑设计软件系统”( b k 2 0 0 1 1 3 0 ) 和江苏省高校自然科学基 金课题“集成电路多值逻辑最优化技术研究”( 0 3 k j b 5 2 0 1 0 3 ) 的资助。 1 1 2 研究目的和意义 随着集成技术的不断发展和集成度的迅速提高，集成电路芯片的设计工作越 来越复杂，因而急需在设计方法和设计 ：具这两方面有一个大的变革，这就是人 们经常谈论的“设计革命”。各种计算机辅助工具的涌现以及设计方法学的诞生 丁f 是为了适应这样的要求 1 3 。 当前国家正在大力推进软件和集成电路产业的发展，集成电路的核心问题是 设计，而设计的关键是要有优秀的集成电路设计软件作为开发工具，尤其要有中 幽自己知识产权的优秀集成电路设计软件。本课题一方面研究集成电路多输出逻 辑函数最优化算法和数学模型及机器的处理方法；另一方面研究实现集成电路多 输出逻辑函数最优化的软件方案。 逻辑优化是数字电路自动设计的基础，数字电路计算机辅助设计系统的发展 对计算机科学的许多领域都产生着深远的影响，越来越迫切地对高速度、高集成 度和高复杂度电路的需求，对数字系统设计自动化带来越来越大的挑战 4 8 。 而数字电路自动设计系统固有的高度复杂性，为计算机科学的理论和技术提供了 广阔的研究空间。 逻辑设计的最优化，直接影响到产品的规模和微型化程度。逻辑综合领域一+ 直是自动设计、自动解析的一个瓶颈问题，深入开展对大规模集成电路逻辑综合 理论问题的研究是非常迫切的，计算机辅助逻辑设计的发展对计算机科学的许多 领域都产生着重大的影响。 在国际上逻辑优化问题是计算机科学及相关领域中的一个持久研究热点。开 展从事逻辑综合理论和技术研究，紧跟国际研究步伐，不断地掌握、改进和进一 步研究逻辑综合的新理论和新方法，对逻辑综合技术进行不断实践和深入研究， 将关系到对国民经济、社会发展和国家安全的重大问题。 i 海人学t 程坝士学位论文 1 2 集成电路设计发展背景 1 2 1e d a 发展 电子系统( 集成电路) 设计自动化e d a ( e l e c t rc m i us y s t e md e s i 舯 a u t o m a t i o n ) 2 4 5 8 的发展，大致可分为2 个阶段，见图1 1 。 年代高层反馈计自动化 7 口年代计算帆辅助设计 图ii 7 0 年代的第一代e d a 称为计算机辅助设计c a d ( c o m p u t e ra i d e dd e s i g n ) 系 统，它以交互式图形编辑和设计规则榆查为特点，硬件采用1 6 位小型机。那时 的逻辑图输入、逻辑模拟、电路模拟与版图设计及版图验证是分别进行的，人们 需要对两者的结果进行多次的比较和修改j 能得到正确的设计。第一代c a d 系统 的引入使设计人员摆脱了繁复、易出错误的手工画图、机械刻红膜的传统方法， 大大提高了效率，因而得到了迅速的推1 。但它仍不能适应规模较火的设计项目， 而且设计周期长、费用高。有时在投片制作后发现原设计存在锗误，小得不返工 修改，其代价是昂贵的。 8 0 年代出现了第二代e d a 系统，常称为计算机辅助工程c a e ( c o m p u t e ra i d e d e n g i n e e r i n g ) 系统，它以3 2 位工作站为硬件平台。它集逻辑图输入( s e h e m a t i c e n t r y ) 、逻辑模拟、测试码生成、电路模拟、版图设计、版图验证等工具于一体， 构成了一个较完整的设计系统。工程师以输入线路图的方式丌始设计集成电路， 并在工作站上完成全部设计工作。它不仅有设计全定制电路的版图编辑工具，还 包括有门阵列、标准单元的自动设计工具和具有经过制造验证的、针对不同工艺 包括有门阵列、标准单元的自动设汁工具和具有经过制造验证的、针对不同工艺 i 海人学t 程硕= | = 学位论文 1 2 集成电路设计发展背景 1 , 2 1e d a 发展 电子系统( 集成电路) 设计自动化e d a ( e l e c t r o n i c s y s t e md e s i g n a u t o m a t i o n ) 2 4 - 5 8 的发展，大致可分为三个阶段，见图1 1 。 9 0 年代高层次设计自动化 7 0 年代计算帆辅助设计 幽ii 7 0 年代的第一代e d a 称为计算机辅助设计c a d ( c o m p u t e ra i d e dd e s i g n ) 系 统，它以交互式图形编辑和设计规则检查为特点，硬件采用1 6 位小型机。那时 的逻辑图输入、逻辑模拟、电路模拟与版图设计及版图验证是分别进行的，人们 需要对两者的结果进行多次的比较和修改才能得到正确的设计。第一代c a d 系统 的引入使设计人员摆脱了繁复、易出错误的手工画图、机械刻红膜的传统方法， 大大提高了效率，因而得到了迅速的推广。但它仍不能适应规模较大的设计项目， 而且设计周期长、费用高。有时在投片制作后发现原设计存在错误，不得不返工 修改，其代价是昂贵的。 8 0 年代出现了第二代e d a 系统，常称为计算机辅助工程c a e ( c o m p u t e ra i d e d e n g i n e e r i n g ) 系统，它以3 2 位工作站为硬件平台。它集逻辑图输入( s c h e m a t i c e n t r y ) 、逻辑模拟、测试码生成、电路模拟、版图设计、版图验证等工具于一体， 构成了一个较完整的设计系统。工程师以输入线路图的方式开始设计集成电路， 并在工作站上完成全部设计工作。它不仅有设计全定制电路的版图编辑工具，还 包括有门阵列、标准单元的自动设计工具和具有经过制造验证的、针对不同工艺 j 海人学工程硕上学位论文 的单元库。对于门阵列、标准单元等电路，系统可完成自动布局、自动布线功能， 因而大大减轻了版图设计的工作量。在c a e 统中，更重要的是引入了版图与电路 之间的一致性检查( 1 a y o u tv e r s u ss c h e m a t i c ) 工具。此工具对版图进行版图参 数提取( l p e ) 得到相应的电路图，并将此电路图与设计所依据的原电路图进行比 较，从而可发现设计是否有错。同时还将l p e 得到的版图寄生参数引入电路图， 作一次电路模拟( 通常称这一次电路模拟为“后模拟”) ，以进一步检查电路的时 序关系和速度( 在引入这些寄生参数后) 是否仍符合原设计要求。尽管这些功能的 引入保证了投片流水的一次成功率，但是一致性检查和“后模拟”仍是在设计的 最后阶段爿加以实施的，因而如果一旦发现错误，还需修改版图或修改电路，仍 需付出相当的代价( 当然可避免投片流水的损失) 。 进入9 0 年代，芯片的复杂程度越来越高，数万门以至数十万门的电路设计 的需求越来越多。单是依靠原理图输入方式已不堪承受，采用硬件描述语言 h d l ( h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 的设计方式就应运而生，设计工作从行为、 功能级开始，e d a 向设计的高层次发展。这样就出现了第三代e d a 系统，其特点 是高层次设计的自动化h l d a ( h i g hl e v e ld e s i g na u t o m a t i o n ) 。 在第三代e d a 系统中，日i 入了硬件描述语言，一般采用两种语言即v h d l 语 苦和v e r i l o gh d l 语占；此外引入了行为综合和逻辑综合工具。采用较高的抽象 层次进行设计，并按层次式方法进行管理，可大大提高处理复杂设计的能力，设 计所需的周期也大幅度缩短；综合优化工具的采用使芯片的品质如面积、速度功 耗等获得了优化，因而第三代e d a 系统迅速得到了推广应用。 硬件描述语言的优点极其突出。如对一个3 2 位的加法器，利用图形输入软 件需要输入5 0 0 至i 0 0 0 个门，工件量庞大；而利用h d l 语言只需书写一行 “彳( _ b + c ”即可。此外h d l 语言的可读性强，易于修改和发现错误。 高层次设计阶段是与具体生产技术无关的，即与工艺无关( t e c h n o l o g y i n d e p e n d e n t ) 。一个h d l 原码可以通过逻辑综合工具综合为一个现场可编程门阵 列，即f p g a 电路，也可综合成某一工艺所支持的专用集成电路，即a s i c 电路。 h d l 原码对于f p g a 和a s i c 是完全一样的，仅需更换不同的库重新进行综合。此 外，由于工艺技术的进步，需要采用更先进的工艺时，如从lum 技术改为采用 0 8um 技术时，也可利用原来所书写的h d l 原码。 由于采用了高层次设计自动化，可使设计者在正式投片流水以前多次改换电 路的结构，从而选出最佳方案。 原有的e d a 设计系统是以软件工具为核心，新代系统是一个统一的、协同 的、集成化的、以数据库为核心的系统。其结构框架( f r a m e w o r k ) 具有面向目标 的各种数据模型及数据管理系统，有一致性较好的用户界面及用户界面系统，有 1 ：海大学工程硕士学位论文 一_ h _ _ - _ _ _ h _ 一 采用图例( p a r a d i g m ) 的设计管理环境和设计管理系统。其主要特点如下： ( 1 ) 统一的数据库。数据库中存储了所有的、各种设计视窗( d e s i g n 。i e w ) 的信息e 这些设计视窗包括网表( n e tl i s t ) 、原理图( s c h e m a t i c ) 、符号图 ( s y m b o l i c ) 、掩膜图( m a s k1 a y o u t ) 、行为描述( b e h a v i o r ) 、模拟结果( s i m u l a t i o n ) 以及各种文档( d o c u m e n t a t i o n ) 等。由于各个设计视窗的数据形式和结构有很大 的差异，因而统一数据库的建立就比较复杂。数据库要确定每一设计视窗的设计 数据与另一设计视窗的设计数据之间的关系，并提供对所有工具都有用的中间结 果。各个工具可直接向数据库写入或从数据库中读出数据，消除了各工具在转换 过程中所产生的数据出错现象。 ( 2 ) 操作的协同性。利用对所有工具都有用的中间结果，可在多窗口的环境 下同时运行多个工具。例如，当版图编辑器完成了个多边形的设计，该多边形 就被存入数据库，被存入的信息对版图设计规则检查器同样有效。因此允许在版 图编辑的过程中交替地进行。 ( 3 ) 操作的协同性。利用对所有工具都有用的中间结果，可在多窗口的环境 下同时运行多个工具。例如，当版图编辑器完成了一个多边形的设计，该多边形 就被存入数据库，被存入的信息对版图设计规则检查器同样有效。因此允许在版 图编辑的过程中交替地进行版图设计规则检查。这样，就可以在设计过程中寻找 错误，而不再是等到设计完成后再进行设计规则检查，以避免整个设计过程的反 复。再如，当在逻辑窗口中对该逻辑图的某一节点进行检查时，在版图窗口可同 时看到该节点所对应的版图区域。这种协同操作的并行设计环境使设计者能同时 访问设计过程中的多种信息，并分享设计数据。 ( 4 ) 结构的开放性。新一代e d a 系统的结构框架具有一定的丌放性。通过一“ 种特定的编程语言作为界面可访问统一数据库。同时在此结构框架中可嵌入第三 者所开发的设计软件。 ( 5 ) 系统的可移植性。整个软件系统可安装到不同的硬件平台上( p l a t f o r m ) 。 这样可组成一个由不同型号工作站( w o r k s t a t i o n ) 所组成的设计系统而共享同一 设计数据。也可由低价的个人计算机p c ( p e r s o n a lc o m p u t e r ) 和高性能的工件站 共同组成一个系统。 1 2 2 集成电路设计流程 典型的设计流程从总体来讲，集成电路设计共经历3 个子过程 4 5 8 ，示 于图1 2 。 ( 1 ) 高层次综合。将系统的行为、各个组成部分的功能及其输入和输出用硬 件描述语言加以描述，然后进行行为级综合。同时通过高层次的硬件仿真进行验 证。 j ：海人学丁程硕上学位论文 ( 2 ) 逻辑综合。通过综合， 具将逻辑级行为描述转换成使用门级单元的结构 描述( 门级的结构描述称为网表描述) 。同时还要进行门级逻辑仿真和测试综合。 再厘次描地 图1 2图1 3 ( 3 ) 物理综合。将网表描述转换成版图即完成布图设计。这时对每个单元确 定其几何形状、大小及位置，确定单元间的连接关系。 详细的设计流程如图1 3 。 一般讲，设计综合被定义为两种不同的设计描述之f b j 的转换，但这里谈到的 综合是指一种将设计的行为描述转换成设计的结构描述的过程。 高层次综合也称为行为级综合( b e h a v i o r a ls y n t h e s i s ) 。它的任务是将一个 设计的行为级描述转换成寄存器传输级的结构描述。它首先翻译和分析设计的 h d l 语占描述，并在给定的一组性能、面积和功耗的条件下，确定需要哪些硬件 资源，如执行单元、存储器、控制器、总线等( 通常称这一步为分配( a l l u c a t i o n ) ， 以及确定在这一结构中各种操作的次序( 通常称之为调度( s c h e d u li n g ) ) 。同时还 可通过行为级和寄存器传输级硬件仿真进行验证。 由于实现设计的功能可能有多种硬件结构，因而高层次综合的目的是要在满 足目标和约束条件下，找到一个代价最小的硬件结构，并使设计的功能最佳。 逻辑综合是将逻辑级的行为描述转换成逻辑级的结构描述，即逻辑门的网 表。逻辑级的行为描述可以是状态转移图、有限状态机，也可以是布尔方程、真 值表或硬件描述语言。逻辑综合过程还包括一系列优化步骤，如资源共享、连接 优化和时钟分配等。优化目标是面积最小，速度最快，功耗最低或它们之间的某 种折衷。一般讲，逻辑练合分成两个阶段：与工艺无关的阶段，这时采用布尔 操作或代数操作技术来优化逻辑；工艺映象阶段，这时根据电路的性质( 如组 合型或时序型) 及采用的结构( 多层逻辑、p l o 或f p g a ) 做出具体的映象，将与一l 艺无关的描述转换成门级网表或p l d 或f p g a 的执行文件。 坶大学工程硕士学位论文 逻辑综合优化完成后，还需要进行细致的时延分析和时延优化。此外，还要 进行逻辑仿真。 逻辑仿真是保证设计f 确的关键步骤。过去通常采用软件模拟的方法，近年 来则强调硬件仿真手段，如通过p l d 或f p g a 进行仿真。 测试综合是提供自动测试图形生成a t p g ( a u t o m a t i ct e s td a t t e r n g e n e r a t i o n ) ，测试综合还可消除设计中的冗余逻辑，诊断不可测的逻辑结构， 还能自动插入可测性结构。 物理综合也称版图综合( 1 a y o u ts y n t h e s i s ) 。它的任务是将门级网表自动转 换成版图，即完成布图。 布图规划( f l o o r p l a n ) 是对设计进行物理划分，同时对设计的布局进行规划 和分析。在这一步骤中，面向物理的划分，其层次结构可以与逻辑设计时的划分 有所不同。布图规划可以估算出较为精确的互连延迟信息，预算芯片的面积以及 分析得到何处为捌挤的布线区域。布局是指将模块安置在芯片上的适当位置，并 能满足一定的目标函数。一般和局时总是要求芯片面积最小，连线总长最短和性 能最优且容易布线。布局又分为初始布局和迭代改善两个予步骤。进行初始布局 的目的是提高布局质量及减少下一步迭代改善时的迭代次数，而迭代改善是设法 加以优化的过程，它是决定布局质量的关键。 在集成电路设计领域，综合( s y n t h e s i s ) 一词是指把一个比较概念化的设计 形式转化为比较具体、比较实在的设计形式，这通常称作自顶向下的过程。其实 做任何事情，都是从抽象开始，比如订计划、作方案，再落实到具体的过程。早 期的综合靠人的脑力劳动完成，这罩所说的综合是指靠计算机完成的自动综合。 自动综合是设计自动化中自顶向下设计方法的特点之。最早出现的自动综合工 具是逻辑综合，即把逻辑真值表反映出的逻辑功能设计变为由逻辑元件组成的逻 辑图表示的具体的结构设计。随着v l s i 技术发展，设计方法的不断进步，又发 展了高层综合工具行为综合，它能把硬件的行为描述转化为结构描述。当然 在逻辑综合出现之前，已有从逻辑图到版图的转换工具自动布图，后来又有 了从电路图到版图的自动转换。因为这些也是自上而下的设计流向，所以也纳入 综合的范畴。可以晚整个自上而下的设计过程，就是由各个层次的综合工具相衔 接完成的自动过程。 逻辑综合的作用是根据一个系统逻辑功能与性能的要求，在个包含众多结 构、功能、性能均已知的逻辑元件的逻辑单元库的支持下，寻找出一个逻辑网络 结构的最佳的( 至少是较佳的) 实现方案。 这个过程主要包括两个方面的内容： ( 1 ) 逻辑结构的生成与优化。主要是进行逻辑化简与优化，达到尽可能地用 h 海人学工程硕上学位论文 较少的元件和连线形成一个逻辑网络结构( 逻辑图) ，满足系统逻辑功能的要求。 ( 2 ) 逻辑网络的性能优化。利用给定的逻辑单元库，对已生成的逻辑网络进 行元件配置，进而估算性能与成本。性能主要指芯片的速度，成本主要指芯片的 面积与功耗。速度与面积或速度与功耗是矛盾的。这步允许使用者对速度与面 积或速度与功耗互相矛盾的指标进行性能与成本的折衷，以确定合适的元件配 置，完成最终的、符合要求的逻辑网络结构。 1 3 集成电路逻辑设计研究现状 美国加里福尼亚大学伯克列分校r k b r a y t o n 9 - 1 1 与日本九州大学 r s a s a o 1 l 一3 2 最为代表，处于国际领先地位。r k b r a y t o n 教授是国际公认的 在逻辑综合设计领域的权威，多次担任过i e e et r a n s a c t i o no nc a d 的执行主编 及i c c a d ( i n t e r n a t i o n a lc o n f e r e n c eo nc o m p u t e ra i d e dd e s i g nd i g e s to f t e c h n ic a lp a p e r s ) 的大会执行主席，发表期刊论文和会议论文几百篇。t s a s a o 教授是国际公认的在逻辑综合设计多值逻辑领域的权威，多次担任国际m u t i p l e v a l u el o g i c 的执行主编及i n t e r n a t i o n a ls y m p o s i u mo nm u l t i p l e v a l u e d l o g i c 会议和a c m i e e ed e s i g na u t o m a t i o nc o n f e r e n c e 会议的大会执行主席， 发表期刊和会议论文几百篇。 目前国内在多值逻辑优化领域的研究与国际水平尚有一定的差距。国内清华 大学薛洪熙、边计年、洪先龙，浙江大学陈偕雄、严晓浪，上海交通大学林争辉， 吉林大学刘大有、孙吉贵，宁波大学吴训威，湘潭大学罗铸楷、刘任任，北京理 工大学刘明业，华南理工大学郑启伦、哈尔滨工程大学马光胜等在逻辑设计自动 化方面进行了大量的研究与应用，主要从事逻辑设计的模糊数学理论研究、逻辑 电路的高级综合( 布线、版图级) 研究、逻辑电路的加工设计的研究 3 3 3 9 ， 在逻辑电路设计多值逻辑优化领域研究的机构和人员相对较少。 本文的研究主要以r k g r a y t o n 教授和t s a s a o 教授和王波教授的研究成果 为基础，特别是t s a s a o 教授和王波教授的多输出逻辑优化领域的相关期刊和会 议论文作为参考文献。 1 4 研究内容和主要工作 在理论上对集成电路多输出逻辑优化算法作进一步研究，多输出逻辑优化研 究是对单输出二值逻辑优化研究的扩充，其应用面更广。文中所进行的内容，即 逻辑化简与优化。对此按以下步骤进行： 求补一 积项扩展成本源项一 无冗余覆盖。求补是基础，积项扩展是中 m 过程，无冗余覆盖是逻辑化简与优化的关键。 研究内容包含逻辑函数求补、多输出逻辑实质蕴涵项的选取，覆盖问题的求 l 海大学工程硕+ 学位论文 解，以及使覆盖无冗余 4 0 4 3 。分析掌握算法并对已有的算法进行改进；实现 逻辑优化的结果最小造价，降低时空复杂度。讨论多输出函数的表示方法，对怎 样用单输出2 z 值逻辑优化软件实现多输出函数的优化、展示优化结果的问题进行 研究 4 4 5 2 。 在单输出二值逻辑优化的基础上利用数学理论建立集成电路多输出逻辑最 优化数学模型和优化算法。对“集成电路多输出逻辑最优化技术研究”系统进行 总体分析，确定规模、范围、总体要求、所需的硬件环境和支撑软件、外界接1 ：3 ； 分析掌握算法并对已有的算法进行改进；以单输出二值优化程序为基础加以改进 研究进行多输出函数逻辑优化的处理；根据改进后的算法进行软件设计，对软件 进行测试。算法的研究须有理论上的证明，也需要实践的检验。对逻辑优化算法 的正确性和优化效果的验证分三步进行：先在小变量上用常规方法检验产生 随机数据，用专用测试工具检验用b e n c h m a r k 例题测试 本论文的全部研究成果可归纳如下： 详细分析了逻辑函数的几种求补算法，并对其时空复杂度及 适用环境等进行了综合的比较分析。 针对单边函数求补、基于最小项求补、递归裂变求补通过编 程实现其算法并对部分算法进行了改进。 综合研究了多输出函数的蕴涵项扩展、全域判断及无冗余覆 盖技术选择算法，设计和实现了多输出逻辑优化软件o p l g 。 基于二值逻辑进行多值逻辑优化的技术研究，并对逻辑函数 优化的结果进行测试。 1 5 本论文章节安排 第二章主要介绍集成电路逻辑设计的基本概念，包括逻辑函数的多维体表 示、真值表表示、三种输入集合和逻辑多维空间、多维体与命尔表达式、逻辑函 数的覆盖、组合逻辑的综合等基本概念。 第三章主要对逻辑函数的补集算法进行了研究，详细分析了逻辑函数的几种 求补算法，针对单边函数求补、基于最小项求补、递归裂变求补算法进行了程序 设计与实现，并对其时空复杂度及适用环境等进行了综合的比较分析，并设计了 一个基于最小项求补的改进算法。 第四章主要对多输出逻辑函数的无冗余覆盖技术进行了研究，系统综合的研 究了多输出逻辑函数的蕴涵项扩展、全域判断及无冗余覆盖技术选择算法，设计 和实现了多输出逻辑优化软件o p i 。g 。在基于二值逻辑优化技术的基础上对多值 逻辑优化技术进行了研究，并对逻辑函数优化结果进行系统测试。 最后是本论文的结束语。 二旦堕盔堂三堡堡主主垡丝塞 第二章集成电路逻辑设计的基本概念 2 1 逻辑函数的真值表表示 一般逻辑函数具有多个输入与多个输出，可表示为 y = f ( x ) 其中x 代表一组输入变量，代表一组输出变量，输入变量个数用n 表示， 输出变量个数用m 表示。z ，( ，s ，胛) 表示某一位输入变量，y ( 1 l ，所) 表示某 一位输出变量。一可取值为0 或1 ，y j 可取值为0 或1 或。在一组确定的输入 情况下，若某输出位y ，允许为0 也允许为1 ，则其值用表示。 下面是一个三输出的逻辑函数真值表的一种阵列表示形式： t = 0 0 0 0 0 l 0 0 1 0 0 l 0 1 0 x 0 1 0 1 l x 0 1 1 0 0 1 1 0 1 0 1 0 1 0 此阵列中每一一行代表一种输入情况下的对应输出，圆点左边为输入，圆点右 边为输出。观察其中第一行、第二行，输出完全相同，输入仅一位不同，这一位 为0 或为1 皆得相同输出，这两行可合并为一行，并将可为0 亦可为l 的那一位 也用表示。类似，第三、第四行亦可合并。于是上式可化简为 t = 0 0 * 0 0 l 0 1 0 1 1 0 0 1 1 0 1 0 】0 1 0 2 2三种输入集合 根据输出变量取值的不同，可把各种输入序列归入三个集合 8 - 9 1 7 一1 8 4 1 4 3 ：导通集合l o n 、断开集合l “一及无关集合。“。使某位 输出为1 的输入序列的集合为该输出位的导通集合，使某输出为0 的输入序列的 集合为该输出位的断开集合，使某输出为的输入序列的集合为该输出位的无关 集合。 从真值表可直接得到整个逻辑函数的三个集合。把真值表中输出y 位为l 的 保留为l ，其余非1 位改为0 ，即得导通集合；把真值表中输出y 位为0 的改为 l ，原来非0 位全改为0 ，即得断开集合；把真值表中y 位为的改为l ，原来非 ：! ：堡查兰三堡塑堂竺堡兰 x 位全改为0 ，即得无关集合。 上面的逻辑函数的三个集合为 c ：i n = c ，x = 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 l 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 l l 0 1 0 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 l o o 1 1 0 1 1 l 1 1 1 1 1 1 三输入逻辑函数的输入组态应有2 3 = 8 种，而丁式只给出了其中6 种输入， r 。遗漏，的两种输入组态为【l 1 o 和【l 1 1 】。这意味着，这两种输入组态， 对输出各位均无规定，即各位y 都可取值，故在断开集合中补进了这两种输入 组念。 从简化的真值表也可得三种集合的简化形式： fo。0。x,。0。0，1 2 11 0 0 1 l o 1 0 1 0 1 0 j c ：” 0 0 x 1 1 0 0 l x 0 1 0 1 0 0 o o l 1 0 1 1 0 1 o l o 1 0 0 。b 1 1 1j 0 型丛塑型型塑垫一一 前述三个集合的表达式中，都是把各输出位的某种集合合并表示于一式。 上述三个集合中的各y 位的取值只能是0 或1 。取1 表示该行左边的输入序列后 浚输出位的该种集合。但是某y 位取0 ，只能理解为此行没有表示该输入序列属 于该输出位的该种集合，并不表示该输入序列不在该输出位的该种集合中。如 c o n 中第三行可拆作两行，得 c f w2 0 0 * 0 0 1 0 1 x * 0 0 1 1 0 0 1 0 0 1 0 0 0 i o 1 0 l 0 1 0 上式中第三、四行分别表示同一输入序列【l 0 u j 属于y l 和y 2 的导通集合， 第三行并不表示输入序列【1 ”“坏在，z 的导通集合中，同样第四行并不表示输 入序歹0 p u ”坏在_ y ，的导通集合中。这两行没有矛盾。这说明逻辑函数的真值 表表示和它的三种集合表示有很大不同。 2 3逻辑多维空间 逻辑函数的三个集合均可形象地表示在个聊+ 维的多维空间 8 4 6 中。 这个多维空间中的n 维对应逻辑自变量，另外矾维对应逻辑因变量y 。出于变 量工与变量，都只能取值为l 或0 ，所以这个多维空间可看成是一个有限的单位 空间。这是一个特殊的多维空间。无论从物理意义上还是运算规则e 看，z 变量 与y 变量都是不等同的。因此对这个多维空问，与其想象为疗根工轴与耽根，轴 征交构成的多维空问，还不如想象为m 个相同的, 维子空间重叠而成月个z 变量 构成一个”维子空间，每位y 与一个子空间对应。一个集合在多维空f 白j 的图象由 每行分别对应的图象合成。对于每一行中y 为l 的位，在相应的子空间有一个图 形，此图形由该行全部x 位坐标决定。如一行有多个y 位为l ，则相应的多个子 空问有相同的图形，而y 为o 的位的对应子空间则无此图形。每一行在多维空浏 对应的全部图形称为一个多维体，这个多维体可能是某几个子空问相同图形的重 叠。上面导通集合l o n 共表示六个多维体，其中仅第五行所代表的多维体由两个 子多维体组成，其余五个多维体均只含一个子多维体。这些集合中所有子多维体 均由o 和1 表示，它的图形就是相应f 坐标决定的子空间中某一个顶点。图中画 出l o n 式所表示的全部多维体( 把三个子空间分开表示) ，其实总共就是分散在三 个子空间的7 个顶点。 塑垡苎塑! 生堂些堡兰 m 圃目 o u ) ( 0 1 0 ) “唧 ，1( 1 嘞乃 儿 圈2l 同样的导通集。o n 表示变成了4 行，则被看成四个多维体，其中两个子多维 体中含有，如( o o x ) ，实际为( o o o ) 和( o o d 两个点。这两个点的连线为子空间 的一条棱。所以子多维体( o o x ) 或( 0 l x ) 皆代表由两个顶点形成一条棱。如果子 多维体中含2 个，则表示它是由两条棱形成的个面，共含4 个顶点。一般来 说，子多维体中含几个x 就称为几维多维体。如不合，为一个点，称0 维多维 体；含一个x ，为一维多维体，为一条棱；含两个x ，为二维多维体，为一个面 “余此类推。 从图2 1 上可以看出三个y 位对应的子空间分别含一个点、一条棱和一个面。 因此该导通集合又可直接从图上得出，即有 f 100 l00 c o n = i l o x 0 10f l o x x * 0 0 1j 一个多维体可表示成a b ，a 代表n 位输入，b 代表m 位输出。若a 中含 的数目为n ，b 中含l 的数目为m ，则此多维体所含顶点数为2 “m 。在m + f l 维 空削中最大的多维体是各顶点位置皆有点，称为全多维体，记作玑，且有 “? 5 坚翟些 最大多维体“：7 所含顶点数为2 ”m 2 4 多雏体与布尔表达式 由多维体的阵列表达式可直接获得逻辑函数的布尔表达式。 1 导通集合与二级“与或”表达式 任何组合逻辑均可表示成二级“与或”布尔表达式，这可从导通集合得到。 导通集合的阵列表达式的左右两半分别为“与”阵列和“或”阵列。“与”阵列 中的每行为“与”关系，产生一个乘积项，位为1 贡献一原码，为0 贡献一反码， 为表示乘积项与该位无关。“或“阵列中的每列为“或”关系，每列对应一位 输出。每列中所有1 所在行的乘积项之逻辑“或”，就是该输出位的“与或”布 尔表达式。该逻辑函数可表示为 堡旦苎竺塑主兰堡丝苎 _ y i = x i x2 x 3 _ y 2 = x l x 2 x 3 + z i x 2 x 3 y 3 = x l x 2 x 3 + x l x 2 x 3 + x l x 2 x 3 + x l x 2 x 3 同一逻辑函数又可表示为 y t5 一x 2 x 3 y 2 = x l x 2 儿5o l 形式略有不同的布尔表达式，但它们都是等价的。 2 断开集合与二级“或与”表达式 任何组合逻辑也可表示成二级“或与”布尔表达式。把断刀：集合的阵列表达 式的左右两半分别看作“或”和“与”两个阵列。“或”阵列中每行表示一个逻 辑“或”，各x 位为o 贡献一原码x ，为1 贡献一反码，为无贡献。“与”阵列 中，按列取所有l 对应行的逻辑“或”相“与”构成“或与”表达式，即为相应 y 位的“或与”布尔表达式。该逻辑函数又可表示为 y i = ( x 】+ x 2 ) ( x i + x 2 + x 3 ) y 2 = ( x 1 + z 2 ) ( 工1 + x 2 ) y 3 = ( x l + x 2 + x 3 ) ( 一+ x 2 + x 3 ) 上式与前述“与或”逻辑式与前面的不一定完全等价。因为从导通集合导出 的布尔表达式只保证导通，而从断开集合导出的靠尔表达式则只保证断开。 2 5逻辑函数的覆盖 逻辑函数多维体表示方法。此方法比卡诺图更加规范化，更利于在计算机上 用来对逻辑函数进行化简。 逻辑函数的覆盖是一个符合一定条件的多维体的集合。可以定义两种意义的 覆盖。一种是包含导通集合中所有顶点，而不含断开集合中任一顶点，为导通覆 盖。另一种是包含断开集合中所有顶点，而不含导通集合中任一顶点，为断开覆 盖。只讨论导通覆盖，下面提到的覆盖皆指导通覆盖。显而易见，这样的覆盖将 与二级“与或”布尔表达式相联系。 覆盖的性质如下： ( 1 ) 覆盖中必须包含导通集合中全部顶点，不得含断开集合中任一顶点，但 可含无关集合中的某些顶点。 ( 2 ) 覆盖中的每一个多维体称为蕴涵体，每个蕴涵体必须至少包含一个属于 海大学工程硕十学位论文 导通集合的顶点。晟小的蕴涵体就是导通集合中的个顶点。 ( 3 ) 组成覆盖的所有蕴涵体都必须是质蕴涵体如果一个蕴涵体不会被另 个已存在或可能存在的蕴涵体全部包含，则称此蕴涵体为质