Using If-Then-Else DAGs for Multi-level Logic Minimization

本研究是将布尔函数电路描述转换为满足时间和成本约束的实现功能的电路。该方法是在多级最小化中使用if-then-else DAG的转换。它们对于表示布尔函数特别有吸引力，因为它们可以紧凑地表示有用的函数，例如算术和奇偶校验函数，这些函数需要以乘积和格式进行指数级的表示。初步研究表明，即使是相当粗糙的转换也能有效地最小化。主要研究的算法有：因式分解，降低表达式的复杂度；共享公共子表达式，消除冗余电路；并使用不关心信息来处理部分指定的函数。本课题的研究方向是集成电路芯片自动化设计的一个重要领域——逻辑合成。首席研究员是该领域公认的专家研究员，具有新颖想法的历史，并有继续进行良好研究的潜力。本研究对我们理解集成电路设计理论和方法具有重要意义。

This research is on converting a Boolean function circuit description into a circuit that implements the functions, meeting time and cost constraints. The approach is to use transformations of if-then-else DAG's in multi-level minimization. These are particularly attractive for representing Boolean functions because they can compactly express useful functions, such as arithmetic and parity functions, that require exponentially larger representations in the sum-of-products format. Preliminary studies indicate that even fairly crude transformations provide effective minimization. Research is on algorithms for: factoring, to reduce the complexity of expressions; sharing common sub- expressions to eliminate redundant circuitry; and using don't care information to handle partially specified functions. The proposed research is in an important area of automated design of IC chips, logic synthesis. The Principal Investigator is recognized as an expert researcher in this area, has a history of novel ideas, and the potential to continue producing good research. This research is important to our understanding of IC design theory and methods.