文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Minimization of Fixed-Polarity ANDXOR Canonical Networks 1 Minimization of Fixed-Polarity A
侵权投诉

Minimization of Fixed-Polarity ANDXOR Canonical Networks 1 Minimization of Fixed-Polarity A

A method to extract the cubes of the Generalized Reed-Muller form (GRM) of a Boolean function with a given polarity is presented. The method does not require exponential space and time complexity and it achieves the lower bound time complexity. The proof o

Minimization of Fixed-Polarity AND/XOR Canonical

Networks

ABSTRACT

A method to extract the cubes of the Generalized Reed-Muller form (GRM) of a Booleanfunction with a given polarity is presented. The method does not require exponential space andtime complexity and it achieves the lower bound time complexity. The proof of the method’s cor-rectness constitutes the rst half of this paper. Also, a separate heuristic algorithm to nd the op-timal polarity that requires the least number of cubes in the GRM representation is proposed. Thealgorithm is fast and derives the polarity for variables and extracts all cubes simultaneously. It isbased on the concept of a Boolean center for vertices, which emulates the center of gravity con-cept in geometry. The experimental results for the heuristic algorithm agree strongly with our ob-servations and analysis.

1 Introduction

It has been known [1-2][4-8][10-11][13-17][20,21] that for arithmetic functions and error-correcting circuits the best realizations include XOR gates. High testability of the AND/XORdesigns makes them additionally attractive [12]. However, popular logic synthesis tools cannottake the XOR into consideration. Perhaps one reason for low popularity of XOR gates is that, inearlier technologies, such gates were much larger and slower than AND/NAND/OR/NOR blocks.This is no longer true with the present technologies. Hence, incorporation of XOR into logic syn-thesis becomes a technologically feasible and important issue. Recent developments in symmetrydetection [18] and Boolean matching [19] utilize the XOR representations as a tool to analyzeBoolean functions. These new applications make it critical that we investigate and derive moreef cient methods to obtain the XOR representation of Boolean functions.

The foundations of XOR representation are based on the well-known Reed-Muller (RM)Form. In an RM form, each Boolean function can be represented by the XOR sum of a unique setof cubes, in which every variable is in the positive polarity. A Generalized Reed-Muller (GRM)form allows each variable to be in either positive or negative polarity, but not both, in the forms.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email