Bit reduction using dither, rounding and error feedback

Details Bit reduction using dither, rounding and error feedback Bit reduction using dither, rounding and error feedback

2001-05-09

2004-10-05

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S551000

Reexamination Certificate

active

06801925

ABSTRACT:

This application claims the benefit of United Kingdom Application No. 0031771.9, filed Dec. 29, 2000.
FIELD OF THE INVENTION
The present invention relates to data processing generally and, more particularly, data processing to reduce of the number of bits in a data word.
BACKGROUND OF THE INVENTION
In data processing operations, particularly those involving some form of arithmetic calculation, it is usually desirable to truncate the number in the calculation in order to reduce the number of bits used to represent the result. This is necessary since registers in a computer only hold numbers of a fixed length bits. Arithmetical operations on such numbers can result in a number which has more bits than allowable. The number must then be reduced for further processing. The Least Significant Bits (LSBs) of the data word or number are typically removed. When dealing with graphics or video data, the bit reduction process can lead to unsightly quantisation-type visual effects when the data is displayed on screen.
FIG. 1
shows a diagrammatic representation of the bit reduction process where three 9-bit data streams R
1
, R
2
, R
3
are processed in a processing block
10
to produce a 12-bit output data stream R. The data stream R is then is reduced in a bit reduction circuit
12
to an 8-bit data stream.
One way to reduce the bits of the 12-bit data word R to 8-bits is to remove the four LSBs from the 12-bit number. This is known as truncation.
FIGS.
2
(
a
),
2
(
b
) and
2
(
c
) are graphs of the brightness of an object across a screen display where the object dims from left to right on the screen. One example would be an object provided with a shadow. The effect of truncation on the object edge is illustrated in FIG.
2
(
a
). The line
14
indicates the desired sharp edge and the line
16
represents the effect produced by truncation. This is, of course, greatly magnified in FIG.
2
(
a
). However, the effect could still be discernable by the eye.
Various techniques have already been developed and are widely used in bit reduction to reduce the impact of these visual effects and these are discussed below. For example, when rounding, half of the maximum number which can be represented by the LSBs is added to the number to be rounded and then the LSBs are discarded.
FIG. 3
illustrates an example of rounding of two 12-bit numbers
18
,
20
to which the number 1000 is added to give two new 12-bit numbers
22
,
24
. When the four LSBs of the new numbers
22
,
24
are discarded, the result, in the case of number
18
, is a number which is the same as the number which would have been generated by discarding the four LSBs of number
18
. However, with the number
20
the result is a different 8-bit number. The effect of rounding is shown at
26
in FIG.
2
(
b
) where the ideal object edge
14
is formed by the 12-bit number.
A dither process is similar to rounding but, instead of the offset being half the maximum possible value of the four LSBs, the offset for each data word representing each pixel is varied from pixel to pixel.
FIG. 4
is a diagrammatic representation of an array
28
of pixels in a rectangular region of the screen display with the coordinates for the pixel in the top left hand corner of the region being X, Y. The pixels in the rectangular block covered by coordinates X, Y to X+3, Y+1 represent the dimming edge of an object being drawn. In this example, the offset for the pixel at coordinate x, y would be one quarter of the maximum value of the four LSBs. Since the maximum value for the four LSBs is 1111, one quarter of this is 0100 and this offset value is shown in the x, y pixel coordinate of FIG.
4
. For the pixel for the coordinate x+1, y the offset would be one half (1000) of the maximum value for the LSBs. Moving along the horizontal row of pixels the offset would alternate between one quarter and one half, as can be seen from FIG.
4
. Then, for the next row the offset for the pixel coordinate x, y+1 would be one half (1000) and that for x+1, y+1 would be three quarters (1011), again alternating pixel by pixel along the x axis. Thus, the offsets are indicated in binary form in the pixel squares of FIG.
4
. The effect of dithering is to “fuzz” the changes in brightness (pixel) values to reduce the visible effects of quantisation, as shown at
30
in FIG.
2
(
c
).
Error feedback can be used with any of the above processes (i.e., truncation, rounding or dither). Error feedback is diagrammatically represented in
FIG. 1
by the feedback path
32
. Using error feedback, some or all of the discarded LSBs from a 12-bit word are fed back and added to the next 12-bit word before the LSBs of the next 12-bit word are discarded. Error feedback has the effect of providing a smearing of brightness errors along the object edge.
SUMMARY OF THE INVENTION
One aspect of the present invention provides a circuit for reducing the number of bits in a K bit value from K to N bits. The circuit generally comprises a first summing circuit, a control circuit, an error feedback circuit, a second summing circuit, and a processor. The first summing circuit may add an error offset value and the N+m MSB's of the K bit value to produce a result data value. The control circuit may generate a dither offset value. The error feedback circuit may receive m LSBs of the result data value and generate an error value in dependence on the m LSBs. The second summing circuit may add the dither offset value and the error value to provide the error offset value. The processor may selectively control generation of the dither offset value and the error value.
The present invention also provides a method of applying error concealment to the reduction of a data value, comprising the steps of (A) receiving a series of successive data values, (B) generating a respective error offset value for each of said data values and (C) adding each of said error offset values to a MSBs of the next following data value to produce a respective result value.
In one example, the K bit data value may be representative of a pixel data for display on a video display screen. The control circuit has a dither generating circuit for generating the dither offset value in dependence on n LSBs of each of the X and Y coordinates of the pixel data represented by the K bit data value.
The object, features and advantages of the present invention include a circuit which enables one or a combination of bit reduction techniques to be applied selectively to any video or graphics component


REFERENCES:
patent: 5157489 (1992-10-01), Lowe
patent: 5301269 (1994-04-01), Alcorn et al.
patent: 5329475 (1994-07-01), Juri et al.
patent: 5734369 (1998-03-01), Priem et al.
patent: 6148317 (2000-11-01), Riddle et al.
patent: 0620675 (1994-10-01), None
patent: 2222342 (1990-02-01), None

Affiliated with

Also associated with

Rating

Bit reduction using dither, rounding and error feedback does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bit reduction using dither, rounding and error feedback, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit reduction using dither, rounding and error feedback will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3267248