Asynchronous Leading Zero Counter Employing Iterative Cellular Array

The present invention relates generally to a leading zero detector. More particularly, the present invention relates to an asynchronous leading zero counter employing an iterative cellular array.

In computer systems, arithmetic operations are usually carried out in a memory, such as a register of an ALU. The memory in which the operand is stored usually has as many bit locations as would be required to store the largest possible number that the computer has been designed to operate upon. In many operations, however, the magnitude of the operand is substantially smaller than the magnitude of this largest number. In such case, the memory, or register, is filled with zeros to the left of the most significant bit of the operand that is a binary "1". These are known as 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. Leading zero detectors/counters for performing this function are well known in the art. Some leading zero detectors/counters employ synchronous circuitry for "normalizing" the operand. U.S. Pat. Nos. 3,234,368, 3,831,012, and 4,586,154 are exemplary. Generally, these systems employ some kind of a shifting or synchronous counting function to determine the location of the most significant "1" bit in the operand. Synchronous systems require clock driven shifters and/or counters and therefore detract from the computer's overall processing speed.

Other leading zero detectors/counters employ asynchronous circuitry for determining the number of leading zeros in the operand. U.S. Pat. Nos. 3,678,259, 4,106,105, and 4,247,891 are exemplary. Asynchronous circuitry for performing the leading zero count function is preferred because it does not detract from the computer's overall processing speed. However, known asynchronous leading zero detectors/counters are cumbersome and are not always easily implemented in a computer design. Moreover, known asynchronous leading zero detectors/counters are not easily expandable for use with ever widening bus architectures. A significant drawback of known leading zero detectors/counters, both synchronous and asychronous, is that their design results in substantial overlap of signal lines interconnecting circuitry components. Thus, in the case of circuit implementations employing some type of metallization to effect the interconnections, such as would be the case in printed circuit board and integrated circuit (e.g., custom LSI) implementations, an expensive and/or complex construction having several insulated metallization layers is required.

It is therefore desirable to provide an asynchronous leading zero counter that is easily expandable to any bus width and wherein there is no crossover of any of the signal lines interconnecting any of the circuitry, but at the same time is simple in construction. The present invention achieves these goals.

A leading zero detector cell provided in accordance with the present invention is cascadable with a plurality of other cells of like kind to define an array that provides a digital output word having a magnitude indicative of the leading zero count on the inputs to the plurality of cells. Each cell comprises: a first data input (In0) to an asynchronous logic circuit for receiving a signal of the status of a bit; a second data input (In1) to the asynchronous logic circuit for receiving another signal indicative of the status of an immediately preceding, less significant bit; an enable input (G) to the asynchronous logic circuit for enabling/disabling the cell; a carry input (Yin) to the asynchronous logic circuit; a data output (Y) from the asynchronous logic circuit for providing an indication of leading zero count on the first and second data inputs (In0, In1); and, an enable output (In=0) from the asynchronous logic circuit for providing a first indication that both (i) the cell is enabled and (ii) the signals received on the first and second data inputs (In0, In1) both indicate binary 0, but otherwise providing a second opposite indication. The data output (Y) is responsive only to the status of the carry input (Yin) when the cell is disabled but is responsive to the status of the first and second data inputs (In0, In1) when the cell is disabled.

The array is defined by a plurality of cells defining at least one row, a first cell in the row being associated with two least significant bits of a bus (e.g., a bus carrying an input word to a register), a last cell in the row being associated with two most significant bits of the bus, and the remaining cells (if there are more than two in the row) being associated, in succession, with bit pairs of the bus therebetween. The data output and the enable output of all except the first cell are coupled to the carry input and enable input, respectively, of an immediately neighboring cell that is associated with two lower significant bits of the bus. The data output of the first cell is indicative of the least significant bit of the leading zero count. Depending upon the bus width (i.e., number of bits), additional rows of cells may be provided and interconnected to preceding rows as hereindescribed. The data output of the first cell of each succeeding row will be indicative of a more significant bit of the leading zero count.

According to one embodiment of the invention, the array is for use with a bus having 2.sup.N bits and, the array is two dimensional and there are 2.sup.N -1 cells defining N successive rows of cells. Each row succeeding the first row contains only half the number of cells of the immediately preceding row, and the data output of the first cell of each row succeeding the first row is indicative of a higher significant bit of the leading zero count. The data outputs of each of the first cells of each row collectively define a digital word having a magnitude indicative of the leading zero count on the bus.

All bits on the bus are simultaneously input into the array in parallel fashion and its operation is completely asynchronous. The topology of the array results in no crossover of any signal lines interconnecting the cells.

FIG. 1 illustrates the functional inputs and outputs of a leading row detector cell according to the present invention.

FIG. 2 is a truth table for the cell of FIG. 1.

FIG. 3 illustrates one design for an asynchronous logic circuit for implementing the cell of FIG. 1.

FIGS. 4A and 4B illustrate an exemplary array for a leading zero counter according to the present invention.

FIGS. 5A and 5B illustrate another exemplary array for another leading zero counter according to the present invention.

Referring now to the drawings, wherein like numerals represent like elements, there is illustrated in FIG. 1 a leading zero detector cell 10 according to the present invention. The cell 10 comprises a pair of digital data inputs 12, 14 (labeled In0, In1, respectively), an enable/disable input 18 (labeled G) and a carry input 16 (labeled Yin). The cell also comprises a data output 22 (labeled Y) which is the primary functional output of the cell 10, and an enable output 20 (labeled In=0). The inputs/outputs preceeded with a "+" are active high, while those preceeded by a "-" are active low. As will become apparent hereinafter, the data input 12 is for coupling to a more significant bit of a bus (e.g., carrying an input word to a register) whose leading zero count is to be determined, while the data input 14 is for coupling to the immediately adjacent, next lower significant bit of the bus.

FIG. 2 illustrates the truth table for the cell 10 of FIG. 1. The "x's" in the truth table indicate "don't cares." The truth table of FIG. 2 illustrates that the data output 22 the data inputs 12, 14, respectively. The truth table of FIG. 2 also illustrates that, when the cell 10 is one of a plurality of like cells arranged in an array (described hereinafter), the data outputs 22 of all subsequent cells 10 (i.e., those associated with less significant bits) will be forced active upon detection of a binary "01" pattern on the data inputs 12, 14, respectively, and all subsequent cells 10 (again, those associated with less significant bits) will be disabled. The truth table further illustrates that, when a cell is disabled (i.e., when the input 18 is inactive or binary "1"), only the carry input 16 will affect the data output 22. The truth table still further illustrates that if a binary "11" or "10" is detected at the data inputs 12, 14, respectively, all subsequent cells 10 in the array will be disabled and the data output 22 for all subsequent cells will be forced inactive (binary "0"). The truth table finally illustrates that the enable output 20 is active (i.e., binary "0") when both a binary "00" appears on the data inputs 12, 14 and the enable input 18 is active (i.e., binary "0"). As will become apparent, when an array comprising a plurality of rows of cells 10 is constructed as described herein, the enable output 20 of a cell 10 in a preceding row serves as a data input to a cell in a succeeding row.

Preferably, the cell 10 is comprised of asynchronous logic circuitry. One asynchronous logic circuit for implementing the cell 10 is illustrated in FIG. 3. The asynchronous logic circuit of FIG. 3 includes two AND gates 24, 28 and an OR gate 26 connected as shown. Thus, the AND gate 24 has inverted inputs for receiving the data input 12 and enable input 18, and a non-inverted input for receiving the data input 14. The AND gate 28 has three inverted inputs for receiving the data inputs 12, 14 and the enable input 18. The AND gate 28 also has an inverted output for providing the enable output 20. The OR gate 26 has one input receiving the carry input 16 and another input receiving the output of AND gate 24. The output of OR gate 26 provides the data output 22.

Summarizing the function of the cell 10, (and as will be appreciated from the truth table of FIG. 2), the data output 22 is responsive only to the status of the carry input 16 when the cell is disabled, but the data output 22 is forced active when both the cell is enabled and a binary "01" is detected at the data inputs 12, 14, respectively. The data output 22 is rendered inactive when both the cell is enabled and a binary "10" or "11" is detected at the data inputs 12, 14, respectively. The enable output 20 provides a first indication (binary "0") that both (i) the cell is enabled and (ii) a binary "00" has been detected at the data inputs 12, 14. The enable output 20 provides a second, opposite indication (binary "1") at all other times.

It will thus be seen that, when the cell 10 is enabled, the data output 22 provides a bit that is indicative of the number of leading zeros at the data inputs 12, 14. A single cell, therefore, will process a two bit binary input word. The data output 22 will count zero or one leading "0's in the input word (e.g., the operand). If both bits of the word that is input to the cell 10 are binary "0's", then the data output 22 will be a binary "0" and the enable output 20 will be active (i.e., binary "0"), indicating that the input word is all "0's". A binary "01" at the data inputs 12, 14 will cause the data output 22 to be a binary "1", thus indicating one leading "0" A binary "11" or "10" at the data inputs 12, 14 will cause the data output 22 to be a binary "0", thus indicating no leading "0's"

As mentioned, each of the cells 10 may be combined with a plurality of like cells to form an iterative array for counting the number of leading zeros on an N bit bus. The construction and operation of such an array will now be described.

FIGS. 4A and 4B each illustrate an exemplary one-dimensional array, comprising three cells of the type of FIG. 1, designated 100, 102 and 104. The input word from the bus is labelled 30 for the example of FIG. 4A and 32 for the example of FIG. 4B. The cell 104 receives the two most significant bits of the bus or word 30, 32. The cell 100 receives the two least significant bits of the bus or word 30, 32, and the cell 102 receives the intermediate bits. The examples of FIGS. 4A and 4B are for a simple six-bit bus with the inputs as shown, and "x's" representing don't cares. As shown, the cells 100, 102, 104 are interconnected so that the data output 22 of cell 104 is supplied as the carry input 16 to the cell 102, and the data output 22 of cell 102 is provided as the carry input 16 to the cell 100. Similarly, the enable output 20 of cell 104 is provided as the enable input 18 to the cell 102, and the enable output 20 of cell 102 is provided as the enable input 18 to the cell 100. Data output 22 of the cell 100 (i.e., the first cell in the row) provides the indication of leading zero count. Thus, in the example of FIG. 4A, there are four leading zeros in the input word 30, and the data output 22 is a binary "0" In the example of FIG. 4B, there are three leading zeros in the input word 32, and the data output 22 is a binary "1" Thus, the data output 22 of the array of FIGS. 4A and 4B indicates whether there is an even or odd number of leading "0's" in the input word. Accordingly, the data output 22 of the arrays of FIGS. 4A and 4B can be considered as the least significant bit of the total count of leading "0's".

FIGS. 5A and 5B each illustrate a two-dimensional array for receiving an input word from a 16 bit bus. The input word from the bus is labeled 34 for the example of FIG. 5A and 36 for the example of FIG. 5B. As shown, the array of FIGS. 5A and 5B comprises four rows: the first row comprises cells 100-114 (cell 100 defining the first cell); the second row comprises cells 200-206 (cell 200 defining the first cell); the third row comprises the cells 300-302 (cell 300 defining the first cell); and, the fourth row comprises cell 400 (cell 400 being the only cell and thus defining the first and last cell of the fourth row). As also shown, the cell 114 receives as an input (at data inputs 12, 14) the two most significant bits of the input word, and the cell 100 receives on its inputs 12, 14, the two least significant bits of the input word. The remaining cells, 102-112, each receive as inputs, in succession, the remaining bit pairs of the input word, as shown. The first row of cells 100-114 of the array of FIGS. 5A and 5B is configured, and its cells are interconnected, in the manner described in connection with FIGS. 4A and 4B. It will be appreciated that the data output 22 of the first cell 100 of the first row will indicate whether there are an even or odd number of "0's" in the input word, and thus represents the least significant bit of the total count of leading "0's" in the input word.

The function of the succeeding rows, i.e., the second row (cells 200-206), third row (cells 300-302) and fourth row (cell 400) is to obtain the next more significant bit in the leading zero count. More particularly, the function of the second row (cells 200-206) is to count the pairs of "0's" (pair data) in the leading zero string of the input word. Thus, only half the number of cells in the first row are required to construct the second row. As illustrated, this pair data is obtained from the enable outputs 20 of the cells in the second row. Thus, the data inputs 12, 14 of each cell in the first row are coupled to receive the enable outputs 20 of adjacent pairs of cells in the first row. When the enable output 20 of any cell 200-206 in the second row is active (i.e., binary "0"), this is an indication that the data inputs 12, 14 for that cell, and thus the enable outputs 20 supplying those data inputs, are both binary "0's". It will be appreciated that the data output 22 of the first cell 200 of the second row of cells 200-206 will indicate the odd/even sense of the total count of "0" pairs in the input word. Thus, the data output 22 of the first cell 200 of the second row of cells indicates the second least significant bit of the total leading zero count.

The construction and operation of the third row of cells 300-302 and the fourth row of cell 400, is as set forth above. It will be appreciated that the data output 22 of the first cell 300 of the third row of cells 300, 302 will be indicative of the second most significant bit of the total leading zero count. Similarly, it will be appreciated that the data output 22 of the cell 400 comprising the fourth row will be indicative of the most significant bit of the total leading zero count. Accordingly, the data outputs 22 of the first cell of each row collectively define a data word whose magnitude is indicative of the total leading zero count.

In the example of FIG. 5A, there are no leading zeros in the input word 34, i.e., every bit in the input word is a binary "0" Accordingly, as shown, the magnitude of the digital output word is binary "0000" (decimal 0), indicating no leading zeros in the input word. In the example of FIG. 5B, there are nine leading zeros in the input word and, as shown, the magnitude of the data output word is binary "1001" which is a decimal "9".

From the foregoing, it will be appreciated that a plurality of cells 10 may be cascaded and interconnected as above described to define a leading zero counter for an input word of any width. The input word is supplied to the data inputs of the first row of cells, and each succeeding row has only half the number of cells as the immediately preceding row. The data output 22 of the first cell 100 of the first row of cells 100-114 provides an output indicative of the least significant bit of the leading zero count, while the data output 22 of the first cell of each succeeding row (i.e., cells 200, 300, 400) provide an output indicative of a more significant bit of the leading zero count. It will be appreciated that the last row will always comprise only one cell (e.g., cell 400), and that the enable output 20 of this cell serves as a zero indicator for the entire input word. For example, referring to FIG. 5A, the enable output 20 of the cell 400 is a binary "0", thus indicating that there are no leading zeros in the input word. In contradistinction, in the example of FIG. 5B, the enable output 20 of the cell 400 is a binary "1", indicating that there are leading zeros in the input word.

Although the leading zero counter array described above has application to a bus having any bit width, certain relationships may be defined when the bit width is a power of two. Thus, for a 2.sup.N bit bus, it will be appreciated that the array will always comprise 2.sup.N -1 cells, and that there will always be N successive rows of cells, and the first row of cell wills always comprise 2.sup.N /2 cells. These relationships are illustrated in the examples of FIGS. 5A and 5B. Irrespective of the configuration, however, it will be appreciated from the drawings, and in particular FIGS. 4A, 4B, 5A and 5B, that the last cell of each row (i.e., cells 104 in FIGS. 4A and 4B, and cells 114, 206, 302 and 400 in FIGS. 5A and 5B) should have their carry inputs 16 and enable inputs 18 both tied to a source which represents a binary or logical "0".

An important feature of the invention is illustrated by FIGS. 4A, 4B, 5A and 5B. It will be noted that, due to the array topology, and in particular, the manner in which the cells 10 are cascaded and interconnected, there is no crossover of any signal lines connecting any of the cells 10. This feature of the invention simplifies implementation of the invention, particularly implementations employing some type of metallization to effect the interconnections. Thus, implementation of the invention on a printed circuit board or in an integrated circuit (e.g., a custom LSI chip) requires only one layer of metallization. In other words, several insulated layers of metallization are not required as in the prior art.

Another important feature of the invention is that all of the bits of the input word are supplied to the counter array in parallel, and the operation of the counter array is totally asynchronous. Accordingly, no machine cycles are wasted in processing the input word to determine the number of leading zeros.

The present invention may be embodied in other specific forms without departing from the spirit or essential attributes thereof and, accordingly, reference should be made to the appended claims, rather than to the foregoing specification, as indicating the scope of the invention.