US 9,753,693 B2Granted

Constant fraction integer multiplication

AssigneeImagination Technologies Limited

InventorThomas Rose

Life of this patent

Estimating the term…

Abstract

A binary logic circuit is provided for determining a rounded value of px q , where p and q are coprime constant integers with p<q and q≠2i, i is any integer, and x is an integer variable between 0 and integer M where M≧2q, the binary logic circuit implementing in hardware the optimal solution of the multiply-add operation ax + b 2 k where a, b and k are fixed integers.

Claims20

Dependent claims

In an integrated circuit for performing mathematical operations, the improvement comprising a binary logic circuit configured to determine, for an input value x, a rounded value of

px
q
by implementing the operation
ax
+
b
2
k
,
where p and q are coprime constant integers with p<q and q≠2i, i is an integer, input value x is an integer variable between 0 and integer M where M≧2q,
a and b are predetermined fixed integers, and k is the smallest integer that satisfies either:
2
k
(
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
>
q
⁢
⌊
M
q
⌋
-
q
+
p
-
1
;
or
(
a
)
2
k
(
-
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
>
M
-
(
(
M
+
p
-
1
)
⁢
mod
⁢
⁢
q
)
;
(
b
)
wherein the binary logic circuit comprises:
multiplication and addition logic comprising a binary multiplier array having an input to receive x and configured to perform the multiplication of x by the predetermined fixed integer a and being incapable of performing multiplication of x by a variable factor, wherein the multiplication and addition logic is further configured to perform the addition of b;
wherein, in dependence on the values of p and q:
if (a) is satisfied by a smaller integer k than (b), then a is predetermined to be an integer given by
⌊
p
⁢
⁢
2
k
q
⌋
and b is predetermined to be an integer in the range
[
⌊
M
q
⌋
⁢
(
(
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
)
,
2
k
+
(
q
-
p
-
1
)
⁢
(
(
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
)
q
-
1
]
;
and
if (b) is satisfied by a smaller integer k than (a), then a is predetermined to be an integer given by
⌈
p
⁢
⁢
2
k
q
⌉
and b is predetermined to be an integer in the range
[
0
,
2
k
-
(
M
-
(
(
M
+
p
-
1
)
⁢
mod
⁢
⁢
q
)
)
⁢
(
(
-
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
)
q
-
1
]
.

196 more elements

A method of deriving a hardware representation of a binary logic circuit configured to determine, for an input value x, a rounded value of

p
⁢
⁢
x
q
by implementing the operation
ax
+
b
2
k
,
where p and q are coprime constant integers with p<q and q≠2i, i is an integer, input value x is an integer variable between 0 and integer M where M≧2q, and a, b and k are fixed integers, the method comprising:
determining, in dependence on the values of p and q, the integer k as the smallest integer that satisfies either:
2
k
(
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
>
q
⁢
⌊
M
q
⌋
-
q
+
p
-
1
;
or
(
a
)
2
k
(
-
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
>
M
-
(
(
M
+
p
-
1
)
⁢
mod
⁢
⁢
q
)
,
(
b
)
determining the fixed integers a and b such that:
if (a) is satisfied by a smaller integer k than (b), calculating a as the integer given by
⌊
p
⁢
⁢
2
k
q
⌋
and selecting b from the set of one or more integers in the range
[
⌊
M
q
⌋
⁢
(
(
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
)
,
2
k
+
(
q
-
p
-
1
)
⁢
(
(
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
)
q
-
1
]
,
and
if (b) is satisfied by a smaller integer k than (a), calculating a as the integer given by
⌈
p
⁢
⁢
2
k
q
⌉
and selecting b from the set of one or more integers in the range
[
0
,
2
k
-
(
M
-
(
(
M
+
p
-
1
)
⁢
mod
⁢
⁢
q
)
)
⁢
(
(
-
p
⁢
⁢
2
k
)
⁢
mod
⁢
⁢
q
)
q
-
1
]
;
and
deriving, using the determined fixed integers a, b and k, a hardware representation for a binary logic circuit configured to implement the operation
a
⁢
⁢
x
+
b
2
k
by using multiplication and addition logic comprising a binary multiplier array configured to perform multiplication of x by the fixed integer a and being incapable of performing multiplication of x by a variable factor, the multiplication and addition logic further configured to perform addition of b.

208 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/208,591Filed 13 Mar 2014 · us provisional application
Priority: 15 Mar 2013
Published: US 2014/0280410 A118 Sep 2014
Granted: 5 Sep 2017
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

G06F 7/49947
Significance control: rounding
G06F 7/4824
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: using signed-digit representation
G06F 7/483
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: computations with numbers represented by a non-linear…
G06F 7/52
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: multiplying; Dividing

Family

Application61/790,123Us provisional application · filed 15 Mar 2013
US 2014/0280410 A1Pre-grant publication · published 18 Sep 2014
US 9,753,693 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

Facts

Application

14/208,591Filed 13 Mar 2014 · us provisional application

Priority

15 Mar 2013

Published

US 2014/0280410 A118 Sep 2014

Granted

5 Sep 2017

Term ends

Not estimatedThe source records don’t support an estimate.

Classification11 codes

G06F 7/49947
Significance control: rounding
G06F 7/4824
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: using signed-digit representation
G06F 7/483
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: computations with numbers represented by a non-linear…
G06F 7/52
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: multiplying; Dividing