US 8,015,230 B2Granted

Fast modular zero sum and ones sum determination

AssigneeApple Inc.

InventorHonkai Tam

Life of this patent

Estimating the term…

Loading patent…

Abstract

In one embodiment, a state determiner comprises a plurality of logic circuits and a second logic circuit. Each logic circuit corresponds to a respective bit position of a result of an adder. A first logic circuit corresponds to a least significant bit of the result and is coupled to receive a least significant bit of each operand of the adder and a carry-in input to the adder. Each remaining logic circuit is coupled to receive a bit from the respective bit position of each operand and a less significant bit adjacent to the bit of each operand. Each logic circuit generates an output signal indicative of whether or not a specific result occurs in the respective bit position of the result. Coupled to receive the output signals second logic circuit is configured to generate a sum signal indicative, when asserted, that the specific result occurs.

Claims15

Dependent claims

A zero determiner for an adder, comprising:

a plurality of logic circuits, wherein each logic circuit corresponds to a respective bit position of a result of the adder, and wherein a first logic circuit of the plurality of logic circuits corresponds to a least significant bit of the result and comprises:
a first exclusive OR (XOR) logic gate and a first exclusive NOR (XNOR) logic gate coupled to receive a least significant bit of each operand of the adder and generate a first XOR result and a first XNOR result,
a first inverter coupled to receive a carry-in input to the adder and to output an inverted carry-in,
a first AND logic gate coupled to receive the carry-in input to the adder and the first XOR result and generate a first AND result,
a second AND logic gate coupled to receive the inverted carry-in and the first XNOR result and generate a second AND result, and
a first OR logic gate coupled to receive the first and second AND results and generate a first output signal;
and
wherein each remaining logic circuit of the plurality of logic circuits comprises:
a second XOR logic gate and a second XNOR logic gate coupled to receive a respective bit from the respective bit position of each operand and generate a second XOR result and a second XNOR result,
a second OR logic gate and a NOR logic gate coupled to receive a respective less significant bit adjacent to the respective bit position of each operand and generate a second OR result and a NOR result,
a third AND logic gate coupled to receive the second XOR result and the second OR result and generate a third AND result,
a fourth AND logic gate coupled to receive the second XNOR result and the NOR result and generate a fourth AND result, and
a third OR logic gate coupled to receive the third and fourth AND results and generate a second output signal;
and
wherein each first and second output signal is indicative of whether a zero result occurs in the respective bit position of the result responsive only to inputs that the logic circuit is coupled to receive as recited previously;
and
a second logic circuit coupled to receive the output signals from the plurality of logic circuits and configured to generate a zero sum signal indicative, when asserted, that a zero result occurs for the adder, and wherein the second logic circuit is configured to assert the zero sum signal responsive to each of the output signals indicating zero.

14 more elements

A ones determiner for an adder, comprising:

a plurality of logic circuits, wherein each logic circuit corresponds to a respective bit position of a result of the adder, and wherein a first logic circuit of the plurality of logic circuits corresponds to a least significant bit of the result and comprises:
a first exclusive OR (XOR) logic gate and a first exclusive NOR (XNOR) logic gate coupled to receive a least significant bit of each operand of the adder and generate a first XOR result and a first XNOR result,
a first inverter coupled to receive a carry-in input to the adder and to output an inverted carry-in,
a first AND logic gate coupled to receive the inverted carry-in and the first XOR result and generate a first AND result,
a second AND logic gate coupled to receive the carry-in input to the adder and the first XNOR result and generate a second AND result, and
a first OR logic gate coupled to receive the first and second AND results and generate a first output signal;
and
wherein each remaining logic circuit of the plurality of logic circuits comprises:
a second XOR logic gate and a second XNOR logic gate coupled to receive a respective bit from the respective bit position of each operand and generate a second XOR result and a second XNOR result,
a NAND logic gate and a third AND logic gate coupled to receive a respective less significant bit adjacent to the respective bit position of each operand and generate a NAND result and a third AND result,
a fourth AND logic gate coupled to receive the second XOR result and the NAND result and generate a fourth AND result,
a fifth AND logic gate coupled to receive the second XNOR result and the third AND result and generate fifth AND result, and
a second OR logic gate coupled to receive the fourth and fifth AND results and generate a second output signal;
and
wherein each first and second output signal is indicative of whether a one result occurs in the respective bit position of the result responsive only to inputs that the logic circuit is coupled to receive as recited previously;
and
a second logic circuit coupled to receive the output signals from the plurality of logic circuits and configured to generate a sum signal indicative, when asserted, that a one result occurs in each bit position of the result of the adder, and wherein the second logic circuit is configured to assert the sum signal responsive to each of the output signals indicating one.

14 more elements

An execution core comprising:

an adder coupled to receive a first operand, a second operand, and a carry-in input, wherein the adder is configured to generate a sum of the first operand, the second operand, and the carry-in input;
and
a zero detector coupled to receive the first operand, the second operand, and the carry-in input in parallel with the adder, wherein the zero detector comprises:
a plurality of logic circuits, wherein each logic circuit corresponds to a respective bit position of the sum, and wherein a first logic circuit of the plurality of logic circuits corresponds to a least significant bit of the sum and comprises:
a first exclusive OR (XOR) logic gate and a first exclusive NOR (XNOR) logic gate coupled to receive a least significant bit of the first operand and a least significant bit of the second operand and generate a first XOR result and a first XNOR result,
a first inverter coupled to receive the carry-in input and to output an inverted carry-in,
a first AND logic gate coupled to receive the carry-in input and the first XOR result and generate a first AND result,
a second AND logic gate coupled to receive the inverted carry-in and the first XNOR result and generate a second AND result, and
a first OR logic gate coupled to receive the first and second AND results and generate a first output signal;
and
wherein each remaining logic circuit of the plurality of logic circuits comprises:
a second XOR logic gate and a second XNOR logic gate coupled to receive a respective bit from the respective bit position of each of the first operand and the second operand and generate a second XOR result and a second XNOR result,
a second OR logic gate and a NOR logic gate coupled to receive a respective less significant bit adjacent to the respective bit position of each of the first operand and the second operand and generate a second OR result and a NOR result,
a third AND logic gate coupled to receive the second XOR result and the second OR result and generate a third AND result,
a fourth AND logic gate coupled to receive the second XNOR result and the NOR result and generate a fourth AND result, and
a third OR logic gate coupled to receive the third and fourth AND results and generate a second output signal;
and
wherein each first and second output signal is indicative of whether a zero result occurs in the respective bit position of the result responsive only to inputs that the logic circuit is coupled to receive as recited previously;
and
a second logic circuit coupled to receive the output signals from the plurality of logic circuits and configured to generate a zero sum signal indicative, when asserted, that a zero result occurs for the adder, and wherein the second logic circuit is configured to assert the zero sum signal responsive to each of the output signals indicating zero.

17 more elements

A processor comprising:

a register file configured to store a first operand and a second operand;
and
an execution core coupled to receive the first operand and the second operand from the register file, the execution core comprising:
an adder coupled to receive the first operand, the second operand, and a carry-in input, wherein the adder is configured to generate a sum of the first operand, the second operand, and the carry-in input;
and
a zero detector coupled to receive the first operand, the second operand, and the carry-in input in parallel with the adder, wherein the zero detector comprises:
a plurality of logic circuits, wherein each logic circuit corresponds to a respective bit position of the sum, and wherein a first logic circuit of the plurality of logic circuits corresponds to a least significant bit of the sum and comprises:
a first exclusive OR (XOR) logic gate and a first exclusive NOR (XNOR) logic gate coupled to receive a least significant bit of the first operand and a least significant bit of the second operand and generate a first XOR result and a first XNOR result,
a first inverter coupled to receive the carry-in input and to output an inverted carry-in,
a first AND logic gate coupled to receive the carry-in input and the first XOR result and generate a first AND result,
a second AND logic gate coupled to receive the inverted carry-in and the first XNOR result and generate a second AND result, and
a first OR logic gate coupled to receive the first and second AND results and generate a first output signal;
and
wherein each remaining logic circuit of the plurality of logic circuits comprises:
a second XOR logic gate and a second XNOR logic gate coupled to receive a respective bit from the respective bit position of each of the first operand and the second operand and generate a second XOR result and a second XNOR result,
a second OR logic gate and a NOR logic gate coupled to receive a respective less significant bit adjacent to the respective bit position of each of the first operand and the second operand and generate a second OR result and a NOR result,
a third AND logic gate coupled to receive the second XOR result and the second OR result and generate a third AND result,
a fourth AND logic gate coupled to receive the second XNOR result and the NOR result and generate a fourth AND result, and
a third OR logic gate coupled to receive the third and fourth AND results and generate a second output signal;
and
wherein each first and second output signal is indicative of whether a zero result occurs in the respective bit position of the result responsive only to inputs that the logic circuit is coupled to receive as recited previously;
and
a second logic circuit coupled to receive the output signals from the plurality of logic circuits and configured to generate a zero sum signal indicative, when asserted, that a zero result occurs for the adder, and wherein the second logic circuit is configured to assert the zero sum signal responsive to each of the output signals indicating zero.

20 more elements

Dependencies are inferred from the claim text.