JPS607816B2 - Overflow detection and correction circuit - Google Patents

Description

[Detailed description of the invention] The present invention relates to overflow detection and correction circuits.

In a secondary cyclic digital filter or the like, overflow occurring in an adder may cause an oscillation phenomenon called a limit cycle, which poses a problem.

Therefore, an overflow detection circuit and an overflow correction circuit are required. In the following explanation, all input/output data are expressed in digit numbers of 2, and are in a serial data format in which the 4th most significant bit (hereinafter abbreviated as LSB) comes first in terms of time.

FIG. 1 shows an example of a conventional overflow detection circuit.

Two data to be added are input to terminals 1 and 2, and data after addition is input to terminal 3.

Furthermore, a pulse indicating the position of a sign bit (hereinafter abbreviated as MSB) for indicating polarity is input to the terminal 4. If the signs (polarity) of the two input data before addition are both negative (“1”)
”) and the sign of the data after addition is positive (0), the output of the NAND element 10 becomes “1” and is output from the terminal 10, causing negative overflow. shows.

Conversely, if the signs of the two input data to be added are both correct 0
”) and the sign of the data after addition is negative (“1”), the output of the NAND element 20 becomes “1” and is output to the terminal 200, causing a positive overflow. shows.

FIG. 2 shows an example of a conventional overflow correction circuit.

Information indicating that a positive overflow has been detected is input to terminals 1 and 2, and information indicating that a negative overflow has been detected is input to terminals 3 and 4.

Here, it is assumed that two sets of overflow detection circuits as shown in FIG. 1 are provided at the front stage. Further, the positive number with the maximum absolute value is input to the terminal 5, and the negative number with the maximum absolute value is input to the terminal 6. With the above configuration, when overflow occurs, the maximum number of absolute values depending on the sign can be obtained at the terminal 8. Also, when overflow does not occur, terminal 7
The data input to the terminal 8 is output to the terminal 8 as is.
FIG. 3 is a block diagram of an overflow detection and correction circuit constructed by combining the overflow detection circuit shown in FIG. 1 and the overflow correction circuit shown in FIG.

Reference numeral 1 means the overflow detection circuit shown in Figure 1, reference numerals 20 and 30 refer to the flip-flops, reference numeral 40 represents the positive and negative maximum number generation circuit, and reference numeral 50 represents the overflow detection circuit shown in Figure 2. The detection circuit and reference numeral 60 are one word long shift registers.

As shown in FIG. 1, two data to be added are input to terminals 1 and 2, and data after addition is input to terminal 3.

Also, when a positive overflow occurs, terminal 1 becomes “1” at the MSB, and when a negative overflow occurs, the MSB
At time B, the terminal 12 becomes "1". Therefore, in order to correct data that has caused an overflow, it is necessary to use the flip-flops 20 and 21 to hold information for one word length (one data) as to whether or not an overflow has occurred. Furthermore, the data after the addition is given to the shift register 6, and the output 61 delayed by one word length, the outputs 41 and 42 of the positive and negative maximum number generation circuit 40, and the output 31 of the flip-flop 30 are corrected for overflow. If it is the input of the circuit 50, the terminal 4
output data with overflow corrected is obtained. As mentioned above, the number of ICs is large because SS1 (small sized inch graded circuit) is used for the subordinate overflow detection circuit and overflow correction circuit, which increases the hardware scale. There are drawbacks that lead to An object of the present invention is to provide an overflow detection and correction circuit that integrates an overflow detection circuit and an overflow correction circuit and has a simplified configuration.

Another object of the present invention is to provide an overflow detection and correction circuit with a small circuit scale.

The overflow detection and correction circuit of the present invention includes an 8-input and 2-output read-only memory (hereinafter referred to as ROM), two flip-flops, a first and second flip-flop, a 2-1 selector, and a shift register. , two serial data to be added ×
and Y, the serial data Zn after addition, and the serial data Zn
serial data Zn- delayed by 1 bit, the output OFn- of the first flip-flop, the output sn- of the second flip-flop, and the sign bit (hereinafter abbreviated as MSB) of the serial data ×, Y, and Zn. ) and a timing pulse indicating the position of 2 bits from the MSB are set as 8 inputs of the ROM, and OFn indicating an overflow and the data Zn are corrected when the serial data Zn causes an overflow. The output sn for the flip-flop is set as two outputs of the ROM, the OFn indicating the overflow and the output sn of the ROM are respectively input to the first and second flip-flops, and the outputs sn-, and Serial data obtained by delaying the serial data Zn by one data are used as two inputs of the 2-1 selector, and the output OFn of the first flip-flop is used as a selection signal input of the 2-1 selector. It is characterized by having been configured.

First, before explaining the present invention, the relationship between the number of bits of one word length and overflow will be briefly described.

Let the data chair be M bits, and consider it as (M-2) bits below the decimal point.

In this case, the value of the displayable data x is −2S×<2. Now, assume that the two data to be added are X and Y, and the data of their sum is Z. However, Z=X+Y,
It is assumed that ×, Y, and Z are all expressed in M bits. It is also assumed that the input data X and Y are in the range of -2SX<2, -2SY<2, and the output Z satisfies the condition -ISZ<1. Therefore, Z becomes -4miZ<4, and -ISZ
Z that does not satisfy the condition <1 is considered to have caused an overflow. Therefore, if overflow occurs, the following two steps should be taken.
limited to the street. First, Z is -2 mi Z<-1,1
This is a case where MiZ<2.

At this time, overflow can be detected by determining whether the upper two bits match or do not match. Further, the true code that does not cause overflow at that time matches the MSB of Z. Second, Z
is in the range of -4miZ<-2, 2miZ<4.

At this time, overflow can be detected since input data X and Y have the same sign and Z has a different sign. Further, the true code that does not cause overflow at that time matches the MSB of input data X or Y. As described above, overflow is limited to the first case and the second case, so overflow detection and overflow correction need only be performed for the above two cases.

Next, the present invention will be explained in detail with reference to the drawings.

FIG. 4 is a block diagram showing one embodiment of the present invention. Reference numeral 2 is a 256 word x 2 bit ROM, reference numerals 1, 3 and 4 are flip-flops, reference numeral 5 is a 2-1 selector, and reference numeral 6 is a shift register. Fourth
The contents written in the ROM 2 in the figure are shown in Tables 1, 2, and 3.

Table 1 Table 2 Table 3 In Tables 1, 2 and 3, the symbols OFh-,,
sn-. , Zn, Zn-, , x and y indicate input bits, and symbols OFn, sn indicate output bits.

Further, the symbol 0/1 indicates that it may be either "0" or "1". Table 1 shows that the timing pulse indicating the MSB position is “1”.
” shows the contents of ROM2 at the time of “.

When the output bit OFn is "1", it indicates that an overflow has occurred, and when it is "0", it indicates that an overflow has not occurred.

For example, Zn="0", Zn-,="1", x="0"
And when y="0", the MSB of the sum Z is Zn="0", and the bit 1 bit before the MSB is Zn="1", so it can be considered as an overflow in the first case mentioned above. As a result, the output bit OFn becomes "1".

Also, when Zn="0", x="1" and y="1", the MSB of sum Z is Zn="0", and the inputs X, Y at this time
Since the MSB of is x=“1” and y=“1”, it is regarded as an overflow in the above-mentioned second case, and the output bit OFn becomes “1”. Output bit sn has meaning only when output bit OFn is "1" and outputs the opposite sign of the true addition result when overflow does not occur. For example, in the above example, Zn="0", Zn-, one "1"
, x=“0” and y=“0”, the true addition result when digit overflow does not occur is positive, so Sn=“1”. Also, when Zn = "0", Zn = ''0'', x = "1" and y = "1", the true addition result without overflow is negative, so sn = “0”.

The output bit sn is used to generate the maximum number according to the sign of the correct addition result for overflow correction.

Table 2 shows the timing pulses and M
This shows the contents of the ROM 2 when the timing pulses indicating the position 2 bits before SB are both "0".

Input bit OFn- and output bit OFn have exactly the same content, and input bit sn- and output bit sn have exactly the same content. Table 3 shows the contents of the ROM 2 when the timing pulse indicating the position 2 bits before the MSB is "1". Input bit OFn- and output bit OFn have exactly the same content, but input bit sn-
, and output bit sn have opposite contents. Table 1,
The input bits Zn, x and y of Tables 2 and 3 appear at input terminals 300, 400 and 500' of FIG. 4, respectively.

Furthermore, input bits OFn-, , sn-, and Zn- correspond to inputs 30, 40, and 1 of the ROM 2, respectively. Furthermore, the output bit O of Tables 1, 2, and 3
Fn and sn correspond to outputs 21 and 22 in FIG. 3, respectively. In FIG. 4, timing pulses indicating the position of the MSB are input to terminals 100 and 200, respectively.

Now, when the MSB of three serial data Z,
and sn are produced as outputs 21, 22.

Outputs 21 and 22 of ROM2 corresponding to output bits OFn and sn are delayed by 1 bit by flip-flops 3 and 4, respectively, and then fed back to become inputs 30 (OFn-,) and 40 (sn-,) of ROM2. .
The ROM 2 reads output bits OFn and sn according to Table 2 until the timing pulse indicating the position 2 bits before the MSB becomes "1".

Next, when the timing pulse indicating the position 2 bits before the MSB is "1", the ROM 2 reads out the output bits OFn and sn according to Table 3. Finally, at a point one bit before the MSB, the ROM 2 reads output bits OFn and sn according to Table 2. The read operation of ROM2 is
Repeat the operations described above.

Further, the 2-1 selector 5 in FIG. 4 selects the input 40 when the output OFn of the flip-flop 3 is "1".
When it is "0", input 60 is selected. Reference numeral 6 indicates a shift register of one word length (M bits). Figure 5 is the 4th
This is a timing chart for explaining the operation of the block in the figure, where the reference letter a is a timing pulse indicating the position of the MSB, and the reference letter b is the two inputs × and Y to be added.
and the timing phase of each one word length of their sum Z and M
The position of SB is representatively shown.

However, s is considered a sign bit (MSB) in X and Y, but is unknown in Z. Moreover, s is the inversion of s. Reference letters c and d designate the output 22 corresponding to the output bit Sn of the ROM 2 in FIG. 4 and the output 40 (Sn-) of the flip-flop 4, respectively. Reference numeral e indicates a timing pulse indicating a position two bits before the MSB. Reference numerals f and g designate the output 21 corresponding to the output bit OFn of the ROM 2 in FIG. 4 and the output 30 (OFn-,) of the flip-flop 3, respectively. Therefore, by making OFn-, of the reference alphabetic character g, the selection signal input of the 2-1 selector 5 as shown in FIG. , is selected and output from terminal 5 in FIG.

Next, the operation of the present invention will be explained using a specific example. Let the data word length Vi be 5 bits, and consider the following addition. However, B represents the least weighted bit.

In the above formula, the binary code shown on the left is expressed in decimal notation in parentheses.

In the above calculation, if the addition result Z is expressed in 6 bits, it becomes 011,010 (13.25), which is the true addition result, but in order to express Z in 5 bits like the inputs x and Y, It will be considered as 11.010 (-0.750). In other words, overflow occurs. If the above equation is calculated using the present invention, the following will be obtained.

The bits corresponding to the five bits from peak B to MSB are named clocks 0, 1, 2, 3, and 4. At clock 4, it is possible to detect whether overflow has occurred. At this time, Zn="1", Zn-. = “1”, x = “0
” and y=“0” are respectively input to the input terminals A, B, C and D of ROM2 in FIG. 4, and OFn is input according to Table 1.
="1" and sn="1" are given as outputs 21 and 22 of ROM2, respectively.Next, clock 0
At the time point, OFn-, -"1", sn-,="1" are input, and OFn="1", sn="1" are output according to Table 2.

At clock 1, the aircraft has OFn-,=''1'',
sn,="1" is input and OFn="1" according to Table 2
, sn="1" is output. M at the time of Clock 2
Since it is 2 bits before SB, OFn,,sn-, is input, and according to Table 3, OFn="1", sn-,="
0" is output. Therefore, as shown in the timing chart of FIG.
Since Fn=“1”, OFn=“1” from clock 0 to clock 4, and selector 5 of 2-1 in FIG.
The output 40 of the flip-flop 4 will be selected. Furthermore, since the output 40 of the flip-flop 4 corresponds to sn-, "1", "1", "1", "0", "
0". Therefore, the input data Z
The value of is corrected to 00.111 (100.875) and output 5
It becomes 0. However, the output data is delayed by 5 bits (M bits) compared to the input data Z. As described above, according to the present invention, it is possible to provide an overflow detection and correction circuit with a simple circuit and small hardware scale using a ROM, a flip-flop, a 2-1 selector, and a shift register.

[Brief explanation of drawings]

Figure 1 shows an example of a conventional overflow detection circuit; Figure 2 shows an example of a conventional overflow detection circuit;
The figure shows an example of a conventional overflow correction circuit, FIG. 3 is a block diagram of a conventional overflow detection and correction circuit that combines the circuits of FIGS. 1 and 2, and FIG. 4 shows the present invention. A block diagram showing one embodiment of the present invention and FIGS. 5a to 5g are diagrams for explaining the operation of the circuit shown in FIG. 4. In Fig. 4, 1, 3, 4... flip-flop, 2
...ROM, 5...2-1 selector, 6"
“” shift register. Ino'zu hair zozu Tsutomu J figure hair 4 figure hair 5 figure

Claims (1)

[Claims] 1 Two serial data X and Y to be added, serial data Zn after addition, serial data Zn-_1 obtained by delaying the serial data Zn by 1 bit, output OFn-_1 of the first flip-flop, and output OFn-_1 of the second flip-flop. The output sn-
_1, a first timing pulse indicating the position of the polarity display bit of the serial data X, Y, and Z, and a second timing pulse indicating the position 2 bits before the polarity display bit are input, a read-only memory that generates an output OFh indicating an overflow and an output sn for correcting the data Zn when the serial data Zn causes an overflow; and the first flip-flop which receives the output OFn of the memory. and the output s of the memory
The second flip-flop inputs n, and the output OFn-_1 of the first flip-flop is used as a selection signal, and the output sn-_1 of the second flip-flop and the serial data Zn are delayed by one data. and is two inputs and selects one of those inputs 2-
An overflow detection and correction circuit comprising: 1 selector.