Reduced product term carry chain

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.

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.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring to FIG. 3 , a block diagram of a circuit 100 is shown in accordance with a preferred embodiment of the present invention. The circuit 100 may be implemented, in one example, as a macrocell in a programmable logic device (PLD). The circuit 100 may have an input 102 that may receive a signal (e.g., CPT 0 ), an input 104 that may receive a signal (e.g., CPT 1 ), an input 106 that may receive a signal (e.g., OR_IN), an input 108 that may receive a signal (e.g., C i 1 ), an input 110 that may receive a signal (e.g., PSUM i ), an output 112 that may present a signal (e.g., PSUM i 1 ), an output 114 that may present a signal (e.g., C i ), and an output 116 that may present a signal (e.g., OUT).

The signals CPT 0 and CPT 1 may be generated in an AND (product term) plane of the PLD. The signals CPT 0 and CPT 1 may be implemented, in one example, as dedicated carry product term input signals. In one example, the signal CPT 0 may be the result of ANDing a pair of AND plane inputs (e.g., A*B). The signal CPT 1 may be generated by ANDing a complement of the AND plane inputs (e.g., /A*/B). The AND plane inputs A and B may be, in one example, sum operands that may be used to generate a sum output bit according to the following EQUATION 1:

S A B C

where S is the sum bit and C is a carry input bit. The signal OR_IN may be generated, in one example, as a sum of products term. In one example, the signal OR_IN may be generated in a product term matrix (PTM) or a product term allocator (PTA) of a PLD. The circuit 100 may be used to implement a stage of a ripple carry full adder. The signal PSUM i 1 may be generated, in one example, in response to the signals CPT 0 and CPT 1 . When the signal CPT 0 is set to A*B and the signal CPT 1 is set to /A*/B, the signal PSUM i 1 may be similar to a logical XOR of the AND plane inputs (e.g., A B). A further discussion of the signal PSUM i 1 may be found in connection with TABLE 1 below. In a multi-bit ripple carry full adder where each stage is implemented with the circuit 100 , the signal PSUM i 1 of a current stage may represent a logical XOR of the AND plane inputs for a sum bit of a previous stage (e.g., A i 1 B i 1 ) The signal PSUM i 1 of a next stage may be presented as the signal PSUM i of the current stage. For example, the signal PSUM i of the current stage may be similar to a logical XOR of AND plane inputs for a sum bit of a current stage (e.g., A i B i ).

A number of the, signals C i 1 , C i , CPT 0 , CPT 1 , OR_IN, PSUM i , and PSUM i 1 may be used to implement a sum and carry chain with two product terms. In one example, a number of circuits similar to the circuit 100 may be connected together to implement an N-bit ripple carry adder, where N is an integer. The N-bit ripple carry adder implemented in accordance with the present invention will generally require only two product terms per macrocell.

The circuit 100 may comprise a gate 120 , a multiplexer 122 , a gate 124 , a multiplexer 126 , a gate 128 , a multiplexer 130 , a register 132 , and a multiplexer 134 . The gate 120 may be implemented, in one example, as an AND gate. The gate 124 may be implemented, in one example, as a NOR gate. The gate 128 may be implemented, in one example, as an exclusive OR gate (XOR). However, other types of gates may be implemented to meet the design criteria of a particular application. For example, in an alternative embodiment, the gate 124 may be implemented as an XNOR gate 124 or other appropriate logic circuit. In another alternative embodiment, the gate 124 may be implemented as either an OR gate or an XOR gate and the gate 128 may be implemented as an XNOR gate or other appropriate logic circuit.

The multiplexers 122 , 130 and 134 may be implemented, in one example, having two inputs and a single control bit. The multiplexer 126 may be implemented, in one example, having 4 inputs and 2 control bits. However, other types of multiplexer circuits may be implemented to meet the design criteria of a particular application. The register 132 may be implemented, in one example, as a D-type flip-flop. However, other types of flip-flops may be implemented to meet the design criteria of a particular application.

The signal C i 1 may be presented to a first input of the gate 120 . A user configurable signal (e.g., C 2 ) may be presented to a second input of the gate 120 . An output of the gate 120 may present a control signal (e.g., SEL) to a control input of the multiplexer 122 . The gate 120 may be a carry decoupler circuit. Setting the signal C 2 to 0 within a particular macrocell will generally decouple the macrocell from a next adjacent macrocell by interrupting the propagation of the signal C 1 1 to the next macrocell. Decoupling one macrocell from the next by setting C 2 to 0 may have an added benefit of permitting the gate 128 and the signal CPT 0 to be used for additional logic synthesis.

The multiplexer 122 may have, in one example, an inverting input and at least one non-inverting input. The signal CPT 0 may be presented to a non-inverting input of the multiplexer 122 and a first input of a gate 124 . The signal CPT 1 may be presented to the inverting input of the multiplexer 122 and a second input of the gate 124 . The gate 124 may have an output that may present the signal PSUM i 1 . When the carry product terms CPT 0 and CPT 1 are set as follows:

the signal PSUM i 1 may be similar to the logical XOR of A and B (A B). The XOR of A and B may be generated, in one example, from the signals CPT 0 and CPT 1 either by a NOR (CPT 0 , CPT 1 ) or an XNOR (CPT 0 , CPT 1 ) as illustrated in the following TABLE 1:

The multiplexer 122 may have an output that may present the signal Ci to a first input of the multiplexer 126 and the output 114 of the circuit 100 . The signal C i may be a carry input for a current sum bit and the multiplexer 122 may be thought of as the carry generator. The multiplexer 126 may have a second input that may receive a signal from a Q output of the register 132 , a third input that may be connected to a supply voltage (e.g., VCC), and a fourth input that may be connected to a supply voltage ground (e.g., VSS). A user configurable signal (e.g., C 0 ) may be presented to a first control input of the multiplexer 126 . Another user configurable signal (e.g., C 1 ) may be presented to a second control input of the multiplexer 126 . An output of the multiplexer 126 may present a signal to a first input of the gate 128 .

The signal OR_IN may be presented to a first input of the multiplexer 130 . The signal PSUM i may be presented to a second input of the multiplexer 130 . A user configurable signal (e.g., C 3 ) may be presented to a control input of the multiplexer 130 . The multiplexer 130 may be, in one example, an input selector for the circuit 100 . The multiplexer 130 may have an output that may present either the signal OR_IN or the signal PSUM i to a second input of the gate 128 .

The gate 128 may have an output that may present a signal to a D input of the register 132 and a first input of the multiplexer 134 . The register 132 may have a set input that may receive a signal from a multiplexer (not shown) configured to select between one or more set signals, a reset input that may receive a signal from a reset multiplexer (not shown) that may be configured to select from one or more reset signals, and a clock input that may receive a clock signal from a clock multiplexer (not shown) that may select from one or more clock signals. The register 132 may present a signal at the Q output that may be presented to a second input of the multiplexer 134 . The multiplexer 134 may select the output of the gate 128 or the Q output of the register 132 for presentation as a signal OUT in response to a user configurable signal (e.g., Cn) presented at a control input of the multiplexer 134 . The user configurable signals C 0 , C 1 , C 2 , C 3 , and Cn may be implemented as configuration bits.

Referring to FIG. 4 , a block diagram illustrating a portion of an N-bit ripple carry adder 136 implemented in accordance with the present invention is shown. In one example, the N-bit ripple carry adder 136 may be implemented with N 1 macrocells, where each macrocell may be configured to receive two product terms. However, the N-bit ripple carry adder 136 may be implemented, in another example, with N macrocells 100 a - 100 n , where the last macrocell loon may be configured to receive four product terms (e.g., CPT 0 n , CPT 1 n , and OR_IN). Each of the macrocells 100 a - 100 n may be implemented similarly to the macrocell 100 of FIG. 3 . However, the registers 132 a - 132 n and the multiplexers 134 a - 134 n have not been included in FIG. 4 for clarity. For the purposes of FIG. 4 , it may be assumed that the configuration bit CX of each of the macrocells 100 a - 100 n may have been set so as to select the output of the gates 128 a - 128 n and to bypass the registers 132 a - 132 n.

For a first set of AND plane inputs (e.g., A 0 and B 0 ), the configuration bit C 2 0 may be set to a first state (e.g., a logical LOW, or 0). When the configuration bit C 2 0 is set to the first state, the multiplexer 122 a may be configured to select the signal CPT 0 0 as the carry input to the macrocell 100 a . An initial carry into the sum (e.g., CIN 0 ) may be presented as a signal CPT 0 0 . The signal CPT 1 0 may be unused. The multiplexer 122 a may present the signal CIN 0 to an input of the multiplexer 126 a . The user configurable signals C 0 0 and C 1 0 may be set to 1 and 0, respectively, so that the multiplexer 126 a may present the signal CIN 0 to a first input of the gate 128 a . The user configurable signal C 3 0 may be set, in one example, to a second state (e.g., a logical HIGH, or 1). When the signal C 3 0 is in the second state, the multiplexer 130 a may select a signal (e.g., PSUM 1 ) that may be presented at an output of the macrocell 100 b for presentation to a second input of the gate 128 a . The signal PSUM 1 may be generated by a logical NOR or XNOR of the signals CPT 0 1 and CPT 1 1 . The signal PSUM 1 may be similar to the result of a logical XOR of the AND plane inputs A 0 and B 0 . The gate 128 a may have an output that may present a signal (e.g., S 0 ). The signal S 0 may be a least significant sum output of the N-bit ripple carry adder 136 .

For a next and subsequent sets of AND plane inputs (e.g., A 1 -A n 1 and B 1 -B n 1 ), the signals CPT 0 1 -CPT 0 n 1 may be presented to a non-inverting input of the multiplexers 122 b - 122 n and a first input of the gates 124 b - 124 n , respectively. The signals CPT 1 1 -CPT 1 n 1 may be presented to an inverting input of the multiplexers 122 b - 122 n and a second input of the gates 124 b - 124 n , respectively. The gates 124 b - 124 n may be configured to generate a signal (e.g., PSUM 1 -PSUM n 1 ) in response to a logical combination of the respective signals CPT 0 1 -CPT 0 n 1 and CPT 1 1 -CPT 1 n 1 The configuration bits C 2 1 -C 2 n 1 may be set to a second state (e.g., a logical HIGH, or 1). When the configuration bits C 2 1 -C 2 n 1 are set to the second state, the multiplexers 122 b - 122 n may be configured to select the signals CPT 0 1 -CPT 0 n 1 or the signals CPT 1 1 -CPT 1 n 1 as the carry input signals CIN 1 -CIN n 1 , in response to the carry input signals CIN 0 -CIN n 2 , respectively. The multiplexers 122 b - 122 n may present the signals CIN 1 -CIN n 1 to an input of the multiplexers 126 b - 126 n . The user configurable signals C 0 1 -C 0 n 1 and C 1 1 -C 1 n 1 may be set to 1 and 0, respectively, so that the multiplexers 126 b - 126 n may present the signals CIN 1 -CIN n 1 to a first input of the gates 128 b - 128 n . The user configurable signals C 3 1 -C 3 n 1 may be set, in one example, to the second state, a logical HIGH, or 1. When the signals C 3 1 -C 3 n 1 are in the second state, the multiplexers 130 b - 130 n may select the respective signal PSUM 2 -PSUM n for presentation to a second input of the respective gates 128 b - 128 n . Each of the signals PSUM 2 -PSUM n may be generated, in one example, as a logical NOR or XOR of the signals CPT 0 2 -CPT 0 n and CPT 1 2 -CPT 1 n , respectively. Each of the signals PSUM 2 -PSUM n may be similar to a logical XOR of the respective AND plane inputs A 2 -A n and B 2 -B n . The gates 128 b - 128 n may have an output that may present a respective sum output signal (e.g., S 1 -S n 1 ).

The signals presented to the macrocells 100 b - 100 n may be characterized as follows: the signal CPT 0 i for a particular macrocell 100 i will generally be set to a product of a pair of AND plane inputs for a preceding sum output S i 1 (e.g., A i 1 and B i 1 ). The signal CPT 1 i will generally be set to a product of the complements of the pair of AND plane inputs for the preceding sum output (e.g., /A i 1 and /B i 1 . The signal PSUM i will generally be similar to a logical XOR of the AND plane inputs for the preceding output (e.g., A i 1 B i 1 ); The signal OR_IN i will generally not be used when the macrocells 100 a - 100 n are implemented as part of an N-bit ripple carry adder with N 1 macrocells.

Referring to FIG. 5 , a block diagram of a circuit 100 illustrating an alternative embodiment of the present invention is shown. The circuit 100 may be implemented similarly to the circuit 100 except that (i) the gate 128 may be implemented as an XNOR gate 128 and (ii) the gate 124 may be implemented as either an OR gate 124 or an XOR gate 124 .

The present invention may provide an architecture that may use two product terms per macrocell to implement a carry chain and/or a ripple carry full adder.

While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention. For example, the carry chain architecture of the present invention may be incorporated into the macrocells illustrated in FIGS. 5-8 of U.S. Pat. No. 6,034,546.