Browse Prior Art Database

Count Leading Zeros Function Implementation

IP.com Disclosure Number: IPCOM000035282D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Furman, A: AUTHOR

Abstract

A unique circuit implementation is shown for the diagonalizer function for leading zeros, consisting of chains of alternating NAND and NOR blocks with parallel data inputs and serial feed forward inputs and with its I/O polarities corrected appropriately with inverters.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Count Leading Zeros Function Implementation

A unique circuit implementation is shown for the diagonalizer function for leading zeros, consisting of chains of alternating NAND and NOR blocks with parallel data inputs and serial feed forward inputs and with its I/O polarities corrected appropriately with inverters.

Some processor architectures utilize a count leading zeros (CLZ) function which extracts from the 232 (4 billion +) combinations of ones and zeros, the 33 (0,1,2,...31,32) desired combinations of leading zeros, and expresses them in binary output form (000000,000001,000010, 000011,....0111111,100000). Previously a design utilizing massive random logic macros with extensive parallelism was implemented to achieve the required performance. Also, other custom designs, e.g., dynamic PLA and LSS logic technologies, have been used to implement the CLZ function. A new design shown utilizes a stackable macro which can be included in the data flow without wiring penalty and fits the standard library well. The longest delay path is 13 logic stages. This implementation of the CLZ function has superior density and performance attributes.

A kernel of the design is that a 32-bit input word of 232 combination of ones and zeros is first converted to the simpler 32 bit word of leading zeros, i.e., diagonal matrix, using a unique diagonalizing circuit. Then, relatively simple non- unique combinatorial logic (NAND/NOR) is used to decode down to the six-bit binary word needed to describe the "number" of leading zeros.

The figure shows an eight-bit version of the diagonalizing circuit for leading zeros. It consists of a chain of alternating 2-way NANDS and 2-way NORS, each of which has a parallel data input and serial (or feed forward) input. This circuit is chained and iterative in that it generates one block delay per bit, can start with ...