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

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

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.