Cyrix Corporation

Southern Methodist University

Advanced Micro Devices Corporation

National Semiconductor Corporation

David W Matula

Willard S Briggs

Thomas B Brightman

Cheng Yang

Alexandru Fit-Florea

Mitchell A Thornton

Lee Dobson McFearin

Willard B Briggs

Debjit Das Sarma

Cristina S Iordache

Lun Li

Peter-Michael Seidel

Transforming an integer comprises receiving the integer, where the integer can be expressed as a modular factorization. The modular factorization comprises one or more factors, where each factor has an exponent. The integer is expressed as a product of residues. A discrete logarithm of the integer is established from a sum corresponding to the product of residues. A value for an exponent of a factor is determined from the discrete logarithm. The integer is represented as the modular factorization comprising the one or more factors, where each factor has a value for the exponent.

Method and apparatus for integer transformation using a discrete logarithm and modular factorization

Determining a table output of a table representing a hierarchical tree for an integer valued function includes determining an address from a table input. A subset of a memory is selected according to the address, where the memory represents the hierarchical tree and the subset represents a subtree of the hierarchical tree. Bit fields are selected from the subset, and bits are extracted from the bit fields. A table output is determined from the extracted bits.

Determining a table output of a table representing a hierarchical tree for an integer valued function

An apparatus and method are disclosed for providing higher radix redundant digit lookup tables for digital lookup table circuits. A compressed direct lookup table unit accesses a redundant digits lookup table that is capable of providing a high order part and a low order part that can be directly concatenated to form an output numeric value. The redundant digits lookup table of the invention is structured so that no output overflow exceptions are created. A redundant digits lookup table recoder capable of providing recoded output values directly to partial product generators of a multiplier unit is also disclosed.

Apparatus and method for providing higher radix redundant digit lookup tables for recoding and compressing function values

Methods for determining the square root, reciprocal square root, or reciprocal of a number performed by a processor of a computer system. The methods produce high precision estimates without using iterative steps. In addition, the methods taught herein utilize compressed tables for the coefficient terms A, B, and C from the quadratic expression Ax+Bx+C, thus minimizing hardware requirements.

Arithmetic processor utilizing multi-table look up to obtain reciprocal operands

A circuit and methodology for higher radix multiplication with improved partial product generation. The invention relates to the design of a high precision multiplier for an arithmetic unit of a digital processor.

Higher radix multiplier with simplified partial product generator

An apparatus and method are disclosed for minimizing accumulated rounding errors in coefficient values in a lookup table for interpolating polynomials. Unlike prior art methods that individually round each polynomial coefficient of a function, the method of the present invention use a 'ripple carry' rounding method to round each coefficient using information from the previously rounded coefficient. The 'ripple carry' method generates rounded coefficients that significantly improve the total rounding error for the function.

Apparatus and method for minimizing accumulated rounding errors in coefficient values in a lookup table for interpolating polynomials

An apparatus and method are disclosed for providing higher radix redundant digit lookup tables for digital lookup table circuits. A compressed direct lookup table unit accesses a redundant digits lookup table that is capable of providing a high order part and a low order part that can be directly concatenated to form an output numeric value. The redundant digits lookup table of the invention is structured so that no output overflow exceptions are created. A redundant digits lookup table recoder capable of providing recorded output values directly to partial product generators of a multiplier unit is also disclosed.

The division and square root systems include a multiplier. The systems also include a multipartite table system, a folding inverter, and a complement inverter, each coupled to the multiplier. The division and square root functions can be performed using three scaling iterations. The system first determines both a first and a second scaling value. The first scaling value is a semi-complement term computed using the folding inverter to invert selected bits of the input. The second scaling value is a table lookup value obtained from the multipartite table system. In the first iteration, the system scales the input by the semi-complement term. In the second iteration, the resulting approximation is scaled by a function of the table lookup value. In the third iteration, the approximation is scaled by a value obtained from a function of the semi-complement term and the table lookup value. After the third iteration, the approximation is available for rounding.

Method and apparatus for performing division and square root functions using a multiplier and a multipartite table

Cellular communication systems supporting high utilization geographic regions having extensive cell overlap segments that collectively contain a substantial portion of the mobile units. A system and method for channel assignments incorporating selection from alternative transceivers defining overlapping cells is provided with load balancing to reduce call blocking. The system incorporates selective multiple handoffs responsive to channel assignment requests both to extend load balancing and also to substantially avoid call cutoff when active mobile units cross cell boundaries into possibly saturated cells.

Channel assignment selection reducing call blocking and call cutoff in a

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.

Table compression using bipartite tables

A system for the early detection of overflow or exceptional quotient/remainder pairs is used in conjunction with performing nonrestoring division using two's complement 2n bit dividends N and two's complement n bit divisors D--if early overflow is not signaled, and if an exceptional quotient/remainder pair is not detected, a quotient Q and remainder R are obtained by successive iterative partial remainder computations, which may be performed with no possibility of overflow. The detection system uses only the divisor, dividend, and first partial remainder. Early overflow detection uses three tests (FIGS. 2a, 2b, 2c): an exceptional divisor test, an exceptional dividend test, and an exceptional quotient test. Early exceptional quotient/remainder pair detection provides, when overflow is not signaled, exceptional quotient/remainder pairs using the exceptional divisor test for the exceptional divisor -2.sup.n-1 (FIG. 2c) and the exceptional quotient test for the exceptional quotient -2.sup.n-1 (FIG. 2b).

Early detection of overflow and exceptional quotient/remainder pairs for

A numeric processor includes a multiply-add circuit with redundant value interface circuitry for performing mathematical function computations as a succession of product sums using redundant binary format values (such as signed digit) as the multiplicand and/or the addend inputs to the multiply-add circuit. The redundant value interface circuitry (i) extracts a predetermined number of bits from a redundant product sum to form a redundant truncated product sum, and (ii) couples the redundant truncated product sum to either, or both, multiplicand and addend inputs. In this manner, successive redundant product sums are calculated using without conversion to nonredundant binary format. In a preferred embodiment, the numeric processor includes a single multiply-add circuit, with redundant truncated product sum values being fed back to the multiplicand and/or addend inputs.

Numeric processor including a multiply-add circuit for computing a

A multiple-layered cellular communication system particularly adapted to mobile phones and LAN type communication is provided with an overlaid arrangement of cell transceivers. By having this overlay, multiple service providers can provide a cooperative method of load sharing. The usage of the frequency spectrum can be improved and an advanced hand-off arrangement can be used to prevent or reduce the possibility of blocked calls due to cell saturation.

Multilayered arrangement for load sharing in a cellular communication

An early no-overflow signaling system and method is used in conjunction with performing nonrestoring division using two's complement 2n bit dividends N and two's complement n bit divisors D--when a no-overflow condition is signaled, a subsequent plurality of iterative partial remainder computations are performed to obtain the quotient Q and remainder R with no possibility of overflow. Dividends N are characterized by a 2-bit sign field N(s1s2) formed by a first sign bit N(s1) and a second sign bit N(s2), a high order n-1 dividend magnitude bits N(himag), and a low order n-1 dividend magnitude bits N(lomag), such that N(s1) and N(himag) form a 2's complement number N(hi), while divisors D are characterized by a leading sign bit D(s) and n-1 divisor magnitude bits D(mag). Early no-overflow signaling logic uses the input dividend N and divisor D, and a 2n-1 bit first partial remainder (which has a value of [N-2.sup.n-1 D]) obtained by computing an n-bit first partial remainder PR1 corresponding to the first n bits of the first partial remainder of value [N-2.sup.n-1 D] (including a leading sign bit PR1(s)), such that the first partial remainder of value [N-2.sup.n-1 D] corresponds to PR1 and N(lomag). No-overflow signaling (illustrated in FIGS. 2a/2b and 4) uses (i) the divisor sign and magnitude D(s) and D(mag), (ii) the two bit sign field of the dividend N(s1s2), (iii) and the first partial remainder of value [N-2.sup.n-1 D]. A no-overflow condition is signaled if (i) the divisor magnitude D(mag) is not equal to zero (FIG. 2a, 102, and FIG. 4, 151), and (ii) the dividend sign bits N(s1) and N(s2) are equal (FIG. 2a, 112, and FIG. 4 , 152), and (iii) the sign of the first partial remainder PR1(s) in not equal to the dividend sign bit N(s2) (FIG. 2b, 131, and FIG. 4, 153), and (iv) the divisor and dividend are not both negative (FIG. 2b, 141, and FIG. 4, 154, 156), or if they are, (v) the first partial remainder corresponding to PR1 and N(lomag) is not equal to zero (FIG. 2b, 141, 142, 143, and FIG. 2b, 155, 156).

Early signaling of no-overflow for nonrestoring twos complement division

An arithmetic circuit 10 for performing prescaled division uses a rectangular multiplier 16 and accumulator 30 operable to calculate a short reciprocal and scaled dividend and divisor to enable the sequential iterative calculation of large radix quotient digits. Each quotient digit can be calculated using a single pass through the rectangular multiplier 16 and accumulator 30 and can be accumulated to form a full precision quotient in a quotient register 36.

Growing community of inventors

Dallas, TX, United States of America

David W Matula