Method and apparatus for N-nary incrementor

Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C708S493000

Reexamination Certificate

active

06347327

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital computing, and more particularly to an apparatus and method for an incrementor.
2. Description of the Related Art
An often-useful degenerate form of an adder is the incrementor, which adds a value of “1” (usually conditionally) to a numeric operand. Incrementors are particularly useful in some address generation situations where sequential addresses must be generated efficiently. Because the incrementor only has one true operand, it is simpler in structure than a full adder, and a 32-bit incrementor can be built in only two logic levels, in contrast to a full adder. (An example of an adder utilizing three logic levels is set forth in co-pending application, U.S. Pat. Ser. No. 09/206,463 entitled “Method and Apparatus for 3-stage 32-bit Adder/Subtractor,” now U.S. Pat. No. 6,269,387, hereinafter referred to as “the 3-stage Adder Application.”
Traditional Binary Addition
In most computer systems, addition and subtraction of numbers is supported. In systems using traditional binary logic, the truth table for one-bit addition is set forth in Table 1.
TABLE 1
A
B
A + B
0
0
0
0
1
1
1
0
1
1
1
 0*
In the last row of Table 1, a carry condition occurs. That is, the result is 0, but a carry into the next-higher-order bit position, corresponding to a decimal value of 2, has conceptually occurred.
In addition to single bits, the addition operation may be performed on multiple bits, including addition of two two-bit values. The truth table for such an operation is set forth in Table 2, where the first operand A is a two-bit value comprising bits A
0
and A
1
. The second operand, B, is a two-bit value comprising bits B
0
and B
1
.
TABLE 2
A =
B =
Decimal
Decimal
A + B =
A
1
A
0
B
1
B
0
Value
Value
A + B
Dec. Value
0
0
0
0
0
0
00
0
0
0
0
1
0
1
01
1
0
0
1
0
0
2
10
2
0
0
1
1
0
3
11
3
0
1
0
0
1
0
01
1
0
1
0
1
1
1
10
2
0
1
1
0
1
2
11
3
0
1
1
1
1
3
 00*
0
1
0
0
0
2
0
10
2
1
0
0
1
2
1
11
3
1
0
1
0
2
2
 00*
0
1
0
1
1
2
3
 01*
1
1
1
0
0
3
0
11
3
1
1
0
1
3
1
 00*
0
1
1
1
0
3
2
 01*
1
1
1
1
1
3
3
 10*
2
Each output value in the “A+B” column of Table 2 indicated with an asterisk denotes a carry condition where a one has conceptually carried into the next-higher-order bit (the bit position corresponding to a decimal value of four).
N-nary Logic
The present invention utilizes N-nary logic. The N-nary logic family supports a variety of signal encodings, including 1-of-4. The N-nary logic family is described in a copending patent application, U.S. patent application Ser. No. 09/019,355, filed Feb. 5, 1998, now U.S. Pat. No. 6,066,965, and titled “Method and Apparatus for a N-Nary logic Circuit Using 1-of-4 Signals”, which is incorporated herein for all purposes and hereinafter referred to as “The N-nary Patent.” In 1-of-4 encoding, four wires are used to indicate one of four possible values. In contrast, traditional static design uses two wires to indicate four values, as is demonstrated in Table 2. In Table 2, the A
0
and A
1
wires are used to indicate the four possible values for operand A: 00, 01, 10, and 11. The two B wires are similarly used to indicate the same four possible values for operand B. “Traditional” dual-rail dynamic logic also uses four wires to represent two bits, but the dual-rail scheme always requires two wires to be asserted. In contrast, N-nary logic only requires assertion of one wire. The benefits of N-nary logic over dual-rail logic, such as reduced power and reduced noise, should be apparent from a reading of The N-nary Patent.
All signals in N-nary logic, including 1-of-4, are of the 1-of-N form where N is any integer greater than one. A 1-of-4 signal requires four wires to encode four values (0-3 inclusive), or the equivalent of two bits of information. More than one wire will never be asserted for a 1-of-N signal. Similarly, N-nary logic requires that a high voltage be asserted for all values, even 0.
Any one N-nary gate may comprise multiple inputs and/or outputs. In such a case, a variety of different N-nary encodings may be employed. For instance, consider a gate that comprises two inputs and two outputs, where the inputs are a 1-of-4 signal and a 1-of-2 signal and the outputs comprise a 1-of-4 signal and a 1-of-3 signal. Various variables, including P, Q, R, and S, may be used to describe the encoding for these inputs and outputs. One may say that one input comprises 1-of-P encoding and the other comprises 1-of-Q encoding, wherein P equals two and Q equals four. Similarly, the variables R and S may be used to describe the outputs. One might say that one output comprises 1-of-R encoding and the other output comprises 1-of-S encoding, wherein R equals four and S equals 3. Through the use of these, and other, additional variables, it is possible to describe multiple N-nary signals that comprise a variety of different encodings.
SUMMARY OF THE INVENTION
The preferred embodiment of the present invention comprises a two-stage 32-bit incrementor that receives as inputs a 32-bit 1-of-4 operand to be incremented and a 1-of-2 increment control select signal. In the first level of logic, the value of each dit of the operand is both stored in a buffer and is also incremented. Also in the first level, an HPG carry propagate signal is also generated for each block of four dits. Both the buffered value and the incremented value for each dit are passed to the second level of logic, along with the block HPG signals. In the second level of logic, the block HPG signals are used to determine whether the original buffered value or the incremented value of each dit should be output from the incrementor. The preferred embodiment of the incrementor also produces, in addition to an incremented 1-of-4 32-dit output operand, a 1-of-2 carry out indicator.


REFERENCES:
patent: 5198993 (1993-03-01), Makakura
patent: 5208490 (1993-05-01), Yetter
patent: 5719803 (1998-02-01), Naffziger

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for N-nary incrementor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for N-nary incrementor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for N-nary incrementor will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2950799

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.