Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
2000-06-23
2004-11-16
Bahta, Kidest (Department: 2125)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S090000, C708S525000
Reexamination Certificate
active
06819971
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to circuits for digital signal processing systems, and, more particularly, detecting the overflow flag of a barrel shift operation.
2. Description of the Related Art
Bit manipulation units (BMUs) are circuits commonly employed in digital signal processors (DSPs), micro-controllers, or other types of processors to scale and format data. Typical instructions executed by a BMU include: (a) arithmetic shift left or right, (b) logical shift right, and (c) normalize. Pseudo-code equations (1) through (4) below represent these operations:
aD0=aS0>>aS1
/*arithmetic shift right */
(1)
aD0=aS0<<aS1
/*arithmetic shift left */
(2)
aD0=aS0>>>aS1
/*logical shift right */
(3)
aD0=norm(aS0,aD1)
/*normalize */
(4)
where aD0 and aD1 represent resulting output data written to corresponding destination accumulators, and aS0 and aS1 represent input data stored in corresponding source accumulators. For an arithmetic shift right operation, redundant sign bits are shifted in from the left, while for a logic shift right operation, padding bits (logic “0” or logic “I”) are shifted in from the left. For an arithmetic shift left operation, padding bits are inserted from the right. For a BMU, an operation for logical shift left is generally not defined since a logical shift left operation generates the same numerical result as an arithmetic shift left operation.
A BMU executes one operation in one clock cycle. In the DSP16000 processor available from Lucent Technologies of Murray Hill, N.J., for example, the source and destination accumulators are 40 bits wide; each accumulator may contain up to 32 bits of data and eight guard bits for overflow, and have a maximum shift amount of 31 bits. FIGS.
1
(
a
),
1
(
b
), and
1
(
c
) illustrate changing bit positions for the three shift operations of equations (1), (2), and (3), respectively, in the exemplary prior art processor. For the normalize operation of equation (4), the BMU shifts the bits of the 40-bit input data an appropriate shift amount (number of bit positions) to represent the value with a 32-bit result and an exponent.
FIG. 2
shows logic circuit
200
for an exemplary implementation of a prior art BMU
201
and external accumulator
202
. The circuit
200
has three primary input values: (a) the data aS0, which is a sequence of bit values, (b) the shift value, which is the direction (indicated by the sign bit of the shift value) and number of bit positions by which the data is to be shifted corresponding to the shift amount, and (c) the saturation mode value SAT. The saturation mode value SAT identifies whether the output values are to be limited to a 32-bit sequence. The data aS0 is provided to BMU
201
from, for example, 40-bit wide first source accumulator included in external accumulator
202
. The shift value may be the shift value aS1 that is provided to BMU
201
from the upper half of a second source accumulator, that may be included in external accumulator
202
, or the shift value may be an immediate value from the instruction itself. The shift value aS1 may be limited to 6 bits by limiter
210
. The saturation mode value SAT is provided from an external control register (not shown) that is set by an instruction. If the saturation mode value SAT is enabled, as described subsequently, then a result generated by BMU
201
may be limited to a length of 32 bits. In addition, the input value SHIFT identifies whether an arithmetic/logic shift operation or a normalize operation is to be performed.
The circuit
200
has three primary output values: (a) two 40-bit results aD0 and aD1 written to external accumulator
202
(or other register file), and (b) an overflow flag LMV that is set and written to a status register (not shown). The input value SHIFT applied to multiplexer (mux)
211
selects either 1) the shift value from limiter
210
for an arithmetic shift left or right operation or 2) the shift amount for a normalize operation that is generated by exponent/compare module
205
. Barrel shifter
203
performs a shift, either left or right, of the input data aS0 based on the decoded input SV from mux
211
. Barrel shifter
203
may include a decoder to translate the value SV from mux
211
into 1) the number of bit positions to shift the input data aS0 and 2) whether to shift the input data aS0 left or right.
The result aD0 is the output of a barrel shift operation applied to the input sequence aS0 by barrel shifter
203
, where the sequence length of the result may be limited by saturate module
204
. When the overflow flag LMV is not set, the result aD0 may be represented with 32-bits, and so limiting the result from barrel shifter
203
with saturate module
204
is not necessary (SAT is in a “don't care” state).
When the overflow flag LMV is set, the result aD0 may not be represented with 32 bits (i.e., an overflow occurs). Whether a 32-bit or 40-bit result aD0 is written to the external accumulator is determined by the output signal of AND gate
208
applied to saturate module
204
. AND gate
208
generates as an output signal the logical AND of 1) the overflow flag LMV and 2) the saturation mode value SAT. If saturation mode value SAT is enabled, then the output of AND gate
208
causes saturate module
204
to limit the result aD0 to the range 0xff80000000 to 0x007fffffff (Hex). If saturation mode value SAT is disabled, then the output of AND gate
208
causes saturate module
204
to pass the entire 40-bit result aD0 to the external accumulator
202
.
For the normalize operation, the BMU
201
shifts the input bits by an appropriate shift amount to represent the value with 32-bits. The shift amount is referred to as the “exponent” and the result aD1 is the exponent for the normalize operation. The (e.g., 6-bit) exponent is generated by exponent/compare module
205
based on the input data aS0, and exponent/compare module
205
also generates the logical overflow value LLV component of the overflow flag LMV (described below).
The overflow flag LMV is a value comprising two components. The first component is the logical overflow value LLV determined by exponent/compare module
205
. Exponent/compare module
205
compares the 6-bit value SV from the mux
211
to the 6-bit exponent generated for the input data aS0. The exponent also indicates the number of redundant sign bits in the input data aS0. If the shift value is greater than the number of redundant sign bits, a logical overflow has occurred, and exponent/compare module
205
sets the logical overflow value LLV to one. For the described exemplary implementation of the prior art, the logical overflow value LLV is only set to one on left shifts and, by definition, is set to zero on right shifts. The second component of the LMV, sometimes referred to as the math overflow value, is determined after the input has been shifted. A test determines if the bits in the positions corresponding to the guard bits and the most significant bit of the input data aS0, such as bits
39
to
31
in the exemplary embodiment, and the result aD0 are not all the same. Compare module
212
applies the test to the output aD0 prior to application to saturate block
204
, and the overflow flag LMV is set when the test determines the bits are not the same. As shown in
FIG. 2
, the overflow flag LMV is generated by OR gate
209
as a logic OR of 1) the logical overflow value LLV and 2) the math overflow value of the compare module
212
. In some implementations, the logical overflow value LLV is a separate flag and the LMV is only set if all of the guard bits are not the same as bit
31
.
SUMMARY OF THE INVENTION
The present invention relates to faster computation of the overflow flag LMV in a bit manipulation unit (BMU). For fast computation, the overflow flag is computed based on the input data and the shift amount. The overflow flag is calculated separately as either a LMV
left
for an arithmetic shift left operation or LMV
right
, for an arithmetic shift right oper
Alidina Mazhar M.
Goldovsky Alexander
LandOfFree
Fast computation of overflow flag in a bit manipulation unit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast computation of overflow flag in a bit manipulation unit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast computation of overflow flag in a bit manipulation unit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3356003