Error bounded multiplication by invariant rationals
AssigneeImagination Technologies Limited
InventorTheo Alan Drane
Life of this patent
Estimating the term…
Abstract
A hardware logic representation of a circuit to implement an operation to perform multiplication by an invariant rational is generated by truncating an infinite single summation array (which is represented in a finite way). The truncation is performed by identifying a repeating section and then discarding all but a finite number of the repeating sections whilst still satisfying a defined error bound. To further reduce the size of the summation array, the binary representation of the invariant rational is converted into canonical signed digit notation prior to creating the finite representation of the infinite array.
Claims15
A method of fabricating a hardware logic implementation of an operation to multiply an input value by a predetermined invariant rational that satisfies a defined error bound, the method comprising:
- in response to determining that a binary expansion of the predetermined invariant rational comprises two adjacent non-zero bits, in a synthesizer module, truncating the binary expansion, converting the truncated binary expansion into canonical signed digit notation and expanding the canonical signed digit representation into a finite representation of an infinite expansion;
- generating, in the synthesizer module, a truncated single summation array from the infinite expansion by discarding one or more repeating sections of the array based upon the defined error bound;
- and
- generating, in the synthesizer module, a hardware representation implementing the truncated single summation array, wherein the generated hardware representation is the hardware logic implementation of an operation to multiply an input value by the predetermined invariant rational that satisfies the defined error bound.
A non-transitory computer readable storage medium having stored thereon computer executable instructions which, when executed by a processor, cause the processor to:
- in response to determining that a binary expansion of a predetermined invariant rational comprises two adjacent non-zero bits, truncate the binary expansion, convert the truncated binary expansion into canonical signed digit notation and expand the canonical signed digit representation into a finite representation of an infinite expansion;
- generate a truncated single summation array from the infinite expansion by discarding one or more repeating sections of the array based upon the defined error bound;
- and
- generate a hardware representation implementing the truncated single summation array, wherein the generated hardware representation is the hardware logic implementation of an operation to multiply an input value by the predetermined invariant rational that satisfies the defined error bound.
An apparatus configured to perform lossy synthesis of an operation to multiply an input value by a predetermined invariant rational that satisfies a defined error bound and generate a hardware logic implementation of the operation, the apparatus comprising:
- a processor;
- and
- a memory comprising computer executable instructions which, when executed, cause the processor to:
- in response to determining that a binary expansion of the predetermined invariant rational comprises two adjacent non-zero bits, truncate the binary expansion, convert the truncated binary expansion into canonical signed digit notation and expand the canonical signed digit representation into a finite representation of an infinite expansion;
- generate a truncated single summation array from the infinite expansion by discarding one or more repeating sections of the array based upon the defined error bound;
- and
- generate a hardware representation implementing the truncated single summation array, wherein the generated hardware representation is the hardware logic implementation of an operation to multiply an input value by the predetermined invariant rational that satisfies the defined error bound.
Dependencies are inferred from the claim text.