Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-09-28
2002-04-02
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C326S010000, C326S041000, C326S047000
Reexamination Certificate
active
06367054
ABSTRACT:
The present invention generally relates to the field of sequential circuits and more particularly to the field of cascade decomposition of sequential circuits
Digital electronics sequential circuits have the property that the output depends not only on the present input but also on the past sequence of inputs. In effect, sequential circuits must be able to store something about the past history of inputs in order to produce the present output. Conventionally, a sequential circuit is synthesised as a forward path containing combinational logic and a feedback path that includes memory as shown for a Mealy sequential circuit in FIG.
1
. In such an implementation the cycle time is measured from input to updating the memory.
Sequential circuits have a wide variety of applications such as code converters, sequence detectors, controllers, etc. and their speed of operation i.e. their cycle time can be a limitation in electronic equipment.
Thus, work has been carried out in an attempt to improve the speed of operation of sequential circuits.
It is known that the implementation of the sequential circuit as a set of interacting sequential circuits functioning concurrently i.e. in parallel is desirable primarily because of the resulting improvements in performance.
One such method is a decomposition approach based on the Algebraic Structure Theory disclosed in a book by J. HartManis and R. E. Stearns (“Algebraic Structure Theory of Sequential Machines”, Prentis Hall, Englewood Cliffs, 1996). This work has been further analysed in a paper by M. Geiger and T. Mülle-Wipperfürth (“FSM Decomposition revisited: Algebraic Structure Theory applied to MCNC Benchmark FSMS”, 28th ACM/IEEE Design Automation Conference, 1991, ACMO-89791-395-7/91/0006/0182, pages 182 to 185). In this approach a sequential circuit is decomposed into a cascade of component sequential circuits. In such a configuration all of the component sequential circuits function concurrently. It has been shown that such an approach can result in reduced cycle time and reduced circuit components and/or a reduced circuit area. However, such an approach relies on determining partitions and it is known that partitions are scarce. Consequentially, such methods rarely yield a decomposition and if they do it is typically only into two or three smaller machines.
It is known in the Algebra Structure Theory of K. Krohn and J. L. Rhodes (“Algebraic Theory of Machines, I Prane Decomposition Theorem for Finite Semi-Groups and Machines” Trans. Amer. Math. Soc. Vol. 116 (1965) pages 450 to 464) and from the later work by H. P. Zeiger (“Cascade Synthesis of Finite State Machines” Information and Control, 1967, pages 419 to 433) that the state transition graph of a sequential circuit gives rise to an algebraic structure known as a semi-group and that a semi-group can be decomposed into component semi-groups. Moreover, each decomposition of the semi-group results in a decomposition of the sequential circuit into a cascade of component sequential circuits as shown in
FIG. 2
such that each machine is a permutation reset machine.
The problem of the approach of Zeiger is that his method requires the calculation of the semi-group of the sequential circuit and this can be very large. Thus the method is not generally implementable. Since the technique calculates functions for all possible sequences of inputs this can give rise to p
p
functions where p is the number of states in the given circuit. If the elementary functions are not fully defined the number of functions can be larger than p
p
. Further, as can be seen in
FIG. 2
, the input to the p
th
circuit is the output of all the previous p-
1
circuits. Clearly even for p the amount of wiring between the circuits becomes considerable and the calculations of the component machines becomes very difficult.
FIG. 2
is only a schematic drawing and only shows one wire output for each circuit. In fact the number of wires is at least as large as the number of bits required to encode the states of the machine.
It is therefore an object of the present invention to provide a sequential circuit design and method in which the disadvantages of the prior art methods are overcome and a sequential circuit of reduced cycle time is produced.
In accordance with one aspect of the present invention there is provided a method and apparatus for determining the decomposition of a sequential circuit which does not require the semi-group to be calculated. From the state transition graph of the sequential circuit, a dynamic data structure is generated which represents all the information required to determine the component sequential circuits.
In accordance with another aspect of the present invention the above mentioned data structure is utilised so as to optimise the wiring so that the resulting decomposition only requires a single connection between each component sequential circuit.
In accordance with a further aspect of the present invention there is provided a method and apparatus for generating finite state graphs for designing a cascade decomposed sequential circuit from an input finite state graph for a sequential circuit, wherein functions are determined defining all transitions from the current state to a next state of the logic circuit caused by an input to the logic circuit, sets of states which include the possible state of the logic circuit are determined using the functions, the levels are assigned to the sets such that each level corresponds to one of a cascaded plurality of circuit units, each circuit unit is defined to have a plurality of the states, where each state comprises a set of states of the sequential circuit, the sets of states are assigned to the plurality of cascaded circuit units on the basis of the assigned levels such that at least two states of the circuit unit are subsets of a set of states of an immediately preceding circuit unit in the cascade, where the subsets are a cover of the set, and at least one circuit unit has a state which is a set of states of an immediately preceding circuit unit in the cascade, and next sets of states for the circuit unit are determined using the functions and the states of a proceeding circuit unit in the cascade.
In this aspect of the present invention an input can comprise any number of bits which are input within an instance in time. Where there are no transitions between states for an input the functions need not be defined.
The term “logic” is used to describe the usual circuit components used to build sequential circuits and includes logic gates and memory devices for example.
Thus, in this aspect of the present invention, extra states are added to at least one circuit unit and instead of using wires to pass states of one circuit unit to another circuit unit so that intermediate circuit units are by passed, logic is used within the intermediate circuit units to store and thereby pass on the states of the proceeding circuit units. In this way the wiring required is reduced and instead extra logic may be added if necessary into the intermediate circuit units thereby increasing the number of states of those intermediate circuit units.
Another aspect of the present invention provides a method and apparatus wherein the functions defining all the transitions from a current state to a next state of the logic circuit caused by a single input to the logic circuit are determined, sets of states which comprise possible states of the logic circuit are determined using the functions thereby ensuring that the sequences of actions which cannot possibly take place are not defined, and levels are assigned to the sets, where each level corresponds to one of the cascaded plurality of the said units, the sets of states are assigned to the cascaded circuit units on the basis of the assigned levels, information on the states of the preceding circuit units are passed along the cascade, and determining next states for the sequential circuit components using said functions and the states of preceding sequential circuit components in the cascade.
In accordance with this embod
Automatic Parallel Designs Limited
Schwegman Lundberg Woessner & Kluth P.A.
Speight Jibreel
LandOfFree
Method of generating finite state data for designing a... 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 of generating finite state data for designing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of generating finite state data for designing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876050