Trailing or leading zero counter having parallel and combinational logic

Patent metadata

Field	Value
Publication number	US-9600240-B2
Application number	US-201615218306-A
Country	US
Kind code	B2
Filing date	Jul 25, 2016
Priority date	Jan 17, 2014
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

A trailing/leading zero counter includes a plurality of hardware logic blocks, each of which calculates one bit of the output value (i.e. the number of trailing/leading zeros depending on whether it is a trailing/leading zero counter). Each hardware logic block includes two blocks of section hardware logic which each receive a section of an input string and generate one or two outputs from this section of bits. Combining logic then combines the outputs of the section hardware logic to generate the bit of the output value. For hardware logic blocks which calculate bits other than the least significant bit of the output, the hardware logic blocks also include one or more OR reduction stages which reduces the length of the input string by pairwise combining of bits using OR gates before the resultant string is divided into two sections and input to the section hardware logic.

First claim

What is claimed is:

1. A zero counter comprising a plurality of hardware logic blocks each arranged to calculate one bit of an output value, the output value corresponding to a number of trailing or leading zeros in an input string, wherein a first of the plurality of hardware logic block is arranged to calculate a least significant bit of the output value and comprises:
a low section hardware logic block comprising inputs arranged to receive bits from a first section of the input string including a least significant bit in the input string and one or more logic gates arranged to combine the received bits and generate at least one output;
a high section hardware logic block comprising inputs arranged to receive bits from a second section of the input string including a most significant bit in the input string and one or more logic gates arranged to combine the received bits and generate at least one output, wherein the first and second sections of the input string are non-overlapping and comprise all the bits in the input string; and
combining logic arranged to combine the outputs of the two section hardware logic blocks and generate the least significant bit of the output value, wherein
each other hardware logic block in the plurality of hardware logic blocks is arranged to calculate a bit of index i of the output value.

2. A zero counter according to claim 1 , wherein the zero counter comprises a trailing zero counter and the output value corresponds to a number of trailing zeros.

3. A zero counter according to claim 2 ,
wherein a low section hardware logic block in one of the plurality of hardware logic blocks is arranged to generate two outputs, the first output, D(v L ), being equal to one if there is no trailing one in an even column of the received section and the second output, B(v L ), being equal to one if there is a one in an odd indexed column of the received section,
wherein a high section hardware logic block in the same one of the plurality of hardware logic blocks is arranged to generate one output, G(v H ), being equal to one if there is a trailing one in an odd indexed column of the received section, and
wherein the combining logic in the same one of the plurality of hardware logic blocks is arranged to generate the bit of the output value by combining the outputs of the high and low section hardware logic blocks using:
D ( v L )·( B ( v L )+ G ( v H ))

where:
· represents an AND function, and
+ represents an OR function.

4. A zero counter according to claim 2 ,
wherein the low section hardware logic block in each of the plurality of hardware logic blocks is arranged to generate two outputs, the first output, D(v L ), being equal to one if there is no trailing one in an even column of the received section and the second output, B(v L ), being equal to one if there is a one in an odd indexed column of the received section,
wherein the high section hardware logic block in each of the plurality of hardware logic blocks is arranged to generate one output, G(v H ), being equal to one if there is a trailing one in an odd indexed column of the received section, and
wherein the combining logic each of the plurality of hardware logic blocks is arranged to generate the bit of the output value by combining the outputs of the high and low section hardware logic blocks using:
D ( v L )·( B ( v L )+ G ( v H ))

where:
· represents an AND function, and
+ represents an OR function.

5. A zero counter according to claim 2 ,
wherein a low section hardware logic block in one of the plurality of hardware logic blocks is arranged to generate two outputs, the first output, G(v L ), being equal to one if there is a trailing one in an odd indexed column of the received section and the second output, A(v L ), being equal to one if there is not a one in any even indexed column of the received section,
wherein a high section hardware logic block in the same one of the plurality of hardware logic blocks is arranged to generate one output, G(v H ), being equal to one if there is a trailing one in an odd indexed column of the received section, and
wherein the combining logic in the same one of the plurality of hardware logic blocks is arranged to generate the bit of the output value by combining the outputs of the high and low section hardware logic blocks using:
G ( v L )+( G ( v H )· A ( v L )).

6. A zero counter according to claim 2 , wherein at least one of the high or low section hardware logic blocks comprises:
a low subsection hardware logic block comprising inputs arranged to receive bits from a first subsection of a section of a string, the first subsection including a least significant bit in the section and one or more logic gates arranged to combine the received bits and generate at least one output;
a high subsection hardware logic block comprising inputs arranged to receive bits from a second subsection of a section of a string, the second subsection including a most significant bit in the section and one or more logic gates arranged to combine the received bits and generate at least one output, wherein the first and second subsections of the section are non-overlapping and comprise all the bits in the section; and
combining logic arranged to combine the output of the two subsection hardware logic blocks and generate an output of the section hardware logic block.

7. A zero counter according to claim 6 , wherein a low subsection hardware logic block in one of the high or low section hardware logic blocks is arranged to generate two outputs, the first output, D(v LS ), being equal to one if there is no trailing one in an even column of the received subsection and the second output, B(v LS ), being equal to one if there is a one in an odd indexed column of the received subsection,
wherein a high subsection hardware logic block in the same one of the high or low section hardware logic blocks is arranged to generate one output, G(v HS ), being equal to one if there is a trailing one in an odd indexed column of the received subsection, and
wherein the combining logic in the same one of the high or low section hardware logic blocks is arranged to generate the output of the section hardware logic block by combining the outputs of the high and low subsection hardware logic blocks using:
D ( v LS )·( B ( v LS )+ G ( v HS )).

8. A zero counter according to claim 6 , wherein a low subsection hardware logic block in one of the high or low hardware section logic blocks is arranged to generate two outputs, the first output, G(v LS ), being equal to one if there is a trailing one in an odd indexed column of the received subsection and the second output, A(v LS ), being equal to one if there is not a one in any even indexed column of the received subsection,
wherein a high subsection hardware logic block in the same one of the high or low section hardware logic blocks is arranged to generate one output, G(v HS ), being equal to one if there is a trailing one in an odd indexed column of the received subsection,
wherein the combining logic in the same one of the high or low section hardware logic blocks is arranged to generate the bit of the output of the section hardware logic block by combining the outputs of the high and low subsection hardware logic blocks using:
G ( v LS )+( G ( v HS )· A ( v LS )).

9. A zero counter according to claim 6 , wherein at least one of the high or low subsection hardware logic blocks comprises:
a further low subsection hardware logic block comprising inputs arranged to receive bits from a first further subsection of a subsection of a string, the first further subsection including a least significant bit in the subs

Assignees

• Imagination Tech Ltd

Inventors

• Exall Freddie Rupert
• Drane Theo Alan

Classifications

• G06F7/74 Primary

  Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders {(with shifting G06F5/01)} · CPC title

• G06F9/30029

  Logical and Boolean instructions, e.g. XOR, NOT · CPC title