Loading...
Please wait, while we are loading the content...
Similar Documents
An Efficient Method for Generating Kernels on Implicit Cube Set Representations
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sawada, Hiroshi Yamashita, Shigeru |
| Copyright Year | 1999 |
| Abstract | In the process of logic synthesis and optimization, it is an important operation to extract common logic parts among several logic functions. Most methods currently used are based on SOP (sum-of-products) expressions of logic functions. In such methods, special sub-expressions named kernels [1, 2] are generated, and attempts are made to find good intersections of kernels for common logic expressions. A SOP expression can be represented by a set of cubes. Although it is a straight-forward way to enumerate cubes explicitly, there is a case where the number of cubes becomes so large that we can hardly manipulate them explicitly. The typical case is the SOP expression of an adder, which contains many XOR operations. To handle larger cube sets, methods have been proposed [3], [4] that represent cube sets implicitly on BDDs [5] or similar data structures. There are few methods [6], however, for extracting common logic expressions using implicit cube set representations. In this paper, we propose a new method that efficiently generates all kernels for implicitly represented cube sets, and show how to apply it to the extraction of common logic expressions. The main feature is the memorization of the kernel generation process using a graph structure, which is called a kernel graph in this paper. Nodes of the graph are identified by the pair of a cube set and an integer value, and are easily accessible by a hash table. With this mechanism, we can skip the process of kernel generation that was processed before. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.kecl.ntt.co.jp/icl/signal/sawada/mypaper/iwls99.pdf |
| Alternate Webpage(s) | http://www.kecl.ntt.co.jp/csl/car/members/sawada/mypaper/iwls99.pdf |
| Alternate Webpage(s) | http://www.kecl.ntt.co.jp/csl/car/members/sawada/mypaper/kws99.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
