Parallel hybrid adder
Inventors
Assignees
US Department of Navy • Government of the United States of America
Publication Number
US-11620106-B1
Publication Date
2023-04-04
Expiration Date
2040-12-16
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
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.
Core Innovation
The invention provides a combined adder for N logical bits that produces a sum from a first addend and a second addend each having N bits. The adder uses a least significant adder to produce a segment sum of the least significant bits and a carry out. For higher order segments, pairs of segment adders are used: one producing a segment sum portion, and the other producing an incremented segment sum portion. Carry logic associated with each segment is combined with a multiplexer to select either the incremented or non-incremented segment sum portion. The selected segments are then assembled with a most significant carry out to produce the final sum.
The background problem addressed is the delay in traditional addition methods caused by carry propagation from the least significant bit to the most significant bit. Ripple-carry adders wait sequentially for carry bits to propagate, introducing multiple stages of delay proportional to the number of bits. The Kogge-Stone adder computes sums in parallel but requires extensive routing and hardware area, leading to slower speed and increased power consumption, especially in programmable logic devices like FPGAs. Existing approaches are inefficient, slow, and consume large area and power on such devices.
The present invention aims to provide an adder that operates more efficiently by combining features of ripple-carry and carry look-ahead logic. It reduces computational cycles and is particularly adapted for implementation with field programmable gate arrays. The design segments the addends and uses segment adder pairs with carry logic and multiplexers to efficiently select and combine segment sums, thereby avoiding long carry propagation delays and reducing the need for extensive carry propagation hardware.
Claims Coverage
The patent includes two independent claims focusing on the structure and operation of a combined segmented adder with carry logic and multiplexers.
Segmented adder architecture with segment adder pairs
An adder structure comprising a least significant adder for the least significant segment and multiple segment adder pairs for higher order segments, where each pair includes one adder producing a sum portion and a carry, and another producing an incremented sum portion plus a carry.
Carry logic with XOR and OR gates for carry propagation
Carry logic components associated with each segment receive carry bits from adjacent segments. Each includes an XOR gate to produce a carry check bit and an OR gate that combines the carry check bit and the prior segment's selector value to produce a selector for multiplexing sum portions.
Multiplexer selection of segment sum based on carry logic output
Multiplexers for each segment adder pair select between the non-incremented and incremented sum portions based on the selector value from the carry logic, enabling the correct segment sum portion to be output.
The independent claims collectively describe a segmented adder design featuring paired adders per segment, associated carry logic using XOR and OR gates to compute selector signals, and multiplexers that select between sum portions to efficiently compute the final sum with reduced carry propagation delay.
Stated Advantages
The adder utilizes fewer computational cycles compared to traditional designs.
It is particularly adapted for efficient implementation in field programmable gate arrays, reducing area and power consumption.
The design hybridizes ripple-carry and carry look-ahead logic to improve speed by avoiding long carry propagation delays inherent in prior art.
Documented Applications
Implementation in programmable logic components such as field programmable gate arrays (FPGAs) to provide faster and more efficient addition operations.
Interested in licensing this patent?