Verifying the correctness of a leading zero counter

Patent metadata

Field	Value
Publication number	US-12056465-B2
Application number	US-202217704938-A
Country	US
Kind code	B2
Filing date	Mar 25, 2022
Priority date	Mar 25, 2022
Publication date	Aug 6, 2024
Grant date	Aug 6, 2024

Abstract

Verifying the correctness of a leading zero counter, including: generating, based on an input value comprising a plurality of digits, a first bit vector, wherein each entry of the first bit vector indicates whether a corresponding digit of the input value is equal to zero; calculating, based on the first bit vector, a leading zero count for the input value; generating a bit mask comprising a number of leading ones equal to the leading zero count; generating a second bit vector comprising a one at a same index as a first occurring zero in the bit mask; and verifying the leading zero count based on the first bit vector and one or more of the bit mask and the second bit vector.

First claim

What is claimed is:

1. A method of verifying the correctness of a leading zero counter, the method comprising:
generating, based on an input value to a leading zero counter and comprising a plurality of digits, a first bit vector, wherein each entry of the first bit vector indicates whether a corresponding digit of the input value is equal to zero;
calculating, by the leading zero counter based on the first bit vector, a leading zero count for the input value;
generating, as an output by a half decoder and responsive to the leading zero count being an input to the half decoder, a bit mask comprising a number of leading ones equal to the leading zero count;
generating, as an output by a plurality of exclusive OR (XOR) gates and responsive to the bit mask being an input to the plurality of XOR gates, a second bit vector comprising a one at a same index as a first occurring zero in the bit mask; and
verifying, by testing logic including a number of AND gates, the leading zero count based on the first bit vector and one or more of the bit mask and the second bit vector as inputs into the testing logic.

2. The method of claim 1 , wherein each entry of the first bit vector is calculated based on a bitwise OR applied to each bit of the corresponding digit of the input value.

3. The method of claim 1 , wherein each digit is encoded using four bits.

4. The method of claim 1 , wherein generating the bit mask comprises providing the leading zero count to the half decoder.

5. The method of claim 1 , wherein generating the second bit vector comprises performing an XOR operation on each bit pair in the bit mask.

6. The method of claim 1 , wherein verifying the leading zero count comprises determining whether the leading zero count is too large by determining whether a bitwise AND of the first bit vector and the bit mask is all zeroes.

7. The method of claim 1 , wherein verifying the leading zero count comprises determining whether the leading zero count is too small by determining whether a bitwise AND of the first bit vector and the second bit vector is not all zeroes.

8. An apparatus for verifying the correctness of a leading zero counter, the apparatus comprising:
a tester comprising a half decoder, a plurality of exclusive OR (XOR) gates, and testing logic, the tester configured to perform steps comprising:
receiving a first bit vector for an input value and a leading zero count for the input value based on the first bit vector, wherein each entry of the first bit vector indicates whether a corresponding digit of the input value is equal to zero;
generating, as an output by the half decoder and responsive to the leading zero count being an input to the half decoder, a bit mask comprising a number of leading ones equal to the leading zero count;
generating, as an output by the plurality of XOR gates and responsive to the bit mask being an input to the plurality of XOR gates, a second bit vector comprising a one at a same index as a first occurring zero in the bit mask; and
verifying, by the testing logic including a number of AND gates, the leading zero count based on the first bit vector and one or more of the bit mask and the second bit vector as inputs into the testing logic.

9. The apparatus of claim 8 , wherein each entry of the first bit vector is calculated based on a bitwise OR applied to each bit of the corresponding digit of the input value.

10. The apparatus of claim 8 , wherein each digit is encoded using four bits.

11. The apparatus of claim 8 , wherein generating the bit mask comprises providing the leading zero count to the half decoder.

12. The apparatus of claim 8 , wherein generating the second bit vector comprises performing an XOR operation on each bit pair in the bit mask.

13. The apparatus of claim 8 , wherein verifying the leading zero count comprises determining whether the leading zero count is too large by determining whether a bitwise AND of the first bit vector and the bit mask is all zeroes.

14. The apparatus of claim 8 , wherein verifying the leading zero count comprises determining whether the leading zero count is too small by determining whether a bitwise AND of the first bit vector and the second bit vector is not all zeroes.

15. A system for verifying the correctness of a leading zero counter, comprising:
a leading zero counter configured to perform steps comprising:
generating, based on an input value comprising a plurality of digits, a first bit vector, wherein each entry of the first bit vector indicates whether a corresponding digit of the input value is equal to zero; and
calculating a leading zero count for the first bit vector; and

a tester for the leading zero counter comprising a half decoder, a plurality of exclusive OR (XOR) gates, and testing logic including a number of AND gates, the tester configured to perform steps comprising:
generating, as an output by the half decoder and responsive to the leading zero count being an input to the half decoder, a bit mask comprising a number of leading ones equal to the leading zero count;
generating, as an output by the plurality of XOR gates and responsive to the bit mask being an input to the plurality of XOR gates, a second bit vector comprising a one at a same index as a first occurring zero in the bit mask; and
verifying, by the testing logic, the leading zero count based on the first bit vector and one or more of the bit mask and the second bit vector as inputs into the testing logic.

16. The system of claim 15 , wherein each entry of the first bit vector is calculated based on a bitwise OR applied to each bit of the corresponding digit of the input value.

17. The system of claim 15 , wherein generating the bit mask comprises providing the leading zero count to the half decoder.

18. The system of claim 15 , wherein generating the second bit vector comprises performing an XOR operation on each bit pair in the bit mask.

19. The system of claim 15 , wherein verifying the leading zero count comprises determining whether the leading zero count is too large by determining whether a bitwise AND of the first bit vector and the bit mask is all zeroes.

20. The system of claim 15 , wherein verifying the leading zero count comprises determining whether the leading zero count is too small by determining whether a bitwise AND of the first bit vector and the second bit vector is not all zeroes.

Assignees

• IBM

Inventors

• Klein Michael
• Leber Petra
• Lichtenau Cedric
• Payer Stefan
• Schelm Kerstin Claudia

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