| Presentation | 1993/5/27 Minimum Unicode One-Shot State Assignment Using SBDD Yong-Jin Kwon, Shuzo Yajima, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We propose a new method of the unicode one-shot state assignments for asynchronous sequential circuits,in which the propositional calculus,or Boolean algebra is adopted.Exact minimum solutions of the unicode assignment are obtained by our method.The problem of the unicode one-shot state assignment coincides with the hypercube embedding problem,which is known to be NP-complete. The known algorithms for the hypercube embedding problem almost consist of the mechanism of backtracking.Using newly introduced Boolean variables here,we can check the possibility of the unicode one-shot state assignment or the hypercube embedding for a given flow table or graph by even making propositional formula.In order to handle huge propositional formulas,the shared binary decision diagrams(SBDD′s)are used as an internal representation of the form ulas which denote the unicode assignment for a given flow table. Experimental results show that methods are effective to obtain minimum solutions at significantly reduced computation cost. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | unicode one-shot state assignment / minimum / propositional calculus / Hypercube embedding / SBDD′s |
| Paper # | COMP93-15,SS93-9 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1993/5/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Minimum Unicode One-Shot State Assignment Using SBDD |
| Sub Title (in English) | |
| Keyword(1) | unicode one-shot state assignment |
| Keyword(2) | minimum |
| Keyword(3) | propositional calculus |
| Keyword(4) | Hypercube embedding |
| Keyword(5) | SBDD′s |
| 1st Author's Name | Yong-Jin Kwon |
| 1st Author's Affiliation | Faculty of Engineering,Kyoto University() |
| 2nd Author's Name | Shuzo Yajima |
| 2nd Author's Affiliation | Faculty of Engineering,Kyoto University |
| Date | 1993/5/27 |
| Paper # | COMP93-15,SS93-9 |
| Volume (vol) | vol.93 |
| Number (no) | 81 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |