Carry chain for use between logic modules in a field...

Details Carry chain for use between logic modules in a field... Carry chain for use between logic modules in a field...

2002-10-02

2004-06-15

Le, Don (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Having details of setting or programming of interconnections...

C326S041000

Reexamination Certificate

active

06750674

ABSTRACT:

BACKGROUND OF THE SYSTEM
1. Field of the System
The present system relates to field programmable gate array (FPGA) devices. More specifically, the system relates to a carry chain between combinatorial logic components within logic modules in an FPGA that will increase the performance in the FPGA.
2. Background
FPGAs are known in the art. An FPGA comprises any number of logic modules, an interconnect routing architecture and programmable elements that may be programmed to selectively interconnect the logic modules to one another and to define the functions of the logic modules. An FPGA is an array of uncommitted gates with uncommitted wiring channels. To implement a particular circuit function, the circuit is mapped into an array and the wiring channels' appropriate connections are programmed to implement the necessary wiring connections that form the user circuit.
A gate array circuit can be programmed to implement virtually any set of functions. Input signals are processed by the programmed circuit to produce the desired set of outputs. Such inputs flow from a user's system, through input buffers and through the circuit, and finally back out the user's system via output buffers. Such buffers may provide any or all of the following input/output (I/O) functions: voltage gain, current gain, level translation, delay, signal isolation or hysteresis.
An FPGA core tile may be employed as a stand alone FPGA, repeated in a rectangular array of core tiles, or included with other devices in a system-on-a-chip (SOC). The core FPGA tile may include an array of logic modules, and input/output modules. An FPGA core tile may also include other components such as read only memory (ROM) modules. Horizontal and vertical routing channels provide interconnections between the various components within an FPGA core tile. Programmable connections are provided by programmable elements between the routing resources.
The programmable elements in an FPGA can be either one-time programmable or re-programmable. Re-programmable elements used in FPGA technologies may comprise transistors or other re-programmable elements as is well known to those of ordinary skill in the art. One-time programmable elements used in FPGA technologies may comprise antifuse devices.
In an integrated circuit, addition forms the basis for many logic operations from counting to multiplication. Adder logic is one of the preferred arithmetic logic functions in a digital FPGA system. An adder circuit is constructed using a group of logic gates. Adder circuits are used to implement the arithmetic operations (addition and/or subtraction) using two-input operands. Since addition/subtraction is a bit-by-bit operation, a full adder circuit should consist of two pieces of logic: “sum logic” to produce a sum result (S) on each corresponding operand bit and “carry logic” to generate a carry output (COUT) propagated between each successive operand bit.
FIG. 1
is a simplified schematic diagram illustrating a one-bit full adder. One-bit full adder
100
has an X input
114
, a Y input
116
and an initial carry-in (CIN)
118
. X input
114
and Y input
116
are coupled to an S output
120
through NOR gate
102
. CIN
118
is coupled to an S output through NOR gate
104
. Furthermore, X input
114
, Y input
116
and CIN
118
are coupled to output COUT
122
through AND gates
106
,
108
, and
110
and OR gate
112
.
The equation of the sum output S and carry-out output COUT
122
may be expressed mathematically as a function of the two-input operand x, y and the initial carry input CIN as follows:
S=x⊕y
⊕CIN
COUT=
x·y+x
·CIN+
y
·CIN
Two operands, each with n binary digits, can be added/subtracted using an n-bit ripple carry adder. An n-bit ripple carry adder is constructed by cascading n one-bit full adders.
FIG. 2
is a simplified schematic illustrating an n-bit ripple carry adder. N-bit ripple carry adder
200
is comprised of n one-bit full adders illustrated, for an example only, as
202
,
204
and
206
. Each one-bit full adder
202
,
204
and
206
has X inputs
210
,
214
and
228
and Y inputs
212
,
214
and
226
. Each one-bit adder also has a carry-in, CIN, input
208
,
220
and
224
and a carry-out output, COUT,
218
,
222
and
230
. The inputs are n-bit X and Y values. The initial carry-in input to the least significant adder stage is normally set to 0 and the carry-out output of each adder stage is connected to the carry-in input of the next most significant adder. The n-bit S forms the sum result and the carry-out output of the most significant stage adder indicates the final carry-out of the arithmetic operation.
In the case of ripple adder, each adder has to wait for the carry-out output signal from the previous least significant adder before it can perform the calculation on the current stage. Thus, the most significant bit of the sum S and the final carry-out output COUT must be delayed until the sequential evaluation of the carry-out output from the least significant adder stage to the most significant adder stage. The total delay, Tn, associated with the ripple carry adder can be expressed in a formula as follows:
Tn=n·Tc
where n=the number of full adder stages (number of binary digits in the operands) and Tc=the carry delay of one stage.
Based on the above equation, the delay of a ripple carry adder grows linearly with the number of binary digits in the operand. The sequential chain reaction makes the ripple adder very slow. A method of increasing the speed of the process is by calculating the carry-out outputs of each stage in parallel. This type of implementation is termed a carry lookahead adder.
FIG. 3
is a simplified schematic diagram illustrating an n-bit carry lookahead adder. N-bit carry lookahead adder
300
is comprised of n one-bit full adders illustrated as an example only as
302
,
304
and
306
. Each one-bit full adder
302
,
304
and
306
has X inputs
308
,
314
and
318
and Y inputs
310
,
316
and
320
. However, as opposed to the n-bit ripple carry adder, each one-bit adder shares a carry-in, CIN, input
212
while each n-bit full adder
302
,
304
and
306
has a carry-out output, COUT,
324
,
328
and
332
. The inputs are n-bit X and Y values.
The carry-out output of the ith adder stage (the ith adder stage, which is used to calculate the S and COUT of the two operands' ith operand bit), Ci, can be expressed as follows:
Ci=Gi+Pi
·Cin
where
Gi=Xi·Yi
and
Pi=Xi+Yi
Recursively expanding the above formula indicates that the carry logic of the ith stage Ci depends only on the operand input of the current stage adder (Xi, Yi) and all the previous least significant stage adders (Xi−1, Yi−1, . . . , X
0
, Y
0
). Instead of waiting for the previous carry-out signal from the previous sequential stages, each stage's carry-out output signal may be anticipated from the determined operand inputs. These anticipated carry-out output signals are fast because they proceed through fewer logic stages in sequence. However, compared with the ripple adder, the carry lookahead adder requires an increased number of gates and increased layout area to implement the carry anticipation.
In addition to the issues set forth above, the majority of existing logic modules perform both combinatorial and sequential logic functions. The majority of logic modules that perform combinatorial logic functions can be programmed to implement a variety of functions including adder logic. In fact, a very high percentage of combinatorial logic units are used to perform adder logic. As user designs become more complicated and overall device size (more logic modules per FPGA) increases this number increases. In current devices, combinatorial logic modules can be programmed to implement either one-bit sum logic or the one-bit carry logic but not full adder logic (sum logic and carry logic can not be programmed into one single logic module). This implies that whenever an n-bit ripple adder is configured

Affiliated with

Also associated with

Rating

Carry chain for use between logic modules in a field... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Carry chain for use between logic modules in a field..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Carry chain for use between logic modules in a field... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3297457