Performing constant modulo arithmetic

• US 10,691,416 B2
• Filed: 07/02/2019
• Issued: 06/23/2020
• Est. Priority Date: 05/08/2015
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Rose, Thomas
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Larocque, Emily E
• Application Number:
  US16/459,886
• Publication Number:
  US 20190324726A1
• Time in Patent Office: 357 Days
• Field of Search: 708491
• CPC Class Codes: G06F 7/72 using residue arithmetic

Abstract

A binary logic circuit for determining y=x mod(2^m−1), where x is an n-bit integer, y is an m-bit integer, and n>m, includes reduction logic configured to reduce x to a sum of a first m-bit integer β and a second m-bit integer γ; and addition logic configured to calculate an addition output represented by the m least significant bits of the following sum right-shifted by m: a first binary value of length 2m, the m most significant bits and the m least significant bits each being the string of bit values represented by β; a second binary value of length 2m, the m most significant bits and the m least significant bits each being the string of bit values represented by γ; and the binary value 1.

Claims

1. A binary logic circuit for reducing x to a sum of a first m-bit integer) β

and a second m-bit integer γ

, for use in determining y=x mod(2^m−

1), where x is an n-bit integer, y is an m-bit integer, and n>

m, the binary logic circuit comprising fixed function reduction logic configured to;

interpret x as a sum of m-bit rows x′

, each row representing m consecutive bits of x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row;

reduce the sum of such m-bit rows x′

in a series of reduction steps so as to generate the sum of the first m-bit integer β and

the second m-bit integer γ

.

2. The binary logic circuit as claimed in claim 1, wherein each reduction step comprises summing a plurality of the m-bit rows of x′

so as to generate a sum of one or more fewer m-bit rows.

3. The binary logic circuit as claimed in claim 1, wherein the fixed function reduction logic is further configured to, on a reduction step generating a carry bit for a row at binary position m+1, use the carry bit as the least significant bit of the row.

4. The binary logic circuit as claimed in claim 1, wherein the fixed function reduction logic comprises one or more reduction cells each configured to sum a plurality of the m-bit rows of x′

so as to generate a sum of one or more fewer m-bit rows.

5. The binary logic circuit as claimed in claim 4, wherein the fixed function reduction logic comprises a plurality of reduction cells and the plurality of reduction cells being configured to operate in parallel on the rows of x′

at each reduction step.

6. The binary logic circuit as claimed in claim 5, wherein the fixed function reduction logic comprises at least

7. The binary logic circuit as claimed in claim 5, wherein the fixed function reduction logic comprises a plurality of reduction stages coupled together in series, each reduction stage comprising one or more reduction cells configured to operate in parallel so as to perform a reduction step.

8. The binary logic circuit as claimed in claim 7, wherein the fixed function reduction logic comprises a number of reduction stages equal to the number of reduction steps required to reduce the sum of m-bit rows x′

to the sum of m-bit integers β and

γ

.

9. The binary logic circuit as claimed in claim 4, wherein the fixed function reduction logic is further configured to iteratively operate the one or more reduction cells over the rows of x′

until two rows remain which represent m-bit integers β and

γ

.

10. The binary logic circuit as claimed in claim 4, wherein each reduction cell is further configured to receive three rows of x′

and comprises m full adders, each full adder being arranged to sum bits at a corresponding bit position in each of the three received rows so as to generate two rows;

a first row comprising m sum bits and a second row comprising m carry bits.

11. The binary logic circuit as claimed in claim 10, wherein the first row represents sum bits at the first to m^th bit positions and the second row represents carry bits at the second to (m+1)^th binary positions, and the fixed function reduction logic is configured to wrap-around the carry bit at the (m+1)^th position for use as the least significant bit of the second row.

12. The binary logic circuit as claimed in claim 1, wherein the fixed function reduction logic is further configured to output the sum of the first m-bit integer β

and the second m-bit integer γ

.

13. A method of reducing x to a sum of a first m-bit integer β

and a second m-bit integer γ

for use in determining y=x mod(2^m−

1) in a binary logic circuit comprising fixed function reduction logic, where x is an n-bit integer, y is an m-bit integer, and n>

m, the method comprising;

interpreting, by the fixed function reduction logic, x as a sum of m-bit rows x′

, each row representing m consecutive bits from x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row; and

reducing, by the fixed function reduction logic, the sum of m-bit rows, x′

, in a series of reduction steps so as to generate the sum of the first m-bit integer β and

the second m-bit integer γ

.

14. A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when processed at a computer system for generating a manifestation of an integrated circuit, cause the computer system to generate a manifestation of a binary logic circuit for reducing x to a sum of a first m-bit integer β

and a second m-bit integer γ

for use in determining y=x mod(2^m−

1), where x is an n-bit integer, y is an m-bit integer, and n>

m, the binary logic circuit comprising fixed function reduction logic configured to;

interpret x as a sum of m-bit rows x′

, each row representing m consecutive bits of x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row;

reduce the sum of such m-bit rows x′

in a series of reduction steps so as to generate the sum of the first m-bit integer β and

the second m-bit integer γ

.