The currently used technologies for design of digital circuits include, among others, gate arrays, standard cells, custom and semi-custom circuits and Programmable Logic Devices. Many design automation tools are currently available on the market for these technologies from different vendors. They include: schematic capture, logic minimization, geometrical cell layout, placement, routing, design rule checking, simulation and other. In this paper we will concentrate on high-level tools that are relatively independent of the technology and are applied to all the above technologies. Tools of this type have been built for a number of years by large hardware companies and at universities and are starting to arrive also from companies that produce commercially available CAD software: ENDOT Inc., and Daisy being the first examples [73, 43].
While the circuit/system design on most current workstation systems starts either from the netlist of the circuit and/or logic equations of a Boolean function described in a textual form or from the schematic capture of a logic circuit, the new generation of software design tools will start from higher level descriptions and will generate these data in resultant or intermediate formats only. Since the lower design stages are well known, we will concentrate in this paper on the upper ones and we will briefly present design methods and software which produces data for the current CAD systems in the form of netlists, minimized truth tables and logic expressions.
High level descriptions available in the in-house tools from large companies, like IBM, GE, GTE, RCA, INTEL include: register-transfer languages, finite-state machines, Boolean expressions and structural languages. Universities (Carnegie-Mellon, Stanford, UCLA, Kiel) experiment with various system description hardware languages, regular expressions, Petri Nets, nondeterministic and parallel automata, recursive equations, general purpose languages like Lisp, C, Concurrent Prolog or Ada as the high-level design automation source formats.
It is not clear these days, which direction design automation will follow with respect to the high level languages and design methodologies. Some trends are however clearly visible while attending the premiere conferences like the Design Automation Conference or International Conference on Computer Aided Design and watching the new software tools presented, and especially talking to the company's representatives about future plans. These trends include: integration of design/analysis/verification tools into comprehensive systems; giving the designer choices to select various design styles, and providing him/her with tools to build his own CAD software; mastering user-friendly interfaces based on windows and graphics; incorporating Boolean minimization methods and technology adaptation methods for various design styles, not only PLAs; using finite-state machine description for custom cell design.
In this paper I will concentrate on the topics of finite state machine design tools, that in my opinion are one of the most important tasks in CAD tools development for the coming years. At Portland State University we investigate various algorithms and programs for designing finite state machines (FSMs) with the goal of building a comprehensive FSM design system. The following selection of topics will present a subjective perspective; from large number of approaches we disscuss those, which are related to methods and algorithms applied in our system. Other important high-level issues like simulation, verification, and data-path design will be not discussed in this paper due to size restrictions.
Good tutorials on CAD VLSI tools can be found in [131, 154, 115, 135]. The recommended logic design textbooks, useful from the point of view of designing CAD tools for logic design are: [26, 173, 148, 68, 123, 95, 77, 176, 112, 127, 179, 186, 38].
First, various methods of describing sequential circuits realized as finite-state machines will be presented. Next, various methods to optimize FSMs will be presented, including minimization of the number of states of machines, state assignment of machines' internal states, decomposition, and partitioning of machines. We will mention asynchronous circuits design methodologies that will be also gaining importance in coming years. Finally we will discuss modern CAD tools for logic minimization.
Papers presented in this session will be all related to implementation of software tools for FSM design. The first paper will present optimization methods for designing with PLDs (Programmable Logic Devices) using industrial tools. The author discusses both the implementer's and the user's aspects of PLD design tools. Such devices permit for very fast and inexpensive design (programming) of logic and sequential circuits from small to medium size circuits. They are expected to have a massive impact on the market and are of increasingly applied by electrial engineers who are not able or do not require using more expensive highly integrated technologies. The next paper will describe the user's interface to the design automation system Diades, under design at Department of Electrical Engineering at PSU. Designing better user interfaces is very important from the practical point of view, not only in industrial, but also in the University environment, where most of the system's users are only casual digital designers and have troubles with quickly learning how to use many various CAD tools. The system is implemented in Lisp, Prolog, Pascal, C and Fortran on a Vax 11/750 computer under Unix and cooperates with the widely used UC Berkeley CAD VLSI tools. The system can be a front-end to both PLDs and Custom VLSI circuits design tools. The last two papers describe two tools, implemented in C and Pascal, which are not only useful, but can be easily implemented on personal computers. They will be used by everybody interested in logic design, but having no access to expensive mainframes - undergraduate PSU students being the first, to simulate and design logic circuits on their personal home computers. Portable register-transfer simulator, described in the third paper will permit for simulation of logic circuits on logic and register-transfer levels. Visualization of logic values in time or geometrical domains is helpful to understand intuitively a circuit's behavior and was proven a very useful design/debugging tool for both novice and experienced designers. Finally , the last paper describes a Boolean minimizer based on the new principle of graph coloring. It can be useful for PAL minimization on personal computers with small memory. All papers, including this one, will be illustrated in lectures with many practical examples.
Availability of the described above software tools, together with inexpensive PAL and PLD programming devices (widely advertized in journals like Byte) permits small and medium businnesses, as well as the individual hobbyists, to make his/her own "poor man's LSI CAD/CAM design shop".