US 6,473,529 B1Granted

Sum-of-absolute-difference calculator for motion estimation using inversion and carry compensation with full and half-adders

AssigneeNeoMagic Corp.

InventorTao Lin

Life of this patent

Estimating the term…

Loading patent…

Abstract

A specialized Sum-of-Absolute-Difference (SAD) calculator for motion estimation uses inversion rather than 2's complementing. The absolute-value operation of each pixel-pair difference is performed by a bit-wise inversion rather than a complement. This reduces delay since the adder/incrementer propagation is eliminated. The increment needed to adjust for inversion rather than 2's complementing is accomplished by using the carry inputs to the summing and final adders that generate the sum of the absolute differences. When 2-input final adders are used for summing, a total of k−1 adders are used to sum k absolute differences. One additional increment is needed since only k−1 adders are available. A reduced half-adder rather than a full adder is inserted between the summing and final adder for this remaining increment. Propagation of carries between bit positions in a full adder can be avoided using the half adder. The final adder generates the final sum (the SAD) by adding the sum and carry bits from the half-adder array and propagating the carries.

Claims20

Dependent claims

A Sum-of-Absolute-Difference (SAD) calculator comprising:

a plurality of k pixel-pair inputs, each pixel-pair input including a first pixel input receiving a first pixel from a first macroblock and a second pixel input receiving a second pixel from a second macroblock;
a plurality of k subtractors, each subtractor generating a difference by subtracting a numeric value of the second pixel from a numeric value of the first pixel;
a plurality of k inverter banks, each inverter bank coupled to the difference from one of the k subtractors, for generating bit-inverted differences;
a plurality of k muxes, each mux receiving a difference from one of the k subtractors and receiving a bit-inverted difference from an inverter bank that receives the difference;
a sign bit for each difference generated by each subtractor, the sign bit indicating when a difference represents positive or a negative value;
each mux in the plurality of muxes being controlled by a sign bit for the difference input to the mux, each mux outputting the difference when the sign bit indicates that the difference represents a positive value, but each mux outputting the bit-inverted difference when the sign bit indicates that the difference represents a negative value;
a plurality of k−2 summing adders, each summing adder having 2 multi-bit inputs and a single-bit carry input;
wherein a first level of the summing adders receive outputs from the plurality of muxes, the plurality of summing adders outputting a first partial sum and a second partial sum;
wherein each of the k−2 summing adders receives as the single-bit carry input a sign bit for a different one of the differences, wherein the k−2 summing adders compensate for bit-wise inversion rather than 2's complementing of all but 2 of the differences;
a half-adder array, receiving the first and second partial sums from the plurality k−2 summing adders, for generating a sum and a carry bit for each bit position by adding each bit position of the first partial sum to a same bit position of the second partial sum, the half-adder array outputting all sum bits as a sums output and all carry bits as a carries output;
and
a final adder, having 2 multi-bit inputs and a single-bit carry input, receiving the sums output and the carries output from the half-adder array, the final adder receiving at the single-bit carry input the sign bit for a difference generated by one of the k subtractors, the final adder for summing the sum and carry bits output by the half-adder array with the sign bit and for propagating carries to generate a SAD value, the SAD value being a sum of absolute-values of the differences generated by the k subtractors,
whereby the k−2 summing adders compensate for bit-wise inversion rather than 2's complementing of all but 2 of the differences, while the final adder and the half-adder array compensate for a remaining 2 of the differences.

10 more elements

A Sum-of-Absolute-Difference SAD generator for motion estimation comprising:

difference generators, each receiving a pair of corresponding-location pixels, for generating a difference and a bit-inverted difference, each difference generator outputting a most-significant-bit (MSB) of the difference as a compensation bit;
summing adders, each having 2 multi-bit inputs and a carry input, for generating a first and a second partial sum of the difference or bit-inverted differences output from the difference generators;
wherein all but two of the compensation bits from the difference generators are applied to the carry inputs of the summing adders, the summing adders adjusting to a 2's complement of the bit-inverted differences for all but two of the difference generators;
a half-adder array, receiving the first and second partial sum from the summing adder, and receiving the compensation bit from one of the difference generators, for generating sum and carry bits for each bit position, but not propagating carries;
and
a final adder, receiving the sum and carry bits from the half-adder array, and receiving the compensation bit from one of the difference generators, for generating a final output, the final output being a Sum-of-Absolute-Difference of the corresponding-location pixels input to the difference generators,
whereby compensation for bit-inversion rather than 2's complementation is accomplished by carry inputs to the summing adders, the final adder, and to the half-adder array.

4 more elements

A Sum-of-Absolute-Difference (SAD) calculator comprising:

k pixel-pair inputs, each pixel-pair input including a first pixel input receiving a first pixel from a first macroblock and a second pixel input receiving a second pixel from a second macroblock;
k subtractor means, each subtractor means for generating a difference by subtracting the second pixel from the first pixel;
inverter means, coupled to the difference from one of the k subtractor means, for generating bit-inverted differences;
k mux means, each mux means receiving a difference from one of the k subtractor means and receiving a bit-inverted difference from an inverter means that receives the difference;
sign means for each difference generated by each subtractor means, the sign means indicating when a difference represents positive or a negative value;
each mux means being controlled by a sign means for the difference input to the mux means, each mux means outputting the difference when the sign means indicates that the difference represents a positive value, but each mux means outputting the bit-inverted difference when the sign means indicates that the difference represents a negative value;
k−2 summing adder means, each summing adder means having 2 multi-bit inputs and a single-bit carry input;
wherein a first level of the summing adder means receive outputs from the mux means, the summing adder means outputting a first partial sum and a second partial sum;
wherein each of the k−2 summing adder means receives as the single-bit carry input a sign means for a different one of the differences, wherein the k−2 summing adder means compensate for bit-wise inversion rather than 2's complementing of all but 2 of the differences;
a half-adder array means, receiving the first and second partial sums from the k-2 summing adder means, for generating a sum and a carry bit for each bit position by adding each bit position of the first partial sum to a same bit position of the second partial sum, the half-adder array means outputting all sum bits as a sums output and all carry bits as a carries output;
and
a final adder means, having 2 multi-bit inputs and a single-bit carry input, receiving the sums output and the carries output from the half-adder array means, the final adder means receiving at the single-bit carry input the sign means for a difference generated by one of the k subtractor means, the final adder means for sunning the sum and carry bits output by the half-adder array means with the sign means and for propagating carries to generate a SAD value, the SAD value being a sum of absolute-values of the differences generated by the k subtractor means,
whereby the k−2 summing adder means compensate for bit-wise inversion rather than 2's complementing of all but 2 of the differences, while the final adder means and the half-adder array means compensate for a remaining 2 of the differences.

10 more elements

Dependencies are inferred from the claim text.