JPH04170637A - Divider circuit - Google Patents

Abstract

PURPOSE:To shorten an arithmetic time required for the succeeding dividend by expressing a divisor of n bits as n<n+1>, adjusting the number of digits of the divisor to that of the divident and finding out the succeeding dividend by the constitution of two stages. CONSTITUTION:A divisor Y of n bits is converted into 2<n+1> by a 2<n+1> forming circuit 5 to form a divisor Y', and when a dividend X is more than the divisor Y', the divisor Y' is shifted to the left by an m-(n+1) bit shifting circuit 7 to adjust the number of digits of the divisor Y' to that of the dividend X consisting of m bits. Respective digits are passed through an exclusive OR circuit 11 to find out a difference V between a dividend X1 and the divisor Y'. Then a difference W between the 2<n+1> and a divisor Y2 is found out by allowing digits less than n bits to pass an exclusive OR circuit 8 and an '1' adder 9. The difference W is shifted by an m-(n+1) bit shifting circuit 10 and added to the difference V by a dividend X' forming adder 12 to find out the succeeding dividend X'. Thus, the succeeding dividend can be found out by the two-stage constitution and the arithmetic time can be shortened.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a division circuit, and particularly to a division circuit in binary numbers.

[Conventional technology]

FIG. 2 is a block diagram showing an example of a conventional division circuit.

The division method in this example shown in FIG. 2 is the same as the decimal subtraction method. That is, the m-bit dividend X1 is shifted bit by bit from the most significant bit to the left by the shift circuit 16, and the obtained dividend X' and the n-bit divisor Y passed through the inverter circuit 18 are added together in the adder circuit 19. . X/.

The Y comparator 17 compares the dividend X' and the divisor Y, selects the added value when the dividend X' becomes a value greater than or equal to the divisor 7, and sets "1" to the quotient. After the added value at this time, the remainder of the dividend X that has not yet been shifted is added. When the value of the divisor is less than 7, select the dividend X' itself and enter "
0" and shift the next bit.

Then, in the same manner, the calculation is repeated by shifting one bit at a time until subtraction is no longer possible. The final value of quotient 3 is X', Y every time the dividend X is shifted.
It is obtained by shifting the value determined by the comparator 17 as a quotient in the shift circuit 21. The value of remainder 4 is the value at the time when subtraction is no longer possible.

[Problem to be solved by the invention]

In this conventional division circuit, in order to subtract the dividend X shifted by 1 bit to the left, the result obtained by inverting and adding the divisor Y and the simply shifted dividend X is subtracted from the shifted dividend X.
Since the selection is made based on whether the number is greater than or less than the divisor Y, the circuit block has a three-stage configuration of an inverter, an adder, and a selector, and it takes a considerable amount of calculation time to find the next dividend.

Taking an example in which the dividend is 4 bits and the divisor is 3 bits in a CMO8G/A, the inverter takes about 0.4n S + the addition takes about 5 n s v The selector takes about 1.2 ns, and it takes the entire time to find the next dividend. There was a problem that it took about 8.8 ns.

Currently, one cycle of the clock used for signal processing is approximately 20
Since it is a high-speed device of ns, a division circuit with a short calculation time is required, but conventional circuits cannot satisfy this requirement.

SUMMARY OF THE INVENTION An object of the present invention is to provide a division circuit that takes a short calculation time to obtain the next dividend.

[Means to solve the problem]

The division circuit of the present invention increases the divisor by one digit and sets the most significant digit to “
1'', a first circuit that calculates the difference between the dividend and the divisor by setting all other digits to "O", and an exclusive OR after adding the divisor increased by one digit to the dividend and the number of digits. a second circuit that calculates the difference using a circuit; a third circuit that calculates the difference between the divisor increased by one digit and the divisor of light using an exclusive NOR circuit and a 1 addition circuit that adds 1; and a fourth circuit that calculates the next dividend by adding the differences between the numbers.

[Effect]

FIG. 1 is a block diagram of a division circuit showing one embodiment of the present invention.

When dividing the m-bit dividend X1 by the n-bit divisor Y2,
First, the n-bit divisor Y2 is 2'' by the 2 n+1 creation circuit 5.
+1 to create a divisor Y', and if the dividend X1 is greater than or equal to the divisor Y', it is shifted to the left by the m-(n+1) bit shift circuit 7 to match the number of digits with the m-bit dividend X1.

Then, by passing each digit through an exclusive OR circuit (EX-OR) 11, the difference V between the dividend X1 and the divisor Y' is determined.

Next, find the difference W between 21''+1 and the divisor Y2. This is found by passing the digits of n bits or less through an exclusive NOR circuit (EX-NOR) 8 and a 1 adder circuit 9, respectively. Then, This difference W is shifted by the m-(n+1) bit shift circuit 10, and the next dividend X' is obtained by adding it to the difference V in the dividend X' creation adding circuit 12.The quotient of the division is m-(n+1). The bit shift to the left is determined by the 2''''-110 generation circuit θ.

Next, it is checked whether the current dividend X' is greater than or equal to 2n+1.

If the above is the case, the same process as described above is repeated, and the newly found quotient is added to the previous quotient by the addition circuit 13. If it is less than Y, a comparison is made with the divisor Y. If the divisor Y or more, X'
The final remainder 4 is determined by subtraction in the -Y subtraction circuit 15. When it is less than, the current dividend X' becomes the remainder itself. When the quotient is subtracted, the 1 addition circuit 14 adds "1" to the accumulated quotient to obtain the final quotient 3. When it is not subtracted, "1" is not added, and this state becomes the final quotient 3.

〔Example〕

Next, the specific operation of one embodiment of the present invention will be explained.

The calculation is shown when the dividend is r21J and the divisor is "5".

Here, if we express each number in binary, we get “2
1” is 5 bits of “1otoi”.

"5" is 3 bits of "101".

First, the 3-bit divisor "101" is replaced by the 2fi+1 generating circuit 5 into the form 2341, that is, "1000".

Then, it is checked whether the dividend number "10101" is greater than or equal to "1000", and if it is, it is changed to "1000" by the m-(n+1) bit shift circuit 7 in order to match the number of digits of the dividend number "10101".
is shifted to the left by 5-(3+1) bits, that is, 1 bit, to make it "10000", and the difference V with the dividend "10101" is found by EX-ORII to obtain "101". Furthermore, the difference W between the original divisors "101" and "1000" is passed through EX-NOR8 and the 1 addition circuit 9 in the lower three bits to obtain "11", and the m-(n+1) bit shift circuit 10 is used to obtain "11". Bit shift to “110”
is found.

Here, the difference between the two is added by the dividend X' creation/addition circuit 12 to obtain the next dividend "1011". For the quotient, "2" is found by the 2m-1n+11 creation circuit 6. At this point, the relationship 21=5X2+11 holds true.

Next, in order to repeat the same process for the next dividend "1011", it is checked whether it is greater than or equal to "1000" and "11" is found. Further, the difference W is not shifted and is directly added to the difference V to obtain the next dividend "110". In the quotient, 2 m-
(The n+11 generation circuit 6 obtains "1", and the adder circuit 13 adds it to the previously obtained "2" to obtain "3".

At this point 21=5X6 The relationship holds true.

Next, it is checked whether the current dividend number "110" is "1000" or more. '110' is smaller than '1000', so it is compared with the original divisor '101', and if it is greater than x' -
The y subtraction circuit 15 subtracts the divisor from the dividend. Here, since the above is the case, subtraction is performed, and the answer becomes the remainder, which becomes "1".

Since the quotient has been successfully subtracted, the 1 addition circuit 14 adds "1" to the quotient, resulting in "4". Ultimately, the relationship 21=5X4+1 holds true.

〔Effect of the invention〕

As explained above, in the present invention, the n-bit divisor is set to 2n+
Make the number 1 and match the number of digits with the dividend, EX
This has the effect that the next dividend can be determined using a two-stage configuration in which the difference V system in -OR and the difference W system in EX-NOR are respectively added. Taking an example of CMO8G/A with a dividend of 4 bits and a divisor of 3 bits, EX-O
Approximately 1.2 ns for R1EX-NOR + approximately 5 ns for addition, resulting in a total of approximately 6.2 ns, compared to conventional inverters, addition,
The next dividend can be determined approximately 0.4 ns faster than the calculation using the three-stage selector configuration.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a division circuit showing an embodiment of the present invention, and FIG. 2 is a block diagram showing an example of a conventional division circuit. 1... m-bit dividend X, 2... n-bit divisor Y1
3...quotient, 4...remainder, 5...2 m+1 creation circuit, 6...2m-3n+11 creation circuit, 7...m-
(n+1) bit shift circuit, 8... exclusive NOR circuit (EX-NOR), 9-1 addition circuit, 10...
m-(n+1) bit shift circuit, 11... Exclusive OR circuit (EX-OR), 12... Dividend X' creation addition circuit, 13... Addition circuit, 14... 1 addition circuit,
15...X'-Y subtraction circuit, 16...shift circuit,
17...X I. Y comparator, 1 inverter circuit, 19 river adder circuit,
20...Select circuit, 21...Shift circuit.

Claims (1)

[Claims] A first circuit that calculates the difference between the dividend and the divisor by increasing the divisor by one digit and setting the most significant digit to "1" and all other digits to "0"; A second circuit that calculates the difference using an exclusive OR circuit after matching the number of digits, and an exclusive NOR circuit that calculates the difference between the divisor increased by one digit and the original divisor, and a 1 addition that adds 1. A division circuit comprising: a third circuit that calculates the next dividend; and a fourth circuit that adds the respective differences to calculate the next dividend.