Circuit for Prevention of the Metastable State in Flip-Flops

This invention relates generally to improved apparatus and methods for synchronizing signals in a data processing system.

In a data processing system, timing is typically provided by one or more system clocks which are used for clocking signals into the various logic and storage elements of the system, such as flip-flops and latches. When an input signal applied to a system element is properly synchronized with an input clock pulse, reliable operation can readily be provided, since the resulting clocked signals applied to the element will have a predictable duration and energy level.

In modern day computer systems, provision must be made for properly handling asynchronous signals as well as synchronous signals, since most clocked central processors are required to interact with other systems, subsystems or peripherals having independent clocking. The central processor typically uses a clock pulse to interrogate the input line on which an asynchronous signal is applied. Since the clock pulse and the asynchronous signal have no defined relationship, the resulting effect may be a misshapen pulse (commonly referred to as a split pulse or runt pulse) which can produce unreliable results.

A well known solution to the above problem is to apply the clock pulse and the asynchronous signal to a synchronizing element, such as a flip-flop or latch. The assumption is then made that, even if the clock pulse and asynchronous signal have little overlap, the flip-flop or latch will nevertheless arrive at a stable state within some known minimum time after the clock pulse is applied, at which time the output of the synchronizing element may then be used as a properly synchronized logical pulse.

The assumption that the synchronizer element will always provide a stable output after some known minimum period of time has been found to be unreliable because, for certain pulse energy levels, a metastable state is produced which remains for an indeterminate period of time. As a result, it has been found necessary in the design of computer systems to allow a significantly greater waiting time before using the output of the synchronizing element in order to obtain an acceptable error rate. This problem has been considered, for example, in the following articles: T. J. Chaney, et al., "Anomalous Behaviour of Synchronizer and Arbiter Circuits", IEEE Transactions on Computers, April 1973, pp. 421-2; and G. R. Couranz, et al., "Theoretical and Experimental Behaviour of Synchronizers Operating in the Metastable Region", IEEE Transactions on Computers, Vol. C-24, No. 6, June 1975. Both of these articles suggest that the problem be solved by appropriately increasing the wait time before using the output of the synchronizing flip-flop.

The above solution to the synchronizer instability problem whereby the synchronizer waiting time is increased to obtain an acceptable error level has the disadvantage of limiting the transfer data rate that can be provided. Another difficulty is that considerable effort must sometimes be expended in order to determine what waiting time will provide an acceptable error rate in a given system.

In accordance with the present invention, I have discovered that by injecting a relatively small amount of energy into the synchronizing element in an asymmetric fashion and at a slower rate than the element's reaction time, the occurrence of a balanced or metastable condition can be inhibited. As a result, there is no need to provide the additional waiting time normally required to overcome the above described synchronizer instability problem, thereby permitting greater data transfer rates to be obtained.

Accordingly, it is a broad object of the present invention to provide improved apparatus and methods for synchronizing asynchronous signals in a data processing system.

Another object of the invention is to provide apparatus and methods for increasing the data transfer rate between independently clocked systems.

A more specific object of the invention is to provide apparatus and methods for inhibiting the occurrence of a balanced or metastable condition in a synchronizing element so as to obviate the need for providing an additional waiting time before the output of the synchronizing element can be used.

An additional object of the invention is to provide for accomplishing the above objects in a relatively simple and inexpensive manner.

The specific nature of the invention as well as other objects, features, advantages and uses thereof will become evident from the following description of a preferred embodiment along with the accompanying drawings .

FIG. 1 is a schematic electrical circuit diagram of a prior art synchronizing circuit.

FIG. 2 is a series of timing graphs for use in describing the operation of the circuit of FIG. 1.

FIG. 3 is a schematic electrical circuit diagram of a preferred embodiment of a synchronizing circuit in accordance with the invention.

FIG. 4 is a series of timing graphs for use in describing the operation of the circuit of FIG. 3.

FIG. 1 illustrates how synchronization is conventionally provided using a flip-flop 10. As shown, an asynchronous signal S is applied to an input J of flip-flop 10 and a clock pulse C is applied to a clock input CK of flip-flop 10, the output of flip-flop 10 being obtained at an output Q which is applied to an AND gate 12 along with a delayed clock C'.

The timing graph of FIG. 2 illustrates how the prior art circuit of FIG. 1 handles the synchronizer instability problem occurring when the input clock C (graph A) and the asynchronous input signal S (graph B) occur at times such that only a runt pulse P (graph C) is produced within flip-flop 10 for switching purposes. This runt pulse P causes a metastable state to be maintained which produces an indeterminate value on output Q as illustrated in graph D in FIG. 2. If specific circuit parameters are known (which is not always the case), it is possible to calculate the probability of these metastable states, and thus obtain a prediction as to how much waiting time should be provided before using the signal appearing at the output Q of the flip-flop 10 in order to obtain a required error rate. Accordingly, as illustrated in graph E in FIG. 2, the delay t.sub.d provided for the delayed clock pulse C' applied to AND gate 12 is chosen to be such that the probability of obtaining a valid signal at the flip-flop output Q will be sufficiently high to provide the required error rate. Graph F illustrates the resulting output from AND gate 12.

Referring next to FIG. 3, a preferred embodiment of the present invention is illustrated which provides for proper synchronization of an asynchronous signal while substantially eliminating any need for an additional waiting period as is required for the prior art circuit of FIG. 1. Basically, this most important feature is achieved by injecting a relatively small amount of energy into a synchronizing element in an asymmetric fashion and at a slower rate than the element's reaction time. The manner in which this is accomplished in the preferred embodiment illustrated in FIG. 3 will now be described.

The synchronizing element in the preferred embodiment of FIG. 3 is illustrated as being the same conventional flip-flop 10 as is shown in FIG. 1. A suitable flip-flop which may, for example, be used is one of the two flip-flops provided on a standard 74S109 integrated circuit chip containing two J-K flip-flops, each having a 5-7 nanosecond reaction time (about 140 to 200 megahertz). An appropriate injection signal for the preferred embodiment of FIG. 3 is provided by a ring oscillator 16 which may, for example, be a 50 megahertz ring oscillator such as is contained on a standard 74S04 integrated circuit chip. Preferably, the ring oscillator 16 has a frequency no greater than approximately one-half of the reaction time of the flip-flop 10. The ring oscillator 16 provides a distorted sine wave output which is injected into the inverse Q output of the flip-flop 10 through a resistor 18. The resistor 18 is chosen so that the magnitude of the ring oscillator signal which is applied to the Q flip-flop output does not affect the normal switching operation of the flip-flop 10. For example, where the logical levels are 3 volts and 0.3 volts and a 74S109 flip-flop and a 74S04 ring oscillator are used, a suitable value for the resistor 18 is 1780 ohms. This results in a 200 millivolt, 50 megahertz distorted sine wave signal I being applied to the Q flip-flop output. It has been found that this signal applied to Q does not interfere with normal flip-flop operation, yet inhibits the maintenance of a balanced or metastable state of the flip-flop 10. Consequently a valid signal will be obtainable at the Q output of flip-flop 10 in the synchronizing circuit of FIG. 3 after the normal flip-flop settling time without having to provide an additional waiting time, as is required in the prior art synchronizing circuit illustrated in FIG. 1. Furthermore, since the preferred embodiment of the synchronizing circuit illustrated in FIG. 3 does not permit a balanced or metastable state to be maintained, the error rate of the system will not be dependent upon the design of the synchronizing circuit. As pointed out previously, the prior art synchronizing circuit illustrated in FIG. 1 requires that the waiting period be chosen based on probability considerations to provide a desired error rate in order to take into account the fact that the metastable state may remain for an indefinite period of time.

The timing graphs of FIG. 4 illustrate typical operation of the preferred synchronizing circuit illustrated in FIG. 3. As in FIG. 2, graph A illustrates the clock C and graph B illustrates an input asynchronous signal S which occurs at a time such that a split or runt pulse P (graph C) is produced within flip-flop 10 for switching purposes (FIGS. 1 and 3). It will be remembered that, in the prior art synchronizing circuit illustrated in FIG. 1, such a runt pulse P as illustrated in graph C can cause a metastable state to be maintained by the flip-flop 10 for an indefinite period of time (see graph D of FIG. 2).

In the preferred synchronizing circuit of the invention illustrated in FIG. 3, on the other hand, the injected signal I applied to the Q flip-flop output will not permit a balanced or metastable state to be maintained. A typical injection signal I is shown in graph E in FIG. 4. Thus, as illustrated in graph D of FIG. 4, if the runt pulse P in graph C is insufficient to cause the flip-flop 10 to switch, the output Q will remain in its "0" or "false" state until the next occurring clock, at which time the flip-flop 10 will then switch to produce a "1" or "true" signal at the Q output. However, if the runt pulse P in graph C of FIG. 3 is sufficient to cause switching of the flip-flop 10, the flip-flop output Q will then switch to a "1" or "true" state in substantially the normal settling time expected for the flip-flop 10, as illustrated in graph D' in FIG. 3. At worst, only a relatively brief period of metastability will occur depending upon the characteristics of the particular injected signal I applied to the Q flip-flop input.

It will be understood that the resulting synchronized "1" or "true" signal appearing at the Q flip-flop output (as illustrated in graphs D and D' in FIG. 4) in response to the detection of the asynchronous input signal S may be employed in a conventional manner as a synchronized signal for use by a data processing system which supplied the clock C. It will also be understood that this synchronized signal at the flip-flop output Q is also employed in a conventional manner (not shown) to prevent interrogation of the asynchronous input line until the system is ready to receive a new asynchronous signal and also to cause a reset signal to be applied to the flip-flop 10 preparatory to synchronizing the next occurring asynchronous signal.

Although the above description has been primarily concerned with a particular preferred embodiment of the invention, it is to be understood that many modifications and variations in construction and use are possible which are within the inventive contribution disclosed herein.

For example, although the injected signal I in FIG. 3 is illustrated as being applied to the Q input of the flip-flop 10, it may also be applied to other inputs of the flip-flop 10. Also, other types of synchronizing elements may also be employed. The important requirement is that the asymmetry, frequency and magnitude of the injected signal be such that the maintenance of a balanced or metastable state of the synchronizing element is prevented (or reduced to an acceptable time period) without interfering with the normal operation of the synchronizing element.

The present invention should thus be considered as encompassing all possible modifications and variations coming within the scope of the invention as defined by the appended claims.