多值多输入多输出逻辑优化(戴芸).pptVIP

多值多输入多输出逻辑优化软件研究 计算机科学与技术学院 学生:戴芸 指导老师:邱建林 副教授 研究的目的和意义 随着IC工艺的发展，集成电路的规模不断扩大，设计的复杂度越来越高，这就需要寻求新的设计方法，其关键就是要有优秀的集成电路设计软件作为开发工具。我们要紧跟时代的步伐，开展从事这方面的研究，这不仅是我国国民经济发展的要求，也是国家强盛的基础。 本课题一方面研究集成电路多输入多输出逻辑函数递归裂变求补算法和基于积项扩展的多输入多输出集成电路逻辑优化算法；另一方面研究实现这两种算法的软件方案。 step3：在叶子结点求出相应的，并将它与其父结点到该叶子的分枝上的变量相乘，构成其父结点的补集的一个蕴涵项，由该父结点的左、右叶子构成其父结点的补集；转step4； step4：每次父结点的补集形成后均进行去冗员余操作及相邻项的合并；并将其左、右叶子删除，使其自身为上级父结点的叶子，直至该父结点为函数F的根结点，转step5；否则转step3； step5：输出根结点函数F的补集。  例1：设 ，求 。 基于积项扩展的多输入多输出集成电路逻辑优化算法要点 step1：根据给定的多输入多输出逻辑函数输入积项，计算出各输入积项的余因子，形成无共享积项的假集矩阵； step2：再根据各输入积项形成阻塞矩阵和覆盖矩阵； step3：依据最小列覆盖的选择算法得到阻塞矩阵和覆盖矩阵最小列覆盖集合和提升集合； step4：针对各输入积项的最小列覆盖集合和提升集合，扩展后的积项形式； step5：各输入积项是否扩展完成，是转step6，否则转step2； step6：对扩展后的积项进行合并去除重复项形成优化后的多输入多输出逻辑函数。 例2：给定一个多输入多输出逻辑函数F的表示如下，求其扩展后的逻辑函数F 。 模块划分 图1.2模块划分图 1.系统登录 用户输入用户名和密码，系统查询数据库中的信息对密码进行验证。如果密码不正确将不能进入系统。如果密码正确，系统会自动根据该用户所具有的权限进入不同界面。 2.系统管理 修改密码：对于任何用户，包括管理员和一般用户都可以对自己的密码进行重新设置。 用户管理：只针对管理员才能进行操作，管理员可以查看用户状态，当一般用户忘记密码时能够找回其密码，并且能添加、删除用户，修改用户权限。 3.程序优化 递归裂变求补：能够根据给定的输入积项，计算出补集矩阵，用比较直观的方法向用户显示递归裂变求补的二叉裂变过程和最后的结果。 积项扩展：能够根据给定的输入积项计算出无共享积项的假集矩阵、阻塞矩阵和覆盖矩阵，对阻塞矩阵和覆盖矩阵依据最小列覆盖的选择算法得到最小列覆盖集合和提升集合，形成输入积项扩展后的积项形式。 递归裂变求补流程图 图1.3 递归裂变求补流程图 递归裂变求补运行界面 积项扩展流程图 图1.5积项扩展流程图 积项扩展运行界面 结束 谢 谢 大 家！ * * 递归裂变求补算法(对完全举列) 注：①当F= ￠ 时， =U；②当F含有一个全2行，即F=U， 则有 =￠； ③当F仅含一行，则用摩根定理求出 。如果遇上到上述终止情况之一，则结束裂变，进行回归收集。 step1：建立一棵递归展开二叉树，根结点为F，判断结点是否为终止3种情况之一，若是则分别按3种情况处理，结束递归，转step3。若不是3种情况之一，则转step2。 step2：选取分裂变量xj，使xj所在列的0和1个数最多；令为左分枝，形成左子树根结点。令xj为右分枝，形成右子树根结点；新产生的结点作为根结点，转step1； 用矩阵形式表示为： ， 图1.1 二叉树裂变过程 根据最小列覆盖的选择算法得到最小列覆盖 和提升集合 根据定义5得到积项 的扩展后的积项形式 ； 同样方法令 ，得到扩展后的积项 ； 令 ，得到扩展后的积项 ；