Electronic digital logic circuitry – Multifunctional or programmable – Sequential or with flip-flop
Reexamination Certificate
1999-09-29
2001-09-18
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Sequential or with flip-flop
C327S208000
Reexamination Certificate
active
06292023
ABSTRACT:
RELATED APPLICATIONS
Subject matter relating to that of the present application is presented in U.S. Patent applications filed on the same day as this application: “Spiking Neuron Circuit” by R. Sarpeshkar; and “Edge-Triggered Toggle Flip-Flop Circuit,” by R. Herrera and R. Sarpeshkar. These applications are assigned to the assignee of the present application and are hereby incorporated by reference in the present application.
1. Field of the Invention
The present invention relates to electronic circuits, for implementing (usually complex) logical functions—including computers—as finite state machines. More particularly, the present invention relates to asynchronous finite state machines. Still more particularly, the present invention, in its various embodiments, relates to spike-triggered asynchronous finite state machines.
2. Background of the Invention
Finite State Machines are fundamental to all aspects of digital computation. All computers in use today may be viewed as nothing more than very complex finite state machines operating on inputs from memory. More generally, a finite state machine (or sequential machine) may be considered to be a machine having a number of states, with inputs and outputs, and in which transitions between states is determined by a current state and inputs. See, for example,
Dictionary of Computing,
Oxford University Press, Oxford, Third Edition, 1990.
While finite state machines have been designed for many particular applications, most are designed to respond to synchronous signals, i.e., clocked inputs and state transitions. When asynchronous inputs are received, some finite state machines known in the art provide specific adjustments or compensation techniques to accommodate such inputs in primarily synchronous contexts. Such accommodations to asynchronous behavior impose restrictions on design flexibility and penalties measured, for example, in increased complexity. Many system applications, including some modeled after animal sensory and brain functioning, are inherently asynchronous over all or a significant portion of their processing activities, and so are not readily represented using standard synchronous finite state machine techniques.
In common practice, n-state finite state machines are realized with log
2
n bistable elements that code the present state and receive periodic (synchronous) trigger signals. To trigger a change to the next state, a decoded representation of the current state is logically combined with zero or more logic inputs. Therefore, while the use of log
2
n binary elements provides an efficient coding scheme in prior art finite state machines, complexity of decoding of state information increases in proportion to the number of states n.
State encoding in prior art n-state finite state machines employing log
2
n bistable elements permits exactly one stable state to exist at a time. However, certain logical schemes and applications profit from so-called parallel-evolution processing in which one or more initial conditions (present states) are allowed. See for example, Zhang J., and Kumar S. (1997), Detection of convergent and parallel evolution at the amino acid sequence level.
Mol. Biol. Evol.
14: 527-536. Other parallel evolution applications include processing of weights or organizations in neural network applications. In parallel-evolution processing, transitions can occur to fewer succeeding states (convergent evolution) or to a greater number of succeeding states (divergent evolution). As is readily apparent, state encoding using the prior art log
2
n binary elements does not readily lend itself to parallel evolution processing for important classes of applications.
SUMMARY OF THE INVENTION
Limitations of the prior art are overcome and a technical advance in Finite State Machine design and use are achieved in accordance with the present invention, illustrative embodiments of which are described below.
Briefly, embodiments of the present invention feature finite state machines in which n discrete states of the machine are encoded using a set of n bistable elements. Though conventional use of log
2
(n)-element binary state encoding would appear to offer complexity advantages, n-element state coding in accordance with present teachings permits simplified decoding of states in the machine. Resources saved in the decoding of the states, which scale in proportion to n in conventional machines, more than compensates for resources used in n-element state encoding.
Further, the n-element encoding allows for the simultaneous evolution of multiple initial-condition states in the machine in a concurrent fashion. Thus, for example, n bistable elements, with n=8, produces state information illustratively represented (for an arbitrarily selected state 2) as 00100000. But in other circumstances based on parallel evolution, successive states are illustratively represented as 00000010, 00110000, 11000100, 00001000, or any other defined-state representation. In this illustrative state sequence representation, the first two transitions reflect divergent parallel evolution (one-state to two-state and two-state to three-state), while the third transition reflects convergent (three-state to one-state) parallel evolution.
In accordance with another aspect of illustrative embodiments of the present invention, transitions between discrete states of a finite state machine are advantageously executed on positive edges of asynchronous spiking inputs to the finite state machine. Thus, unlike conventional synchronous machines, no external clock is necessary for machine operation; transitions are self timed by such asynchronous spiking inputs. Moreover, an arbitrary number of spiking inputs may be applied at the same time.
In accordance with yet another aspect of illustrative embodiments of the present invention, a uniform transition circuit directs transitions between states in a finite state machine. Thus, a finite state machine having many states is conveniently implemented using many copies of this transition circuit,—each having its particular set of inputs.
REFERENCES:
patent: 4648105 (1987-03-01), Priebe et al.
patent: 4740891 (1988-04-01), Kirkpatrick
patent: 5097151 (1992-03-01), Eerenstein et al.
patent: 5412795 (1995-05-01), Larson
patent: 5469079 (1995-11-01), Mahant-Shetti et al.
patent: 5612632 (1997-03-01), Mahant-Shetti et al.
patent: 5706473 (1998-01-01), Yu et al.
patent: 5789956 (1998-08-01), Mahant-Shetti et al.
Herrera Ruben
Sarpeshkar Rahul
Agere Systems Guardian Corp.
Chang Daniel D.
Ryan William
Tokar Michael
LandOfFree
Spike-triggered asynchronous finite state machine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spike-triggered asynchronous finite state machine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spike-triggered asynchronous finite state machine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455215