Automatic Overflow/Imminent Overflow Detector

The present invention generally relates to arithmetic digital circuits and more specifically relates to error detection circuits.

The introduction and widespread use of large scale integrated circuit (LSI) technologies have made possible the incorporation of complex functions within a single device. As a result, many contemporary systems have performance and price characteristics which have significant advantages over previous systems but which introduce some new problems. Of most interest to the present invention is the use of LSI devices to perform complex arithmetic tasks. Because the arithmetic relationship between the inputs and outputs may be quite complex, scaling of the resultant, especially for fixed-point operations, can become difficult. Normally, the scale factor to be used in scaling the output (i.e., postscaling) is determined in advance of the actual arithmetic operation. Whereas this causes efficiency in post scaling, it does tend to cause overflow conditions.

It is very difficult and time consuming to determine the presence of an overflow condition from the data following the postscaling operation, though this approach is common in the art. It would be more desirable to check for an overflow condition before postscaling, but the problem is greatly complicated if the scale factor to be used in postscaling is a variable.

The present invention checks for an overflow condition after the arithmetic operation but before postscaling but permits the scale factor to be used in postscaling to be a variable. This is accomplished by evaluating the data prior to postscaling in light of the scale factor to be used. In this manner, it is determined whether the scale factor to be used is or is not appropriate to the postscaling of the current data. If an overflow condition will occur as a result of postscaling the present data using the present scale factor, an overflow signal is generated and the output of the postscaler is forced to +1 if the arithmetic sign of the unscaled number was positive and -1 if the arithmetic sign of the unscaled number was negative. The forcing of the postscaler output to .+-.1 permits subsequent arithmetic operations to use this resultant with a minimum of propagated error.

The present invention also checks for imminent overflow conditions. An imminent overflow is defined as a postscaler output whose absolute value exceeds 1/2 (but not 1). A signal is generated indicating an imminent overflow which is expected to be useful in prescaling data before the next or subsequent arithmetic operations.

FIG. 1 shows the prior art method of postscaling data following an arithmetic operation.

FIG. 2 shows the same postscaling method with the addition of the overflow/imminent overflow detector.

FIG. 3 shows a detailed block diagram of the preferred embodiment of the present invention.

FIG. 4a shows the format of inputs to the multiplier/accumulators.

FIG. 4b shows the format of the output of the multiplier/accumulators.

FIG. 4c shows the format of the input to the shifters.

FIG. 4d shows the format of the input to the detector.

FIG. 5a is a detailed view of IMAGINARY MUX 106.

FIG. 5b is a detailed view of REAL MUX 107.

FIG. 6 which comprises FIGS. 6a, 6b, and 6c, is a detailed view of IMAGINARY SHIFTER 104.

FIG. 7 which comprises FIGS. 7a, 7b, and 7c, is a detailed view of REAL SHIFTER 105.

FIG. 8 is a detailed view of DETECTOR 108.

FIG. 9 is a table showing the inputs and outputs of the programmable logic arrays.

FIG. 1 shows the prior art method of postscaling the resultant of an arithmetic operation. In this case, MULTIPLY/ACCUMULATE 10 performs an arithmetic operation upon the data received via line 12. The output of MULTIPLY/ACCUMULATE 10 is transferred to SHIFTER 11 for postscaling via line 13. The scale factor to be used by SHIFTER 11 is received via line 14. After postscaling, the enable data signal received via line 16 enables the output of SHIFTER 11 to be transferred via line 15.

FIG. 2 shows the same elements with the addition of DETECTOR 20 and multiplexer, MUX 21. DETECTOR 20 is enabled and disabled via the control line 26 shown. When enabled, DETECTOR 20 utilizes the data received via line 13a to evaluate the appropriateness of the scale factor received via line 14a. If the output of SHIFTER 11 will be the result of an overflow or an imminent overflow (i.e., absolute value greater than 1/2) condition following postscaling, DETECTOR 20 will so indicate via the appropriate signal on line 25.

DETECTOR 20 presents a +1 quantity signal to MUX 21 via line 23 if the arithmetic sign of the data received via line 13a is positive or presents a -1 quantity signal to MUX 21 via line 23 if the arithmetic sign of the data received via line 13a is negative. For non-overflow conditions, DETECTOR 20 transfers a signal via line 24 causing MUX 21 to select the data received from SHIFTER 11 via line 22 for output on line 15. If an overflow condition is detected, DETECTOR 20 transfers a signal to MUX 21 via line 24 causing MUX 21 to select the quantity (i.e., .+-.1) received via line 23 for output via line 15. In this manner, an overflow condition causes the DATA OUT (transferred via line 15) to be .+-.1 whenever an overflow condition is present. The enable data signal on line 16 is now transferred to MUX 21 cause data to be output on line 15.

FIG. 3 shows the functional operation of the preferred embodiment which processes complex fixed point numbers. The imaginary portion is processed by IMAGINARY MULT/ACC 100, BUFFER 102, IMAGINARY SHIFTER 104, and IMAGINARY MUX 106. The real portion is processed by REAL MULT/ACC 101, BUFFER 103, REAL SHIFTER 105, and REAL MUX 107. As shown, the imaginary and real portions are processed in parallel. IMAGINARY MULT/ACC 100 and REAL MULT/ACC 101 are implemented with TRW Model TDC1003J. BUFFER 102 and BUFFER 103 are implemented with standard monolithic devices to provide 20 bits of buffering as required. IMAGINARY SHIFTER 104 and REAL SHIFTER 105 are implemented as shown in FIGS. 6 and 7, respectively. IMAGINARY MUX 106 and REAL MUX 107 are implemented as shown in FIGS. 5a and 5b, respectively. DETECTOR 108 is implemented as shown in FIG. 8.

FIG. 4a shows the format of data input to IMAGINARY MULT/ACC 100 via lines 110 and 112 and input to REAL MULT/ACC 101 via lines 111 and 113. FIG. 4b shows the format of data output from IMAGINARY MULT/ACC 100 via line 116 and from REAL MULT/ACC 101 via line 117. Notice that bit positions 2.sup.0 -2.sup.-22 provide 23 bits of data. The sign is normally found in bit position 2.sup.1 with bit positions 2.sup.2 -2.sup.4 providing three bits of sign overflow. BUFFER 102 and BUFFER 103 are implemented using industry standard part type 74S241. BUFFER 102 and BUFFER 103 buffer only 20 bits with the least significant seven data bits (i.e., bit positions 2.sup.-16 -2.sup.-22) being truncated.

Referring again to FIG. 3, the output of BUFFER 102 is transferred to IMAGINARY SHIFTER 104 and DETECTOR 108 via line 118. The output of BUFFER 103 is transferred to REAL SHIFTER 105 and DETECTOR 108 via line 119. FIG. 4c shows the format of the 19 bits transferred to IMAGINARY SHIFTER 104 and REAL SHIFTER 105 via lines 118 and 119, respectively. FIG. 4d shows the format of the 10 bits transferred to DETECTOR 108 via lines 118 and 119. FIG. 4a shows the format of the 12 bits transferred via line 120, line 121, line 126, and line 127.

As shown in FIG. 3, DETECTOR 108 detects overflow and imminent overflow during processing of the imaginary portion by using the 10 bit quantity received from BUFFER 102 via line 118 and a three bit scale factor received via line 114. DETECTOR 108 controls IMAGINARY MUX 106 via lines 122 and 124. Overflow and imminent overflow conditions involving the real portion are detected by DETECTOR 108 using the 10 bit quantity received from BUFFER 103 via line 119 and the three bit scale factor received via line 114. REAL MUX 107 is controlled by DETECTOR 108 via lines 123 and 125. Line 128 contains two conductors. One conductor transfers an overflow signal generated as a result of an overflow condition involving either the imaginary portion or the real portion. The other conductor transfers an imminent overflow signal generated as a result of an imminent overflow condition involving either the imaginary portion or the real portion. Line 115 transfers detector control signals which are discussed further below. The enable data signal received via line 129 enables IMAGINARY MUX 106 and REAL MUX 107 to output imaginary data via line 126 and real data via line 127, respectively.

FIGS. 6 and 7 show the detailed implementation of IMAGINARY SHIFTER 104 and REAL SHIFTER 105, respectively. 4-BIT SHIFTERS 300, 301, 302, 303, 304, 305, 350, 351, 352, 353, 354, and 355 are industry standard part type 25S10. Table A shows the relationship between the conductors of lines 118 and 119 and the bit positions shown in FIG. 4c as input to IMAGINARY SHIFTER 104 and REAL SHIFTER 105, and the bit positions as shown in FIG. 4d as input to DETECTOR 108. Table B shows the relationship between the bit positions of FIG. 4a and the various conductors of lines 120 and 126. Table C shows the relationship between the bit portions of FIG. 4a and the various conductors of lines 121 and 127. As is seen in FIGS. 6 and 7, the imaginary portion and the real portion, respectively, are postscaled according to the eight possible and distinct values of the scale factor received via the three conductors of line 114 (i.e., lines 114a, 114b, and 114c).

FIGS. 5a and 5b show the detailed implementation of IMAGINARY MUX 106 and REAL MUX 107, respectively. QUAD MUX's 201, 202, 203, 251, 252, and 253 are implemented using industry standard part type 74S257.

FIG. 8 shows the detailed implementation of DETECTOR 108. LOGIC ARRAY 400 and LOGIC ARRAY 401 are SIGNETICS part type 82S100. The manufacturer provides instructions in how to program the LOGIC ARRAY.

FIG. 9 provides the program required to be entered into each (i.e., LOGIC ARRAY 400 and LOGIC ARRAY 401). Referring again to FIG. 8, LATCH 404 is industry standard part type 9314. As can be seen, line 128 indicates whether there is an overflow condition involving the imaginary portion or the real portion and whether there is an imminent overflow condition involving the imaginary portion or the real portion.

Line 115 contains three conductors which control the operation of DETECTOR 108. As can be seen in FIG. 8, line 115c supplies a clear signal to LATCH 404. The clear signal is used by the system controller to clear LATCH 404 from any previous overflow or imminent overflow conditions. Lines 115a and 115b are the enable/disable imminent overflow and overflow detection, respectively. The system controller uses lines 115a and 115b to enable/disable detection. In the preferred embodiment, the system controller is a microprogrammed device having a 120 bit microinstruction word. In this application, the state of lines 115a and 115b are determined by bits 2.sup.9 and 2.sup.10 of the microinstruction word. However, lines 115a, 115b, and 115c may be set or cleared by other means including manual switches.

Referring again to FIG. 9, the various detection conditions can be observed. Note at condition No. 16, input connection A1 is low. This corresponds to a low on line 115b (see also FIG. 7). This condition disables overflow detection making Z0, Z3, and Z5 active. From FIG. 9 it is seen that Z0 and Z5 are low and Z3 is high. Therefore, from FIG. 8 it can be seen that the bit position of LATCH 404 corresponding to overflow (i.e., Q3) cannot be set via gate 402 and no overflow condition will be detected. Furthermore, lines 122a, 124a, 123a, and 125a will be forced low causing IMAGINARY MUX 106 (see also FIG. 5a) and REAL MUX 107 (see also FIG. 5b) to select the data received from IMAGINARY SHIFTER 104 via line 120 and from REAL SHIFTER 105 via line 121, respectively. Similarly, condition No. 34 of FIG. 9 shows a low on input connection A2. From FIG. 8 this can be seen to be a disable imminent overflow detection condition causing output connection Z2 to be active (i.e., high). This condition prevents the imminent overflow bit positions (i.e., Q0 and Q1) of LATCH 404 from being set.

Condition No. 17 of FIG. 9 shows that whenever input connection A12 (i.e., lines 118a or 119a) is high, corresponding to sign bit position 2.sup.4 set (see Table A and FIG. 4d), connections Z1 and Z4 are active, making Z1 low and Z4 high. This signifies that a negative quantity is present. A -1 rather than a +1 is presented to IMAGINARY MUX 106 via lines 122b and 124b and to REAL MUX 107 via lines 123b and 125b. Reference to FIG. 5a will show that if line 122b is high and line 124b is low, the D1 input of QUAD MUX 201 will be one and all other inputs of QUAD MUX 201 and all inputs of QUAD MUX 202 and QUAD MUX 203 are zero signifying -1. Reference to FIG. 5b shows the corresponding result for REAL MUX 107 as a result of line 123b high and line 125b low.

Condition No.'s 18-33 of FIG. 9 show the operation of the imminent overflow detector when enabled (i.e., input connection A2 high). Notice that Z2 is active (i.e., high) and no imminent overflow can occur for the combinations of scale factor (i.e., input connections A13, A14, and A15) and input connections A3-A12 shown. Any other combination of scale factor and input connections A3-A12 is detected as an imminent overflow causing Z2 to be low and setting the appropriate (i.e., either Q0 or Q1) position of LATCH 404. See also FIG. 8.

Condition No.'s 0-15 of FIG. 9 similarly show the operation of the overflow detector as enabled by the high at input connection A1. For each of the conditions shown (i.e., condition No.'s 0-15) no overflow condition is present causing Z0, Z3, and Z5 to be active as explained above. For all other conditions, an overflow is detected causing output connections Z0 and Z5 to be high and output connection Z3 to be low. As seen in FIG. 8, if Z3 of either LOGIC ARRY 400 or LOGIC ARRAY 401 is low, bit position Q3 of LATCH 404 is set by gate 402. Furthermore, IMAGINARY MUX 106 and REAL MUX 107 are caused to select a .+-.1 for output, because lines 122a and 124a, or 123a and 125a, are high. Referring again to FIG. 5a, if lines 122a and 124a are high, QUAD MUX 201, QUAD MUX 202, and QUAD MUX 203 select the inputs presented at A1, B1, C1, and D1. These inputs are received via lines 122b and 124b and are determined by DETECTOR 108 as explained above. Reference to FIG. 5b will show that lines 123a and 125a similarly cause REAL MUX 107 to select the inputs received via lines 123b and 125b.

One can readily verify the existence of overflow conditions or imminent overflow conditions not present in FIG. 9. The preferred embodiment uses specific design parameters which may readily be modified by those skilled in the art to utilize the present invention within other applications.