Logic circuits and carry-lookahead circuits

Details Logic circuits and carry-lookahead circuits Logic circuits and carry-lookahead circuits

2000-03-08

2001-12-11

Tokar, Michael (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Having details of setting or programming of interconnections...

C326S039000, C326S037000

Reexamination Certificate

active

06329838

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
The subject application is related to subject matter disclosed in the Japanese Patent Application No.Hei11-62346 filed in Mar. 14, 1999 in Japan, to which the subject application claims priority under the Paris Convention and which is incorporated by reference herein.
The subject application is also related to subject matter disclosed in the Japanese Patent Application No.Hei11-186956 filed in Jun. 30, 1999 in Japan, to which the subject application claims priority under the Paris Convention and which is incorporated by reference herein.
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention is related to a logic circuit for finding a “0” bit or a “1” bit by searching a binary bit string. Furthermore, the present invention is related to a carry-lookahead (CLA) circuit for use in arithmetic units handling a number of bits.
PRIOR ART
There are utilized logic circuits called a “0” bit searching circuit and a “1” bit searching circuit as logic circuits for constituting the hardware of a computer system. The logic circuits of this kind is used to find a “0” bit or a “1” bit by searching a binary bit string from the most significant bit to the least significant bit. The logic circuits are used to constitute a comparator for determining the largest number among a plurality of numbers, or a priority encoder used in a signal reception circuit having a plurality of input lines and provided, when receiving input signals at two or more input lines, for generating an output signal indicative of the input line receiving an input signal and having the highest priority among from the input lines receiving input signals.
On the other hand, a “1” bit searching circuit in accordance with the prior art is composed of a number of the logic gate connected in a matrix form or in a tree arrangement so that the circuit design tends to be complicated. Furthermore, there are a number of gates arranged from the input to the output so that it takes much time to pass input data therethrough.
On the other hand, carry lookahead circuits have been generally utilized in adder circuits for performing the addition operation of an N-bit input signal a<N−1>, a<N−2>, . . . , a<
0
>), referred to simply as a<N−1:
0
>, and an N-bit input signal b<N−1>, b<N−2>, . . . , b<
0
>, referred to simply as b<N−1:
0
>. An example of such a prior art CLA circuit is described in Japanese Patent Published Application No.Hei 3-150630. The prior art carry lookahead circuit as described is a so-called carry select adder which performs the addition operation both in the case that the carry-in signal is “0” and in the case that the carry-in signal is “1”. In accordance with the carry out from the lower bit operation, either result of the addition operation is selected and output as a correct result.
There is described a carry lookahead circuit as illustrated in
FIG. 2
in Japanese Patent Published Application No.Hei 3-150630. Propagate signals P<
3
:
0
> and generate signals G<
3
:
0
> are calculated during the addition operation of the input signals a<
3
:
0
> and the input signals b<
3
:
0
> by obtaining the EX-OR and the AND of each corresponding bits of the input signals a<
3
:
0
> and the input signals b<
3
:
0
>. The propagate signals P<
3
:
0
> and the generate signals G<
3
:
0
> are input to the carry lookahead circuit together with the carry-in signal Cin from the lower stage in order to generate carry signals C<
3
:
0
>.
FIG. 3
is a block diagram showing an exemplary carry select adder which performs the addition operation both in the case that the carry-in signal is “0” and in the case that the carry-in signal is “1” and, in accordance with the carry out from the lower bit operation, either result of the addition operation is selected and output as a correct result. The carry lookahead circuit CLA
1
serves to performs the addition operation in the case that the carry-in signal is “1” while the carry lookahead circuit CLA
2
serves to performs the addition operation in the case that the carry-in signal is “0”. Either of the outputs of the carry lookahead circuits CLA
1
and CLA
2
are selected by means of a
2
-
1
multiplexer MUX.
A bit group
0
is arranged in the form of the 4-bit carry lookahead circuit as illustrated in
FIG. 2
in order to handle <
0
:
3
> bits of data having a 32 bit length to be handled while seven bit groups
1
to
7
are arranged in the form of the 4-bit carry lookahead circuits each designed as illustrated in
FIG. 3
in order to handle <
4
:
7
> bits, <
8
:
11
> bits, <
12
:
15
> bits, . . . <
28
:
31
> bits of the data. A carry lookahead circuit capable of handling 32 bits is then formed as illustrated in FIG.
1
. C<
0
> to C<
3
>, C<
4
> to C<
7
>, C<
8
>to C<
11
>, . . . , C<
28
> to C<
31
> are sequentially generated in this order in the group
0
, the group
1
, . . . the group
7
.
However, there is a following problem in the prior art CLA as described above.
FIG. 4
shows the delay time required for completing the calculation, i.e., the delay time required for generating the carry signals C<
0
> to C<
31
>. Each of the carry lookahead circuits CLA
1
and CLA
2
of the respective carry lookahead circuits of the group
0
to the group
7
takes the same time T1 required for calculation. However, the multiplexer MUX of the carry lookahead circuit of the group
1
can initiate the operation required for selecting carry signals only after receiving the carry signal C<
3
> as given from the group
0
. The delay time T2 of the multiplexer MUX is accumulated from the group
1
to the group
7
resulting in the total delay time T1+T2*7. Because of this, in accordance with the prior art technique, there is a problem that a longer delay time is required for completing the calculation of carry signals for data having longer bit sequence.
SUMMARY OF THE INVENTION
The present invention has been made in order to solve the shortcomings as described above. It is an object of the present invention to provide logic circuits capable of performing high speed operations with simplified designs.
It is another object of the present invention to provide a carry lookahead circuit wherein it is possible to reduce the delay time required for completing the calculation by obtaining group propagate signals, group generate signals and group kill signals for each m bits by the use of the respective propagate signals, generate signals and kill signals respectively for each of m bits.
In brief, the above and other objects and advantages of the present invention are accomplished by a logic circuit for searching a binary bit string from the most significant bit to the least significant bit for a first “0” or “1” bit, said logic circuit comprising:
a NOT gate circuit receiving the most significant bit of said binary bit string and composed of a dynamic logic circuit;
NOR gate circuits provided in a one-to-one correspondence to the respective bits of said binary bit string, each NOR gate circuit receiving the bit of said binary bit string corresponding to the bit position of said each NOR gate circuit and, if any, the bit(s) of said binary bit string which is more significant than the bit corresponding to the bit position of said each NOR gate circuit except for the most significant bit; and
two-input NOR gate circuits each of which receives two logic signals as output from adjacent ones of said NOT and NOR gate circuits.
In accordance with a preferred embodiment of the present invention, said NOT and NOR gate circuits are composed of NMOS FETs connected in parallel between the ground level and the output lines of said NOT and NOR gate circuits.
Also, in accordance with a preferred embodiment of the present invention, a plurality of inverters are provided in advance of said 2-input NOR gate circuits.
In accordance with another a

Affiliated with

Also associated with

Rating

Logic circuits and carry-lookahead circuits does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Logic circuits and carry-lookahead circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic circuits and carry-lookahead circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2573506