Coded data generation or conversion – Digital code to digital code converters – Byte length changed
Reexamination Certificate
1999-02-17
2003-01-07
Le, Don Phu (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Byte length changed
C341S096000, C341S102000, C341S103000, C712S241000, C712S226000, C712S036000, C712S034000, C712S200000, C712S009000, C712S212000, C712S210000, C712S217000, C712S220000, C712S225000, C712S035000, C345S505000, C345S563000, C345S215000
Reexamination Certificate
active
06504495
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data processing systems. More particularly, this invention relates to techniques for clipping data values within data processing systems such that the resulting data values lie within a predetermined range with data values originally outside that range being modified to a data value of the respective boundary of the permitted range to which they are closest.
2. Description of the Prior Art
The need to clip data values within data processing systems is widespread. Examples of situations in which clipping is needed are the processing of signal data (e.g. image or audio) that may be captured (e.g. by a camera or a microphone) or decoded from another source (e.g. an MPEG data stream or a JPEG image). A characteristic of the situations is which clipping is often required is that large volumes of data need to be processed. As an example, a single image frame may contain millions of pixel values all of which may need to be clipped. Accordingly, the data processing resources that are consumed by clipping can be considerable and measures that can make the clipping process more efficient are highly advantageous.
SUMMARY OF THE INVENTION
Viewed from one aspect the present invention provides apparatus for processing an unclipped data value in a range of −0.5N to (1.5N−1) to generate a clipped data value clipped to a range of 0 to (N−1), where N is 2
m
said unclipped data value is represented by an overflow bit followed by an m-bit number extending from an (m−1)
th
bit to a 0
th
bit and said unclipped data value is part of an n-bit twos complement input data word, said apparatus comprising:
left shifting logic for left shifting said unclipped data value to generate a left shifted data value in which said (m−1)
th
bit is a most significant bit in said left shifted data value and a carry flag is set in dependence upon said overflow bit;
saturated value generating logic for generating said clipped data value in accordance with:
said clipped data value is 0 if said carry flag indicates that said overflow bit was 1 and said most significant bit in said left shifted data value is 1;
said clipped data value is (N−1) if said carry flag indicates that said overflow bit was 1 said most significant bit in said left shifted data value is 0; and
said clipped data value is said m-bit number if said carry flag indicates that said overflow bit was 0.
The invention recognises that in many practical cases the values are being clipped such that they can be represented by a binary number with a fixed number of bits and the degree of overflow from the permitted range in many cases will not exceed half of the width of the permitted range at either extreme. In these circumstances, the numbers being clipped display the property that the most significant bit will be an overflow bit representing whether any clipping is needed and, if there is an overflow, the next most significant bit will give an indication of to which of the saturated values of the permitted range the number should be modified. The recognition of these properties allows highly efficient clipping to be achieved by a combination of left shifting and substitution with a saturated value conditional upon an overflow occurring using a saturated value selected in dependence upon the most significant bit of the shifted number.
It will be appreciated that the unclipped data value may be embedded within a larger number with quantization and alignment being required as well as clipping, e.g. the raw input words could be 8-bit plus sign numbers in the range −128 to 383 that effectively contain embedded unclipped data values of −16 to 47 that require clipping to the range 0 to 31.
Improving the efficiency of a clipping operation even by a small degree is highly advantageous when that clipping operation must in practice be executed a large number of times on a set of data such that the gains each time a value is clipped accumulate to produce a significant reduction in total processing load.
The type of data that requires clipping often also requires quantization. The shifting and saturated value generation operations used to clip the data value may be modified with, for example, the use of appropriate masks to simultaneously achieve quantization without any additional processing steps being required.
Whilst it will be appreciated that special purpose hardware could be provided for performing the clipping techniques of the invention, the invention is particularly well suited for use with general purpose processor units operating under software control as such systems typically have the shifting and logical combination instructions that may be used to implement the invention.
In preferred embodiments of the invention said left shifting and said quantization is provided by said processor unit executing a first instruction giving a result of a logical AND operation with input operands of a logically left shifted version of said n-bit input data value and a mask value having its m most significant bits set to 1 and at least its (n−m) next most significant bits set to 0, said first instruction yielding a left shifted and quantized intermediate value.
Such a logical AND operation using a shifted input operand is able to detect the overflow, place the most significant bit of the data value indicating the direction of the overflow in a known position and quantize the data all in one processing step.
In preferred embodiments of the invention generation of said clipped value is provided by said processor unit conditionally executing a second instruction if said carry flag indicates said overflow bit is 1, said second instruction giving the result of a bit clear operation with input operands of an arithmetically right shifted by (m−1) bit positions version of said left shifted and quantized intermediate value and said mask value, said bit clear operation giving a result of said mask value AND NOT said arithmetically right shifted by at least (m−1) bit positions version of said left shifted and quantized intermediate version to yield said clipped value.
The conditional execution of the second instruction responds to whether or not an overflow has taken place and the arithmetic right shift with a logical AND NOT serves to saturate the value to the correct extreme.
The clipped values may often be a component value and in these circumstances preferred embodiments of the invention may combine component values to form a composite value using a logical OR together with logical right shifting.
As previously mentioned the unclipped data value could represent many different forms of data. However, the invention is particularly well suited to the clipping of image data values as these frequently require clipping and when this is the case there is typically a large number of values requiring clipping and so the efficiency gains of the invention yield greater benefits.
A particularly frequently occurring problem is the processing of decompressed data values obtained following a lossy compression process. Lossy compression, such as JPEG or MPEG compression, is good at achieving high degrees of compression but has the disadvantage that when the data is decompressed sometimes the data values generated lie outside of the predetermined range and require clipping. These circumstances are also often ones in which the degree to which the data values lying outside the permitted range is limited to less than half the span of the predetermined range and so the present invention may be used to considerable advantage.
Viewed from another aspect the present invention provides a computer program storage medium bearing a computer program for controlling a data processing apparatus to perform a method of processing an unclipped data value in a range of −0.5N to (1.5N−1) to generate a clipped data value clipped to a range of 0 to (N−1), where N is 2
m
, said unclipped data value is represented by an overflow bit followed by an m-bit num
Dijkstra Wilco
Symes Dominic Hugo
Arm Limited
Le Don Phu
Mai Lam T.
LandOfFree
Clipping data values in a data processing system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Clipping data values in a data processing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clipping data values in a data processing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3004324