FOD (first-one-detector) circuit

Details FOD (first-one-detector) circuit FOD (first-one-detector) circuit

1998-09-16

2001-02-27

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06195673

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a circuit for a first-one-detector (hereinafter, “FOD”) which detects the number of leading zeros (0s) from a most significant bit to a first one. (1) in a binary number, which is capable of optimizing its speed and chip area.
2. Description of the Background Art
In general, a binary number may be expressed by a combination of an exponent and a fraction (mantissa). Assuming that an exponent is 2
n
(n=0, 1, 2 . . . ) and its fraction is “A” (for example, 0.00000 . . . 1), the binary value (2
n
*A) may be expressed in many ways. For example, 2
−3
*0.101101 . . . , may be substituted by 2
−4
*0.0101101 . . . , or 2
−5
*0.00101101 . . .
A normalization is regarded as essential in designing a floating point unit for a microprocessor. Such a normalization places “1” at a first bit location after a fraction point in a binary number. In other words, the normalized binary value is expressed as 2
−3
*0.101101 . . . , instead of as 2
−4
*0.0101101 . . . , 2
−5
*0.00101101 . . . , or the like.
Therefore, in order to normalize an exponential expression such as 2
−5
*0.00101101 . . . , the number of leading zeroes counted from a fraction point to a first one should be recognized to compensate for the exponential expression, and then the leading zeros in 2
−5
*0.00101101 . . . , that is, the number of zeros (two) after the fraction point until the first one appears, are initially obtained.
Then, the exponent value “−5” of 2
−5
is added to the obtained value “2” denoting the number of leading zeros, to thereby produce “2
−3
”, so that the fraction point is shifted by two bits to the right for thereby obtaining a normalized fractional value of “0.101101 . . . ”.
A FOD (or leading zero detector) is employed to recognize the number of leading zeroes counted until a first one occurs, and an adder and a shifter are used to execute its adding operation and shifting operation.
When the number of bits are increased during the design of a floating point unit, the FOD circuit has a crucial role on the speed of normalization.
Specifically, when applied to 16 bits, a leading zero detection does not seriously affect the normalization, since the number of zero bits appearing from after the fraction point till the first one are not so many. However, when applied to 64 bits, the speed of normalization depends on how fast the number of leading zeros from after the fraction point to a first one bit are detected.
Due to its recursive characteristic, FOD may be expressed in Boolean terms as follows:
Z
[
0
]=
I
[
4
]
Z
[
1
]=
/I
[
4
]*
I
[
3
]
Z
[
2
]=
/I
[
4
]*/
I
[
3
]*
I
[
2
]
Z
[
3
]=/
I
[
4
]*/
I
[
3
]*/
I
[
2
]*
I
[
1
]
Z
[
4
]=/
I
[
4
]*/
I
[
3
]*/
I
[
2
]*/
I
[
1
]*
I
[
0
]  Eq. (1)
wherein, I[
0
]~I[
4
] denote a 5-bit binary number, and Z[
0
]~Z[
4
] denote that the number of zeros counted from the MSB is 0, 1, 2, 3 and 4, respectively.
Using the recursive characteristic of equation 1, the conventional FOD realizes a cascade circuit structure as shown in
FIG. 1
, and the encoding circuit
10
integrates respective numbers of zeros Z[
0
], . . . , Z[
4
] which appear from the MSB.
Initially, when I[
4
] is “1”, Z[
0
] becomes “1”, and the others, Z[
1
], . . . , Z[
4
], become zero, respectively, so that output values N[
2
], N[
1
], N[
0
] of the encoding circuit
10
, that is, the binary number N[
2
:
0
] become “0”, whereby the leading zero number becomes “0”.
Also, when I[
4
] and I[
3
] are “0” and I[
2
] is “1”, Z[
0
], Z[
1
], Z[
3
], Z[
4
] respectively become “0” and Z[
2
] becomes “1”, so that a binary number of “010” satisfying N[
2
]=0, N[
1
]=1 N[
0
]=0 is outputted, thereby indicating the existence of two (2) leading zeros.
In addition, when I[
4
], I[
3
], I[
2
], I[
1
] are respectively “0” and I[
0
] is “1”, Z[
0
], Z[
1
], Z[
2
], Z[
3
] respectively become “0” and Z[
4
] becomes “1”, so that a binary number of “100” is outputted from the encoding circuit
10
, thereby indicating the existence of four (4) leading zeros.
However, when a “0” value is transited from I[
4
] serving as the MSB to I[
0
] serving as the LSB, the “0” signal flows along AND gates AD
11
~AD
13
including inverters I
11
~I
14
and a plurality of transistors, so that the more the input bit number, the longer becomes the propagation delay time of the “0” signal by the AND gates AD
11
~AD
13
.
Further, the AND gates AD
11
~AD
13
are made up of a plurality of transistors, which disadvantageously increases the entire FOD chip layout area.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide an FOD circuit enabling a fast detection of leading zeros when the input bits are increased during a fraction input, using a fewer number of transmission transistors.
To achieve the above-described object, there is provided an FOD (First-One-Detector) circuit detecting the number of leading zeros counted from a most significant bit to a first one (“1”) bit in a binary number, wherein the FOD circuit includes a plurality of unit blocks connected in cascade depending on the number of bits and respectively provided with a plurality of transmission transistors. The unit blocks according to the present invention respectively include a first transmission transistor for transmitting a fraction input in accordance with a control signal outputted in response to a previous bit, an inverter for inverting the fraction input and outputting a control signal with regard to a corresponding transmission transistor for a subsequent bit, a second transmission transistor for fixing an output signal of the first transmission transistor to a high level in accordance with the control signal outputted in response to the previous bit, and an logic gate for ANDing the fraction input and the control signal outputted in response to the previous bit and outputting the number of leading zeros counted from the most significant bit.
Further, to achieve the above-described object, there is provided an FOD circuit according to the present invention which includes a plurality of sub-FODs for respectively outputting corresponding numbers of leading zeros with regard to predetermined bits of fraction inputs from a previous bit stage when the number of fraction input bits surpasses 16 bits, and an encoding circuit for encoding the number of leading zeros outputted from the plurality of sub-FODs and the determinative signal and outputting the resultant number of 5-bit leading zeros.
The object and advantages of the present invention will become more readily apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific example, while indicating a preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.


REFERENCES:
patent: 4785421 (1988-11-01), Takahashi et al.
patent: 4926369 (1990-05-01), Hokenek et al.
patent: 5091874 (1992-02-01), Watanabe et al.
patent: 5317527 (1994-05-01), Britton et al.
patent: 5345405 (1994-09-01), Walsh et al.
patent: 5493520 (1996-02-01), Schmookler et al.
patent: 5504697 (1996-04-01), Ishida
patent: 5511222 (1996-04-01), Shiba et al.
patent: 5568410 (1996-10-01), B&e

Affiliated with

Also associated with

Rating

FOD (first-one-detector) circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with FOD (first-one-detector) circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FOD (first-one-detector) circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2577281