JPH0252893B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Technical Field of the Invention The present invention has a first to nth digital input and a digital output, and a (j-th)
1) The present invention relates to a logic circuit that uses logical condition signals such as OR and AND condition signals of up to the digital inputs as the j-th digital output.

Prior Art and Problems FIG. 1 is a circuit diagram showing an example of the configuration of this type of logic circuit. The logic circuit shown in the figure has an n-bit input I ₁
When the smallest i such that I _i = “1” among ~I _o is i _nio , the output O _j = “0” (j<i _nio ), O _j = “1”
It is a logic circuit that outputs (j≧i _nio ), and a unit circuit consisting of a NOR gate 1 and a NOT gate 2 is repeatedly used. As described above, this type of logic circuit is generally constructed by repeatedly using the same unit circuit, and is often used as a partial circuit in a digital logic circuit block having various functions.
FIG. 2 is a circuit diagram showing an example of a logic circuit block having various functions. The same reference numerals as in FIG. 1 indicate the same parts, 3 is a NOR gate, and 4 is a NOT gate. The figure shows the configuration of a multiple selection separation circuit in an associative memory, which means that when I _nio is the minimum i such that I _i = “1”, O _j = “1” (j = i _nio ), O _j
="0" (j≠ _inio ). Note that the details of the multiple selection separation circuit are described in, for example, the following document.

“Large-scale associative memory LSI” IEICE Technical Report, SSD80−
56 By the way, the number of gate stages N _c of the critical path of the logic circuit shown in Figure 1 is given by the number of gate stages from I ₁ determination to O _o determination, and N _c = 2 × n (stages).
becomes. From this, when n becomes large,
It can be seen that this operation takes an extremely long time.

FIG. 3 is a circuit diagram showing another example of the configuration of a conventional logic circuit of this kind. Among n-bit inputs I ₁ to _{I o} ,
When the smallest i such that I _i = “0” is i _nio , O _j =
This is a logic circuit that outputs “1” (j<i _nio ) and O _j = “0” (j≧i _nio ). This also uses a unit circuit consisting of a NAND gate 5 and a negative gate 6 repeatedly, and the number of gate stages in the critical path is N _c
is given by N _c =2×n (stages) as in the logic circuit shown in FIG. Therefore, if n becomes large, the operation will take an extremely long time.

As described above, in the conventional logic circuit of this type, when the number of input bits n increases, the number of gate stages of the critical path increases, and the disadvantage is that the operation thereof requires an extremely long time.

OBJECTS OF THE INVENTION The present invention has been made to improve upon these conventional drawbacks, and its purpose is to provide a logic circuit that has a small number of gate stages in a critical path and can operate at high speed.

Structure of the Invention In the logic circuit of the present invention, the gate output corresponds one-to-one to the first to n-th digital outputs of the n-bit outputs, and one of the gate inputs corresponds to the first digital output of the n-bit inputs. A total of n NAND gates and NOR gates corresponding one-to-one to the n-th digital input are alternately connected in series so that the gate output of the previous stage becomes the other gate input of the latter stage, and the gate of the previous stage When the digital input is inverted and used as the input of one of the gates, the output of the gate in the later stage is inverted and used as the digital output.When the output of the gate in the previous stage is inverted and used as the digital output, the output of the gate in the later stage is inverted and used as the input of the gate in the later stage. n n NOT gates are connected to the NAND gate and NOR gate. Examples will be described in detail below.

Embodiment of the Invention FIG. 4 is a circuit diagram showing an embodiment of the present invention, where I ₁ to I ₄ are digital inputs, and O ₁ and O ₄ are inputs I _{1 to} I 4 .
Digital output of bit corresponding to I ₄ , 19 is logic “0” input (control input) to the first stage, 20 to 23
is a negative gate, 24 and 25 are two-input NOR gates, and 26 and 27 are two-input NAND gates.

This logic circuit is a logic circuit that realizes the same logic as in FIG. 1, and the digital outputs O ₁ to O ₄ are respectively given by the following equations.

O ₁ = I ₁ O ₂ = ₁・₂ = I ₁ + I ₂ O ₃ = ( ₁ + ₂ ) + ₃ = I ₁ + I ₂ + I ₃ O ₄ = ( ₁ + ₂ + ₃ )・₄ = I ₁ + I ₂ +I ₃ +I ₄ (1) That is, when i _nio is the minimum i with I _i = 1 among the 4-bit inputs, O _j = “0” (j < i _nio ), O _j
= “1” (j≧i _nio ), that is, the (j
−1) is the logical sum of the digital inputs up to the jth
This is a logic circuit that sequentially ripples (propagates) to the th.

Number of gate stages in critical path of this logic circuit
N _c is given by the number of gate stages from I ₁ determination to O ₄ determination, and N _c =4 (stages). Although the figure shows the case of a 4-bit input, it is clear that the present invention can be applied to a circuit with an arbitrary number of input bits, and that in general, when the input is n bits, N _c is given by N _c =N. According to the equation, N _c has been reduced to 1/2 of that of the conventional method, and it can be seen that even if n becomes large, high-speed operation is possible.

FIG. 5 is a circuit diagram when the embodiment shown in FIG. 4 is applied to a multiple selection separation circuit of an associative memory as in FIG. 2, and the same reference numerals as in FIG. 4 indicate the same parts;
P ₁ to _{P 4} are the outputs of the multiple selection separation circuit, 32, 33
is a negative gate, and 34 to 37 are two-input NOR gates. The outputs P ₁ to _{P 4} are each expressed by the following equations.

P ₁ = I ₁ P ₂ = ₂ + I ₁ = ₁・I ₂ P ₃ = ₃ + (I ₁ + I ₂ ) = ( ₁ + ₂ )・I ₃ = ₁・₂・I ₃ P ₄ = ₄ + (I ₁ + I ₂ + I ₃ ) = ( ₁ + ₂ + ₃ ) · I ₄ = ₁ · ₂ · ₃ · I ₄ (2) As described above, by applying the present invention to the multiple selection separation circuit, the critical path gate The number of stages can be reduced to 1/2 of the conventional one.

FIG. 6 is a circuit diagram showing another embodiment of the present invention, where Q ₁ to Q ₄ are digital inputs, and R ₁ to R ₄ are inputs Q ₁
~ Digital output of bits corresponding to Q ₄ , 46
is the logic “1” input (control input) to the first stage, 47~
50 is a NOT gate, 51 and 52 are two-input NAND gates, and 53 and 54 are two-input NOR gates.

In this embodiment, the NOR gate and NAND gate in the fourth illustrated embodiment are replaced and the control input is changed to "1", and the outputs R ₁ to _{R 4} are given by the following equations.

R ₁ = Q ₁ R ₂ = ₁ + ₂ = Q ₁・Q ₂ R ₃ = ( ₁・₂ )・₃ = Q ₁・Q ₂・Q ₃ R ₄ = ( ₁・₂・₃ ) + ₄ = Q ₁・Q ₂ , Q ₃・Q ₄ (3) That is, as in the logic circuit shown in FIG. 3, when the smallest i with Q _i = “0” among the 4-bit inputs is i _nio , R _i = “1” (j<i _nio ), R _j = “0” (j≧
i _nio ), that is, it sequentially ripples (propagates) the AND of digital inputs up to the (j-1)th digital input to the jth digital input. The number of gate stages N _c in the critical path of this logic circuit is Q ₁
It is given by the number of gate stages from confirmation to R ₄ confirmation,
N _c =4 (stages). Although the figure shows the case of 4-bit input, it is clear that this circuit can be applied to any number of input bits, and that when n-bit input is given by N _c =N, according to the present invention,
It can be seen that N _c is reduced to 1/2 of the conventional value, and high-speed operation is possible even when n becomes large.

Note that one method of configuring this type of logic circuit is to divide the n-bit input into several blocks, provide a look-ahead circuit for the propagation signals between the blocks, and operate each block in parallel to increase speed. There are known methods for achieving this. The present invention is also effective for such a method, and can be applied to the configuration of logic circuits within a block and the configuration of look-ahead circuits between blocks.

7 and 8 are circuit diagrams showing still another embodiment of the present invention, and in each figure, FIGS.
The same reference numerals as in the figure indicate the same parts.

In the seventh illustrated embodiment, the positions of the inverters 20 to 23 of the fourth illustrated embodiment are moved such that those on the output side are moved to the input side, and those on the input side are moved to the output side. When the minimum i such that _i = 0 is i _nio , O _j = “1” (j < i _nio ), O _j = “0” (j
≧i _nio ).

Further, in the eighth illustrated embodiment, the positions of the inverters 47 to 50 in the sixth illustrated embodiment are moved in the same way as in the seventh illustrated embodiment, and among the 4 bit inputs,
When the minimum i that is Q _i = “1” is i _nio , R _i =
“0” (j<i _nio ) and R _j = “1” (j≧i _nio ) are output.

Effects of the Invention As explained above, according to the present invention, it is only necessary to connect a total of n gates in series for an n-bit input, so the number of gate stages in the critical path is reduced to 1/2 compared to the conventional configuration. 2, resulting in a logic circuit that can operate at high speed even when the number of input bits increases. Since the logic circuit of the present invention can be used as a partial circuit of a logic circuit block having various functions, the operation of many other logic circuit blocks having various functions using the logic circuit of the present invention as a component circuit is also possible. It has the advantage of being faster. In particular, the multiple selection separation circuit in an associative memory device defines the operating speed of the entire associative memory device.
By applying the logic circuit of the present invention to this,
It is possible to achieve high-speed associative memory devices.

[Brief explanation of the drawing]

Fig. 1 is a block diagram of a conventional logic circuit, Fig. 2 is a block diagram of a multiple selection separation circuit in an associative memory to which it is applied, Fig. 3 is a diagram showing another configuration of a conventional logic circuit, and Fig. 4 , FIGS. 6 to 8 are circuit diagrams of different embodiments of the present invention, and FIG. 5 is a diagram showing a configuration example of a multiple selection separation circuit in an associative memory to which the embodiment shown in FIG. 4 is applied. _I1 to _I4 , _Q1 to _Q4 are digital inputs, _O1 to _O4 ,
R ₁ to _{R 4} are digital outputs, 20 to 23, 32,
33, 47-50 are negative gates, 24, 25, 3
4-37, 53, 54 are Noah Gate, 26, 2
7, 51, 52 are NAND gates.

Claims (1)

[Claims] 1. It has the first to nth digital inputs and the first to nth digital outputs, and up to the (j-1)th (2≦j≦n) In a logic circuit in which the logic condition signal of the digital input is the j-th digital output, the gate output corresponds one-to-one to the first to n-th digital outputs, and one of the gate inputs is A total of n NAND gates and NOR gates corresponding one-to-one to the first to nth digital inputs are alternately connected in series so that the gate output of the previous stage becomes the other gate input of the latter stage, and , when the digital input of the previous gate is inverted and used as the input of the one gate, the output of the latter gate is inverted and used as the digital output, and when the output of the previous gate is inverted and used as the digital output, the output of the latter gate is inverted and used as the digital output. n negative gates are connected to the NAND gate and the NOR gate, and the other input of the first gate is a control input to which a control digital signal is applied. A logic circuit characterized by the following. 2. In the logic circuit according to claim 1, the logic condition signal is an OR condition signal, and the first gate is a NOR gate, and the gate output is inverted to become the digital output. A logic circuit characterized by connected gates. 3. In the logic circuit according to claim 1, the logic condition signal is an AND condition signal,
A logic circuit characterized in that the first gate is formed of a NAND gate, and is connected to a NOT gate that inverts the gate output to provide the digital output. 4. In the logic circuit according to claim 1, the logic condition signal is a NOR condition signal, and the first gate is formed of a NOR gate, and the digital input is inverted and one of the NOR gates is inverted. A logic circuit characterized in that a negation gate is connected as an input. 5. In the logic circuit according to claim 1, the logic condition signal is a NAND condition signal, the first gate is constituted by a NAND gate, and the digital input is inverted to input one gate of the NAND gate. A logic circuit characterized in that a negation gate is connected.