Patent ID: 6584483
Filing Date: 2003-06-24
Classification: G06F,G06T

Abstract:
An apparatus that calculates an intermediate value between a first value, X, and a second value, Y, the intermediate value being approximately equal to P*X+(1âˆ’P)*Y, wherein P is a non-zero, non-unitary fraction value with an odd number denominator and P*X is n bits wide, the apparatus comprising:a multiplication stage comprising: one or more (1 to d) multiplexing devices, each having inputs to receive the first value X and the second value Y and outputting one of value X and value Y; an incrementing device incrementing the output of a predetermined one of the two or more multiplexing devices by a value of one, a first set of (1 to dâˆ’1) mux shifting devices wherein the output of a first mux shifting device is the output of a second multiplexing device shifted to the left one place, and continuing in this manner wherein the output of the (dâˆ’2)th mux shifting device is the output of the (dâˆ’1)th multiplexing device shifted to the left (dâˆ’2) places and finally, the output of the (dâˆ’1)th mux shifting device is the output of the incrementing device shifted to the left (dâˆ’1) places; and an adder having a total of (1 to d) inputs to receive the outputs of the (1 to dâˆ’1) mux shifting devices and the output of the first multiplexing device; and a division stage coupled to the multiplication stage comprising: a second set of mux shifting devices (1 to m), each having an input and an output, wherein m is a smallest integer where 2m&gE;(n+d)/d; a set of adding devices (1 to m), where the output of the 1st adding device is the addition of an output from the adder of the multiplication stage and that output shifted (d) places to the left by the 1st mux shifting device of the second set; and if m is greater than 1, then the output of the 2nd adding device is the addition of the output from the 1st adding device of the set of adding devices and that output shifted (2*d) places to the left by the 2nd mux shifting device of the second set; and continuing in this manner until the output (m)th adding device of the set of adding devices is the addition of the output of the (mâˆ’1)th adding device of the set of adding devices and that output shifted (2mâˆ’1*d) places to the left by the (m)th mux shifting device of the second set; and a decisive mux shifting device that shifts the output from the (m)th adding device to the right by (2m*d) places to produce the intermediate value.