Trailing or leading digit anticipator

Patent metadata

Field	Value
Publication number	US-10698660-B2
Application number	US-201916429869-A
Country	US
Kind code	B2
Filing date	Jun 3, 2019
Priority date	Sep 10, 2015
Publication date	Jun 30, 2020
Grant date	Jun 30, 2020

Abstract

Methods and leading zero anticipators for estimating the number of leading zeros in a result of a fixed point arithmetic operation which is accurate to within one bit for any signed fixed point numbers. The leading zero anticipator includes an input encoding circuit which generates an encoded input string from the fixed point numbers; a window-based surrogate string generation circuit which generates a surrogate string whose leading one is an estimate of the leading one in the result of the arithmetic operation by examining consecutive windows of the encoded input string and setting corresponding bits of the surrogate string based on the examinations; and a counter circuit configured to estimate the number of leading zeros in the result of the arithmetic operation based on the leading one in the surrogate string.

First claim

What is claimed is:

1. A leading zero anticipator configured to estimate a number of leading zeros in a result of an arithmetic operation performed on two or more fixed point numbers, the leading zero anticipator comprising:
an input encoding circuit configured to generate an encoded input string from the two or more fixed point numbers;
a window-based surrogate string generation circuit configured to:
generate a surrogate string whose leading one is an estimate of a leading one in the result of the arithmetic operation by examining consecutive windows of the encoded input string and setting corresponding bits of the surrogate string based on the examinations, the estimate of the leading one being within one bit position of the leading one in the actual result of the arithmetic operation for any signed fixed point numbers; and
set an i th bit of the surrogate string to a high value when the corresponding window of the encoded input string comprises a pattern that always indicates one of the i th bit and the i+1 th bit of the result of the arithmetic operation will be high; and

a counter circuit configured to estimate the number of leading zeros in the result of the arithmetic operation based on the leading one in the surrogate string.

2. The leading zero anticipator of claim 1 , wherein a window of the encoded input string comprises a predetermined number of consecutive positions of the encoded input string.

3. The leading zero anticipator of claim 2 , wherein the predetermined number is greater than or equal to three.

4. The leading zero anticipator of claim 2 , wherein the window-based surrogate string generation circuit is configured to generate an i th bit of the surrogate string based on an i th window of the encoded input string, the i th window comprising the predetermined number of consecutive positions of the encoded input string starting with and including an i th position of the encoded input string.

5. The leading zero anticipator of claim 1 , wherein the input encoding circuit is configured to set an i th position of the encoded input string to one of a z, p or g based on how many of the i th bits of the fixed point numbers are high.

6. The leading zero anticipator of claim 5 , wherein there are two fixed point numbers and the input encoding circuit is configured to: set the i th position of the encoded input string to a z when both of the i th bits of the fixed point numbers are low; set the i th position of the encoded input string to a p when only one of the i th bits of the fixed point numbers is high; and set the i th position of the encoded input string to a g when both of the i th bits of the fixed point numbers are high.

7. The leading zero anticipator of claim 5 , wherein a window of the encoded input string comprises three consecutive positions of the encoded input string and the window-based surrogate string generation circuit is configured to set an i th bit of the surrogate string to a high value when the corresponding window of the encoded input string comprises ggz, gpg, gpp, gpz, gzg, pgg, pzz, zgz, zpg, zpp, zpz or zzg and the window-based surrogate string generation circuit is configured to set the i th bit of the surrogate string to a low value when the corresponding window of the encoded input string comprises ggg, gyp, gzp, gzz, pgp, pgz, ppg, ppp, ppz, pzg, pzp, zgg, zgp, zzp, or zzz.

8. The leading zero anticipator of claim 5 , wherein the window-based surrogate string generation circuit is configured to set the i th bit of the surrogate string, e_y, according to the following formula:
e _ y i =( p l ∧( p i−1 ∨( g i−1 ∧z i−2 )∨( z i−1 ∧g i−2 )))∨( p i ∧(( z i−1 ∧z i−2 )∨( g i−1 ∧g i−2 ))).

9. The leading zero anticipator of claim 5 , wherein the window-based surrogate string generation circuit is configured to set the i th bit of a negated surrogate string, e_y , according to the following formula:
e _ y l =( p l ∧(( z i−1 ∧ g l−2 )∨( g i−1 ∧ z l−2 )))∨( p i ∧(( z i−1 ∧ g l−2 )∨( g i−1 ∧ z i−2 ))).

10. A method of estimating a number of leading zeros in a result of an arithmetic operation performed on two or more fixed point numbers, the method comprising:
generating, using an input-encoding circuit, an encoded input string from the two or more fixed point numbers;
generating, using a window-based surrogate string generation circuit, a surrogate string whose leading one is an estimate of a leading one in the result of the arithmetic operation by examining consecutive windows of the encoded input string and setting corresponding bits of the surrogate string based on the examinations, the estimate of the leading one being within one bit position of the leading one in the actual result of the arithmetic operation for any signed fixed point numbers;
setting the i th bit of the surrogate string to a high value when the corresponding window of the encoded input string comprises a pattern that always indicates one of the i th bit and the i+1 th bit of the result of the arithmetic operation will be high; and
estimating, using a counter circuit, the number of leading zeros in the result of the arithmetic operation based on the leading one in the surrogate string.

11. The method of claim 10 , wherein a window of the encoded input string comprises a predetermined number of consecutive positions of the encoded input string and the predetermined number is greater than or equal to three.

12. The method of claim 11 , wherein generating the surrogate string comprises setting an i th bit of the surrogate string based on an i th window of the encoded input string, the i th window comprising the predetermined number of consecutive positions of the encoded input string starting with and including an i th position of the encoded input string.

13. The method of claim 10 , wherein generating the encoded input string comprises setting an i th position of the encoded input string to one of z, p or g based on how many of the i th bits of the fixed point numbers are high.

14. The method of claim 13 , wherein there are two fixed point numbers and generating the encoded input string comprises: setting the i th position of the encoded input string to a z when both of the i th bits of the fixed point numbers are low; setting the i th position of the encoded input string to a p when only one of the i th bits of the fixed point numbers is high; and setting the i th position of the encoded input string to a g when both of the i th bits of the fixed point numbers are high.

15. The method of claim 13 , wherein a window of the encoded input string comprises three consecutive positions of the encoded input string and generating the surrogate string comprises setting an i th bit of the surrogate string to a high value when the corresponding window of the encoded input string comprises ggz, gpg, gpp, gpz, gzg, pgg, pzz, zgz, zpg, zpp, zpz or zzg and setting the i th bit of the surrogate string to a low value when the corresponding window of the encoded input string comprises ggg, gyp, gzp, gzz, pgp, pgz, ppg, ppp, ppz, pzg, pzp, zgg, zgp, zzp, or zzz.

16. The method of claim 13 , wherein generating the surrogate string comprises setting an i th bit of the surrogate string, e_y, according to the following formula:
e _ y i =( p l ∧( p i−1 ∨( g i−1 ∧z i−2 )∨( z i−1 ∧g i−2 )))∨( p i ∧(( z i−1 ∧z i−2 )∨( g i−1 ∧g i−2 ))).

17. The method of claim 13 , wherein generating the surrogate string comprises setting an i th bit o

Assignees

• Imagination Tech Ltd

Inventors

• Exall Freddie Rupert
• Drane Theo Alan
• Buckingham Joe

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

• G06F7/575

  Basic arithmetic logic units, i.e. devices selectable to perform either addition, subtraction or one of several logical operations, using, at least partially, the same circuitry · CPC title

• G06F5/012

  in floating-point computations · CPC title