Electrical pulse counters – pulse dividers – or shift registers: c – Shift register
Reexamination Certificate
2003-11-21
2004-12-07
Wambach, Margaret R. (Department: 2816)
Electrical pulse counters, pulse dividers, or shift registers: c
Shift register
C377S075000
Reexamination Certificate
active
06829321
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is overflow detection for shifter circuits used in data processing.
BACKGROUND OF THE INVENTION
Detection of overflow when shifting data in an arithmetic logic unit (ALU) requires logic with significant propagation delay. Often overflow detection takes more time than the shift operation that generates the overflow. The conventional algorithm for overflow detection performs mask generation and data propagation serially or sequentially. This algorithm may be described as follows. First a shift mask is generated from the binary value of the desired impending shift.
Table 1 shows an example of the shift mask generation for 16-bit shifter. The mask has five leading bits ‘1’, ten following bits ‘0’ and a least significant bit that is a don't care (X).
TABLE 1
Shift value
0101
Mask
1111 1000 0000 000X
In the next step the mask is used to filter the data with AND gates as follows. The least significant bit of the data is ignored because it will never be shifted out by shift operation. Table 2 shows 16-bit filtering for the example shift value of 5 (binary 0101).
TABLE 2
Data
0010 1001 1110 0011
Shifted Data
0011 1100 011X XXXX
Mask
1111 1000 0000 000X
Result
0010 1000 0000 000X
The resulting bit sequence contains ‘1’ bits if the shift would cause an overflow. The propagation circuit detects occurrence of ‘1’ bits by taking a logical OR of each bit in the sequence, and ‘1’ appears at the overflow output OVF when overflow occurs.
This conventional algorithm takes significant time tc execute because data propagation for the OR operation starts ration and masking operation complete. The truth table for 16-Bit overflow detection is given in Table 3. The complexity of a conventional 16-bit overflow detector function is not extraordinary and the truth table may be satisfied with a straightforward logic design.
TABLE 3
Shift
LSB Data = ‘1’ Causing
Masked
Value
Overflow with Shift
Bits
S0
S1
S2
S3
15
D1
D15-D1
1
1
1
1
14
D2
D15-D2
0
1
1
1
13
D3
D15-D3
1
0
1
1
12
D4
D15-D4
0
0
1
1
11
D5
D15-D5
1
1
0
1
10
D6
D15-D6
0
1
0
1
9
D7
D15-D7
1
0
0
1
8
D8
D15-D8
0
0
0
1
7
D9
D15-D9
1
1
1
0
6
D10
D15-D10
0
1
1
0
5
D11
D15-D11
1
0
1
0
4
D12
D15-D12
0
0
1
0
3
D13
D15-D13
1
1
0
0
2
D14
D15-D14
0
1
0
0
1
D15
D15
1
0
0
0
FIG. 1
illustrates a conventional overflow detection circuit for a 16-bit shifter. The circuit consists of three parts: a mask decoder generator at levels
101
,
102
, and
103
; masking levels
104
and
105
; and a propagation stage in levels
106
through
108
. Shift value 100 is the number of bit positions the data is to be shifted during the impending shift in binary. The mask decoder generator at levels
101
,
102
and
103
decodes the value into a series of binary digits called the shift mask S. When the shift value S is N, the shift mask consists of N bits of ‘l’s and M-N-1 bits of. ‘0’s, where M is bit-length of the data. In the example illustrated above, with shift value binary ‘0101’ (or decimal 5), the leading five bits D
11
through D
15
mark bit positions in which a ‘1’ in the data produces an overflow. Mask generation is performed in logic levels
101
through
103
. The 15-bit shift mask appears at the output of logic level
103
. Recall that the least significant bit cannot generate an overflow. Then, a cluster of AND gates performs the masking operation driving outputs at level
104
. The logic masks these bit positions in logic levels
101
through
103
. Data information enters at level
104
and the resulting bit sequence from the masking operation enters at level
105
. The remaining logic levels
106
,
107
, and
108
form an OR-tree to compute the presence of a data value of ‘1’ within the masked field producing an overflow.
FIGS. 2A and 2B
illustrate a conventional 32-bit overflow detector.
FIG. 2A
is the first portion and
FIG. 2B
the second portion of the logic. First note that several packets of signals form the interconnect between the two figures. Signal packet
201
passes the five shift bits S
0
through
54
between the two drawings. Signal packet
202
passes several intermediate signals generated in
FIG. 2B
to inputs of logic in FIG.
2
. Signal packet
203
passes the sixteen most significant data bits D31:D16 from
FIG. 2A
to FIG.
2
B. Finally, two inputs
206
and
207
to OVF output gate
208
of
FIG. 2A
come from log-c generating these signals in FIG.
2
B.
Table 4 shows the truth table for the 32-bit overflow detector function for shifters. This table can be applied directly to generation of the logic of
FIGS. 2A and 2B
which are most similar in organization to that of the conventional 16-Bit shifter overflow detector function of FIG.
1
. It: is worthwhile to point out that in the design of many high speed logic functions optimal propagation delay performance dictates that each gate have a relatively small number of inputs. Often it is desirable to use cascaded two input gates in preference to less levels of gates having a large number of inputs (e.g. 8-input gates). Also it is sometimes preferable to use cascaded NAND gates to implement the logical equivalent of and AND-OR function for example. The cascaded NAND function appears in several parts of the logic of
FIGS. 2A and 2B
. One example is noted with NAND gates
211
,
212
, and
213
cascaded with NAND gate
205
. Notice that in both the conventional 16-bit overflow function of FIG.
1
and the conventional 32-bit shifter of
FIGS. 2A and 2B
, decoding of the shift value precedes the input of data in the logic path. Levels
101
,
102
perform the shift decoding in FIG.
1
. Levels
201
and
202
perform shift value decoding in
FIGS. 2A and 2B
.
TABLE 4
Shift
LSB Data = ‘1’ Causing
Masked
Value
Overflow with Shift
Bits
S0
S1
S2
S3
S4
31
D1
D31-D1
1
1
1
1
1
30
D2
D31-D2
0
1
1
1
1
29
D3
D31-D3
1
0
1
1
1
28
D4
D31-D4
0
0
1
1
1
27
D5
D31-D5
1
1
0
1
1
26
D6
D31-D6
0
1
0
1
1
25
D7
D31-D7
1
0
0
1
1
24
D8
D31-D8
0
0
0
1
1
23
D9
D31-D9
1
1
1
0
1
22
D10
D31-D10
0
1
1
0
1
21
D11
D31-D11
1
0
1
0
1
20
D12
D31-D12
0
0
1
0
1
19
D13
D31-D13
1
1
0
0
1
18
D14
D31-D14
0
1
0
0
1
17
D15
D31-D15
1
0
0
0
1
16
D16
D31-D16
0
0
0
0
1
15
D17
D31-D17
1
1
1
1
0
14
D18
D31-D18
0
1
1
1
0
13
D19
D31-D19
1
0
1
1
0
12
D20
D31-D20
0
0
1
1
0
11
D21
D31-D21
1
1
0
1
0
10
D22
D31-D22
0
1
0
1
0
9
D23
D31-D23
1
0
0
1
0
8
D24
D31-D24
0
0
0
1
0
7
D25
D31-D25
1
1
1
0
0
6
D26
D31-D26
0
1
1
0
0
5
D27
D31-D27
1
0
1
0
0
4
D28
D31-D28
0
0
1
0
0
3
D29
D31-D29
1
1
0
0
0
2
D30
D31-D30
0
1
0
0
0
1
D31
D31
1
0
0
0
0
SUMMARY OF THE INVENTION
This invention describes a unique high-speed implementation for overflow detection logic to be used in high performance shifter functions. The overflow logic makes use of parallelism in combining shift value decoding and mask generation logic with the logic necessary to propagate data. Designs for both 16-bit and 32-bit shifters are presented and performance improvement of the new designs over conventional overflow detection circuits is demonstrated.
REFERENCES:
patent: 5777906 (1998-07-01), Lau et al.
patent: 6381295 (2002-04-01), Lin
Brady III W. James
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
Wambach Margaret R.
LandOfFree
High speed and compact overflow detection for shifters does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed and compact overflow detection for shifters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed and compact overflow detection for shifters will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3331301