Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-08-11
2001-01-09
Malzahn, David H. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S205000
Reexamination Certificate
active
06173300
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention generally relates to the field of microprocessors, and more particularly to a circuit and method for leading or trailing zero detection.
2. Description of the Relevant Art
Microprocessors determine the speed and power of personal computers, and a growing number of more powerful machines, by handling most of the data processing in the machine. Microprocessors typically include at least three functional groups: the input/output unit (I/O), the control unit, and the arithmetic logic unit (ALU). The I/O unit interfaces between external circuitry and the ALU and the control unit. I/O units frequently include signal buffers for increasing the current capacity of a signal before the signal is sent to external components. The control unit controls the operation of the microprocessor by fetching instructions from the I/O unit and translating the instructions into a form that can be understood by the ALU. In addition, the control unit keeps track of which step of the program is being executed. The ALU handles the mathematical computations and logical operations that are performed by the microprocessor. The ALU executes the decoded instructions received from the control unit to modify data contained in registers within the microprocessor.
Usually, the register which stores the operand to be modified has as many bit locations as would be required to store the largest possible number on which the microprocessor has been designed to operate. In many operations, however, the magnitude of the operand is substantially smaller than the magnitude of this largest number. In such a case, the register is filled with zeros to the left of the most significant bit of the operand that is a logical one. The added zeros which fill to the left of the most significant bit are known as the leading zeros.
It is known that the speed at which arithmetic operations on the operand are performed can be increased if the number of leading zeros in the operand is known ahead of time. To this end leading zero detection circuits are provided as part of the microprocessor for counting or detecting leading zeros within an operand. It is also well known that speed and circuit size are two critical parameters in the design of any microprocessor. Often, these two parameters are mutually exclusive in that a faster microprocessor or components thereof operate faster when employing large complex circuitry but which have the disadvantage of occupying a large area within the integrated circuit. Prior art circuits for detecting or counting leading zeros within operands are subject to this principle. One prior art leading zero detection circuit operates quickly (i.e., in one clock cycle) but occupies a significant amount of area within the microprocessor due to its circuit complexity. Another prior art leading zero detection circuit occupies a significantly less area within the microprocessor but requires a significant number of cycles in order to complete a count of the leading zeros within an operand. Typically, this second prior art leading zero detection circuit employs a microcode loop which tests each bit of the operand per clock cycle.
It would therefore be desirable to produce a leading zero (or trailing zero) detector circuit that achieves a significant reduction in the number of clock cycles required to produce a leading zero count without significantly increasing the amount of area required to implement the circuit.
SUMMARY OF THE INVENTION
The problems set forth above are solved by a method or circuit for determining the position of a leading logical one or a trailing logical one in a first n bit operand. In one embodiment, the present invention generates an n bit operand from the first n bit operand. One bit of the n bit operand represents a first logical value while the remaining bits of the n bit operand represent a second logical value. Thereafter, a k bit operand is generated from the n bit operand. The k bit operand relates to the bit position of the leading or trailing logical one in the first n bit operand.
In another embodiment, the present invention can be employed in a method or circuit solely for determining the position of a leading logical one in a first n bit operand. In this embodiment, a second n bit operand is generated from the first n bit operand. The n
th
most significant bit of the second n bit operand represents a logical zero. The remaining bits of the second n bit operand are generated in accordance with a bit wise ORing operation of the first n bit operand. More particularly, the m
th
most significant bit of the (n−1) least significant bits of the second n bit operand represents a logical OR of the (m−1) most significant bits of the first n bit operand. The second n bit operand is then logically complemented to generate a third n bit operand. The first n bit operand and third n bit operand are logically ORd to generate a fourth n bit operand. This fourth n bit operand has just one bit which represents a logical one while the remaining bits of the fourth n bit operand represent a logical zero. The fourth n bit operand is used to generate a k bit operand wherein the k bit operand relates to the position of the leading one in the first n bit operand. More specifically, the k bit operand encodes the bit position of the leading one within the first n bit operand. The k bit operand is generated by logically ORing n/2 selected bits of the fourth n bit operand. For example, the most significant bit of the k bit operand is generated by logically ORing the n/2 most significant bits of the fourth n bit operand.
In another embodiment, the present invention may be employed in a method or circuit solely for determining a position of a trailing logical one in a first n bit operand. In this embodiment a second n bit operand is generated as a function of the first n bit operand. The least significant bit of the second n bit operand represents a logical zero while the remaining bits of the second n bit operand are generated using a bit wise ORing function. More particularly, the m
th
most significant bit of the (n−1) most significant bits of the second n bit operand represents a logical OR of the (n−m−1) least significant bits of the first n bit operand. Once the second n bit operand is generated, the second n bit operand is logically complemented to generate a third n bit operand. Thereafter, the first n bit operand and third n bit operand are logically ORd to generate a fourth n bit operand. Only one bit of the fourth n bit operand represents a logical one while the remaining bits of the fourth n bit operand represent logical zero. Finally, a k bit operand is generated as a function of the fourth n bit operand. This k bit operand relates to the position of the trailing one in the first n bit operand. Each bit of the k bit operand is generated by logically ORing n/2 selected bits of the fourth n bit operand. For example, the most significant bit of the k bit operand is generated by logically ORing the n/2 most significant bits of the fourth n bit operand.
One advantage of the present advantage is that it detects the bit position of a leading or trailing one in an n bit operand.
Another advantage of the present invention is that it counts the number of leading or trailing zeros in an n bit operand.
Yet another advantage of the present invention is that it determines the position of a leading or trailing logical one in two clock cycles.
Still another advantage of the present invention is that it determines the position of a leading or trailing logical one using less area within a microprocessor when compared to the prior art.
REFERENCES:
patent: 4247897 (1981-01-01), McDonald et al.
patent: 4849920 (1989-07-01), Simpson et al.
patent: 4924421 (1990-05-01), Seguchi
patent: 4954978 (1990-09-01), Terane et al.
patent: 5111415 (1992-05-01), Shackleford
patent: 5241490 (1993-08-01), Poon
patent: 5345405 (1994-09-01), Walsh et al.
patent: 5493520 (1996-02-01), Schmookler et al.
patent: 5657260 (1997-08-01), Makino
Advanced Micro Devices , Inc.
Conley Rose & Tayon PC
Kivlin B. No{umlaut over ( e)}l
Malzahn David H.
LandOfFree
Method and circuit for determining leading or trailing zero... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and circuit for determining leading or trailing zero..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and circuit for determining leading or trailing zero... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2541723