Research on Efficient Manipulation of Boolean Functions Using Shared Binary Decision Diagrams and Its Application to Computer Aided Logic Design

使用共享二元决策图有效操作布尔函数的研究及其在计算机辅助逻辑设计中的应用

基本信息

  • 批准号:
    02452162
  • 负责人:
  • 金额:
    $ 3.71万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for General Scientific Research (B)
  • 财政年份:
    1990
  • 资助国家:
    日本
  • 起止时间:
    1990 至 1991
  • 项目状态:
    已结题

项目摘要

We have carried out researches on efficient representation and manipulation of Boolean functions, and applied them to computer aided logic design.1. Efficient Representation and Manipulation of Boolean FunctionsWe have carried out researches on the efficient representation of Boolean functions using Shared Binary Decision Diagrams (SBDDs). For efficient manipulation of SBDDS, we have proposed attributed edges. We have developed a vector algorithm for manipulating SBDDs. We have also investigated variables ordering methods for minimizing SBDDs.2. Computer Aided Logic Design Using Shared Binary Decision DiagramsWe have applied Boolean function manipulation to fault diagnosis and timing verification of logic circuits. On fault diagnosis, we have developed efficient fault simulation methods for multiple faults and novel methods of generating compact test sets. On timing verification, we have developed methods for simulating logic circuits with nondeterministic delays.3. Formal Verification of Logic Design Using Shared Binary Decision DiagramsWe have proposed a method to represent state transition diagrams using SBDDs. Based on the method, we have developed a formal verification algorithm on branching time regular temporal logic, and implemented a formal verification system for sequential machines.4. Computational Complexity of Boolean Function ManipulationWe have clarified the class of functions efficiently expressed by BDDs. We have also developed a paranelization methods for manipulating BDDs and clarified the computational complexity.5. Systems for Computer Aided Logic DesignWe have developed a package software so as to make it easy to manipulate SBDDs on tools for computer aided logic design.
我们对布尔函数的有效表示和操作进行了研究,并将其应用于计算机辅助逻辑设计.布尔函数的有效表示与操作我们对布尔函数的有效表示进行了研究,使用共享二元决策图(SBDD)。为了有效地操纵SBDDS,我们提出了属性边缘。我们已经开发了一个矢量算法操纵SBDD。我们还研究了最小化SBDD的变量排序方法。用共享二元决策图进行计算机辅助逻辑设计我们将布尔函数操作应用于逻辑电路的故障诊断和时序验证。在故障诊断方面,我们开发了有效的多故障故障模拟方法和新的生成紧凑测试集的方法。在时序验证方面,我们发展了模拟具有不确定延迟的逻辑电路的方法.基于共享二叉决策图的逻辑设计形式化验证提出了一种用共享二叉决策图表示状态转移图的方法。在此基础上,提出了一种分支时间规则时序逻辑的形式化验证算法,并实现了一个时序机的形式化验证系统.布尔函数操作的计算复杂性我们已经阐明了由BDD有效表示的函数类。我们还开发了一种平行化的方法来操纵BDD,并阐明了计算的复杂性。计算机辅助逻辑设计系统我们开发了一个软件包,以便在计算机辅助逻辑设计工具上容易地操作SBDD。

项目成果

期刊论文数量(72)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Nagisa Ishiura: ""A Class of Logic Functions Expressible by Polynomial-Size Binary Decision Diagrams"" Proceedings of the Synthesis and Simulation Meeting and International Interchange. 48-54 (1990)
Nagisa Ishiura:“通过多项式大小的二元决策图表达的一类逻辑函数”综合与模拟会议和国际交流会议论文集。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
松本 忍: "ブ-ル式処理による不完全指定順序機械の最小化" 情報処理学会論文誌. 31. 1644-1652 (1990)
Shinobu Matsumoto:“使用布尔处理最小化不完全指定的有序机器”,日本信息处理学会汇刊 31. 1644-1652 (1990)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Noriyuki Takahashi: ""Fault Simulation for Multiple Faults Using Shared Binary Decision Diagrams"" Proceedings of the Synthesis and Simulation Meeting and International Interchange. 157-164 (1990)
Noriyuki Takahashi:“使用共享二元决策图进行多故障故障仿真”综合与仿真会议及国际交流论文集。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
H.Hiraishi: "Vectorized Symbolic Model Checking of Computation Tree Logic" Procceedings of the Workshop on Computer-Aided Verification. 279-290 (1991)
H.Hiraishi:“计算树逻辑的矢量化符号模型检查”计算机辅助验证研讨会论文集。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Shinobu Matsumoto: ""Minimization of Incompletely Specified Sequential Machines"" Transaction of Information Processing Society Japan. 31. 1644-1652 (1990)
Shinobu Matsumoto:““不完全指定的序列机的最小化””日本信息处理学会汇刊。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

YAJIMA Shuzo其他文献

YAJIMA Shuzo的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('YAJIMA Shuzo', 18)}}的其他基金

Research on Development of Formal Logic Design Verifier for Microprocessors
微处理器形式逻辑设计验证器的开发研究
  • 批准号:
    07558155
  • 财政年份:
    1995
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Scientific Research (A)
Basic Research on High-Speed Boolean Function Manipulator
高速布尔函数操纵器的基础研究
  • 批准号:
    05452352
  • 财政年份:
    1993
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for General Scientific Research (B)
Research on Formal Verifier of Logic Design Based on Temporal Logic
基于时态逻辑的逻辑设计形式验证器研究
  • 批准号:
    05558030
  • 财政年份:
    1993
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Developmental Scientific Research (B)
Research on Development of Logic Synthesizer and Design Verifier for Sequential Circuits Based on Boolean Function Manipulation
基于布尔函数操作的时序电路逻辑综合器和设计验证器的开发研究
  • 批准号:
    03555074
  • 财政年份:
    1991
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Developmental Scientific Research (B)
Research on Development of a Logic Design Verification System Based on Time-Symbolic Simulation
基于时间符号仿真的逻辑设计验证系统开发研究
  • 批准号:
    01850074
  • 财政年份:
    1989
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Developmental Scientific Research (B).
Researches on the Design of Highly Reliable High-Speed Arithmetic Circuits with Redundant Coding
高可靠冗余编码高速运算电路设计研究
  • 批准号:
    63460134
  • 财政年份:
    1988
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for General Scientific Research (B)
Research on Development of High-Speed Logic Simulators Using a Vector Processor and Logic Design Verification Systems
使用矢量处理器和逻辑设计验证系统的高速逻辑模拟器的开发研究
  • 批准号:
    61850062
  • 财政年份:
    1986
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Developmental Scientific Research
Research on Design of VLSI Oriented Hardware Algorithms Using Redundant Representation
采用冗余表示的面向VLSI的硬件算法设计研究
  • 批准号:
    60460133
  • 财政年份:
    1985
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for General Scientific Research (B)
Developmental Research on Interactive Logic Simulator-Verifier with High-Level Hardware Description
具有高级硬件描述的交互式逻辑仿真验证器的发展研究
  • 批准号:
    59850059
  • 财政年份:
    1984
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Developmental Scientific Research

相似海外基金

Quantum-dot logic systems based on the binary decision diagram.
基于二元决策图的量子点逻辑系统。
  • 批准号:
    12450134
  • 财政年份:
    2000
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
Single-electron devices based on the binary decision diagram.
基于二元决策图的单电子器件。
  • 批准号:
    08455156
  • 财政年份:
    1996
  • 资助金额:
    $ 3.71万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了