Trailing or leading zero counter having parallel and combinational logic

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 at least one hardware logic block in the plurality of hardware logic blocks is arranged to calculate a bit of index i of the output value and comprises:

i OR reduction stages arranged in series, a first OR reduction stage arranged to receive the input string and comprising one or more OR gates arranged to combine adjacent bits in the input string to generate an output string and any subsequent OR reduction stages arranged to receive the output string from a preceding OR reduction stage and comprising one or more OR gates arranged to combine adjacent bits in the received string to generate a further output string; and

combining logic arranged to combine outputs derived from a last OR reduction in the series and generate a bit of index i of the output value.

2. The 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. The zero counter according to claim 2 , wherein the at least one hardware logic block in the plurality of hardware logic blocks comprises:

a low section hardware logic block 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, and

a high section hardware logic block 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 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. The zero counter according to claim 2 , wherein at least one hardware logic block in the plurality of hardware logic blocks comprises:

a 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, and

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. The zero counter according to claim 2 , wherein at least one hardware logic block in the plurality of hardware logic blocks comprises:

a low section hardware logic block 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, and

a high section hardware logic block 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. The zero counter according to claim 2 , wherein at least one hardware logic block in the plurality of 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. The 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, and

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. The 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, and

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 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. The 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 subsection and one or more logic gates arranged to combine the received bits and generate at least one output;

a further high subsection hardware logic block comprising inputs arranged to receive bits from a second further subsection of the subsection of a string, the second further subsection including a most significant bit in the subsection and one or more logic gates arranged to combine the received bits and generate at least one output, wherein the first and second further subsections of the subsection are non-overlapping and comprise all the bits in the subsection; and

combining logic arranged to combine the output of the two further subsection hardware logic blocks and generate an output of the subsection hardware logic block.

10. The zero counter according to claim 1 , wherein an output of an OR reduction stage is used by two or more hardware logic blocks.

11. A non-transitory computer readable storage medium having stored thereon computer readable program code for generating a processor comprising a zero counter, the 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 at least one hardware block in the plurality of hardware logic blocks is arranged to calculate a bit of index i of the output and comprises:

i OR reduction stages arranged in series, a first OR reduction stage arranged to receive the input string and comprising one or more OR gates arranged to combine adjacent bits in the input string to generate an output string and any subsequent OR reduction stages arranged to receive the output string from a preceding OR reduction stage and comprising one or more OR gates arranged to combine adjacent bits in the received string to generate a further output string; and

combining logic arranged to combine outputs derived from a last OR reduction in the series and generate a bit of index i of the output value.