Zero detection of a sum of inputs without performing an addition

Patent metadata

Field	Value
Publication number	US-10168993-B2
Application number	US-201715788901-A
Country	US
Kind code	B2
Filing date	Oct 20, 2017
Priority date	Feb 22, 2017
Publication date	Jan 1, 2019
Grant date	Jan 1, 2019

Abstract

A logic circuit and a method using thereof for zero detection of a sum of inputs without performing an addition. The logic circuit and the method using thereof perform a true mathematical zero check and a zero check for trailing N-bits. The logic circuit and the method using thereof include bitwise XOR, XNOR, and OR operations, an OR-reduction, an AND reduction, and a control signal that switches between a true mathematical zero check and a zero check for trailing N-bits. The logic circuit and the method using thereof have less timing delay than an adder or a leading zero anticipator for a zero check. The logic circuit and the method using thereof use less logic gates and therefore less area and less power are needed. The logic circuit and the method using thereof have a great advantage for the zero check of large input vectors.

First claim

What is claimed is:

1. A method for zero detection of a sum of inputs without performing an addition, the method comprising:
performing, by first one or more XOR gates in a logic circuit, a bitwise XOR operation for a first vector as a first input and a second vector as a second input, wherein the bitwise XOR operation for the first vector and the second vector generates a third vector, wherein the first vector and the second vector are signed N-bit 2's complement vectors;
performing, by first one or more OR gates in the logic circuit, a bitwise OR operation for the first vector and the second vector, wherein the bitwise OR operation generates a fourth vector;
performing, by second one or more XOR gates in the logic circuit, a bitwise XOR operation for the third vector and the fourth vector, wherein bit positions of the fourth vector are shifted by one bit to the left and the right end bit of the fourth vector is padded with a zero, wherein the bitwise XOR operation for the third vector and the fourth vector generates a fifth vector;
performing, by a third XOR gate in the logic circuit, an XOR operation of a sign extension bit of the third vector and a sign extension bit of the fourth vector; and
performing, by a first AND gate in the logic circuit, an AND operation of a control signal and an output of the third XOR gate, wherein the control signal switches between a true mathematical zero check and a zero check for trailing N-bits.

2. The method of claim 1 , further comprising:
performing, by a second OR gate in the logic circuit, OR reduction of the fifth vector and an output of the first AND gate;
performing, by a second AND gate in the logic circuit, AND reduction of the third vector;
inverting, by a first inverter in the logic circuit, an output of the second OR gate;
inverting, by a second inverter in the logic circuit, an output of the second AND gate; and
performing, by a third AND gate in the logic circuit, an AND operation of an output of the first inverter and an output of the second inverter;
wherein a sum of the first input and the second input is a zero if an output of the fourth AND gate is one.

3. The method of claim 1 , further comprising:
performing, by a second OR gate, OR reduction of the fifth vector and an output of the first AND gate;
performing, by a second AND gate, AND reduction of the third vector; and
performing, by a NOR gate, a NOR operation of an output of the second OR gate and an output of the second AND gate;
wherein a sum of the first input and the second input is a zero if an output of the NOR gate is one.

4. The method of claim 1 , further comprising:
performing, by a second OR gate, OR reduction of the fifth vector and an output of the first AND gate;
inverting, by a first inverter, an output of the second OR gate;
inverting, by second one or more inverters, the third vector;
performing, by a third OR gate, OR reduction of outputs of the second one or more inverters; and
performing, by a second AND gate, an AND operation of an output of the first inverter and an output of the third OR gate;
wherein a sum of the first input and the second input is a zero if an output of the second AND gate is one.

5. The method of claim 1 , further comprising:
inverting, by a first inverter, an output of the first AND gate;
inverting, by second one or more inverters, the fifth vector;
performing, by a second AND gate, AND reduction of an output of the first inverter and outputs of the second one or more inverters;
performing, by a third AND gate, AND reduction of the third vector;
inverting, by a third inverter, an output of the third AND gate; and
performing, by a fourth AND gate, an AND operation of an output of the third inverter and an output of the second AND gate;
wherein a sum of the first input and the second input is a zero if an output of the fourth AND gate is one.

6. The method of claim 1 , further comprising:
inverting, by a first inverter, an output of the first AND gate;
inverting, by second one or more inverters, the fifth vector;
performing, by a second AND gate, AND reduction of an output of the first inverter and outputs of the second one or more inverters;
inverting, by third one or more inverters, the third vector;
performing, by a second OR gate, OR reduction of outputs of the third one or more inverters; and
performing, by a third AND gate, an AND operation of an output of the second OR gate and an output of the second AND gate;
wherein a sum of the first input and the second input is a zero if an output of the third AND gate is one.

7. The method of claim 1 , wherein it is detected whether a sum of the first input and the second input is a true mathematical zero if the control signal enables the true mathematical zero check.

8. The method of claim 1 , wherein it is detected whether trailing bits of a sum of the first input and the second input are zeros if the control signal disables the true mathematical zero check.

9. A method for zero detection of a sum of inputs without performing an addition, the method comprising:
performing, by first one or more XOR gates in a logic circuit, a bitwise XOR operation for a first vector as a first input and a second vector as a second input, wherein the bitwise XOR operation for the first vector and the second vector generates a third vector, wherein the first vector and the second vector are signed N-bit 2's complement vectors;
performing, by first one or more OR gates in the logic circuit, a bitwise OR operation for the first vector and the second vector, wherein the bitwise OR operation generates a fourth vector;
performing, by one or more XNOR gates in the logic circuit, a bitwise XNOR operation for the third vector and the fourth vector, wherein bit positions of the fourth vector are shifted by one bit to the left and the right end bit of the fourth vector is padded with a zero, wherein the bitwise XNOR operation for the third vector and the fourth vector generates a fifth vector;
performing, by a second XOR gate in the logic circuit, an XOR operation of a sign extension bit of the third vector and a sign extension bit of the fourth vector; and
performing, by a first AND gate in the logic circuit, an AND operation of a control signal and an output of the second XOR gate, wherein the control signal switches between a true mathematical zero check and a zero check for trailing N-bits.

10. The method of claim 9 , further comprising:
inverting, by a first inverter in the logic circuit, an output of the first AND gate;
performing, by a second AND gate, AND reduction of an output of the first inverter and the fifth vector;
performing, by a third AND gate, AND reduction of the third vector;
inverting, by a second inverter, an output of the third AND gate; and
performing, by a fourth AND gate, an AND operation of an output of the second inverter and an output of the second AND gate;
wherein a sum of the first input and the second input is a zero if an output of the fourth AND gate is one.

11. The method of claim 9 , further comprising:
inverting, by a first inverter, an output of the first AND gate;
performing, by a second AND gate, AND reduction of an output of the first inverter and the fifth vector;
inverting, by second one or more inverters, the third vector;
performing, by a second OR gate, OR reduction of outputs of the second one or more inverters; and
performing, by a third AND gate, an AND operation of an output of the second AND gate and an output of the second OR gate;
wherein a sum of the first input and the second input is a zero if an output of the third AND gate is one.

12. The method of claim 9 , wherein i

Assignees

• IBM

Inventors

• Kroener Michael K
• Mueller Silvia M
• Niekisch Manuela
• Schelm Kerstin C

Classifications

• G06F7/575 Primary

  Basic arithmetic logic units, i.e. devices selectable to perform either addition, subtraction or one of several logical operations, using, at least partially, the same circuitry · CPC title

• G06F7/74 Primary

  Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders {(with shifting G06F5/01)} · CPC title