Parallel hybrid adder

Abstract

A combined adder for N logical bits to produce a sum from a first addend having N first addend bits and a second addend having N second addend bits. A least significant adder produces a segment sum of the least significant bits and a carry out. Segment adder pairs are used for each higher order of significant sums. One segment adder produces a segment sum portion, and the other produces an incremented segment sum portion. Carry logic associated with each segment is utilized with a multiplexer to select the incremented segment sum portion or the segment sum portion. The selected segment sum portions are assembled with a most significant carry out to produce the sum.

Claims

1. A combined adder for N logical bits to produce a sum from a first addend having N first addend bits and a second addend having N second addend bits comprising: a least significant adder receiving a least significant segment of the first addend bits and the second addend bits producing a least significant sum portion of the least significant first and second addend bits and a least significant carry bit; a plurality of segment adder pairs, each segment adder pair receiving a unique segment of the first addend bits and the second addend bits, said plurality of segment adder pairs and said least significant adder receiving all of the N logical bits and being ordered by the significance of the unique segment, a first one of said segment adder pair producing a first sum portion of the first addend bits and the second addend bits and a first carry bit, a second one of said segment adder pair producing a second sum portion of the first addend bits and the second addend bits plus one, and a second carry bit; a plurality of carry logic components with one carry logic component associated with each segment adder pair and having a segment selector value output, the carry logic component joined to receive the first carry bit, the second carry bit, and the segment selector value from an adjacent lower order segment, wherein each carry logic component comprises: an XOR gate joined to receive the first carry bit from the adjacent lower order segment and the second carry bit from the adjacent lower order segment to produce a carry check bit; and an OR gate joined to receive the carry check bit for the segment, said OR gate providing a selector value from the carry check bit for the segment and the selector value from the adjacent lower order segment; a plurality of multiplexers with one multiplexer provided for each segment adder pair, each multiplexer joined to receive the first sum portion and the second sum portion from said segment adder pair, each said multiplexer being further joined to receive the selector value from the carry logic component associated with the segment, said multiplexer providing the first sum portion as a segment sum portion output when the received selector value is not asserted and the second sum portion as the segment sum portion output when the received selector value is asserted; and a sum output joined to receive the least significant sum from said least significant adder and the segment sum portion outputs from the plurality of multiplexers to produce the sum of the first addend and the second addend.

2. The apparatus of claim 1, wherein the first one of said segment adder pair and the second one of said segment adder pair each have a fixed number of bits and the most significant bit of the fixed number of bits is identified as the carry bit and the remaining less significant bits are identified as the segment sum portion.

3. The apparatus of claim 1, wherein each segment adder pair comprises a single adder as the first one of said segment adder pair, and an incrementing adder as the second one of said segment adder pair whereby the incrementing adder produces the second sum portion and second carry out by adding 1 to the first sum portion.

4. The apparatus of claim 1, wherein said plurality of segment adder pairs each receive the same number of logical bits.

5. The apparatus of claim 1, wherein a number of segment adder pairs and a number of logical bits in each segment is apportioned to fit a predetermined field programmable gate array.

6. A combined adder for N logical bits to produce a sum from a first addend having N first addend bits and a second addend having N second addend bits comprising: a least significant adder receiving a least significant segment of the first addend bits and the second addend bits producing a least significant sum portion of the least significant first and second addend bits and a least significant carry bit; a plurality of segment adder pairs, each segment adder pair receiving a unique segment of the first addend bits and the second addend bits, said plurality of segment adder pairs and said least significant adder receiving all of the N logical bits and being ordered by the significance of the unique segment, a first one of said segment adder pair producing a first sum portion of the first addend bits and the second addend bits and a first carry bit, a second one of said segment adder pair producing a second sum portion of the first addend bits and the second addend bits plus one, and a second carry bit; a plurality of XOR gates with one XOR gate associated with each segment adder pair to receive the first carry bit from an adjacent lower order segment and the second carry bit from the adjacent lower order segment to produce a carry check bit; a plurality of OR gates with one OR gate associated each segment adder pair and joined to receive the carry check bit for the segment, said OR gate providing a selector value from the carry check bit for the segment and the selector value from the adjacent lower order segment; a plurality of multiplexers with one multiplexer provided for each segment adder pair, each multiplexer joined to receive the first sum portion and the second sum portion from said segment adder pair, each said multiplexer being further joined to receive the selector value from the OR gate associated with the segment adder pair, said multiplexer providing the first sum portion as a segment sum portion output when the selector value is not asserted and the second sum portion as the segment sum portion output when the selector value is asserted; and a sum output joined to receive the least significant sum from said least significant adder and the segment sum portion outputs from the plurality of multiplexers to produce the sum of the first addend and the second addend.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Reference is made to the accompanying drawings in which are shown an illustrative embodiment of the invention, wherein corresponding reference characters indicate corresponding parts, and wherein:

(2) FIG. 1 is diagram of a prior art ripple carry adder.

(3) FIG. 2 is a diagram of an adder according to a first embodiment.

(4) FIG. 3 is a detail of carry logic utilized in the adder of FIGS. 2 and 4.

(5) FIG. 4 is a diagram of an adder according to a second embodiment.

DETAILED DESCRIPTION OF THE INVENTION

(6) In FIG. 2 there is shown an adder embodiment 20 that is tailored for use in programmable logic components such as field programmable gate arrays. This adder 20 provides a hybrid between ripple-carry adder logic and carry look-ahead logic. As in the prior art, adder 20 provides the sum S when a first addend A is added to a second addend B. First addend and second addend are N bits wide. Each individual bit is shown as n. Each addend is separated groups of adjacent bits or segments for provision to segmented adders 22.sub.0, . . . , 22.sub.M−1, and 22.sub.M and to segmented incremented adders 24.sub.0, . . . , 24.sub.M−1, and 24.sub.M. The segments m can be different bit widths, but they should have the same width as the associated segment adder 22.sub.m and incremented segment adder 24.sub.m.

(7) Each segmented adder 22.sub.m produces a segmented sum portion X.sub.m and a segment carry out CX.sub.m. Likewise, each segmented incremented adder 24.sub.m produces an incremented segmented sum portion X′.sub.m and an incremented segment carry out CX′.sub.m. Segmented sum portion X.sub.m and incremented segmented sum portion X′.sub.m are the K−1 least significant bits of a segmented adder having K bits. CX.sub.m and CX′.sub.m are the most significant bits. The incremented segmented sum portion X′.sub.m is equal to the segmented sum portion X.sub.m plus 1. The incremented segment carry out CX′.sub.m reflects any carry that results from adding 1 to the segmented sum portion X.sub.m. Thus, the output of the segment adder 22m is the segmented sum portion if no carry is received from the lower order segment m−1, and the incremented segment adder 24m output is the segmented sum portion if a carry in is received from the lower order segment m−1. There is no incremented segment adder for the lowest segment m=0 because this segment doesn't receive a carry in.

(8) Carry logic 26.sub.m is associated with segments 1 to m to select either the segmented sum portion X.sub.m or the incremented segmented sum portion X′.sub.m as the final segmented sum portion S.sub.m. For this purpose, segmented sum portion X.sub.m and incremented segmented sum portion X′.sub.m are provided to a segment multiplexer 28.sub.m. In the embodiment shown, segment multiplexer 28.sub.m provides incremented segmented sum portion X′.sub.m as the final segment sum portion S.sub.m if carry logic 26.sub.m provides a 1 as the segment carry factor Cf.sub.m. If carry logic 26m provides a 0 as the segment carry factor Cf.sub.m, the final segment sum portion S.sub.m is the segmented sum portion X.sub.m. Carry logic 26.sub.m is shown in further detail in FIG. 3.

(9) As detailed in FIG. 3, carry logic 26m receives a segment carry out CX.sub.m−1 and an incremented segment carry out, CX′.sub.m−1 from the previous, lower order segment m−1 at an XOR component 30w. XOR component 30.sub.m output along with the previous segment carry factor Cf.sub.m−1 are provided to an OR component 32.sub.m. An OR logical function is performed on these components to give the current segment carry factor Cf.sub.m. Referring back to FIG. 2, current segment carry factor Cf.sub.m is used by multiplexer 28.sub.m to select the segmented sum portion X.sub.m or the incremented segmented sum portion X′.sub.m as the final segment sum portion S.sub.m.

(10) For the segment where M=1, the carry factor for segment 0, Cf.sub.0, equals the segment carry out, CX.sub.0 because the XOR between segment carry out and the incremented segment carry out, if computed, is always 1. No carry logic is necessary for this segment.

(11) A final segment carry logic 26.sub.M is used to select between the final segment carry out CX.sub.M and the final incremented segment carry out CX′.sub.M in multiplexer 28.sub.M+1. Selected final segment carry out is assembled with final segment sum portions S.sub.0, . . . , S.sub.M−1, and S.sub.M to give the sum S as shown.

(12) FIG. 4 shows an alternate embodiment. This embodiment is generally suboptimal because it introduces an additional computation cycle. It may be applied to efficiently use FPGA resources. In this embodiment, an incrementer 34.sub.m is joined to each adder 34.sub.1 . . . 34.sub.M. Incrementer 34m adds 1 to segmented sum portion X.sub.m to compute incremented segmented sum portion X′.sub.m and the incremented segment carry out CX′.sub.m. As in the embodiment shown in FIG. 2, multiplexer 26.sub.m is joined to receive segmented sum portion and incremented segmented sum portion to provide a final segment sum portion S.sub.m based on a carry factor Cf.sub.m. Carry factor Cf.sub.m is computed from the carry outs in the previous segment and the previous carry factor as shown in FIG. 3. All other components operate as in the embodiment shown in FIG. 2.

(13) It will be understood that many additional changes in the details, materials, steps and arrangement of parts, which have been herein described and illustrated in order to explain the nature of the invention, may be made by those skilled in the art within the principle and scope of the invention as expressed in the appended claims. For example, the addends can be segmented into different bit lengths in order to best fit the programmable logic configuration. Similarly, as shown in FIG. 4, a two stage adder incrementer configuration can be used. Other configurations and optimizations can also be applied.

(14) The foregoing description of the preferred embodiments of the invention has been presented for purposes of illustration and description only. It is not intended to be exhaustive, nor to limit the invention to the precise form disclosed; and obviously, many modification and variations are possible in light of the above teaching. Such modifications and variations that may be apparent to a person skilled in the art are intended to be included within the scope of this invention as defined by the accompanying claims.