Transformation on input operands to reduce hardware overhead for implementing addition

Patent metadata

Field	Value
Publication number	US-10037190-B2
Application number	US-201615079850-A
Country	US
Kind code	B2
Filing date	Mar 24, 2016
Priority date	Mar 24, 2016
Publication date	Jul 31, 2018
Grant date	Jul 31, 2018

Abstract

Techniques for transforming input operands to reduce overhead for implementing addition operations in hardware are provided. In one aspect, a method for transforming input operands of an adder includes the steps of: receiving a bit array of the input operands; replacing a duplicate signal (e.g., a signal that occurs twice) for a given bit k in the bit array with a single signal at bit k+1; reducing a number of occurrences of the signal on adjacent bits of the input operand, wherein by way of the replacing and reducing a transformed bit array is formed; and providing the transformed bit array to the adder.

First claim

What is claimed is:

1. A method for transforming input operands of an adder performed by a processor device, coupled to a memory, the processor device being implemented to perform the steps of:
receiving a bit array of the input operands at the adder;
replacing a duplicate signal for a given bit k in the bit array with a single signal at bit k+1, wherein the signal is duplicate when it is connected to two or more inputs of the adder;
reducing a number of occurrences of the signal on adjacent bits of the input operand, wherein by way of the replacing and reducing a transformed bit array is formed; and
providing the transformed bit array to the adder for processing.

2. The method of claim 1 , further comprising the step of:
identifying occurrences of the duplicate signal in the array.

3. The method of claim 1 , further comprising the step of:
identifying complementary signals in the array.

4. The method of claim 1 , further comprising the step of:
repeating the replacing for one or more other bits in the array.

5. The method of claim 1 , further comprising the step of:
replacing complementary signals at the given bit k in the array with a logic 1.

6. The method of claim 1 , wherein the adjacent bits are consecutive bits in the array.

7. The method of claim 1 , wherein the adjacent bits are non-consecutive bits in the array.

8. The method of claim 1 , wherein the reducing step comprises the step of:
adding one or more additional rows to the array containing a fewer number of occurrences of the duplicate signal as compared to the bit array that is received.

9. A method for transforming input operands of an adder performed by a processor device, coupled to a memory, the processor device being implemented to perform the steps of:
receiving a bit array of the input operands at the adder;
replacing a duplicate signal for a given bit k in the bit array with a single signal at bit k+1, wherein the signal is duplicate when it is connected to two or more inputs of the adder;
repeating the replacing for one or more other bits in the array;
replacing complementary signals at the given bit k in the array with a logic 1;
reducing a number of occurrences of the signal on adjacent bits of the input operand by adding one or more additional rows to the array containing a fewer number of occurrences of the duplicate signal as compared to the bit array that is received,
wherein by way of the replacing and reducing steps a transformed bit array is formed; and
providing the transformed bit array to the adder for processing.

10. The method of claim 9 , wherein the adjacent bits are consecutive bits in the array.

11. The method of claim 9 , wherein the adjacent bits are non-consecutive bits in the array.

12. A computer program product for transforming input operands of an adder, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to:
receive a bit array of the input operands at the adder;
replace a duplicate signal for a given bit k in the bit array with a single signal at bit k+1, wherein the signal is duplicate when it is connected to two or more inputs of the adder;
reduce a number of occurrences of the signal on adjacent bits of the input operand,
wherein by way of the replacing and reducing a transformed bit array is formed; and
provide the transformed bit array to the adder for processing.

13. The computer program product of claim 12 , wherein the program instructions further cause the computer to:
identify occurrences of the duplicate signal in the array.

14. The computer program product of claim 12 , wherein the program instructions further cause the computer to:
identify complementary signals in the array.

15. The computer program product of claim 12 , wherein the program instructions further cause the computer to:
repeat the replacing for one or more other bits in the array.

16. The computer program product of claim 12 , wherein the program instructions further cause the computer to:
replace complementary signals at the given bit k in the array with a logic 1.

17. The computer program product of claim 12 , wherein the adjacent bits are consecutive bits in the array.

18. The computer program product of claim 12 , wherein the adjacent bits are non-consecutive bits in the array.

19. The computer program product of claim 12 , wherein the program instructions when reducing the number of occurrences of the duplicate signal on the adjacent bits in the bit array further cause the computer to:
add one or more additional rows to the array containing a fewer number of occurrences of the duplicate signal as compared to the bit array that is received.

Assignees

• IBM

Inventors

• Choudhury Mihir
• Geiger David J
• Puri Ruchir
• Sullivan Andrew J

Classifications

• G06F7/504 Primary

  in bit-serial fashion, i.e. having a single digit-handling circuit treating all denominations after each other · CPC title