Patent ID: 7461110

Claim:
An efficient method of counting the number of zeros in a plurality of 4-bit blocks which form a larger value, said method for reducing circuit redundancy comprising: generating three output bits q 0 , q 1 and q 2 for a given one of the 4-bit blocks from four input bits a 0 , a 1 , a 2 and a 3 using digital circuitry, wherein the digital circuitry carries out the logic equations q 0=not( a 1+ a 2+ a 3+ a 4), q 1=not( a 0+ a 1), q 2= a 1(not a 0)+not( a 0+ a 2), said generating including inverting the input bits to create complementary bits a 0 _n, a 1 _n, a 2 _n and a 3 _n, transmitting bits a 0 _n a 1 _n a 2 _n and a 3 _n to respective inputs of a first NAND gate whose output is the complement of bit q 0 , transmitting bits a 0 _n and a 1 _n to respective inputs of a second NAND gate whose output is the complement of bit q 1 , and transmitting bits a 0 _n and a 2 _n to respective inputs of a third NAND gate, and transmitting input bits a 0 _n and a 1 respective inputs of a fourth NAND gate, wherein outputs of the third and fourth NAND gates are connected to respective inputs of a fifth NAND gate whose output is bit q 2 ; combining the output bits for the given 4-bit block to yield a number of leading zeros wherein output bit q 0 is the most significant bit and output bit q 2 is the least significant bit; and combining the output bits from all of the 4-bit blocks to yield a count of leading zeros in the larger value wherein a most significant bit of the count is a one when all input bits from all of the 4-bit blocks are zero.