Incrementer based on carry chain compression
View Patent ↗A computational unit is disclosed to increment or decrement n-bits of data. The unit has n/3 logic blocks to process the n-bits of data, each logic block including: first and second multiplexers to propagate a carry chain; and first, second and third exclusive-OR (XOR) circuits coupled to the carry chain of the multiplexers to generate a 3-bit incremented output.
1. A computational unit to increment or decrement n-bits of data comprising:
a plurality of serially coupled repeating logic circuits, each logic circuit to compute three consecutive bits of data from a least order bit to a highest order bit, each logic circuit including:
a first and second substantially identical logic blocks, each logic block comprising:
a multiplexer to propagate a carry signal, and
a first and second configurable logic element to generate a first and second logic output respectively; and
a third logic element coupled to a carry propagate signal between the first and second logic blocks to generate an intermediate carry logic signal.
2. The computational unit of claim 1 , wherein:
the first logic block multiplexer receives a carry in signal for the least order bit; and
the first logic block multiplexer pass said carry in signal to an input of the second logic block multiplexer; and
the second logic block multiplexer generates a carry-out signal for the least order bit of a next repeating logic circuit.
3. The computational unit of claim 1 , wherein three of the four configurable logic elements of the first and second logic blocks is configured to generate an exclusive-OR (XOR) logic output.
4. The computational unit of claim 1 , wherein the three consecutive bits of data comprises a i , a i+1 and a i+2 and wherein one of the configurable logic elements of a said logic block is configured to generate an AND logic output of the three bits.
5. The computational unit of claim 1 , wherein the three consecutive bits of data comprises a i , a i+1 and a i+2 and wherein the second logic block multiplexer generates a carry-out signal as a function of a i , a i+1 and a i+2 and a carry-in signal c i .
6. The computational unit of claim 3 , wherein the three consecutive bits of data comprises a i , a i+1 and a i+2 , and three consecutive carry-in bits of data comprises c i , c i+1 and c i+2 , and wherein a said XOR determines an output bit b k as the XOR function of inputs a k and c k for k values of i, i+1 and i+2.
7. The computational unit of claim 1 , wherein the third logic element computes an AND function of a data input a i and a carry input c i to generate a logic output c i+1 .
8. The computational unit of claim 1 , wherein a said first and second logic blocks is a configurable look-up-table logic block having four or more inputs.
9. The computational unit of claim 1 , wherein a said first and second logic blocks is a configurable look-up-table (LUT) logic block having two or more outputs.
10. The computational unit of claim 8 , wherein the four or more input LUT can be configured to include:
a first LUT portion that receives fewer than the four inputs and having one output to construct the first configurable logic element; and
a second LUT portion that receives fewer than the four inputs and having one output to construct the second configurable logic element; and
a third LUT portion to receive at least one of the four inputs to construct the multiplexer.
11. A method to increment or decrement n-bits of data, comprising:
providing n/3 logic blocks to process n-bits of data, each logic block processing three consecutive bits a i , a i+1 , and a i+2 of said n-bits of data; and
configuring each of said logic blocks to provide:
three exclusive OR (XOR) circuits to generate said 3-bit outputs; and
a first multiplexer to receive a carry-in signal c i ; and
a second multiplexer to generate a carry-out signal c i+3 .
12. The method of claim 11 , wherein the first multiplexer propagates the carry-in signal to the second multiplexer.
13. The method of claim 11 , wherein each of said logic blocks is further configured to provide an AND circuit to generate a i (a i+1 )(a i+2 ) signal as select input for the second multiplexer.
14. The method of claim 11 , comprising providing a logic element to determine an intermediate carry output signal c i+1 as an AND logic function of a i and c i signals.
15. The method of claim 11 , wherein c i+3 is an AND logic function of a i , a i+1 , a i+2 and c i inputs.
16. The method of claim 11 , wherein the first XOR determines an output bit b i as an XOR function of inputs a i and c i .
17. The method of claim 14 , wherein the second XOR determines an output bit b i+1 as an XOR function of inputs a i+1 and c i+1 .
18. The method of claim 14 , wherein the third XOR determines an output bit b i+2 as an XOR function of inputs a i+2 and (a i+1 c i+1 ).
19. The method of claim 11 , wherein each XOR comprises a look-up table (LUT) logic block.
20. A programmable logic device having a computational unit to increment or decrement n-bits of data, comprising:
a logic circuit having two substantially identical logic blocks to compute three consecutive bits of data, each logic block including:
a configurable look-up-table (LUT) logic block configured to implement a multiplexer to propagate a carry signal, and a first and second LUT logic portions to compute logic functions of said data inputs and a carry input.