Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-02-01
2001-04-10
Teska, Kevin J. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06216260
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates to Electrical Computers and Data Processing Systems and more particularly to Applications to Design and Analysis of Electrical/Electronic Circuits.
2. Description of Prior Art
Usual way of projecting of the equipment that realizes the assigned algorithm consists of the following. (1) The (micro)processor and an appropriate programming language are chosen. (2) The computer program is written and debugged. (3) Read Only Memory that controls the program is hardwired by the debugged program.
As a rule, the computer instructions very little correspond to the algorithm operations. Hence, each block of the algorithm flowchart is realized by the set (subroutine) of computer instructions. The sequential order of the computer instructions' performance results in slowing down of the computer performance of the assigned algorithm. This is a disadvantage if algorithm has to work in a real-time scale, such as communications network control algorithms, error correcting code decoders' algorithms, rocket missiles pursuing algorithms. Thereafter, the hardware realization of the control algorithms performed as Moore or Mealy automatic machines, is implemented (see
Automatic Logic Synthesis Techniques for Digital Systems
, by M. D. Edwards, McGrow-Hilll, New York, 1992, ISBN 0-07-019417-3).
Digital circuit in a form of automatic machine consists of a set of logical elements, type AND, OR, and NOT (inverter), and binary memory elements. Digital circuit receives digital input signals, performs logic operations for the process of control, and directs its digital output signals to the executive parts of the computer system. Binary memory elements, that configured in the digital circuit, are connected to the outputs of logical elements. Each memory element creates a delay in one clock pulse. Therefore, memory element is implemented (that is, connected to the output of a certain logical element) only if it is needed for the correct realization of a control algorithm.
Implementation of digital circuits instead of programmable processors permits to reduce significantly the clock pulses number needed for the control algorithm realization. The speed of the control process increases by this in ten times or more without the change of the digital electronic technology.
The problem of control algorithms' realization by a digital circuit is solved in the book by M. D. Edwards and other known literature, by compiling and coding the state table of an automatic machine. (There are almost no differences between Moore and Mealy machine, see pg. 35 of the cited book). One of the most important problems in the finite state machines' implementation is the efficient binary encoding of the internal states of the machine (see pg. 38, 39). However, if i is the states' number, then “for i<5 it is not feasible to try all the different assignments by enumerative methods in order to find the most economical combinatorial logic solution” (see pg. 131).
Several improved computerized state assignment algorithms included into the cited book: KISS and CREAM algorithms, MUSTANG technique, NOVA, K-MUSTARD and ASYL approaches. However, these algorithms also do not lead to an optimal solution, and the following recommendation included into the book. “For large finite state machines it can be more efficient to decompose a machine into an interconnection of two or more smaller submachines. The resulted submachines may subsequently be synthesized in the usual way” (pg. 132). This recommendation is caused by the lack of satisfactory solution of digital circuits' synthesis method.
U.S. Pat. No. 5,805,462 to Frank Poirot et al (1998, applicant: VLSI Technology, Inc., San Jose, Calif.) discloses automatic synthesis of integrated circuits employing Boolean decomposition. The problem of proper inclusion of memory elements for multistate algorithm realization is not solved in this invention.
The book
The Behavior and Simplicity of Finite Moore Automata
by Andras Adam, Budapest, 1996 is also devoted to digital circuits realizing the control algorithms. As the book by M. D. Edwards it describes the synthesis of digital circuits with the memory elements with the use of the internal states' table. This implementation is difficult for relatively complicated algorithms.
U.S. Pat. No. 4,703,435 to John A. Darringer et al. (1987, applicant IBM Corporation, Armonk, N.Y.) discloses an automated logic synthesis method. A register-transfer level flowchart specification in this method is translated straightforwardly into a single AND-OR logic implementation. Simplified AND-OR implementation is translated to a NAND or NOR representation, depending on the target technology, after logic implementation expands to elementary representation. The problem of the proper synthesis of automatic machine, realizing any finished algorithm, and including logic (of any type) and memory elements, was not stated in this invention.
U.S. Pat. No. 5,029,102 to Anthony D. Drumm et al (1991, applicant IBM Corporation, Armonk, N.Y.) discloses a logic synthesis method and system for a digital circuit, consisting of basic logic blocks. Method is improved to that of U.S. Pat. No. 4,703,435; some of the said blocks may not be primitive (logic) blocks. Method includes the novel technique for performing logic reduction on the individual expressions. However, the problem of the proper synthesis of automatic machine, for the finished algorithm realization, including logic and memory elements, was not stated in this invention.
U.S. Pat. No. 5,258,919 to Roy K. Yamanouchi et al (1993, applicant National Semiconductor Corporation, CA.) provides a structured integrated circuit design methodology, consisting of the following stages:
1) Describing a two-phase logic function using a highlevel behavioral description flowchart;
2) Reducing trial and error in circuit layout implementation using novel chip planning techniques;
3) Definition of signal types and the type of input signal that feeds the current function. A rigid set of rules is established for the signal types;
4) Technical specification of the two-phase logic function is defined. A behavioral flowchart using defined symbols is created;
5) An associated database of the Boolean equations for the parameters of the flowchart elements is created;
6) Boolean equations are converted to a logic diagram by coded state assignment or by direct implementation;
7) Resulted logic diagram is analyzed for speed utilizing a Figure of Merit technique;
8) Circuit design is carried through to layout by CAD tools.
The 6
th
stage among the indicated 8 stages is used to create a Mealy (or Moore) automatic machine and related to the proposed invention. The creation of automatic machine in U.S. Pat. No. 5,268,919 is based on sate assignment, creation of the state transition table, and output table, just as described in the book by M. D. Edwards, pg. 34÷40. Improved algorithms for computerized state assignment, summarized in the book by M. D. Edwards from the previous literature, are not included in this patent. For these reasons the U.S. Pat. No. 5,268,919, as already cited book, cannot be used for the creation and optimization of the relatively complicated digital circuit.
U.S. Pat. No. 5,403,504 to Shin-Ichi Minato (1996, applicant Nippon Telegraph and Telephone Corporation, Tokyo, Japan) discloses a design system of a logic circuit, including a logic synthesis. Logic circuit includes a processing unit, and a set data processing unit. The set data processing unit includes a node table for the elements recording. The control unit of the logic synthesis and processing unit read data from the node table, assign a binary number to each element, and transfer to the data processing unit. The control unit of the data processing unit separates the set data (“0” from “1”), generates a 0-supressed binary decision diagram (BDD) of a logic function, and stores data to the node table. Intermediate nodes in BDD are eliminated. A subset, whose element number is smaller
Anna Alshansky
Garbowski Leigh Marie
Teska Kevin J.
LandOfFree
Method for automatic synthesis of a digital circuit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for automatic synthesis of a digital circuit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for automatic synthesis of a digital circuit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2547905