Quantization device and method using prime number dividers

Details Quantization device and method using prime number dividers Quantization device and method using prime number dividers

2001-03-22

2003-03-04

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S650000

Reexamination Certificate

active

06529929

ABSTRACT:

BACKGROUND
Many digital encoding processes and particularly video encoding processes such as MPEG1, MPEG2, and MPEG4, and H.263 require quantization of data points. Quantization is a process that converts a data point that is within a relatively large dynamic range to an approximately equivalent value within a smaller dynamic range. For example, quantization can convert a 16-bit data value to an 8-bit value, which requires less bandwidth to transmit and less memory capacity to store.
Generally, quantization converts a data point P that has one of N possible values to a quantized value Q having one of M possible values, where M is less than N. Equation 1 describes the general quantization process.
Equation 1:
Q=INT
(
P*M/N
)
In Equation 1, the function INT converts (P*M/N) to an integer value by rounding, truncation, or whatever other method the quantization process may require. The quantized value Q can generally be represented using fewer bits than are required for data point P but typically provides less accuracy.
Hardware encoders or decoders implementing quantization processes generally require hardware dividers. However, full functions dividers are complex circuits that require a significant amount of area in an integrated circuit. Full function dividers thus increase the complexity and cost of hardware.
A hardware encoder can alternatively employ a look-up table to perform divisions by a selected value. Such encoders lack flexibility and cannot accommodate quantization processes that some encoding or decoding processes may require, for example, if an encoding process requires quantization that divides a range by a value not provided for by a look-up table.
A quantization method and circuit is thus sought that has the flexibility to accommodate a wide variety of different quantization process but does not require the complexity or area of a full divider.
SUMMARY
In accordance with an aspect of the invention, a quantization circuit includes a set of prime number dividers that can be implemented as look-up tables and a shifter. A shifter implements divisions by prime number (two) and by powers of two. Multiplexing circuitry interconnects some or all of the prime number dividers to permit performance of a series of prime number divisions in a single clock cycle. The quantization circuit can thus implement one-cycle divisions by divisors that are products of powers of two and the prime numbers in the series that the multiplexing circuitry selects. For divisors corresponding to a longer series of the prime numbers than can be implemented in the quantization circuit, the quantization circuit can implement multi-cycle divisions by feeding an output signal back through one or more further series of the prime number dividers.
For a target divisor that normally would require division by a prime number not implemented in the quantization circuit, the quantization circuit can perform multiple divisions by an implemented divisor that is close to the target divisor with each division acting on the result from the previous division. An accumulation of the results of the multiple cycles provides a final quotient appropriate for the target divisor.
One specific embodiment of the invention is a quantization circuit that includes a plurality of dividers, a first multiplexing circuit, and a second multiplexing circuit. The dividers include a first divider, a second divider, and a third divider, typically look-up table dividers, with each divider corresponding to a prime number divisor and generating from an input signal representing a dividend an output signal representing the quotient of the dividend and the corresponding prime number divisor.
The first multiplexing circuit is connected to input ports of the dividers and operates to select an input signal for the second divider from a set of signals including a first signal representing the dividend and the output signal from the first divider. The multiplexing circuit also selects an input signal for the third divider from a set of signals including the first signal, and the output signal from the first divider, and an output signal from the second divider.
The second multiplexing circuit has input ports connected to the output ports of the first, second, and third dividers and operates to select a second signal for output from a set of signals including the output signals of the first, second, and third dividers.
The prime number dividers can further include fourth and fifth prime number dividers with the first, second, third, fourth and fifth dividers corresponding to prime numbers 3, 5, 7, 11, and 13. A shifter can be coupled to an output port of the second multiplexing circuit for further dividing by powers of two during the same clock cycle as the other dividers. The quantization circuit can further include an arithmetic logic unit connected to combine results based on two or more operations of the dividers or a register file having a read port coupled to an input port of the first multiplexing circuit and a write port coupled to an output port of the second multiplexing circuit.
One method for operating the quantization circuit to divide a dividend by a divisor includes: controlling the first multiplexing circuit so that except for a last divider in a series, each divider in the series provide the signal input to a following divider in the series. Further, the division method can feed back an output signal of the quantization circuit as an input signal to the quantization circuit; and again control the first multiplexing circuit so that except for a last divider in a further series, each divider in the further series provides input to a following divider in the series. Optionally, the method further includes combining (e.g., adding or subtracting) a first result represented by the output signal fed back to the quantization circuit and a second result that the quantization circuit provides when the first multiplexing circuit is controlled for the further series.
Another embodiment of the invention is a quantization circuit including a plurality of dividers, a first multiplexing circuit, a second multiplexing circuit, and a storage circuit. The dividers correspond to prime number divisors, and each divider generates from an input signal representing a dividend an output signal representing the quotient of the dividend and the corresponding prime number divisor. The first multiplexing circuit connects to input ports of the dividers and operates to select input signals for the dividers. The second multiplexing circuit has input ports connected to the output ports of the dividers and operates to select an output signal from a set of signals including the output signals of the dividers. The storage circuit is connected to receive the output signal of the second multiplexing circuit during a first clock cycle and provide a signal to the first multiplexing circuit for processing during a second clock cycle. Accordingly, during the second clock cycle the dividers can divide a result from the first clock cycle.
The storage circuit can include a latch or a register file, and a shifter can be coupled between the second multiplexing circuit and the storage circuit. An arithmetic logic unit coupled to the storage circuit can combine results based on operations of the dividers during the first and second clock cycle.
Aspects of the invention will be further understood in view of the drawings and the detailed description provided below.


REFERENCES:
patent: 4334285 (1982-06-01), Kawakita et al.
patent: 4755961 (1988-07-01), Kuriki et al.
patent: 5140544 (1992-08-01), Lin et al.
patent: 5208770 (1993-05-01), Ito
patent: 5329475 (1994-07-01), Juri et al.

Affiliated with

Also associated with

Rating

Quantization device and method using prime number dividers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Quantization device and method using prime number dividers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantization device and method using prime number dividers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3027974