Achieving fast and exact hazard-free logic minimization of extended burst-mode gC finite state machines

Update Item Information
Publication Type Journal Article
School or College College of Engineering
Department Electrical & Computer Engineering
Creator Myers, Chris J.; Gopalakrishnan, Ganesh
Other Author Jacobson, Hans
Title Achieving fast and exact hazard-free logic minimization of extended burst-mode gC finite state machines
Date 2000
Description Abstract This paper presents a new approach to two-level hazard-free logic minimization in the context of extended burst-mode finite state machine synthesis targeting generalized C-elements (gC). No currently available minimizers for literal-exact two-level hazard-free logic minimization of extended burst-mode gC controllers can handle large circuits without synthesis times ranging up over thousands of seconds. Even existing heuristic approaches take too much time when iterative exploration over a large design space is required and do not yield minimum results. The logic minimization approach presented in this paper is based on state graph exploration in conjunction with single-cube cover algorithms, an approach that has not been considered for minimization of extended burst-mode finite state machines previously. Our algorithm achieves very fast logic minimization by introducing compacted state graphs and cover tables and an efficient single-cube cover algorithm for single-output minimization. Our exact logic minimizer finds minimal number of literal solutions to all currently available benchmarks, in less than one second on a 333 MHz microprocessor - more than three orders of magnitude faster than existing literal exact methods, and over an order of magnitude faster than existing heuristic methods for the largest benchmarks. This includes a benchmark that has never been possible to solve exactly in number of literals before.
Type Text
Publisher Institute of Electrical and Electronics Engineers (IEEE)
First Page 303
Last Page 310
Language eng
Bibliographic Citation Jacobson, H., Myers, C. J., & Gopalakrishnan G. (2000). Achieving fast and exact hazard-free logic minimization of extended burst-mode gC finite state machines. International Conference on Computer-Aided Design, 303-10. November.
Rights Management (c) 2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Format Medium application/pdf
Format Extent 188,312 bytes
Identifier ir-main,15037
ARK ark:/87278/s6ww825n
Setname ir_uspace
ID 705356
Reference URL https://collections.lib.utah.edu/ark:/87278/s6ww825n