Electronic digital logic circuitry – Function of and – or – nand – nor – or not – Field-effect transistor
Reexamination Certificate
2001-05-11
2002-11-26
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Function of and, or, nand, nor, or not
Field-effect transistor
C326S093000, C326S112000, C326S119000
Reexamination Certificate
active
06486709
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to the design of digital circuits. More specifically, the present invention relates to a method and an apparatus for asynchronously distributing data to multiple destinations within a digital circuit.
2. Related Art
Finite state machines are familiar to every designer of computer equipment. They are easy to describe and generally easy to implement. Such a machine can be in any one of a number of “states”. Most implementations use a set of “state flip-flops” to hold the present state of the finite state machine.
For each state there are a set of conditions that will cause the finite state machine to change from that state to some other state. The conditions examined in each state may be unique to that state or shared with other states. The state to which the device changes depends on the state it is in, the conditions examined in that state, and which conditions are TRUE.
For example, a simple up-down counter is a finite state machine. Its states are the finite number of count values that it can hold. The conditions examined in each state are “count up” and “count down”. The up-down counter advances from its present state to the next higher count value when it gets the “count up” condition and advances to the next lower count value when it finds the “count down” condition. Depending on the design it may have a highest state in which it can only count down or a lowest state in which it can only count up or both.
Finite state machines typically use externally-clocked flip-flops to hold their state. Logic elements examine the conditions pertinent to the present state, and upon the arrival of each external clock pulse, set or clear selected clocked flip-flops to establish the next state. The design of such externally-clocked finite state machines is relatively easy, because all flip-flops change, if at all, only in response to the same external clock signal. Thus, for example, it is acceptable to change the state of several flip-flops at once, for example as happens in a binary counter when the “carry” passes through several stages, returning them all to the “zero” state. Were the flip-flops of the counter not clocked externally, the process of changing several flip-flops might cause the counter for a short interval to assume one or more intermediate states outside the proper binary sequence.
Indeed, some simple finite state machines, including binary counters are often built without an external clock for their flip-flops. In such counters, called “ripple counters,” the state flip-flops that hold the count each act independently. The flip-flop holding each bit of the count changes its state in response to changes from “one” to “zero” in the flip-flop that holds the bit representing half its value. Thus, for example, when a six bit ripple counter changes from 001111 to 010000, it will momentarily assume the states 001110, 001100, 001000, 010000 in rapid succession even though they are out of sequence. It is well known to those familiar with ripple counters that one must exercise care in their application because such FALSE states appear in their flip-flops, albeit for very short intervals of time. For finite state machines of any complexity, the simplicity of externally-clocked flip-flops is much preferred.
One aspect of all finite state machines involves the mapping of the allowed states of the machine onto the possible states of the flip-flops that retain the state. Such a mapping is called the “state encoding” used for the finite state machine because it defines the meaning of each possible state of the flip-flops. The encoding may also rule out certain combinations of flip-flop states as outside the range permitted for that finite state machine.
There are two particularly simple encodings. First, some finite state machines use a “one-out-of-N” encoding in which only one state flip-flop is “set” for each state. This encoding rules out the state with no state flip-flops set as well as all states with more than one state flip-flop set. With the one-out-of-N encoding, each change of state sets the state flip-flop associated with the new state and clears the state flip-flop associated with the old state. The one-out-of-N state encoding, though simple, is impractical for finite state machines with large numbers of states.
A second simple state encoding is a binary state encoding. In this state encoding each state is defined by a binary combination of state flip-flops that are set and that are clear. The binary encoding permits all combinations. This encoding is suitable for some finite state machines such as the binary counter already mentioned. It has the problem, however, that some state changes may require simultaneously setting many state flip-flops and clearing many others. The need to change many state flip-flops simultaneously renders binary encoding unsuitable for some applications. Designers have learned to choose encodings suitable to the needs of each particular application.
Finite state machines use complex logic elements to control the set and clear functions of individual flip-flops. These conditions cause “transitions” in the state of the finite state machine. The collection of conditions that must be TRUE to cause a particular transition must first be combined by a logical AND function. The output of this logic function will be TRUE when all relevant conditions are TRUE. Such a function indicates an impending state transition. Next, depending on the particular encoding used, several state flip-flops may have to change for such a state transition, some being set and some being cleared. The state transition logic must deliver its output to all such state flip-flops. Finally, it is likely that several transition functions apply to some state flip-flops. Such multiple transition functions must be combined with logical OR circuits to drive the inputs of the externally-clocked state flip-flops.
In spite of the complexity of such finite state machine implementations, they are so familiar to designers today that they are widely used. Indeed there are even computer automated design methods to help designers develop the required logic from equations describing the desired behavior. The software commonly used to design finite state machines depends on the use of externally-clocked flip-flops as the medium for holding the state.
The methods currently in use for designing finite state machines evolved over a long period of time. They were developed initially for use in machines built from vacuum tubes or even earlier for machines built from relays. They have served well into the era of transistor machines, but only to the extent that the more modern technologies are used in ways similar to those of the older technologies. Thus, the use of clocked flip-flops to hold state, for example, is a form that has survived several changes in the circuit elements and circuits used to implement such flip-flops.
Now, however, most digital computing devices use complementary metal oxide semiconductor (CMOS) circuits. In current CMOS circuits the cost of wires rather than the cost of logic gates dominates area, power consumption and performance. Almost all the space in a modern CMOS circuit is occupied by interconnect wiring; the transistors forming the logic gates generally fit underneath the wires required to interconnect them. The power consumption of the circuit is dominated by the need to put electrical charge onto the wires and later to remove it. The performance of the circuits is limited largely by the time it takes to charge and discharge the wires.
Moreover, in CMOS circuits, electrical capacitance can serve a state-holding function that previously had to be done with logic elements formed into flip-flops. Indeed, the dynamic random access memory (DRAM) industry has honed to a fine level the use of capacitance to store information. In a DRAM the electrical charge stored on a tiny capacitor serves to record each bit of information. However, in other CMOS circuits, the charge on any wire can also serve to store information
Ebergen Josephus C.
Sutherland Ivan E.
Tokar Michael
Tran Anh
LandOfFree
Distributing data to multiple destinations within an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributing data to multiple destinations within an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributing data to multiple destinations within an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2940589