Apparatus and method for determining video encoding motion compensation vectors
AssigneeLinden Technology Limited
InventorG. Jack Lipovski
Life of this patent
Estimating the term…
Abstract
An MPEG-1 or an MPEG-2 motion compensation vector encoder circuit achieves smaller circuit area, and hence lower cost, by using circuitry, including ROMs, designed to implement residue arithmetic to calculate sum squared error in a parallel pipelined fashion. A residue-to-binary converter is implemented using distributed arithmetic and a reduction circuit that removes powers of two times the modulus M, both of which use carry save arithmetic operators. An improved ROM-accumulator, used in the residue-to-binary converter, is implemented using carry-save addition within the ROM-accumulator, and ripple-carry or carry-lookahead addition on the output of the ROM-accumulator.
Claims14
A circuit that determines a sum squared error between a vector v and a vector u comprising:
- a) one or more binary-to-residue converter means, each having an input and an output;
- b) a residue-to-binary converter means having an input and an output;
- c) one or more residue number adder means having two inputs and an output wherein the outputs are the sums, represented in residue number format, of the two inputs, represented in residue number format;
- and
- d) one or more means having two inputs and an output, wherein the outputs, represented in residue number format, are the square of the difference between a variable applied on one input, which is represented in residue number format, with a variable applied on the other input, which may be represented in binary number format or in residue number format;
- e) wherein binary number inputs are coupled to inputs to binary-to-residue converters, wherein binary-to-residue converter outputs are coupled to part d means inputs, wherein adder inputs are coupled to part d means outputs or adder outputs, and wherein one adder output is coupled to a residue-to-binary converter, such that the latter's binary number output is the sum squared error of the vector v and the vector u applied to inputs to part d means.
A circuit that selects the motion compensation vector for an integrated circuit for performing video encoding comprising:
- a) one or more binary-to-residue converter means, each having an input and an output;
- b) a residue-to-binary converter means having an input and an output;
- c) one or more residue number adder means having two inputs and an output wherein the outputs are the sums, represented in residue number format, of the two inputs, represented in residue number format;
- and
- d) one or more means having two inputs and an output, wherein the outputs, represented in residue number format, are the square of the difference between a variable applied on one input, which is represented in residue number format, with a variable applied on the other input, which may be represented in binary number format or in residue number format;
- e) wherein binary number inputs are coupled to inputs to binary-to-residue converters, wherein binary-to-residue converter outputs are coupled to part d means inputs, wherein adder inputs are coupled to part d means outputs or adder outputs, and wherein one adder output is coupled to a residue-to-binary converter, such that the latter's binary number output is the sum squared error of an array of pixel data and another array of pixel data applied to inputs to part d means;
- f) minimum circuit means having an input coupled through residue-to-binary converter means to sum squared error circuit means, to determine which sum squared error input is minimum, in which the output provides an indication of the derived motion compensation vector associated with the reference block having this minimum sum squared error.
A residue-to-binary converter consisting of a ROM, adder, and register, in which the Read Only Memory (ROM) stores all combinations of residue weights for a set of residues, in which the residue values are applied bit serially, as the register value is shifted and added to the ROM outputs, in the manner of distributed arithmetic, and the output of which is reduced by subtracting powers of the product of the moduli, M, as long as the difference is positive, to obtain the binary number.
A method of converting a value from residue number format to binary number format comprising:
- (a) applying residues bit serially to a RAC comprising one or more Read Only Memorys (ROMs), an adder, and an accumulator, and accumulating a binary number which is shifted and added to the Read Only Memory (ROM) outputs to derive the binary number format but with multiples of the product of the moduli added to it;
- and
- (b) applying reduction that subtracts powers of two times the product of the moduli, from a large value applied first to the product of the moduli applied last, taking the difference as long as the difference remains positive.
A Read Only Memory Accumulator (RAC) which computes the inner product of a vector of variables and an equal dimensioned vector of constants utilizing distributed arithmetic, utilizing carry save adders within the RAC and binary adders coupled to outputs of such Read Only Memory Accumulators (RACs) such that carry save addition and/or subtraction is used to accumulate the inner product, and the binary adder is used to convert the carry and sum data to conventional binary data.
Dependencies are inferred from the claim text.