Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-03-01
2004-05-25
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06742008
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to linear interpolators. More particularly, this invention relates to linear interpolators that are accurate and cost-effectively implemented in hardware.
Linear interpolation may be the simplest, fastest, and most commonly implemented form of interpolation. It is based on a straight line relationship between two values, points, pixels, colors, etc. Linear interpolation is a well-known mathematical operation that computes a value between two known values given the ratios of a distance from each known value to an intermediate value divided by the distance between the two known values. For example, given two values P1 and P2, and given that the ratio of a distance from an intermediate value to P2 divided by the distance between P1 and P2 is R1, and the ratio of a distance from the intermediate value to P1 divided by the distance between P1 and P2 is R2, the interpolated value I
V1
, can be represented as follows:
I
V1
=R
1
*P
1+
R
2
*P
2 (1)
The sum of the two ratios, R1 and R2, is equal to one. Therefore, the interpolated value can be represented in terms of one ratio. Assigning R1 to F, commonly known as the linear interpolation factor, I
V1
can be represented as follows:
I
v2
=F*P
1+(1
−F
)*
P
2 (2)
This is a preferred equation for representing linear interpolation because the two distance ratios are in terms of one ratio, F.
Implementing this interpolation in, for example, Application Specific Integrated Circuit (AISC) hardware typically requires two multipliers, an adder, and a subtractor. Primarily because of the multipliers, this conventional approach is expensive to implement. Multipliers occupy large amounts of circuit area because of the number and sizes of transistors included in each. Because adders require less transistors and thus occupy less circuit area, adders are less expensive to implement. As a result, adders are preferred over multipliers where cost is an issue.
A second approach to linear interpolation reduces the cost somewhat by approximating one of the distance ratios. Because (1−F) is approximately equal to ~F, which is the logically inverted value of F, or the one's complement of F, the interpolated value I
V2
can be represented as follows:
I
v2
=F*P
1+~
F*P
2 (3)
This approach typically requires two multipliers, an adder, and an inverter. Although the use of an inverter rather than a subtractor as in the conventional approach reduces the hardware implementation cost somewhat, an error is introduced because of the approximation.
A third approach uses the approximation described in the second approach to construct a set of multi-bit values M. Assuming P1, P2, and M have the same number of bits and that F has n bits, the multi-bit values M can be determined as follows:
M
0
=
F
[
0
]
?
P1
:
P2
M
1
=
F
[
1
]
?
P1
:
P2
M
2
=
F
[
2
]
?
P1
:
P2
⋮
M
n
-
1
=
F
[
n
-
1
]
?
P1
:
P2
(
4
)
The multi-bit values M in equation (4) can be represented using “C” programming language notation (other suitable notations can also be used). The question mark represents a select function dependent on a specified bit of F. For example, if the specified bit of F is equal to binary “1” M is assigned the value immediately after the question mark (P1). If the specified bit of F is equal to binary “0”, M is assigned the value immediately after the colon (P2). Using the multi-bit values, I
V2
can be represented as follows:
I
V2
=[M
0
+(
M
1
<<1)+(
M
2
<<2)+ . . . +(
M
n−1
<<(
n−
1))]>>
n
(5)
The operator “<<” means a logical shift left (shifting a zero in the least significant bit position). The operator “>>” means a logical shift right (shifting out the least significant bit position). The number of bits to shift left or right is indicated by a number immediately to the right of the operator “<<” or “>>.” Shifting aligns the multi-bit values in the correct bit position prior to adding (e.g., if M and F are 4 bits, M
0
=0000.xxxxb, M
1
<<=000x.xxx0b, M
2
<<2=00xx.xx00b, and M
3
<<3=0xxx.x000b). Shifting the sum of these multi-bit values by n removes the fractional part of the interpolated result. Prior to shifting right by n, the summation produces a term in the form “xxxx.xxxxb.” After the shift, I
V2
can be represented in the form “xxxxb.”
This approach significantly reduces the cost of implementing an interpolator to perform this calculation by eliminating the use of multipliers. The multi-bit values allow the interpolation to be implemented using only (n−1) adders and shifters, which occupy less area in hardware and are thus less expensive to implement than the multipliers used in the conventional approach. However, as with the second approach, approximating (1−F) with ~F introduces an error. Therefore, the interpolated value does not have the same accuracy as that of the conventional approach.
In view of the foregoing, it would be desirable to provide a linear interpolator that is both accurate and cost effective to implement in hardware.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a linear interpolator that is both accurate and cost effective to implement in hardware.
In accordance with this invention, a linear interpolator is provided that combines the accuracy of the conventional approach with the cost effective implementations of other known approaches. The present invention uses multi-bit values to eliminate the use of multipliers. Moreover, the present invention improves interpolation accuracy by representing the distance ratios more accurately as follows: because F is a fraction between zero and one inclusive (i.e., 0≦F≦1), −F is equivalent to ~F+1(lsb) (i.e., a binary “1” in the least significant bit position), or the two's complement of F. Through algebraic manipulations, linear interpolation can be accurately performed using the multi-bit value approach in equation (5) when the following two terms are preferably added to the multi-bit value summation prior to shifting right by n: (P2<<n) and P2. These two terms correct the inherent error common in known linear interpolators.
The present invention requires (n+1) adders, which are less costly to implement than approaches involving multipliers. The (n+1) adders represent only a modest increase in the number of devices as compared to known approaches, but result in substantially the same accuracy as the conventional approach while requiring less circuit area to implement.
Advantageously, linear interpolators of the present invention can be combined. For example, three linear interpolators can be combined to form a bilinear interpolator that operates on four values and two distance ratios. Similarly, seven linear interpolators of the present invention can be combined to form a trilinear interpolator that operates on eight values and three distance ratios.
Linear interpolators of the present invention can be advantageously used, for example, in texture filter circuits associated with computer graphics.
REFERENCES:
patent: 5636339 (1997-06-01), Huang et al.
patent: 5801678 (1998-09-01), Huang et al.
patent: 5886911 (1999-03-01), Yang
patent: 5986635 (1999-11-01), Naka et al.
patent: 2002/0076121 (2002-06-01), Shimizu et al.
Fish & Neave
Mak Evelyn C.
Malzahn David H.
Micro)n Technology, Inc.
Tuma Garry J.
LandOfFree
Accurate and cost effective linear interpolators does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accurate and cost effective linear interpolators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accurate and cost effective linear interpolators will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3257881