Logic arrays are used in digital data processing systems to perform logic calculation or transformations; that is, to process data by furnishing data signal outputs which are determined by data signal inputs in accordance with prescribed logic transformation rules. For this purpose, programmed logic arrays (PLAs) provide an easily designed and well-structured alternative to random (individually distributed) combinatorial (or "combinational") logic devices. The advantages of a PLA stem from its compact integrated circuit layout and its ease of systematic design once the desired logic transformation rule or function (PLA's output vs. input) or "characteristic table" is prescribed. Also, because of a PLA's patterned array structure, redefinition of its logical transformation function can be as easily accomplished as modification of a conventional ROM (Read Only Memory) array, i.e., by modification of the pattern of array crosspoints at which cross-connecting elements or links are present vs. absent.
Internally, a conventional PLA comprises two logic array portions known as the AND plane (also known as the DECODER array portion) and the OR plane (also known as the ROM array portion). The AND and the OR planes are often realized by a pair of separate logic arrays each implementing a NOR function, since an AND followed by an OR function is logically equivalent to a NOR followed by a NOR function. The AND and OR planes are electrically connected together by paths or lines known as interconnecting (or intermediate) wordlines, say n in number. During operation, a sequence of PLA binary input data signal combinations is entered into the AND plane on a plurality of input signal lines, say N in number, in order to furnish a sequence of binary input combinations of input words--for example, each word formed by a binary bit string, such as (1,0,1 . . . 0,1,0), or binary digital bits, N in number--and a sequence of PLA binary output data signals or output words emanates in response thereto from the OR plane on a plurality of output signal lines, say P in number. When the PLA is adapted for use as a finite state machine, one or (typically) more of the binary output signals from the OR plane can be fed back as input bits to the AND plane. Both AND and OR planes, in certain specific embodiments, comprise orthogonal row and column lines mutually intersecting at crosspoints; and at each of the crosspoints is situated or is not situated a crosspoint cross-connecting link such as a transistor, depending upon the desired logic transformation function of the PLA.
The binary signal on a line carrying data in the PLA can be either logic HIGH, representing the binary digital bit ONE ("1"), or else logic LOW, representing the binary digital bit ZERO ("0"). Ordinarily, any given intermediate wordline (between AND and OR planes) will be logic HIGH (binary ONE or 1) if and only if the input word introduced on the input lines of the AND plane is a member of a set of given input words corresponding to that wordline. In a specific example, for purpose of illustration, the given intermediate wordline will be logic HIGH if and only if the input word is the bit string characterized by the first bit (I.sub.1) being logic HIGH (I.sub.1 =1), and the second bit (I.sub.2) being logic LOW (I.sub.2 =0), and the third bit (I.sub.3) being logic HIGH (I.sub.3 =1), . . . and the last bit (I.sub.N) being logic LOW; that is, if and only if I.sub.1 =1 and I.sub.2 =0 and I.sub.3 =1 . . . and I.sub.N =0, where N is the number of bits in the input word and hence I.sub.N is the last (N'th) bit. On the other hand, the output signal on a given output line (a given output bit) emanating from the OR plane is logic LOW if and only if any one or more of a given group of intermediate wordlines is logic HIGH, that is, for a specific example, if and only if the first wordline (W.sub.1) is logic HIGH, or the third wordline (W.sub.3) is logic HIGH, or the sixth wordline (W.sub.6) is logic HIGH; that is, the given output bit is ZERO when and only when W.sub.1 =1 or W.sub.3 =1 or W.sub.6 =1. In this way, the PLA supplies output words, each of length P, which are (Boolean) functions of the input words, each of length N.
In ordinary operation with a PLA, it is desired that the PLA should handle many input words in sequence, one input word after another; that is, the PLA should perform its prescribed transformation on many words of input data, one input word after another, and should deliver its corresponding output words in sequence, one output word after another. Accordingly, the PLA is supplied with data shifting means (shift registers) for repetitively temporarily storing and shifting (transferring) data into, through, and out of, the PLA--all in accordance with a suitable timing sequence, so as to avoid confusion of one word or set of data (say, old data) with another (say, new data) in the PLA. Moreover, the PLA must be able to receive each new input word and to deliver each new output word at appropriate respective moments of time or during appropriate time intervals, according to the system requirements of the rest of the data processing system in which the PLA operates. Such system requirements typically are "synchronous": that is, the PLA receives data from and delivers data to the rest of the system in response to (periodic) clock control timing, typically in the form of a sequence of clock pulses. In such a case, ordinarily the PLA can receive input data only during a first predetermined portion or phase of each cycle (period) of the clock control, and the PLA can deliver output data only during a second predetermined (in general, different) portion or phase of each such cycle of the clock. For example, if the clock has two phases (.phi..sub.1, .phi..sub.2) per cycle, then the PLA typically receives input data during one of the phases (.phi..sub.1) and delivers output data during the other of the phases (.phi..sub.2) of each cycle. Accordingly, the rate at which the PLA processes (receives and delivers) data is inversely proportional to the clock cycle time or period T of the control clock and is directly proportional to the clock frequency f=1/T.
The data shifting means required in a PLA ordinarily takes the form of a pair of clocked parallel registers for temporarily storing periodically shifting data. Each register typically takes the form of a group of flip-flop devices (each device being a pair of crosscoupled inverters, the output of one inverter being the input of the other) mutually arranged in parallel, that is, so that each entire binary word being processed by the PLA can be transferred (shifted) into, temporarily stored in, and transferred out of the register--all in response to a single clock cycle of the control timing supplied to the registers. The pair of registers is ordinarily connected and supplied with control timing so as to operate in a "master-slave" relationship, that is, one of the registers serving as the "master" register and the other as its "slave." By definition, the master receives data from an external source (such as another register) and its slave receives data from its master, all in response to control timing arranged so that when one of the registers (master or slave) can receive new data the other cannot.
Thus, for example, during a first phase of a cycle of the clock used to control the timing of both master and slave, data can enter into the master register but not into its slave, and during a second phase of the control cycle, data is shifted (entered) from the master into its slave register but then no data can enter into the master.
The U.S. patent application Ser. No. 448,002, filed by M. E. Thierbach on Dec. 8, 1982, entitled "Programmed Logic Array With Two-Level Control Timing," teaches that a PLA can operate at a faster rate of speed than in prior art (or can be built of larger size, and hence larger data handling capacity, and operate at the same rate) by inserting a pair of parallel registers in master-slave relationship on the intermediate wordline between the AND and OR planes of the PLA. The PLA then operates with two-level control timing; that is, data circulate through the PLA in two cycles of the control timing used to control the registers, rather than in one cycle as in prior art. On the other hand, although the PLA can then operate to yield output data at the faster rate, the time required for data to circulate through the PLA does not correspondingly decrease but remains essentially the same because it takes the two cycles of control timing for data to circulate through the PLA operating with two-level control timing.
U.S. Pat. No. 4,399,516 issued to D. E. Blahut et al on Aug. 16, 1983 entitled "Stored Program Control Machine," teaches that advantage can be gained when an input signal for an input register of a PLA is gated by a combinational logic device (such as an AND gate) with a WAIT signal. That is, for example, a HIGH level of input signal cannot be latched by the input register when the WAIT signal goes LOW ("unready"). When single-level control timing of the PLA registers is used as described in the aforementioned Blahut et al application, that is, when data circulate through the PLA in one cycle, then, if the WAIT signal goes "unready" at the beginning of a given clock cycle, the "unready" signal affects the output of the PLA at the end of the (same) given cycle. However, when a PLA operates with two-level control timing in accordance with the above-mentioned Thierbach application, then the "unready" signal affects the output of the PLA at the end of the second cycle (immediately following the first cycle) but does not affect the output of the PLA at the end of the first cycle. Thus a delay or time lag of a full cycle occurs before the "unready" signal affects the output of the PLA operating with two-level control timing. Accordingly, the output of the PLA in a given cycle cannot respond in a given cycle to a WAIT signal available for the PLA in the same cycle, but only to a WAIT signal available in the previous cycle. In other words, the PLA lacks a desirable same-cycle input-to-output response, i.e., same-cycle decision-making capability, in response to the WAIT signal.
The U.S. patent application Ser. No. 446,343, filed by M. L. Harrison et al on Dec. 2, 1982, entitled "PLA-Based Finite State Machine With Combinational Logic Control of Input Register Thereof" teaches that in certain cases the size of a PLA implementing a finite state machine (i.e., with feedback from output to input of the PLA) can be reduced, and hence its speed of operation can be increased, by inserting a combinational logic device (such as an AND gate) to gate (or "stop") the clock control signal of the input register of the AND plane of a PLA in response to an "unready" level of a WAIT signal applied to an input terminal of the logic device. Such cases arise where it is desired that the feedback state of the PLA should remain the same (should be "frozen"), because the rest of the system is not ready to supply new input data to the PLA or to utilize new output data from the PLA. Thus, for example, if at the commencement of a given cycle of single-level control timing (data circulate through the PLA in one cycle), the WAIT signal goes "unready", then the state of the machine of the previous cycle persists without change throughout the given cycle; that is, the machine is frozen beginning with the same cycle at the beginning of which the "unready" signal is available. However, when a PLA operates with two-level control timing in accordance with the above-mentioned Thierback application, then the state of the machine will not be frozen beginning with the same cycle. Instead, when an "unready" signal is applied at the beginning of a given cycle, then the state of the machine as of the next (future) cycle will be frozen--that is, the state of the machine (at the end) of the present cycle will in general be different from that (at the end) of the previous cycle, and only the state of the next cycle (as well as of still later cycles if the "unready" signal persists) will be the same as that of the present cycle. Thus, a delay or time lag of a full cycle occurs after commencement of the "unready" signal before the machine is frozen. Such a lag constitutes an undesirable delay in those cases where the "unready" signal signifies present unreadiness, for example, present unavailability of input to the PLA from the rest of the system. The PLA thus lacks a desirable same-cycle decision-making capability with respect to freezing in response to the WAIT signal. It would therefore also be desirable to have a means for freezing without delay a PLA implementing a finite state machine using two-level control timing, that is, for freezing the PLA feedback state during the same cycle in which the "unready" signal is available for application to the PLA.
Also, a similar problem arises in the case of a PLA with single-level control timing, i.e., a PLA which requires just one cycle for data to circulate through the PLA--such as, for example, the PLA described in a paper by E. Hebenstreit et al, entitled "High-Speed Programmable Logic Arrays in ESFI SOS Technology," published in IEEE Journal of Solid-State Circuits, Vol. SC-11, pp. 370-374 (1976), at p. 371. In such a case, an input signal for a given cycle of a PLA may not be available at the PLA (from a source of the input signal external to the PLA) until slightly after the beginning of that cycle and hence too late to be received by the input register of the PLA for response and utilization by the PLA during that cycle. Accordingly, it would be desirable to have a means for enabling a PLA operating with single-level control-timing to respond to such a late input signal during the same PLA cycle, that is, for enabling same-cycle response or decision-making in response to late arriving input signals.
USPTO Backgrounds
USPTO Backgrounds