US 5,862,059 A · Table compression using bipartite tables

Abstract

A bipartite compression technique is used to implement a bipartite reciprocal table that provides seed reciprocal values for multiplicative (reciprocal refinement) division. The bipartite reciprocal table (12) includes component tables P and N. The input table index is partitioned into high, middle, and low order parts x.sub.h .vertline.x.sub.m .vertline.x.sub.1 !'the high and middle order parts x.sub.h .vertline.x.sub.m ! index the P Table, and the high and low order parts x.sub.h .vertline.x.sub.1 ! index the N Table. The P and N Tables provide first and second component outputs which form a redundant output from the bipartite lookup table. The bipartite table output may be (a) optimal in that, for each entry in each table, the maximum relative error is the minimum possible, and/or (b) when fused with rounding, faithful (i.e., accurate to one unit in the last place). In an exemplary implementation, the bipartite reciprocal table is used in combination with a Booth recoded multiplier --the redundant borrow-save output from the bipartite table is input directly to the Booth recoder, such that the Booth recoder performs a fusion of the first and second component outputs.

Claims18

Dependent claims

An arithmetic processor comprising:

(a) a multiplier including a redundant format input for input arguments in redundant format;
(b) a bipartite lookup table coupled to the multiplier, the bipartite lookup table including fist and second component tables which together provide a bipartite table output in redundant format;
(c) an input table index characterized by a first component index formed by a first subset of the input table index, and a second component index formed by a second subset of the input table index;
(d) the first component table being indexed by the first component index, and the second component table being indexed by the second component index;
and
(e) in response to the input table index, the first component table outputting first component bits of redundant digits of the bipartite table output, and the second component table outputting second component bits of the redundant digits of the bipartite table output;
(f) wherein the bipartite table output is input to the redundant format input of the multiplier.

4 more elements

An arithmetic processor comprising:

(a) a multiplier including a redundant format input for input arguments in redundant format:
(b) a bipartite lookup table coupled to the multiplier, the bipartite lookup table including first and second component tables which together provide a bipartite table output in redundant format;
(c) an input table index characterized by a high order part x.sub.h of k.sub.1 bits, a middle order part x.sub.m of k.sub.2 bits, and a low order part x.sub.1 of k.sub.3 bits, where k.sub.1, k.sub.2, and k.sub.3 are comparable in size;
(d) a first component index <x.sub.h .vertline.x.sub.m >which indexes 2.sup.k1+k2 entries in the first component table;
(e) a second component index <x.sub.h .vertline.x.sub.1 >which indexes 2.sup.k1+k3 entries in the second component table;
(f) in response to the input table index, the first component table outputting first component bits of redundant digits of the bipartite table output, and the second component table outputting second component bits of the redundant die of the bipartite table output;
(g) wherein the bipartite table output is input to the redundant format input of the multiplier.

4 more elements

A function computation method for use in an arithmetic processor that performs function evaluation using a function computation unit having a plurality of input operands where at least one input operand is in redundant format, and a bipartite lookup table that provides a table output value in redundant digit format with each redundant digit comprising first component and second component bits;

comprising the steps:
(a) constructing first and second component tables which together form a bipartite lookup table that is indexed with an input table index such that the first component table is indexed with a first component index formed by a first subset of the input table index to obtain the first component bits of the redundant digits of the table output value, and the second component table is indexed with a second component index formed by a second subset of the input table index to obtain the second component bits of the redundant digits of the table output value, the first and second component bits forming the table output value in redundant digit format;
(b) inputting a specified input table index to obtain a corresponding table output value;
and
(c) inputting the corresponding table output value as the at least one redundant digit format input operand to the function computation unit.

2 more elements

Dependencies are inferred from the claim text.

Table compression using bipartite tables

Life of this patent

Table compression using bipartite tables

Life of this patent

Abstract

Claims18