Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-11-20
2001-11-06
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S523000
Reexamination Certificate
active
06314443
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data processing systems. More particularly, this invention relates to data processing systems for performing arithmetic operations suitable for performing saturated arithmetic operations.
2. Description of the Prior Art
Many DSP algorithms use what is sometimes known as Q15 arithmetic and Q31 arithmetic. A Q15 number is an ordinary 16-bit 2's complement integer, but is regarded as representing that integer divided by 2
15
. Since a 16-bit 2's complement integer can represent numbers from −2
15
to +2
15
−1, a Q15 can represent numbers from −1 to +(1-2
−15
).
Similarly, a Q31 number is an ordinary 32-bit 2i's complement integer, regarded as being divided by 2
31
, and is able to represent numbers from −1 to +(1−2
−31
). (N+1)-bit QN numbers can be defined analogously for any other value of N.
An important feature of Q15 and Q31 arithmetic is that they are “saturating”. If the mathematical arithmetic result of an operation exceeds the maximum positive value (+1-2
−N
), then the saturated result is the maximum positive value; similarly, if the mathematical result is less than −1, then the saturated result is −1. For example, in Q15 arithmetic, if A=0×8000 (representing −1) and B=0×C0000 (representing −0.5), then adding A and B will produce a result of 0×8000 (representing −1) rather than the normal 16-bit 2's complement result of 0×4000.
A highly desirable and commonly occurring operation in DSP algorithms is a “multiply-accumulate”, i.e. a multiplication of two operands followed by the additional of a third operand:
Result=(A*B)+C
Significant problems arisc when wishing to provide such multiply-accumulate instructions for saturated (sometimes known as clipped) arithmetic. This is particularly the case when performing arithmetic on QN numbers.
In order to accommodate the various different types of instruction in both saturated and non-saturated form a considerable amount of opcode bit space is required. Furthermore, when seeking to provide single cycle multiply performance, the additional burden of having to cope with the requirements for saturation and associated adjustments is such that the clock speed is undesirably limited by the worst-case saturated multiply instruction.
SUMMARY OF THE INVENTION
Viewed from one aspect the present invention provides data processing apparatus comprising.
(i) an instruction decoder responsive to data processing instruction words to generate processing control signals; and
(ii) processing logic controlled by said processing control signals to perform data processing operations upon data operand words; wherein
(iii) said instruction decoder is responsive to a first instruction word to generate control signals to control said processing logic to perform a data processing operation upon a first N-bit data operand word P and a second N-bit data operand word Q to generate a result N-bit data word R as given by:
R=Sat (Fun (P)+Q),
where
Sat (X) is a function returning a saturated value of X, and
Fun (X) is a function operative for at least those values of X that may be generated by an N/2-bit by N/2-bit signed multiplication to return a value obtained by shifting X by a shift amount to generate a shifted word and saturating said shifted word.
The invention recognises that the provision of a special purpose instruction suitable for dealing with the requirements of a saturated multiply-accumulate operation has significant advantages. More particularly, the timing requirements for the standard desired single cycle multiply are eased with the adjustments required to deal with the saturated nature of the arithmetic being more readily accommodated in the cycles used by the subsequent instruction which performs the accumulate operation. The new instruction is also able to replace the need to define saturating versions of several multiply instructions thereby reducing the opcode bit space and other overhead required to support saturating arithmetic. Finally, the new instruction may be implemented with little additional hardware over that which may be already provided within the system to deal with other aspects of unsaturated and saturated arithmetic.
It will be appreciated that the hardware used to implement the new instruction could take many different forms. The different operations necessary to produce the final result N-bit data word could be grouped in various different ways and performed by different circuit block. These various different alternatives that produce the result N-bit data word with the same final value as given above using a single instruction are all embodiments of the invention.
In an analogous manner to the above described instruction for use in saturated multiply-accumulate operations, similar instructions may also be provided to support saturated multiply-decrement operations.
The shift amount applied by the instructions of the invention may have various different values. However, a shift amount being such that the shifted word is double the first N-bit data operand word P is particularly usefull
If an integer multiply is performed on two Q15 numbers, then the normally generated result is a 32-bit “Q30-like” number, for which the ordinary 32-bit signed 2's complement value is regarded as being divided by 2
30
and thus representing numbers from −2 to +(2-2
−30
). A Q30-like number may also be considered to be a signed 32-bit fixed point number with 30 binary places. However, what is required for further processing in such circumstances is a Q31 number. In order to deal with this problem, the instruction of the invention may be executed following a standard integer multiply and the shift amount used to double the result of the integer multiply to change it from Q30-like form to Q31 form prior to it being saturated and subject to an accumulate or decrement. Thus, one of the problematic adjustments needed for saturated arithmetic support may be provided with the adjustment to the result of the integer multiply being accommodated within the subsequent instruction rather than having to be provided by the end of the multiply cycle.
Logic circuits for performing saturation can take many different forms. However, in preferred embodiments of the invention saturating said shifted word comprises detecting predetermined characteristics of said first N-bit data operand word P and, if detected, replacing said shifted value with a respective end point value of a range of permitted values.
This feature recognises that in some circumstances saturation can be provided by detecting characteristics of the first N-bit data operand word P as the manipulation to be performed upon it is of a relatively restricted form and so the circumstances that can give rise to an overflow or an underflow requiring saturation may be specifically detected resulting in an overall decrease in hardware requirements.
In particular, when the shift amount being applied doubles the first N-bit data operand word P, then the need for saturation can be detected in an advantageously simply way by comparing the two most significant bits of the first N-bit data operand word P.
Compared to the relatively restricted range of circumstances that can give rise to an overflow or an underflow for the Fun(X) instruction, overflow or underflow for the Sat(X) function can occur more generally and so preferred embodiments of the invention are such that Sat (X) comprises detecting if X lies outside of a range of permitted values and, if detected, replacing X with a respective end point value of said range of permitted values to generate said N-bit result data word R.
Whilst the new instructions of the present invention are advantageous in their own right, they are, as mentioned above, particularly well suited to embodiments in which a multiplier is provided for executing a second instruction word that genera
ARM Limited
Malzahn David H.
Nixon & Vanderhye P.C.
LandOfFree
Double/saturate/add/saturate and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Double/saturate/add/saturate and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Double/saturate/add/saturate and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588378