# US 10,120,651 B2 · Trailing or leading digit anticipator > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,651 B2 - Document ID: US10120651B2 - Status: Granted - Kind: B2 - Application number: 15/262,168 - Filed: 2016-09-12 - Published: 2017-03-16 - Granted: 2018-11-06 - Earliest claimed: 2015-09-10 - Assignees: Imagination Technologies Limited - Applicants: Imagination Technologies Limited - Inventors: Freddie Rupert Exall; Theo Alan Drane; Joe Buckingham - Web page: https://patentgrep.com/patent/US10120651B2 ## CPC - G06F 7/74: 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)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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, wherein the input encoding circuit is configured to set an ith position of the encoded input string to one of a z, p or g based on how many of the ith bits of the fixed point numbers are high; 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, wherein a window of the encoded input string comprises a predetermined number of consecutive positions of the encoded input string, wherein the predetermined number is greater than or equal to three and wherein the window-based surrogate string generation circuit is configured to generate an ith bit of the surrogate string based on an ith window of the encoded input string, the ith window comprising the predetermined number of consecutive positions of the encoded input string starting with and including an ith position of the encoded input string; 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. ### Claim 2 (depends on 1) The leading zero anticipator of claim 1, wherein the window-based surrogate string generation circuit is configured to set an ith 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 ith bit and the i+1th bit of the result of the arithmetic operation will be high. ### Claim 3 (depends on 1) The leading zero anticipator of claim 1, wherein there are two fixed point numbers and the input encoding circuit is configured to: set the ith position of the encoded input string to a z when both of the ith bits of the fixed point numbers are low, set the ith position of the encoded input string to a p when only one of the ith bits of the fixed point numbers is high; and set the ith position of the encoded input string to a g when both of the ith bits of the fixed point numbers are high. ### Claim 4 (depends on 1) The leading zero anticipator of claim 1, 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 ith bit of the surrogate string to a high value when the corresponding window of the encoded input string comprises ggz, gpg, GPP, gpp, gpz, gzg, pgg, pzz, zgz, zpg, zpp, zpz or zzg and the window-based surrogate string generation circuit is configured to set the ith bit of the surrogate string to a low value when the corresponding window of the encoded input string comprises ggg, ggp, gzp, gzz, pgp, pgz, ppg, ppp, ppz, pzg, pzp, zgg, zgp, zzp, or zzz. ### Claim 5 (depends on 1) The leading zero anticipator of claim 1, wherein the window-based surrogate string generation circuit is configured to set the ith bit of the surrogate string, e_y, according to the following formula: e_yi=(pl∧(pi−1∨(gi−1∧zi−2)∨(zi−1∧gi−2)))∨(pi∧((zi−1∧zi−2)∨(gi−1∧gi−2))). ### Claim 6 (depends on 1) The leading zero anticipator of claim 1, wherein the window-based surrogate string generation circuit is configured to set the ith bit of a negated surrogate string, e_y, according to the following formula: e_yl=(pl∧((zi−1∧gl−2)∨(gi−1∧zl−2)))∨(pi∧((zi−1∨gl−2)∨(gi−1∧zi−2))). ### Claim 7 (depends on 1) A non-transitory computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture the leading zero anticipator as set forth in claim 1. ### Claim 8 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, wherein generating the encoded input string comprises setting an ith position of the encoded input string to one of z, p or g based on how many of the ith bits of the fixed point numbers are high; 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, 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 and wherein generating the surrogate string comprises setting an ith bit of the surrogate string based on an ith window of the encoded input string, the ith window comprising the predetermined number of consecutive positions of the encoded input string starting with and including an ith position of the encoded input string; 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. ### Claim 9 (depends on 8) The method of claim 8, wherein generating the surrogate string comprises setting the ith 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 ith bit and the i+1th bit of the result of the arithmetic operation will be high. ### Claim 10 (depends on 8) The method of claim 8, wherein there are two fixed point numbers and generating the encoded input string comprises: setting the ith position of the encoded input string to a z when both of the ith bits of the fixed point numbers are low; setting the ith position of the encoded input string to a p when only one of the ith bits of the fixed point numbers is high; and setting the ith position of the encoded input string to a g when both of the ith bits of the fixed point numbers are high. ### Claim 11 (depends on 8) The method of claim 8, 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 ith 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 ith bit of the surrogate string to a low value when the corresponding window of the encoded input string comprises ggg, ggp, gzp, gzz, pgp, pgz, ppg, ppp, ppz, pzg, pzp, zgg, zgp, zzp, or zzz. ### Claim 12 (depends on 8) The method of claim 8, wherein generating the surrogate string comprises setting an ith bit of the surrogate string, e_y, according to the following formula: e_yi=(pl∧(pi−1∨(gi−1∧zi−2)∨(zi−1∧gi−2)))∨(pi∧((zi−1∧zi−2)∨(gi−1∧gi−2))). ### Claim 13 (depends on 8) The method of claim 8, wherein generating the surrogate string comprises setting an ith bit of a negated surrogate string, e_y, according to the following formula: e_yl=(pl∧((zi−1∧gl−2)∨(gi−1∧zl−2)))∨(pi∧((zi−1∨gl−2)∨(gi−1∧zi−2))).