Back to results
US 2014/0280410 A1Published application
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.
Claims23
A binary logic circuit configured to determine 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 being configured to implement the operation:
- ax
- +
- b
- 2
- k
- where a and b are 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:
- if (a) is satisfied by a smaller integer k than (b), then a is an integer given by
- ⌊
- p
-
-
- 2
- k
- q
- ⌋
- and b is 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 an integer given by
- ⌈
- p
-
-
- 2
- k
- q
- ⌉
- and b is an integer in the range
- [
- 0
- ,
- 2
- k
- -
- (
- M
- -
- (
- (
- M
- +
- p
- -
- 1
- )
-
- mod
-
-
- q
- )
- )
-
- (
- (
- -
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- )
- q
- -
- 1
- ]
- .
192 more elements
A method of deriving a hardware representation of a binary logic circuit configured to determine a rounded value of
- p
-
-
- x
- 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 method comprising:
- determining an integer k being 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 fixed integers a and b where:
- 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 a hardware representation for a binary logic circuit configured to implement the operation:
- a
-
-
- x
- +
- b
- 2
- k
- using the determined fixed integers a, b and k.
201 more elements
A binary logic circuit configured to determine a rounded value of
- p
- *
- x
- +
- r
- q
- ,
- where p and q are coprime constant integers with p<q and q≠2i, r is a positive integer, i is any integer, and x is an integer variable between integers A and B where (B−A)≧2q, the binary logic circuit being configured to implement the operation:
- ax
- +
- b
- 2
- k
- where a and b are fixed integers and k is the smallest integer that satisfies either:
- 2
- k
- (
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- >
- β
- min
- -
- -
- β
- max
- -
-
-
- where
- ,
-
- β
- max
- -
- =
- A
- +
- (
- -
- A
- -
- P
- q
- -
- 1
-
- (
- r
- +
- 1
- )
- )
-
-
- mod
-
-
- q
-
-
- β
- min
- -
- =
- B
- -
- (
- B
- +
- r
- *
- P
- q
- -
- 1
- )
-
-
- mod
-
-
- q
- (
- a
- )
- or:
- 2
- k
- (
- -
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- >
- β
- max
- +
- -
- β
- min
- +
-
-
- where
- ,
-
- β
- max
- +
- =
- B
- -
- (
- B
- +
- P
- q
- -
- 1
-
- (
- r
- +
- 1
- )
- )
-
-
- mod
-
-
- q
-
-
- β
- min
- +
- =
- A
- +
- (
- -
- A
- -
- r
- *
- P
- q
- -
- 1
- )
-
-
- mod
-
-
- q
- (
- b
- )
- wherein:
- if (a) is satisfied by a smaller integer k than (b), then a is an integer given by
- ⌊
- p
-
-
- 2
- k
- q
- ⌋
- and b is an integer in the range
- [
- r
-
-
- 2
- k
- +
- β
- min
- -
- *
- (
- p
-
-
- 2
- k
- )
-
-
- mod
-
-
- q
- q
- ,
- 2
- k
-
- (
- r
- +
- 1
- )
- +
- β
- max
- -
- *
- (
- p
-
-
- 2
- k
- )
-
-
- mod
-
-
- q
- q
- -
- 1
- ]
- ;
- and
- if (b) is satisfied by a smaller integer k than (a), then a is an integer given by
- ⌈
- p
-
-
- 2
- k
- q
- ⌉
- and b is an integer in the range
- [
- r
-
-
- 2
- k
- -
- β
- min
- +
- *
- (
- -
- p
-
-
- 2
- k
- )
-
-
- mod
-
-
- q
- q
- ,
- 2
- k
-
- (
- r
- +
- 1
- )
- -
- β
- max
- +
- *
- (
- -
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- q
- -
- 1
- ]
- .
312 more elements
A method of deriving a hardware representation of a binary logic circuit configured to determine a rounded value of
- p
- *
- x
- +
- r
- q
- ,
- where p and q are coprime constant integers with p<q and q≠2i, r is a positive integer, i is any integer, and x is an integer variable between integers A and B where (B−A)≧2q, the method comprising:
- determining an integer k being the smallest integer that satisfies either:
- 2
- k
- (
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- >
- β
- min
- -
- -
- β
- max
- -
- (
- a
- )
- where,
- β−max=A+(−A−P−1q(r+1))mod q
- β−min=B−(B+r*P−1q)mod q
- or:
- 2
- k
- (
- -
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- >
- β
- max
- +
- -
- β
- min
- +
- (
- b
- )
- where,
- β+max=B−(B+P−1q(r+1))mod q
- β+min=A+(−A−r*P−1q)mod q
- determining fixed integers a and b where:
- 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
- [
- r
-
-
- 2
- k
- +
- β
- min
- -
- *
- (
- p
-
-
- 2
- k
- )
-
-
- mod
-
-
- q
- q
- ,
- 2
- k
-
- (
- r
- +
- 1
- )
- +
- β
- max
- -
- *
- (
- 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
- [
- r
-
-
- 2
- k
- -
- β
- min
- +
- *
- (
- -
- p
-
-
- 2
- k
- )
-
-
- mod
-
-
- q
- q
- ,
- 2
- k
-
- (
- r
- +
- 1
- )
- -
- β
- max
- +
- *
- (
- -
- p
-
-
- 2
- k
- )
-
- mod
-
-
- q
- q
- -
- 1
- ]
- ;
- and
- deriving a hardware representation for a binary logic circuit configured to implement the operation:
- ax
- +
- b
- 2
- k
- using the determined fixed integers a, b and k.
209 more elements
Dependencies are inferred from the claim text.