US5493520A Expired / Lapsed US ⏱️ 0.0 years remaining

Two state leading zero/one anticipator (LZA)

Assignee: International Business Machines Corp

•

Filing: 1994-04-15

•

Granted: 1996-02-20

•

Expires: 2014-04-15

📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract An apparatus and method for anticipating leading zeros/ones used in normalizing the results of a full adder. The propagate (P), generate (G) and zero (Z) states of the two inputs to the adder are combined in two stages of logic to derive a pair of state outputs LφS and L1S which fully specify by respective bit strings the leading zero and leading one conditions of the output from the adder. The two state bit strings, one representing the leading zero evaluation and the second representing the leading one evaluation, are then compared to determine which one of the two is applicable, correspondingly indicating whether the adder result is a positive or a negative value, and the number of leading bit positions requiring shifted removal during the normalization process. The leading 0/1 anticipator according to the present invention lends itself to high speed and low device count circuit implementations.

Inventors

👤 Martin S. Schmookler
👤 Donald G. Mikan, Jr.

Bibliographic Details

Application Number —

Jurisdiction US

Data Source google_patents

Last Synchronized 2026-11-09 09:09

CPC Classifications

G; G06; G06F; G06F7/00; G06F7/74; G06F7/38; G06F7/48; G06F7/483; G06F7/485; G06F7/499; G06F7/49936

Claims Analysis

Total Claims: 18

Claim 1

Independent Claim 218 words

A leading digit anticipator apparatus utilized in conjunction with an adder of a digital processor, said adder receiving as inputs first and second data bit streams, comprising: means for logically combining said first and said second data bit strings to derive P, Z, and G bit strings, wherein each bit position within said P bit string is derived by XORing corresponding bit positions of said first and second data bit strings, and wherein each bit position within said Z bit string is derived by ORing corresponding bit positions of said first and second data bit strings, and wherein each bit position within said G bit string is derived by ANDing corresponding bit positions within said first and second data bit strings; means for logically combining said P and Z bit strings to derive a PZ bit string and for logically combining said P and G bit strings to derive a PG bit string; means for determining from said PZ bit string a possible number of leading zeros within a sum of said first and second data bit strings; and means for determining from said PG bit string a possible number of leading ones within a sum of said first and second data bit strings, wherein a number of leading zeros or ones within a sum is efficiently determined.

Claim 2

Dependent Claim 218 words

Claim 3

Dependent Claim 84 words

The leading digit anticipator apparatus recited in claim 1, wherein said means for determining from said PZ bit string a possible number of leading zeros comprises means for constructing a first state output bit stream, wherein a value of each bit position within said first state output bit stream is determined, beginning with a most significant bit position, by combining a value of each corresponding bit position within said PZ bit string with values of more significant bit positions within said PZ bit string.

Claim 4

Dependent Claim 42 words

The leading digit anticipator apparatus recited in claim 2, wherein said means for constructing a first output bit string combines a value of each bit position within said PZ bit string with values of more significant bit position utilizing multiple AND gates.

Claim 5

Dependent Claim 82 words

The leading digit anticipator apparatus recited in claim 1, wherein said means for determining from said PG bit string a possible number of leading ones comprises constructing a second state output bit stream, wherein a value of each bit position within said second state output bit stream is determined, beginning with a most significant bit position, by combining the value of each corresponding bit position within said PG bit string with values of more significant bit positions within said PG bit string.

Claim 6

Dependent Claim 43 words

The leading digit anticipator apparatus recited in claim 4, wherein said means for constructing a second output bit string combines a value of each bit position within said PG bit string with the values of more significant bit positions utilizing multiple AND gates.

Claim 7

Dependent Claim 52 words

The leading digit anticipator apparatus recited in claim 1, wherein said means for logically combining said P and Z bit strings and for logically combining said P and G bit strings logically combines said P and Z bit strings and logically combines said P and G bit strings utilizing exclusive-OR (XOR) logic.

Claim 8

Dependent Claim 116 words

The leading digit anticipator apparatus recited in claim 1, wherein said means for determining from said PZ bit string a possible number of leading zeros has as an output a first state output bit string, said first output bit string indicating said possible number of leading zeros by having a corresponding number of leading bit positions set to a particular bit state, and wherein said means for determining from said PG bit string a possible number of leading ones has as an output a second state output bit string, said second output bit string indicating said possible number of leading ones by having a corresponding number of leading bit positions set to a particular bit state.

Claim 9

Dependent Claim 116 words

The leading digit anticipator apparatus recited in claim 7, and further comprising: means for logically combining said first state output bit string and said second state output bit string to derive a matching bit string; and means for comparing said matching bit string to said first and said second state output bit strings to determine a sign of said sum of said first and second data bit strings and a number of leading zeros or ones within said sum, wherein said sign of said sum is positive if said matching bit string corresponds to said first state output bit string and is negative if said matching bit string corresponds to said second state output bit string.

Claim 10

Independent Claim 211 words

A method within a digital processor for anticipating leading digits within a sum of an adder, said adder receiving as inputs first and second data bit strings, said method comprising: logically combining said first and said second data bit strings to derive P, Z, and G bit strings, wherein each bit position within said P bit string is derived by XORing corresponding bit positions of said first and second data bit strings, and wherein each bit position within said Z bit string is derived by ORing corresponding bit positions of said first and second data bit strings, and wherein each bit position within said G bit string is derived by ANDing corresponding bit positions within said first and second data bit strings; logically combining said P and Z bit strings to derive a PZ bit string; logically combining said P and G bit strings to derive a PG bit string; determining from said PZ bit string a possible number of leading zeros within a sum of said first and second data bit strings; and determining from said PG bit string a possible number of leading ones within a sum of said first and second data bit strings, wherein a number of leading zeros or ones within a sum is efficiently determined.

Claim 11

Independent Claim 211 words

Claim 12

Dependent Claim 82 words

The method for anticipating leading digits of claim 9, wherein said step of determining from said PZ bit string a possible number of leading zeros comprises: constructing a first state output bit stream, wherein a value of each bit position within said first state output bit stream is determined, beginning with a most significant bit position, by combining a value of each corresponding bit position within said PZ bit string with values of more significant bit positions within said PZ bit string.

Claim 13

Dependent Claim 47 words

The method for anticipating leading digits of claim 10, wherein said step of constructing a first state output bit stream comprises: beginning with a most significant bit position, ANDing a value of each bit position within said PZ bit string with values of more significant bit positions.

Claim 14

Dependent Claim 82 words

The method for anticipating leading digits of claim 9, wherein said step of determining from said PG bit string a possible number of leading ones comprises: constructing a second state output bit string, wherein a value of each bit position within said second state output bit string is determined, beginning with a most significant bit position, by combining a value of each corresponding bit position within said PG bit string with values of more significant bit positions within said PG bit string.

Claim 15

Dependent Claim 47 words

The method for anticipating leading digits of claim 12, wherein said step of constructing a second state output bit stream comprises: beginning with a most significant bit position, ANDing a value of each bit position within said PG bit string with values of more significant bit positions.

Claim 16

Dependent Claim 52 words

The method for anticipating leading digits of claim 9, wherein said steps of logically combining said P and Z bit strings and logically combining said P and G bit strings comprise: logically combining said P and Z bit strings and logically combining said P and G bit strings utilizing exclusive-OR (XOR) logic.

Claim 17

Dependent Claim 118 words

The method for anticipating leading digits of claim 9, wherein said step of determining from said PZ bit string a possible number of leading zeros has as an output a first state output bit string, said first state output bit string indicating said possible number of leading zeros by having a corresponding number of leading bit positions set to a particular bit state, and wherein said step of determining from said PG bit string a possible number of leading ones has as an output a second state output bit string, said second state output bit string indicating said possible number of leading ones by having a corresponding number of leading bit positions set to a particular bit state.

Claim 18

Dependent Claim 107 words

The method for anticipating leading digits of claim 15, and further comprising: logically combining said first and said second state output bit strings to derive a matching bit string; comparing said matching bit string to said first and said second state output bit strings to determine a sign of said sum of said first and second data bit strings and a number of leading zeros or ones within said sum, wherein said sign of said sum is positive if said matching bit string corresponds to said first state output bit string and is negative if said matching bit string corresponds to said second state output bit string.

References Cited (Backward Citations)

US4777613A Cited

US4866651A Cited

US5181186A Cited

US4979141A Cited

US4926369A Cited

US4969118A Cited

US5282156A Cited

US5204825A Cited

US5343413A Cited

US5317527A Cited

USPTO Annuity & Maintenance Windows

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1999-02-19	1999-08-21	2000-02-20	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2003-02-19	2003-08-21	2004-02-20	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2007-02-19	2007-08-21	2008-02-20	$7700.00	Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag

Select Category

Notes (Optional)