Multiplier with selectable booth encoders for performing 3D graphics interpolations with two multiplies in a single pass through the multiplier

• US 5,935,198 A
• Filed: 11/22/1996
• Issued: 08/10/1999
• Est. Priority Date: 11/22/1996
• Status: Expired due to Term

• Current Assignee: S3 Graphics Co., Ltd. (HTC Corporation)
• Original Assignee: S3 Inc. (SONICblue Incorporated)
• Inventors: Blomgren, James S.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/755,545
• Time in Patent Office: 991 Days
• Field of Search: 364/723, 364/786, 364/757-760, 364/760.01-760.02
• US Class Current: 708/290
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

A multiplier array is modified to perform interpolations. The interpolations use a normalized first operand A between 0 and 1. The interpolation is the function B * A+C * (1-A). Standard multipliers accept two operands as inputs, but interpolations require 3 operands (A, B, C). The AND gates in Booth encoders in a standard multiplier array are replaced by multiplexers. Each multiplexer selects a bit from one of the two operands (B or C) based on a bit of the first operand A. The interpolate operation multiplies the first operand A by the second operand B while simultaneously multiplying the bit-wise inverse of the first operand A'"'"' by the third operand C. Since one multiply is with the first operand A while the second multiply is with the inverse A'"'"' of the first operand, one of the multiplies always generates zero while the other multiply generates either a one or a zero for each bit of the first operand. The multiply producing zero is deleted by not being selected by the multiplexer; instead the multiplexer selects the other multiply as an intermediate product term. Thus the intermediate product terms for the half of the inputs which generate a zero product term are never generated. A correction term is generated and added in to account for the difference between the bit-wise inverse of A and the two'"'"'s complement of A. The multiplexers can be enlarged to allow either standard 2-operand multiplies or 3-operand interpolations in the same multiplier array. The interpolator-multiplier is especially useful for 3D graphics applications.

Claims

1. A multiplier-interpolator comprising:

a first operand input comprising a plurality of electrical signals representing a first operand;

a second operand input comprising a plurality of electrical signals representing a second operand;

a third operand input comprising a plurality of electrical signals representing a third operand;

a plurality of product-term generators for generating intermediate products, each product-term generator receiving a bit of the first operand and a bit of the second operand and a bit of the third operand, each product term generator outputting as an intermediate product either the bit of the second operand or the bit of the third operand in response to the bit of the first operand; and

a summer, receiving the intermediate products from the plurality of product-term generators and receiving each bit of the third operand weighted in accordance with the least-significant bit of the first operand, for generating a sum being a result of interpolating the second operand and the third operand by the first operand,

whereby interpolation of three operands is performed.

2. The multiplier-interpolator of claim 1 wherein the result is generated in a single pass through the plurality of product-term generators and the summer, whereby interpolation of three operands is performed in a single pass through the multiplier-interpolator.

3. The multiplier-interpolator of claim 2 wherein each product term generator outputs as the intermediate product the bit of the second operand when the bit of the first operand is one but outputs the bit of the third operand when the bit of the first operand is zero, the multiplier-interpolator performing a multiply of the first operand with the second operand while simultaneously performing a

multiply of the bit-wise inverse of the first operand with the third operand, whereby two multiplies are simultaneously performed in a single pass through the plurality of product-term generators and the summer.

4. The multiplier-interpolator of claim 3 wherein the first operand comprises i bits and wherein the second operand comprises j bits and wherein the third operand comprises j bits, wherein a number of product-term generators is substantially (i×

j), whereby two multiplies are simultaneously performed using i×

j product term generators.

5. The multiplier-interpolator of claim 3 wherein each product-term generator comprises a multiplexer having a bit of the first operand as a select control input and bits of the second and third operands as data inputs,

whereby multiplexers select either the bit from the second operand or the bit from the third operand in response to the bit from the first operand to generate the intermediate products.

6. The multiplier-interpolator of claim 5 wherein the first operand is a plurality of electrical signals representing a multi-bit binary number between zero and one and wherein the second and third operands are each a plurality of electrical signals representing a multi-bit binary number greater than or equal to zero.

7. The multiplier-interpolator of claim 6 wherein the first operand is stored in a floating-point number format while the second and third operand are stored in an integer format.

8. The multiplier-interpolator of claim 3 wherein each product-term generator further comprises:

standard multiply means, responsive to a multiply signal indicating that a two-operand multiply and not an interpolate is to be performed, for outputting as the intermediate product the bit of the second operand when the bit of the first operand is one but outputting a zero bit when the bit of the first operand is zero, the multiplier-interpolator performing a multiply of the first operand with the second operand when the multiply signal is active,

whereby one multiply of two operands is performed when the multiply signal is active, but simultaneously performing two multiplies of three operands when the multiply signal is not active.

9. In a computer system having a processing unit, a memory graphics processing circuitry and a display device, a computer-implemented method for interpolating a second and a third operand by a first operand, the computer-implemented method comprising the steps of:

loading a first register with the first operand, loading a second register with the second operand, and loading a third register with the third operand;

multiplexing the outputs of the second and third registers by performing the substeps of;

selecting as a term i all bits of the second operand when the first operand has a value of one at bit-position i, but selecting as a term i all bits of the third operand when the first operand has a value of zero at bit-position i; and

shifting term i to the significance of bit-position i to generate a shifted term i,

for each bit-position i in the first operand;

generating an adjustment term from the third operand, the adjustment term being the third operand having the significance of the least-significant bit of the first operand;

forming a sum of all shifted terms i generated and the adjustment term; and

outputting a color signal corresponding to the sum to the display device,

wherein the sum formed is the second operand multiplied by the first operand, added to the third operand multiplied by the two'"'"'s complement of a fractional part of the first operand,

whereby interpolation is performed on three operands.

10. The computer-implemented method of claim 9 wherein the first operand represents a value between zero and one.

11. The computer-implemented method of claim 9 wherein the step of selecting as term i is implemented in a hardware multiplexer.

12. The computer-implemented method of claim 10 wherein the steps of selecting as term i are implemented in i×

j hardware multiplexers.

13. A graphics processor for interpolating between a first pixel and a second pixel using a blending variable, the graphics processor comprising:

a plurality of multiplexers, each multiplexer in the plurality of multiplexers receiving as data inputs a first bit from the first pixel and a second bit from the second pixel and receiving as a select control input a bit of the blending variable, each multiplexer outputting the first bit as an intermediate product when the bit of the blending variable is in a first state but outputting the second bit as the intermediate product term when the bit of the blending variable is not in the first state; and

a carry-save-adder tree, receiving each bit of the second pixel weighted in accordance with the least-significant bit of the blending variable, and the intermediate product terms from the multiplexers, for reducing the intermediate product terms to a result of the interpolation,

whereby the multiplexers select bits from either the first pixel or from the second pixel in response to each bit of the blending variable.

14. The graphics processor of claim 13 further comprising:

second multiplexer means, coupled to each of the multiplexers and responsive to a multiply signal, for applying a zero bit as the second bit input to the multiplexers from the second pixel when the multiply signal is active, whereby standard multiplies are performed by applying a zero bit as the second bit input to the multiplexers.

15. The graphics processor of claim 13 wherein each multiplexer in the plurality of multiplexers receives a first bit from the first pixel and a second bit from the second pixel having a same significance.

16. The graphics processor of claim 13 wherein each multiplexer in the plurality of multiplexers receives a different combination of significance of bits from the blending variable and from the first pixel.

17. The graphics processor of claim 13 wherein the first pixel is a color component of a pixel and wherein the second pixel is a color component of a pixel, the result of the interpolation being a blend of a color of the first pixel and a color of the second pixel, the blend being a color of a displayed pixel.