Background of the Invention
This invention relates to a binary updown counter, and more particularly to a pipeline counter with a reduced number of logic operations that can be implemented with regular, simple, expandable and, therefore, suitable architecture for very large scale integrated circuit (VLSI) implementation.
Large binary updown counters are widely used in digital circuits. Examples include the controller design of a servomotor or the correlator part of very long baseline interferometry. Shown in FIG. 1 is a typical prior-art VLSI design of an up counter which may be used as a model for an updown counter. A single one-bit register labeled R and half adder labeled H is required for each stage (order). The pulses to be counted are applied to the sum input terminal(s) of the half adder for the least significant stage of the counter. The true output (1) of the register is applied to the other input terminal of the half adder through a delay element D. The carry output (C) of the half adder is applied to the sum input of the next stage of higher order.
Such a counter may be readily expanded by replicating the one-bit stage. To adapt that design for an updown counter, only two one bit registers and a half adder are needed in each stage of an n-bit counter, and its expansion to more bits is very easy and straight forward. However, for it to be adapted to also counting down, a fixed value (bias) is added to the sum. Therefore, the sum "zero" represents the middle value of the range of the counter, and the smallest negative number is represented by "zero." Also, it takes n clock times to perform one counting operation in the worst case because of the ripple-carry feature.
To avoid the ripple-carry time for faster counting, it has been common to apply the input pulses simultaneously to all stages through AND gates, but the number of inputs to each gate increases as the size of the counter is increased. And of even more significance is the fact that each stage is different so that expansion by mere replication is no longer possible.
Summary of the Invention
Because of the need to avoid the ripple-carry feature, and retain the ability to replicate stages, a new design of a large binary updown counter is required. In accordance with this invention, each stage of a clocked binary updown counter is defined by the Boolean logic equation:
where A.sub.n (t) denotes the value of the nth bit of the updown counter clocked at time t. Also in Eq. (1), the symbol .sym. denotes the "exclusive OR" operation, the symbol ".multidot." denotes the "AND" operation and the symbol "+" denotes the "inclusive OR" operation.
The input to the counter has three values represented by two binary signals U and D. If U=0 and D=1, then the input is "-1". If both U and D equal zero, then the input is "0". And if U=1 and D=0, then the input is "+1".
In Eq. (1), P.sub.n represents a product of A.sub.k 's for 1.ltoreq.k.ltoreq.n-1, while Q.sub.n is the product of A.sub.k 's for 1.ltoreq.k.ltoreq.n-1, where A.sub.k is the complemented value of A.sub.k. Both P.sub.n and Q.sub.n are expressed as the following two equations:
Equations 2a and 2b can be rewritten in recursion form as
and
with the values P.sub.1 =1 and Q.sub.1 =1 for the first stage.
The design of this new updown counter is simple, regular and expandable. Also, only one clock time is needed to perform one counting operation. Using this new architecture, it has been verified that a 64-bit binary updown counter can be put readily on a single VLSI chip with current NMOS technology. An example describing the pipeline architecture as well as the simplicity of each basic cell of this new counter is illustrated completely for a 3-bit counter which may be readily expanded to the more general case of an n-bit counter.
The novel features that are considered characteristic of this invention are set forth with particularity in the appended claims. The invention will best be understood from the following description when read in connection with the accompanying drawings.
Brief Description of the Drawings
FIG. 1 is a diagram of a prior-art up counter using a single one-bit register and a half adder per stage.
FIG. 2 is a logic diagram of a basic cell of the n-bit updown counter of FIG. 3 which implements Eq. (1).
FIG. 3 is a logic diagram of a basic cell of the n-bit updown counter of FIG. 2 which implements Equation (1).
FIG. 4 is a logic diagram of a one-bit, two-phase shift register used in the basic cell shown in FIG. 3.
Description of Preferred Embodiments
Referring now to FIG. 2 of the drawings, an N-bit updown counter is comprised of a plurality of cells or stages 1, 2 . . . N, each implemented in accordance with Eq. (1) above in a manner shown in FIG. 3. The input has three values, namely -1, 0, and +1. These three values are represented by binary coded signals d.sub.1 d.sub.2 which are converted into up (U) and down (D) count control signals in accordance with the following truth table:
It is evident that a data converter is not needed if the input values are represented in accordance with this d.sub.1 d.sub.2 code. However, it is required in general to match the signal level of the counter to the external system, and to provide input signals U, D capable of driving n cells in parallel. In that case, the data converter is composed of simply a suitable pair of driver amplifiers. If the input value is +1, U=1 and D=0. If the input value is -1, then U=0 and D=1. If the input value is zero, both U and D are zero, and the contents of the counter should remain unchanged. Otherwise A.sub.n is not equal to A.sub.n (t-1), but changes from 1 to 0, or 0 to 1.
It is easily verified from Eq. (1) that when U=D=0, the output of cell n is A.sub.n (t)=A.sub.n (t-1), where n is any one of the cells in the counter. This is so because when both U and D are zero, the second term of Eq. (1) is zero, and by the property of "exclusive OR," the output of the cell is equal to the remaining term A.sub.n (t-1).
On the other hand, if the input value is +1, then U=1 and D=0. The second term of Eq. (1) is then changed to (1.multidot.P.sub.n)+(O.multidot.Q.sub.n)=P.sub.n. This equals 1 if P.sub.n =1 which implies that A.sub.n =A.sub.n-1. In counting up, the value of the nth bit changes fron zero to one if the value of the input to the counter is a 1, and the values of cells 1 to n-1 are all ones. This fact is truthfully reflected by Eq. (1). A similar argument applies to the case when the input value to the counter is a -1, i.e., the counter is counting down.
Assuming a 3-bit binary updown counter, the following truth table which defines its operation is as follows:
In the fourth row of the table, D=0, U=1, A.sub.3 (t)=0, A.sub.2 (t)=1 and A.sub.1 (t)=1. This corresponds to the case for which the contents of counter is decimal three in binary notation and the input is +1. Obviously, the next count should equal four, namely, A.sub.3 (t+1)=1, A.sub.2 (t+1)=0 and A.sub.1 (t+1)=0. Substituting these values of A.sub.i, for i=1, 2, 3, as well as the values U=1, D=0 into Eq. (1), yields the following results: ##EQU1## where P.sub.3 =A.sub.1 .multidot.A.sub.2 =1 and Q.sub.3 =A.sub.1 A.sub.2 =0. The rest of the states of the table can be verified in a similar manner.
In a VLSI architecture of the present invention, an N-bit binary updown counter is comprised of N basic cells as well as a data converter (data mapping programmable logic array) for the input, as shown in FIG. 2, with each cell defined by Eq. (1) conforming to the logic diagram of FIG. 3. The up and down control signals U and P are connected to each cell as a direct input, while the cells are connected in cascade with inputs Q.sub.i and P.sub.i from a preceding stage and outputs Q.sub.i+1 and P.sub.i+1 to the next stage, and a count output A.sub.i from a one-bit register RA.sub.i. The outputs Q.sub.i+1 and P.sub.i+1 are stored in one-bit registers RQ.sub.i+1 and RP.sub.i+1 of the next stage. The inputs to the ith basic cell are U, D, P.sub.i and Q.sub.i while the outputs are U, D, P.sub.i+1, Q.sub.i+1 and A.sub.i. Outputs P.sub.i+1 and Q.sub.i+1 are obtained by the calculation of Eqs. (2a) and (2b). For an N-bit binary updown counter, N identical basic cells are required in the design.
Referring to FIG. 3, the basic cell consists of three one-bit shift registers, as noted above, where registers labeled RQ.sub.i and RP.sub.i are used to store inputs Q.sub.i and P.sub.i respectively. Register RA.sub.i stores the output A.sub.i. The output of RA.sub.i is sent to an exclusive OR circuit (XOR) for calculating the value of A.sub.i (t+1). In the meantime, A.sub.i and its complement .sub.i formed by an inverter 10 are sent to two AND gates 11 and 12 for the calculation of P.sub.i+l and Q.sub.i+1. Two AND gates 13 and 14 and an OR gate 15 are provided to perform the Boolean logic (U.multidot.P.sub.n)+(D.multidot.Q.sub.n). A two-phase nonoverlapping clock is applied to each register as shown in FIG. 4 which illustrates a one-bit NMOS shift register. That NMOS design is used to implement each of the one-bit registers RQ.sub.i, RP.sub.i and RA .sub.i shown in FIG. 3 in order to simplify timing control.
As was described previously, the values of, are P.sub.1 =Q.sub.1 =1. Therefore the inputs to registers of the first basic cell RP.sub.1 and RQ.sub.1 are tied to VDD which is always at the "1" logic level. A.sub.i, for 1.ltoreq.i.ltoreq.n are the outputs representing the results of counting. The final value is obtained N clock periods after the last input d.sub.1, d.sub.2 into the counter. In that regard, it should be noted that the architecture of the counter is aptly described as a pipeline architecture in that while inputs d.sub.1, d.sub.2 may be processed in sequence at the two-phase clock rate, the counting operation proceeds, and intermediate values are stored in registers RA. Then N clock periods later, after the last input d.sub.1, d.sub.2 has been processed, the registers RA contain the final count of d.sub.1, d.sub.2 inputs.
Although particular embodiments of the invention have been described and illustrated herein, it is recognized that modifications and variations may readily occur to those skilled in the art. Consequently, it is intended that the claims be interpreted to cover such modifications and variations.