Constant fraction integer multiplication

Patent metadata

Field	Value
Publication number	US-9753693-B2
Application number	US-201414208591-A
Country	US
Kind code	B2
Filing date	Mar 13, 2014
Priority date	Mar 15, 2013
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

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≠2 i , 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.

First claim

The invention claimed is:

1. 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≠2 i , 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

)

,

Assignees

• Imagination Tech Ltd

Inventors

• Rose Thomas

Classifications

• G06F7/49947 Primary

  Rounding · CPC title

• G06F30/327

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title

• G06F7/722

  Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence) · CPC title

• G06F7/4824

  using signed-digit representation · CPC title

• G06F7/483

  Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)} · CPC title