Reduced product term carry chain

Details Reduced product term carry chain Reduced product term carry chain

2000-06-05

2004-03-16

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C326S039000

Reexamination Certificate

active

06708190

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method and/or architecture for carry chains generally and, more particularly, to a method and/or architecture for implementing a reduced product term carry chain and adder.
BACKGROUND OF THE INVENTION
A programmable logic device (PLD) provides an economical and efficient means for implementing predetermined Boolean logic functions in an integrated circuit. Such a device consists of, generally, an AND plane configured to generate predetermined product terms in response to a plurality of inputs, a group of fixed/programmable OR gates configured to generate a plurality of sum-of-products (SOP) terms in response to the product terms, and a number of logic elements (i.e., macrocells) configured to generate a desired output in response to the sum-of-products terms. The sum-of-products terms can also be generated using programmable NOR-NOR logic or programmable NAND-NAND logic.
One of the main disadvantages of complex programmable logic devices (CPLDs) and other programmable logic devices (PLDs) that do not contain dedicated carry chain circuitry is the size and performance of the arithmetic function implementations. Arithmetic function implementations in CPLDs can be optimized for area and/or speed. These optimizations, however, are based only on optimizing the topology of the implementation. Without dedicated carry chain circuitry, arithmetic function implementations that are optimized for speed require a large amount of device resources. The required resources can grow to become a significant portion of the targeted device, thereby limiting the amount of resources for other portions of the design. Conversely, implementations that are optimized for area require fewer device resources, but are typically much slower than those optimized for speed. The coarse-grain nature of the CPLD does not allow for a good speed/area tradeoff when implementing arithmetic functions.
Referring to
FIG. 1
, a block diagram of a PLD
10
containing dedicated carry chain circuitry is shown. The PLD
10
has an AND (product term) array
12
, a product term matrix (PTM)
14
, and a macrocell
16
. The AND plane
12
generates carry product term signals CPT
0
and CPT
1
. The carry product terms are presented to the PTM
14
and the macrocell
16
. The PTM
14
includes a fixed 16-input OR gate
18
. The OR gate
18
generates a sum of products term signal OR_IN that is presented to the macrocell
16
.
The macrocell
16
comprises a multiplexer
20
, an AND gate
22
, a multiplexer
24
, an XOR gate
26
, a register
28
, and a multiplexer
30
. The multiplexer
20
has a non-inverting input that receives the signal CPT
0
, an inverting input that receives the signal CPT
1
, a control input that receives a control signal from the AND gate
22
, and an output that presents the signal C
i
to a first input of the multiplexer
24
and to an output of the macrocell
16
. The AND gate
22
generates the control signal in response to a carry in signal C
i−1
and a configuration bit C
2
.
The multiplexer
24
has a second input that is connected to a supply voltage VCC, a third input that is connected to a Q output of the register
28
, and a fourth input that is connected to a supply voltage ground VSS. The multiplexer
24
selects one of the input signals for presentation to a first input of the XOR gate
26
in response to a pair of configuration bits C
0
and C
1
.
The XOR gate
26
has a second input that receives the signal OR_IN and an output that presents a signal to a D input of the register
28
and a first input of the multiplexer
30
. The multiplexer
30
can select either the output of the XOR gate
26
or the Q output of the register
28
for presentation as an output signal OUT in response to a configuration bit Cx.
Referring to
FIG. 2
, a block diagram illustrating a 4-bit ripple carry adder
32
implementing the macrocell structure of
FIG. 1
is shown. The ripple carry adder
32
generates output sum bits S
0
-S
3
in response to sum operand input bits A
0
-A
3
and B
0
-B
3
. The 4-bit ripple carry full adder includes 4 macrocells
16
a
-
16
d
. Each of the macrocells
16
a
-
16
d
is similar to the macrocell
16
of FIG.
1
. However, the register
28
and the multiplexer
30
have not been included in any of the macrocells in
FIG. 2
for clarity. For the purposes of
FIG. 2
, it is assumed that the configuration bit Cx is set to select the output of the gate
26
and to bypass the register
28
. A description of the operation of a ripple carry adder may be found in U.S. Pat. No. 6,034,546, which is hereby incorporated by reference in its entirety.
For the first sum operand bits A
0
and B
0
, the first configuration bit C
2
0
is set to 0, so as to cause the multiplexer
20
a
to always select the signal CPT
0
0
, that is set to CIN
0
, the initial carry into the sum. Since the signal CPT
0
0
is always selected by the multiplexer
20
a
, CPT
1
0
is not used. The signal OR_IN
0
is set to the result of the XOR operation A
0
⊕B
0
. Configuration bits C
0
0
and C
1
0
are set to 1 and 0, respectively, so that the multiplexer
24
a
presents the signal CIN
0
to a first input of the gate
26
a
. The gate
26
a
performs the XOR operation OR_IN
0
⊕CIN
0
and presents the result as the least significant sum bit S
0
.
The output of the multiplexer
20
a
(i.e., CIN
0
) is propagated to the select line of the multiplexer
20
b
, as C
2
1
is set to 1, causing the output of the gate
22
b
to follow the output of the multiplexer
20
a
. To generate the signal CIN
1
(i.e., the carry input for sum bit S
1
) the signal CPT
0
1
is set to A
0
*B
0
and the signal CPT
1
1
is set to /A
0
*/B
0
. The multiplexer
20
b
, therefore, outputs the carry-in signal CIN
1
for sum bit S
1
. The multiplexer
24
b
is configured to present the signal CIN
1
to an input of the gate
26
b
. Thereafter, the gate
26
b
presents the sum bit S
1
, the result of the logical XOR operation on OR_IN
1
and CIN
1
. Sum bits S
2
and S
3
are obtained in a similar manner.
Each macrocell
16
a
-
16
d
requires 4 product terms to implement a 1-bit ripple carry adder. Two dedicated carry product terms are used to generate the carry input C
i
(i.e., A
i−1
*B
i−1
and /A
i−1
*/B
i−1
). Two general purpose product terms are needed to generate the XOR, (A
i
⊕B
i
), one for A
i
*/B
i
and one for /A
i
*B
i
. The second two product terms are implemented in the AND-OR plane of the PLD
10
.
The macrocell
16
has a disadvantage of requiring 4 product terms per macrocell to implement a ripple carry adder. Product terms can require a large number of transistors to implement. For example, a PLD with 39 inputs can require 78 to 156 or more transistors per product term. Reducing the number of product terms required to implement a carry chain can reduce the number of transistors required and reduce the die size of a PLD. However, the structure of the macrocell
16
limits the amount of reduction possible.
An architecture and/or method for implementing a carry chain with two product terms per macrocell that can implement a ripple carry adder would be desirable.
SUMMARY OF THE INVENTION
The present invention concerns a programmable logic device comprising one or more macrocells and a product term array. The macrocells may comprise logic that may be configured to (i) generate and propagate a carry signal and (ii) generate a sum bit. The product term array may comprise two product terms per macrocell.
The objects, features and advantages of the present invention include providing a method and/or architecture for implementing a reduced product term carry chain that may (i) be implemented in a complex programmable logic device (CPLD), (ii) require fewer transistors, (iii) reduce die size, and/or (iv) implement an n-bit ripple carry adder with two product terms per macrocell.


REFERENCES:
patent: 5220214 (1993-06-01), Pedersen
patent: 5359242 (1994-10-01), Veenstra
patent: 5898602 (1999-04-01), Rothman et al.
patent: 6034546 (2000-03-01

Affiliated with

Also associated with

Rating

Reduced product term carry chain does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reduced product term carry chain, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced product term carry chain will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3193675