Back to results
US 7,058,675 B1Granted
Apparatus and method for implementing efficient arithmetic circuits in programmable logic devices
AssigneeAltera Corporation
InventorsChang Choo, Asher Hazanchuk
Life of this patent
Estimating the term…
Abstract
Efficient implementation of arithmetic circuits in programmable logic devices by using Look-Up Tables (LUTs) to store pre-calculated values. A table look-up operation is performed in place of complex arithmetic operations. In this way, at the expense of a few LUTs, many logic elements can be saved. This approach is particularly applicable to circuits for calculating reciprocal values and circuits for performing normalized LMS algorithm.
Claims18
A circuit for calculating reciprocal values, comprising:
- an input for receiving input data, the input data being partitionable into a plurality of segments;
- a selector circuit for selecting one of the segments;
- a look-up table coupled to the selector circuit for receiving the selected segment, the look-up table having stored therein pre-calculated values, the look-up table configured to provide a respective one of the pre-calculated values in response to the selected segment;
- and
- a shifter circuit coupled to the look-up table, the shifter circuit configured to shift the respective one of the pre-calculated values according to a relative position of the selected segment within the input data to generate an approximate reciprocal value for the input data.
2 more elements
A method of calculating reciprocal values in a processing circuit, comprising:
- storing in a memory unit a plurality of reciprocal values in a look-up table in association with a plurality of possible input values, wherein the plurality of input values comprise addresses of the memory unit;
- receiving an input value, the input value having a larger bit-width than each of the possible input values;
- partitioning the input value into a plurality of segments each having a bit-width corresponding to each of the possible input values;
- selecting one of the segments and providing the selected one of the segments to the look-up table to retrieve a respective one of the reciprocal values;
- and
- shifting the respective one of the reciprocal values according to a position of the selected one of the segments in relation to the input value to generate an approximate reciprocal value for the input data.
3 more elements
In a programmable logic device, a circuit for determining a mathematical function for an input value, the circuit comprising:
- an input for receiving the input value;
- a partitioning circuit for partitioning the input value into a plurality of segments;
- a look-up table coupled to the input for receiving the input value, the look-up table comprising a plurality of storage addresses and a plurality of pre-determined values stored in association with the storage addresses, wherein the pre-determined values are determined according to the mathematical function and the storage addresses at which the pre-determined values are stored;
- a matching circuit for matching a selected segment of the input value to a respective one of the storage addresses;
- a shifter circuit configured to shift the pre-determined values retrieved from the look-up table according to a relative position of the segment of the input valve that is matched to a storage address;
- and
- an output for outputting the pre-determined values from the shifter circuit.
4 more elements
A method of calculating reciprocal values in a processing circuit, comprising:
- storing a plurality of reciprocal values in a look-up table in a memory unit in association with a plurality of possible input values;
- receiving an input value, the input value having a larger bit-width than each of the possible input values;
- partitioning the input value into a plurality of segments each having a bit-width corresponding to each of the possible input values;
- selecting one of the segments and providing the selected one of the segments as an address to the look-up table in the memory unit to retrieve a respective one of the reciprocal values;
- and
- shifting the respective one of the reciprocal values according to a position of the selected one of the segments in relation to the input value to generate an approximate reciprocal value for the input data.
3 more elements
Apparatus for calculating reciprocal values, comprising:
- means for storing a plurality of reciprocal values in a look-up table in a memory unit in association with a plurality of possible input values;
- means for receiving an input value, the input value having a larger bit-width than each of the possible input values;
- means for partitioning the input value into a plurality of segments each having a bit-width corresponding to each of the possible input values;
- means for selecting one of the segments and providing the selected one of the segments to the look-up table to retrieve a respective one of the reciprocal values;
- and
- means for shifting the respective one of the reciprocal values according to a position of the selected one of the segments in relation to the input value to generate an approximate reciprocal value for the input data.
3 more elements
A circuit for determining a mathematical function for an input value, the circuit comprising:
- an input for receiving the input value;
- a partitioning circuit for partitioning the input value into a plurality of segments;
- a look-up table coupled to the input for receiving the input value, the look-up table comprising a plurality of storage addresses and a plurality of pre-determined values stored in association with the storage addresses, wherein the pre-determined values are determined according to the mathematical function and the storage addresses at which the pre-determined values are stored;
- a matching circuit for matching a selected segment of the input value to a respective one of the storage addresses;
- and
- a shifter circuit coupled to the look-up table, the shifter circuit configured to shift respective ones of the pre-determined values retrieved from the look-up table according to a relative position of the segment of the input value that is matched to a storage address.
3 more elements
Dependencies are inferred from the claim text.