Division synthesis

Patent metadata

Field	Value
Publication number	US-10409556-B2
Application number	US-201715797020-A
Country	US
Kind code	B2
Filing date	Oct 30, 2017
Priority date	Oct 28, 2016
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

A binary logic circuit for determining the ratio x/d in accordance with a rounding scheme, where x is a variable integer input of bit length w and d is a fixed positive integer of the form 2n±1, the binary logic circuit being configured to form the ratio as a plurality of bit slices, the bit slices collectively representing the ratio, wherein the binary logic circuit is configured to generate each bit slice according to a first modulo operation for calculating mod(2n±1) of a respective bit selection of the input x and in dependence on a check for a carry bit, wherein the binary logic circuit is configured to, responsive to the check, selectively combine a carry bit with the result of the first modulo operation.

First claim

The invention claimed is:

1. A binary logic circuit configured to determine the ratio x/d in accordance with a rounding scheme, where x is a variable integer input of bit length w and d is a fixed positive integer of the form 2 n ±1, the binary logic circuit comprising:
fixed function hardware logic configured to form the ratio as a plurality of bit slices, the bit slices collectively representing the ratio;
fixed function hardware logic configured to generate each bit slice according to a first modulo operation for calculating mod (2 n ±1) of a respective bit selection of the input x and in dependence on a check for a carry bit, the fixed function hardware logic configured to generate each bit slice being in communication with the fixed function hardware logic configured to form the ratio; and
fixed function hardware logic configured to, responsive to the check, selectively combine a carry bit with the result of the first modulo operation, the fixed function hardware logic configured to selectively combine a carry bit with the result of the first modulo operation being in communication with the fixed function hardware logic configured to generate each bit slice.

2. A binary logic circuit as claimed in claim 1 , wherein the fixed function hardware logic configured to generate each bit slice i of the ratio is configured to perform the first modulo operation x[w−1:n*(i+1)]mod(2 n −1), where i lies in the range 0 to

⌈

w
n

⌉

-
1.

3. A binary logic circuit as claimed in claim 2 , wherein the fixed function hardware logic configured to, for each bit slice i, perform the check for a carry bit is configured to perform the check by:
in the case d=2 n −1, returning a carry bit of 1 for combination with the result of the first modulo operation when:
x [ w− 1: n *( i +1)]mod(2 n −1)+ x [ n* ( i +1)−1: n*i ]≥2 n 31 1

or
in the case d=2 n +1, returning a carry bit of −1 for combination with the result of the first modulo operation when:
− x [ w −1: n *( i+ 1)]mod(2 n +1)+ x [ n *( i+ 1)−1: n*i ]≥0.

4. A binary logic circuit as claimed in claim 1 , wherein the binary logic circuit comprises a plurality of modulo logic units each configured to perform a first modulo operation on a different respective bit selection of the input x so as to generate a set of modulo outputs.

5. A binary logic circuit as claimed in claim 4 , wherein the binary logic circuit comprises combination logic configured to combine the set of modulo outputs so as to generate the bit slices of the ratio.

6. A binary logic circuit as claimed in claim 4 , wherein the modulo outputs are d-bit one-hot encodings and the binary logic circuit comprises an adder tree configured to determine the result of one or more of the first modulo operations by combining the results of first modulo operations on shorter bit selections from x to form the results of first modulo operations on longer bit selections from x, the binary logic circuit not including logic to evaluate those first modulo operations on longer bit selections from x.

7. A binary logic circuit as claimed in claim 1 , wherein, in the case d=2 n− 1, the binary logic circuit comprises a plurality of full adders each configured to perform, for a given bit slice i, the first modulo operation x[w−1:n(i+1)]mod(2 n −1) and each full adder comprising:
reduction logic configured to reduce the respective bit selection of the input x to a sum of a first n-bit integer β and a second n-bit integer γ; and
addition logic configured to calculate an addition output represented by the n least significant bits of the following sum right-shifted by n:
a first binary value of length 2n, the n most significant bits and the n least significant bits each being the string of bit values represented by β;
a second binary value of length 2n, the n most significant bits and the n least significant bits each being the string of bit values represented by γ; and
the binary value 1.

8. A binary logic circuit as claimed in claim 7 , wherein the reduction logic is configured to interpret the bit selection of x: as a sum of n-bit rows x′, each row representing n consecutive bits of the bit selection of x such that each bit of the bit selection of x contributes to only one row and all of the bits of x are allocated to a row, and the reduction logic is configured to reduce the sum of such n-bit rows x′ in a series of reduction steps so as to generate the sum of the first n-bit integer β and the second n-bit integer γ, wherein each reduction step comprises summing a plurality of the n-bit rows of x′ so as to generate a sum of one or more fewer n-bit rows.

9. A binary logic circuit as claimed in claim 8 , wherein the reduction logic is configured to, on a reduction step generating a carry bit for a row at binary position n+1, use the carry bit as the least significant bit of the row.

10. A binary logic circuit as claimed in claim 8 , the reduction logic comprising a plurality of reduction cells configured to operate in parallel on the rows of x′ at each reduction step and a plurality of reduction stages coupled together in series, each reduction stage comprising one or more of the reduction cells configured to operate in parallel so as to perform a reduction step.

11. A binary logic circuit as claimed in claim 10 , the length of the bit selection from input x for bit i slice v i being and the reduction logic comprising at least

⌊

⌈

v
i

n

⌉

/
3

⌋

reduction cells each operating on a different set of three rows of x′ such that, at each reduction step, the number of rows is reduced by approximately a third.

12. A binary logic circuit as claimed in claim 10 , the reduction logic being configured to iteratively operate the one or more reduction cells over the rows of x′ until two rows remain which represent n-bit integers β and γ.

13. A binary logic circuit as claimed in claim 7 , further comprising:
exception logic configured to form a determination result indicating whether all of the bits of the bit selection of x are 1; and
output logic configured to operate on the addition output in dependence on the determination result received from the exception logic;
wherein the output logic is configured to, if the determination result indicates that all of the bits of the bit selection of x are 1, perform a XOR operation of the addition output with the binary value 1.

14. A binary logic circuit as claimed in claim 13 , the exception logic being configured to form a determination result of 1 if all of the bits of the bit selection of x are 1 and a determination result of 0 if not all of the bits of the bit selection of x are 1, and the output logic comprising a XOR gate configured to receive the addition output and determination result as its inputs so as to form as its output the result of the first modulo operation.

15. A binary logic circuit as claimed in claim 7 , the addition logic comprising a compound adder configured to concurrently form a first sum β+γ an

Assignees

• Imagination Tech Ltd

Inventors

• Rose Thomas

Classifications

• G06F7/727

  Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence) · CPC title

• G06F7/535 Primary

  Dividing only · CPC title

• G06F7/4873

  Dividing · CPC title

• G06F2207/5356

  Via reciprocal, i.e. calculate reciprocal only, or calculate reciprocal first and then the quotient from the reciprocal and the numerator · CPC title

• G06F7/496 Primary

  Multiplying; Dividing · CPC title