Predictive status flag generation in a first-in first-out (FIFO) memory device method and apparatus

Method and apparatus are described for generating more accurate and timely FIFO status flags. Preferably, the asynchronous FIFO read and write pointers are conventionally compared with one another and the output of such comparison is glitch-suppressed. During such operation in accordance with the invented method and apparatus, prediction signals are used to precondition the status flag output latches so that they will provide the earliest possible accurate status reflecting asynchronous read and write clock activity. If a boundary condition is present--e.g. depending upon the next read or write clock activity, the FIFO's half full status flag may change where such change is impossible to predict because it is unknowable whether the next operation will be a read or a write or both--then an asynchronous state machine takes over from the prediction flag logic to ensure accurate and early preconditioning of the status flags' output latches. When no such boundary condition is present, the state machine is dormant and the prediction logic is active.

TECHNICAL FIELD 
The present invention relates generally to generation of status flags in 
first-in, first-out (FIFO) memory devices. More particularly, the 
invention concerns a method and apparatus for generating status flags that 
use predictive asynchronous state machine logic, thereby reducing the 
status flags' access times and improving their dynamic accuracy. 
BACKGROUND ART 
Status flag combinatorial logic such as a comparator typically is used to 
gate asynchronous FIFO read and write operations to produce a flag 
indicating to the user the FIFO's status, e.g. empty, almost empty, half 
full, almost full and full. Often, such combinatorial logic is slow 
(imagine a ripple carry that must propagate through an n-stage adder, 
where n may be sixteen or greater) and has transient outputs that result 
from different (skewed) logic gate delays. Such transient outputs are 
referred to in the literature as glitches and their removal to avoid false 
status indications to the FIFO's user is referred to in the literature as 
glitch suppression. Unfortunately, glitch suppression, which is most often 
implemented as a delay that simply masks such gate delays, further delays 
the output of the flag generation logic so as to render it inaccurate to 
the extent of its lack of currency or immediacy. 
The major disadvantages of prior art methods and apparatus for flag 
generation are outlined below. Since one must ensure that glitches from 
the comparison logic (constructed from purely combinatorial logic) do not 
become visible to the user, the result of the comparison must be passed 
through a glitch suppression block. This typically is implemented as a 
delay greater than the largest possible settling time of the comparison 
logic. If, for example, the comparator were realized with a ripple adder, 
the amount of delay that would have to be inserted would be greater than 
the time necessary for a carry signal to propagate through the entire 
chain of adders to set, for example, the most significant bit (MSB) of the 
sum to its correct value. Therefore, for the ever decreasing clock 
periods, those of skill will appreciate that a flag generated with this 
method can have quite large access times relative to the clock period of 
the device. These large access times would have serious implications on 
certain applications, such as using the status flags for block counting. 
Since the set of status flags for a FIFO are by definition supposed to 
describe the amount of information currently present within the device, 
one can see that if the flags have large access times, the information 
delivered to the user may be stale (describe a historical rather than a 
present state of the FIFO) or simply inaccurate. Any application that 
requires knowledge of how much data is in the FIFO memory array at the 
current (i.e. immediate) point in time, would suffer under prior art and 
methods and apparatus for flag generation. 
DISCLOSURE OF THE INVENTION 
Briefly, the invention uses a combination of predictive, or look-ahead, 
logic and asynchronous state machine logic to minimize flag access times 
and to maximize flag dynamic accuracy. Thus, in applications such as block 
counting which require increasingly accurate knowledge of the present 
volume of data within a FIFO, the status flags may be made substantially 
more accurate and timely, even as FIFO pointer word lengths and read/write 
clock speeds increase (resulting in longer combinational logic delay and 
data skew). 
In accordance with the invention, asynchronous FIFO read and write 
operations within the memory array are conventionally compared with one 
another and the output of such comparison is glitch-suppressed. During 
operations, however, in further accord with the invented method and 
apparatus, prediction logic is used to precondition the status flag output 
latches so that the flags will provide the earliest possible accurate 
status reflecting asynchronous read and write clock activity. If a 
boundary condition is present--for example, depending upon the next read 
or write clock activity, the FIFO's half full status flag may change where 
such change is impossible to predict because it is unknowable whether the 
next operation will be a read or a write operation--then an asynchronous 
state machine takes over from the prediction flag logic to ensure accurate 
and early preconditioning of the status flag output latches. When no such 
boundary condition is present, the state machine is dormant and prediction 
logic is active. The realized increase in dynamic flag resolution over 
prior art techniques, in accordance with the preferred method and 
apparatus of the invention, is nearly seven fold. 
These and additional objects and advantages of the present invention will 
be more readily understood after consideration of the drawings and the 
detailed description of the preferred embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT AND BEST MODE OF CARRYING 
OUT THE INVENTION 
Turning initially to FIG. 1, a representative architecture of the invented 
apparatus is provided in block diagram form, such architecture being 
indicated generally at 10. Architecture 10 represents a status 
flag-generation apparatus for use in a FIFO, a memory device which is 
configured to temporarily store serial data items, and to retrieve such 
data items in the order in which they were received. Data is stored in the 
FIFO during a write operation and retrieved from the FIFO during a read 
operation. 
In accordance with conventional FIFO design, the invented apparatus is 
intended for use in connection with a FIFO wherein the read and write 
operations are independent of one another (i.e., the read and write 
operations are independently docked). The apparatus includes read and 
write address pointers, each of which is (circularly) shifted 
synchronously with a corresponding read or write clock. 
Those skilled in the art will appreciate that in a FIFO having enable 
inputs as well as clock inputs for both writing and reading, a write event 
is synchronized to the write clock input, and is made to occur by 
asserting the write enable input. Likewise, a read event is synchronized 
to the read clock input, and is made to occur by asserting the read enable 
input. In principle, the write clock and the read clock both may be 
free-running periodic waveforms derived from crystal oscillator frequency 
sources. However, most contemporary FIFOs avoid the use of any internal 
circuit techniques which would require that these dock signals must be 
periodic. 
Conventional FIFOs commonly provide several status flags for informing a 
memory management unit (MMU) of a system coupled with the FIFO regarding 
the FIFO's relative state of fullness or emptiness. Typically, there are 
five such flags: full, almost-full, half full ("half" hereinafter), 
almost-empty and empty. The almost-full and almost-empty flags originated 
some years ago, as a semiconductor device adaptation of an interrupt-flag 
scheme used in certain minicomputers to indicate imminent process 
interruption. 
Occasionally, there are not enough pins on a device to provide every FIFO 
feature desired by the semiconductor manufacturer and its customers. For 
example, the almost-full and the almost-empty flags might be combined by 
an OR gate function into an almost-full/empty flag signal that appears on 
a single output pin of the FIFO device. External logic then is used to 
distinguish the full and empty conditions one from another by examining 
the half flag (based upon the fact that a FIFO having a useful depth n, 
e.g. n.gtoreq.2, when almost-empty must be less than half full). 
Some FIFOs feature programmable almost-full and almost-empty flags, wherein 
typically large offset values are programmed into offset value registers 
associated with these two flags. These offset values define the 
almost-full condition in terms of the number of data items the FIFO is 
short of being full and the almost-empty condition in terms of the number 
of data items the FIFO differs from being empty. 
With FIFOs, there are cases where the most recent event which has affected 
a flag value was synchronized with read and write clock signal timing that 
is asynchronous. In such cases, a status-representative signal may change 
in synchronism with a first clock signal, but may be read in synchronism 
with a second, different clock signal that is not synchronized with, or 
even related to the first clock signal. Thus, the FIFO's status flag is 
most unlikely always to meet the setup-time and hold-time requirements of 
downstream, operatively coupled and responsive, semiconductor devices. 
Preliminarily, then, the FIFO fullness flags synchronization dilemma may be 
described as follows. Assume that subsystem A is synchronized to clock A 
and that subsystem B is synchronized to clock B. Subsystem A then 
synchronously is writing data destined for subsystem B in accordance with 
its clock A, into a FIFO the purpose of which is to order and manage the 
data such that subsystem B can synchronously read these same data out of 
the FIFO in accordance with its own clock B. 
Whenever subsystem A writes one or more words, the FIFO suddenly can become 
full, almost-full or half full or it can suddenly cease to be almost-empty 
or empty. Similarly, whenever subsystem B reads a word, the FIFO suddenly 
can cease to be full, almost-full or half full. Thus, each flag signal can 
be affected for one state transition (i.e. status change) by what will be 
referred to herein as a write event and can be affected for the other 
state transition (i.e. status change) by what will be referred to herein 
as a read event. Accordingly, events which can cause the state of any of 
these so-called "fullness" flags to change can occur at either end of the 
FIFO. 
The invention will be described in the context of a FIFO of depth n=1024, 
with independent read and write clocks. The write clock 12b, also 
identified as WCLK, clocks data into the FIFO. The read clock 12a, also 
identified as RCLK, clocks data out of the FIFO. WCLK and RCLK typically 
are completely independent and cycle at any desired rate compatible with 
the data-setup and hold time specifications of the FIFO and with the 
substantially reduced, e.g. approximately 4 nanosecond (ns), flag skew 
time of the present invention. Of course, they may be asymmetric and 
aperiodic, so long as they meet predetermined minimum clock high and clock 
low times. 
The apparatus of the present invention thus includes separate read and 
write clocks 12a, 12b, the read clock 12a indexing the read pointer with 
each read clock pulse, and the write clock 12b indexing the write pointer 
with each write clock pulse. Read counter 14a indexes, e.g. increments, an 
address pointer 16a which is indicative of the address which will be read 
with the next read clock pulse. Write counter 14b indexes, e.g. 
increments, a write pointer 16b which is indicative of an address which 
will receive data upon the next write operation of the device. Either 
pointer may be considered to point to a FIFO memory location, i.e. each 
represents the corresponding next address (whether read or write) of the 
FIFO device. 
Thus, address pointers 16a, 16b point into the FIFO memory array, pointer 
16a pointing to the location of the data item that will be read out of the 
FIFO on the next rising edge of the read clock and pointer 16b pointing to 
the location in the FIFO memory array that will be written on the next 
rising edge of the write clock. The FIFO memory array is managed from an 
address pointer standpoint as a circular buffer so as to provide for 
effectively continuous indexing of the read and write pointers. Those of 
skill in the art will appreciate that the clocks may be low- or 
high-active, and may produce leading or trailing, rising or falling, 
edge-triggered results in FIFO pointer and status flag generation. The 
read and write clock signals that characterize FIFOs for which the 
invented method and apparatus are particularly useful are those that are 
asynchronously pulsed, i.e. where their active, or assertive, regions, or 
pulses, whether high- or low-going, have independently timed leading 
and/or trailing edges. 
The address pointers are output to a comparator 18, which compares the read 
and write address pointers so as to determine a difference therebetween. 
It will be appreciated that the read pointer points to the location of the 
earliest-entered data in the FIFO and the write pointer points to the HFO 
location to which the next piece of data will be written. The difference 
(or distance) between the read and write pointer thus will be understood 
to indicate an address count, such count representing the quantitative 
content of the memory device. An address count of 0, for example, will 
indicate that the memory device is empty and an address count of n, e.g. 
1024, will indicate that the memory device is full. Similarly, a half full 
memory device will have an address count of n/2+1, e.g. 513. The present 
invention provides for the accurate identification of a FIFO's address 
count so as to provide for the accurate generation of a status flag 
indicative of such count. 
Comparator 18 relates the read and write address pointers to identify a 
difference therebetween, i.e. it determines the difference between the 
read and write pointers, and compares such a difference with predetermined 
criteria to predict a status condition of the FIFO memory device, i.e. to 
predict a change in a status condition of the FIFO, and produces a 
corresponding predicted status signal thereupon. Described herein will be 
such comparison generally in the context of the generation of a half full, 
or half flag which is indicative of a half full memory device. 
Nevertheless, those of skill in the art will appreciate that any 
pre-programmed or user-programmed address count or other criteria, within 
the spirit and scope of the invention, may provide the basis for 
comparison to produce useful FIFO status condition indicia. Thus an 
operator-defined address count ;might be the basis for such a comparison 
by the simple expedient of providing a user-programmable address count or 
difference register within apparatus 10. 
It will be appreciated by those skilled in the art that such predefined 
criteria may include the relative emptiness, fullness or other useful data 
content indicia. In accordance with the preferred method and embodiment of 
the invention, such criteria include a transition value corresponding to 
an address count of the memory device that, in turn, denotes a 
predetermined status condition change, as will be described in detail 
below. (The illustrative example is a transition value, e.g. a present 
address count of 512 and a next address count of 513 where n=1024 denotes 
assertion of the FIFO's half full status flag. In such case, as will be 
seen, such change in status of the FIFO's half full flag is predicted when 
the address count of the memory device differs from transition value 
512.fwdarw.513 by a predetermined amount such as one, i.e. when the 
address count is represented by a 511.fwdarw.512 transition.) 
Comparator 18 relates the address count to predefined criteria to condition 
flag generation logic to change state with the next pulse of a 
predetermined one of the clocks. When the flag status is inactive, the 
comparator compares the address count with a predefined assertion 
predictor value, such value representing an address count which is one 
less than the address count at which the half full status flag is to 
become active. A similar assertion predictor value is provided for the 
almost full flag and for the full flag, both of which change status upon a 
transition of the write clock. Assertion of the almost empty flag, and of 
the empty flag, in contrast, occurs upon a transition or change of state 
of the read clock, and these flags in the preferred embodiment are 
associated with an assertion predictor value that is one greater than the 
address count at which a corresponding flag's status is to change. 
As indicated in FIG. 1, the comparator 18 outputs an assertion predictor 20 
and a de-assertion predictor 22. Assertion predictor serves as a status 
signal which indicates that a flag will change from inactive to active, 
e.g. from low to high. Such change may be indicated by an edge, or a 
transition from a low to high output level, or correspondingly from a high 
to a low output level, depending upon the choice of positive-true or 
negative-true logic. Similarly, the de-assertion predictor 22 indicates 
that a flag will change from an active to inactive, e.g. high to low. 
As indicated, the assertion and de-assertion status signals are connected 
to glitch suppression circuitry 24 coupled with comparator 18, such 
circuitry being capable of suppressing transient predicted status signals 
produced thereby, in a manner which is described in detail below. A 
detailed representation of such circuitry is further illustrated in FIGS. 
9A and 9B, to be discussed below. The glitch suppression circuity 24 
produces glitch-free status signals which correspond to the assertion 
predictor and de-assertion predictor signals described above. FIG. 1 
illustrates such signals at 20', 22', such signals corresponding to 
assertion predictor 20 and de-assertion predictor 22. The glitch-free 
signals are passed to an asynchronous state machine 26, which interprets 
such signals to direct a flag output 28 synchronously with a predetermined 
one of the clock signals, or asynchronously with both clock signals. For 
example, where a half full flag is to transition from an inactive to an 
active state, glitch-free status signal 20' will be active, glitch-free 
de-assertion status signal 22' will be low, and flag output 28 will 
transition from inactive to active status synchronously with the write 
clock. In contrast, where the half full flag output is to transition from 
active to inactive status, signal 20' will be low, signal 22' will be 
high, and the flag output will transition synchronously with read clock 
12a. Transition of the almost full flag, in both directions, will be 
similar to that described with respect to the half full flag. 
The almost empty flag will transition from inactive to active status 
synchronously with the read clock and will transition from active to 
inactive status synchronously with the write clock. The full flag will 
transition from inactive to active status with the write clock, and back 
to inactive status with the read clock, (although in this case the 
inactive status will be indicated on the next write clock). It will be 
noted that no prediction is necessary in full flag transition from active 
to inactive status inasmuch as the read operation is the only operation 
which may occur when the memory device is full. Similarly, an empty flag 
will transition from inactive to active status synchronously with the read 
clock, and back to inactive status with the write clock (inactive status 
will be indicated on the next read clock). The only operation which is 
allowed to occur when the memory device is empty is a write operation, and 
so there is no need for prediction of a transition from an active empty 
status flag to an inactive empty status flag. 
Referring now to FIGS. 2A and 2B, an illustrative comparison is made 
between the half-full status flag output of the invented apparatus and the 
half-full status flag output of an apparatus illustrative of the prior 
art. Toward this end, FIG. 2A shows a half full status flag output signal 
waveform 34 as it relates to a write clock signal waveform 30 (WCLK) and a 
read clock signal waveform 32 (RCLK). The FIFO array is initially 
considered at approximately the time of transition between active and 
inactive status of the status flag. FIG. 2B shows half full status flag 
output from a prior art FIFO flag generator wherein the read and write 
clocks are indicated by primed reference designators corresponding with 
those of FIG. 2A. The reader will note that the read and write clocks are 
identical in FIGS. 2A and 2B so as to make clear the difference between 
the invented apparatus and method (shown in FIG. 2A), and the prior art 
apparatus and method (shown in FIG. 2B). 
Considering the signal waveform timing illustrated in FIG. 2A, those 
skilled in the art will appreciate that there is a minimum delay from a 
rising edge of RCLK to a rising edge of WCLK which will ensure that the 
FIFO's full flag will become accurate no later than the end of the current 
write cycle of the FIFO. Similarly, there is a minimum delay from a rising 
edge of WCLK to a rising edge of RCLK which will ensure that the FIFO's 
empty flag will become accurate no later than the end of the current read 
cycle of the FIFO. These design considerations influence the design goals 
and achievements embodied by the invented method and apparatus. 
The importance of improving dynamic accuracy is shown graphically in FIGS. 
2A and 2B, with the half full flag (HF) taken as an example. It will be 
appreciated that WCLK potentially causes the asynchronous half full flag 
to be asserted, and that RCLK potentially causes the flag to be 
de-asserted. Illustrative independent operations of such separate WCLK and 
RCLK clock signals are shown identically in FIGS. 2A and 2B. With the 
prior art shown in FIG. 2B, the HF flag is unavailable for access by the 
user until a time later than that of the invented method and apparatus the 
timing of which is illustrated in FIG. 2A. Also, a false positive 
indication of half-fullness (the third HF pulse from the left in FIG. 2B, 
which pulse is labelled 34c') is avoided with the invented method and 
apparatus the timing of which is illustrated in FIG. 2A. Thus, among the 
advantages of the present invention are shorter flag access times and 
fewer false-positive status flag indications. 
Considering the half full status flag to transition from inactive to active 
status at an address count m, and assuming that the graph in FIG. 2A 
illustrates at 30a, a write clock pulse which signifies a write operation 
which brings the FIFO's contents from m-2 data items to m-1 data items, it 
is to be noted that dashed line 36 represents the time t at which point an 
assertion prediction is made. With the next write clock pulse 30b 
(assuming no intermediate read clock pulse) the half full status flag 
changes to an active state under direction of the state machine. Such 
transition is signified by pulse 34a in FIG. 2A. As will be appreciated 
from the drawing, the illustrated flag is leading-edge-triggered, the half 
full flag beginning its transition to active status at the time indicated 
by the dashed line 38 which is synchronous with the write clock signal 30. 
Upon a read operation, as indicated by pulse 32a, the edge of which is 
indicated at 40, the half full flag will change from active to inactive 
status, the contents of the FIFO having been decremented by one. This 
decrement of the address count will be appreciated to correspond to an 
incremental change in the read address pointer, and correspondingly to a 
decrease in the difference between the read address pointer and the write 
address pointer. The next write clock pulse 30c again results in a change 
of the half full flag to active status, as indicated at 34b, such status 
change occurring synchronously with the write clock. 
Upon the occurrence of read clock pulse 32b, the half full flag transitions 
to inactive status again as indicated at 44. The address count thus is 
again at m-1. With the next read clock pulse 32c, the address count 
decreases to m-2, then increases again to m-1 upon write clock pulse 30d. 
As indicated at 46 and 48, the read clock pulse precedes the write clock 
pulse. Read clock pulse 32d again decreases the address count to m-2. Half 
full flag assertion thus occurs at 38 and 42, and de-assertion occurs at 
40 and 44. 
In contrast, prior art memory devices have been characterized by excessive 
delay in assertion of the half full flag, such delay being made apparent 
by the delay in time between the memory device becoming half full which 
occurs at time 38', and the assertion of the half full flag 34a' which may 
not become active until after a subsequent read clock pulse 32a'. This 
results in inaccurate half full status flag information. Similarly, where 
the read clock and write clock occur in very close timing relation with 
one another, it is possible that a half full status flag would become 
active as indicated at 34c' even when the FIFO has not become half full. 
As indicated, the read clock pulse which would index the read pointer may 
not be interpreted as quickly as the write clock pulse so as to give the 
appearance to the state machine of a momentary transition to half full 
status. This condition is obviated by the present invention by look-ahead, 
pipelined prediction logic which decreases the delay of clock pulses that 
might produce status flag changes. 
Turning now to FIG. 3, a representation of an actual FIFO memory capable of 
containing 1024 data items is shown at 50, along with the corresponding 
addresses 52 and the half full status flag 56. In FIG. 3, the half full 
status flag is indicated as being active high, such active state being 
indicated by an H. The inactive, or low, state is indicated by an L. As 
will be appreciated, the transition between high and low occurs generally 
in the area indicated at 56a, such transition occurring upon a write 
operation which increases the content of the memory device from 512 data 
items to 513 data items. 
Proceeding with a description of the assertion and de-assertion prediction 
signals as they relate to the address content, it will be appreciated that 
the half flag de-assertion prediction logic is always active when the 
address count is below 511, and is always inactive when the address count 
is above 514. Correspondingly, the half flag assertion prediction logic is 
always inactive when the address count is below 511, and is always active 
when the address count is above 514. As the address count increments, and 
specifically as the address count transitions from 511.fwdarw.512, the 
half flag assertion prediction signal transitions from inactive to active 
status so as to predict a change in half full flag status with the next 
write clock pulse. 
The next write clock pulse, it will be appreciated, will index the address 
count from 512.fwdarw.513 (assuming there is no intervening read clock 
pulse). Once the assertion prediction signal has become active, as 
indicated at 62a, the half full flag will be controlled completely by the 
asynchronous state machine. The assertion and de-assertion prediction 
signals therefore are not used. Control will remain with the state machine 
until the status count exits the shaded (crosshatched) region into a 
low-count region indicated fragmentarily at 58 or into a high-count region 
indicated fragmentarily at 62. Upon entry to such regions 58 or 62, which 
in the illustrated embodiment where n=1024 will be understood respectively 
to represent a transition from 516.fwdarw.515 or from 511.fwdarw.510, the 
assertion prediction signal and de-assertion prediction signals again 
control. Such state machine exit transition boundaries are indicated at 64 
and 66. 
For half full status flag de-assertion, it will be appreciated that the 
de-assertion prediction signal will transition from inactive to active 
upon a read clock pulse which decrements the address count from 
514.fwdarw.513. Such transition is indicated at 62b. Again, at such point, 
the status flag output is placed entirely under the asychronous state 
machine control. Control remains with the state machine until the address 
count transitions from 514.fwdarw.515 or from 511.fwdarw.510. Those 
skilled in the art will appreciate that the shaded regions indicated by 
reverse-direction cross-hatching in FIG. 3 represent in the case of lower 
left to upper right lining the narrower region of interest in entering, or 
activating, the state machine, and represent in the case of upper left to 
lower right lining the broader region of interest in exiting, or 
inactivating, the state machine. 
The main advantage or contribution of the present invention over current 
methods of status flag generation is much improved flag access times while 
simultaneously providing a significant increase in the dynamic accuracy of 
the flags. These advantages enable a user of a FIFO device more accurately 
to know how much data the FIFO contains. Given the fact that a FIFO may be 
shared by systems that operate with completely independent clock 
frequencies, the design of such flag logic to process these asynchronous 
transactions is not a trivial task. Conventional methods and apparatus for 
flag generation (discussed previously) avoid much of this complexity by 
sacrificing both flag access time and dynamic accuracy for simplicity. 
Summarizing briefly, the present invention operates on the following 
principles. If, for example, the half flag should become asserted when the 
FIFO contains m elements, the comparator would activate its assertion 
prediction signal to the state machine when the FIFO contains m-1 data 
items. From the state machine's point of view, when the half flag's 
assertion predictor is activated, it knows that on the next WCLK (assuming 
an RCLK does not occur first) it should assert the half flag. The 
situation is symmetrical with de-assertion of the half flag (utilizing 
RCLK and the de-assertion predictor). The programmable almost empty flag, 
half flag, and programmable almost full flag all operate in this manner. 
The empty and full flags operate in a similar fashion, but generation of 
these two flags is greatly simplified. The empty and full flags both 
utilize only assertion prediction signals. De-assertion prediction is not 
required, since becoming not empty and not full only requires a WCLK event 
(with an empty FIFO) and an RCLK event (with a full FIFO) respectively. 
FIG. 3 indicates in a more high-level way, how the invention works. In 
particular, the half flag is again taken as an example. For writing data 
into the FIFO (to assert the half full (HF) flag), entry is made into the 
(narrower) shaded region when the FIFO transitions from 511.fwdarw.512 
data items (the half flag will becomes asserted upon a next write clock 
without an intervening read clock). This initial transition into the 
shaded region was caused by the half flag assertion prediction input to 
the state machine becoming active when 512 elements are contained with the 
FIFO. Once entry is made into the shaded region, the state of the flag is 
completely controlled by the state machine (prediction signals are no 
longer necessary or useful, because at the flag transition point 
prediction becomes impossible). There are now two methods of exiting the 
(broader) shaded region, one is a transition from 511.fwdarw.510 elements 
within the FIFO, the other is a transition from 514.fwdarw.515. The 
example just described assertion of the half flag, although de-assertion 
of the half flag is completely symmetrical. For deassertion, entry into 
the (narrower) shaded region would occur on a 514.fwdarw.513 transition 
(the half flag has just become de-asserted). The exit points are the same 
as the assertion case previously described. 
To reiterate, the state machine is dormant, or asleep, until it is awakened 
by the activation of either the assertion or deassertion flag prediction 
signal. Once this occurs, the state machine knows that the flag may 
transition on the next rising clock edge (depending on what the other 
clock is doing during this period). If the flag transition occurs, entry 
has been made into the shaded region (shown in FIG. 3). In this region, 
the flag state is completely controlled by the state machine (independent 
of the flag prediction signals, since at a flag transition point 
prediction is not possible). When the shaded region is exited (as 
discussed previously), the state machine again is in a sleep mode until a 
flag prediction signal is activated. 
Turning now to FIGS. 4A through 9, the apparatus of the invention made in 
accordance with a preferred detailed embodiment will be described. Those 
of skill in the art will appreciate that, in some cases, the logic sense 
of the signals is different between detailed logic diagrams in FIGS. 4A 
through 9 and corresponding signals illustrated in FIGS. 1 through 3, 
which in the interest of clarity treated all signals as being high-active. 
In aid of understanding the detailed logic diagrams, listed below are the 
signal names, or signatures, and a brief description of their 
significance: 
______________________________________ 
comp.sub.-- ef.sub.-- out 
glitch-free empty flag assertion predictor 
comp.sub.-- ef 
raw empty flag assertion predictor (from 
counter) 
comp.sub.-- ff 
raw full flag assertion predictor (from 
counter) 
comp.sub.-- ff.sub.-- out 
glitch-free full flag assertion predictor 
comp.sub.-- hf 
raw half flag assertion predictor 
comp.sub.-- hf.sub.-- out 
glitch-free comp.sub.-- hf 
comp.sub.-- hf.sub.-- r 
raw half flag de-assertion predictor 
comp.sub.-- hf.sub.-- r.sub.-- out 
glitch-free comp.sub.-- hf.sub.-- r 
comp.sub.-- pae 
raw almost empty assertion predictor 
comp.sub.-- pae.sub.-- out 
glitch-free comp.sub.-- pae 
comp.sub.-- pae.sub.-- r 
raw almost empty de-assertion predictor 
comp.sub.-- pae.sub.-- r.sub.-- out 
glitch-free almost empty de-assertion predictor 
comp.sub.-- paf 
raw almost full flag assertion predictor 
comp.sub.-- paf.sub.-- out 
glitch-free comp.sub.-- paf 
comp.sub.-- paf.sub.-- r 
raw almost full flag de-assertion predictor 
comp.sub.-- paf.sub.-- r.sub.-- out 
glitch-free comp.sub.-- paf.sub.-- r 
edge.sub.-- rclk2 
active high pulse of sufficient duration reliably 
to set or reset flip-flop 
edge.sub.-- rclk2.sub.-- n 
active low pulse of sufficient duration reliably 
to set or reset flip-flop 
edge.sub.-- rclk4.sub.-- n 
active low pulse of duration greater than the 
generation of FLAG.sub.-- rclk.sub.-- n plus the setup 
time of flip-flop 
edge.sub.-- wclk2.sub.-- n 
active low pulse of sufficient duration reliably 
to set or reset flip-flop 
edge.sub.-- wclk4.sub.-- n 
active low pulse of duration greater than the 
generation of FLAG.sub.-- wclk.sub.-- n plus the setup 
time of flip-flop 
ef.sub.-- n 
active low empty flag output 
ff.sub.-- n 
active low full flag output 
hf.sub.-- sy.sub.-- n 
active low half flag output (sync to uwclk) 
hf.sub.-- n 
active low half flag output (async) 
pae.sub.-- sy.sub.-- n 
active low almost empty flag output (sync to 
urclk) 
pae.sub.-- n 
active low almost empty flag output (async) 
paf.sub.-- syn.sub. -- n 
active low almost full flag output (sync to 
uwclk) 
paf.sub.-- n 
active low almost full flag output (async) 
rs.sub.-- n 
active low master reset 
rs active high version of master reset 
rt active high re-transmit request 
urclk rising edge of read clock, independent of the 
state of any enable signals 
uwclk rising edge of write clock, independent of the 
state of any enable signals, 
______________________________________ 
where "sync" is short for synchronized or synchronous and "async" is short 
for asynchronous, and where FLAG.sub.-- rclk.sub.-- n is the output of 
gates 178 (FIG. 6), 216 (FIG. 7), 256 (FIG. 8) and 284 (FIG. 9) and where 
FLAG.sub.-- wclk.sub.-- n is the output of gates 150 (FIG. 5), 176 (FIG. 
6), 218 (FIG. 7) and 258 (FIG. 8), as will become clear from the following 
discussion. 
FIGS. 4A and 4B collectively illustrate, in more detail, the 
glitch-suppression logic or circuitry 24 shown in FIG. 1. 
Glitch-suppression logic 24 preferably includes an OR gate 66 that 
disjunctively combines rs and rt to produce a signal that becomes one of 
the set inputs (rs.sub.-- s) of set-reset (S-R) flip-flops 68, 70. Those 
skilled in the art will appreciate that the behavior of all of the 
so-designated S-R flip flops in FIGS. 4A through 9 may be described by the 
following define statements: 
EQU set.sub.-- in or rs.sub.-- s=1: out.sub.-- n=0 (1); 
EQU reset.sub.-- in or rs.sub.-- r=1: out.sub.-- n=1 (2), 
and that the set function has priority over the reset function in the event 
of concurrent, conflicting inputs. 
Accordingly, the output (out.sub.-- n) of flip-flop 68 is high (inactive) 
if edge.sub.-- rclk2.sub.-- n (inverted at 72) is low, and the output 
(out.sub.-- n) of flip-flop 68 is low (active) if edge.sub.-- wckl4.sub.-- 
n (inverted at 74) is low or rs or rt is high. The output (out.sub.-- n) 
may be seen to be ORd at 76 with comp.sub.-- pae.sub.-- r to determine the 
comp.sub.-- pae.sub.-- r.sub.-- out output of LATCH 78. It also may be 
seen that the complement of the out.sub.-- n output of flip-flop 68 
(produced by inverter 80) may be seen to be ANDed at 82, 84, 86 with 
comp.sub.-- ff, comp.sub.-- paf and comp.sub.-- hf to determine, 
respectively, the comp.sub.-- ff.sub.-- out, comp.sub.-- paf.sub.-- out 
and comp.sub.-- hf.sub.-- out outputs of LATCHes 88, 90 and 92. The 
LATCHes so-labelled in FIGS. 4A and 4B will be understood to behave in 
accordance with the following define statements: 
EQU clk=1: out=in (3); 
EQU clk=0; out=latched version of in (4), 
i.e. the outputs of the LATCHes follow their inputs while the elk inputs 
are high and are latched upon positive.fwdarw.negative transitions of the 
elk inputs. 
Referring still collectively to FIGS. 4A and 4B, it also may be seen that 
the output out.sub.-- n of S-R flip-flop 70 is high (inactive) if 
edge.sub.-- wclk2.sub.-- n (inverted at 94) is low, and the output 
(out.sub.-- n) of flip-flop 70 is low (active) if edge.sub.-- rclk4.sub.-- 
n (inverted at 96) is low or rs or rt is high. The output (out.sub.-- n) 
may be seen to be ORd at 98 and 100 with comp.sub.-- hf.sub.-- r and 
comp.sub.-- paf.sub.-- r, respectively, to determine respectively the 
comp.sub.-- hf.sub.-- r.sub.-- out and comp.sub.-- paf.sub.-- r.sub.-- out 
outputs of LATCHes 102 and 104. It also may be seen that the complement of 
the out.sub.-- n output of flip-flop 70 (produced by inverter 106) is 
ANDed at 108 and 110 with comp.sub.-- ef and comp.sub.-- pae to determine, 
respectively, the comp.sub.-- ef.sub.-- out and comp.sub.-- pae.sub.-- out 
outputs of LATCHes 112 and 114. 
DELAYs 116, 118, 120, 122, 124, 126, 128, 130, 132 (see FIGS. 4A, 4B and 6) 
may be tapped to produce a delayed version of the corresponding inputs 
comp.sub.-- hf, comp.sub.-- paf, comp.sub.-- ff, comp.sub.-- pae.sub.-- r, 
comp.sub.-- pae, comp.sub.-- ef, comp.sub.-- paf.sub.-- r, comp.sub.-- 
hf.sub.-- r, pae.sub.-- n, as may be needed in a particular integrated 
circuit implementation. It is time critical that S-R flip-flops 68, 70 
.(FIGS. 4A and 4B) generate outputs that can disable the inputs to latches 
78, 88, 90, 92, 102, 104, 12, 114 before raw flag prediction signals 
arrive from the comparator. Thus, these delays may be needed to achieve 
the required timing by slowing down the raw flag prediction signals. Those 
of skill in the art will appreciate that in the preferred embodiment of 
the invention described and illustrated herein no delay is needed, but 
that such are shown for completeness of the disclosure. Such delays may be 
implemented in any known way and typically might be implemented as 
variable delays produced by altering a mask to tap a delay quantum of the 
desired number of nanoseconds (ns) or fractions thereof. 
Turning now to FIG. 5, it may be seen that edge.sub.-- wclk4.sub.-- n 
inverted through inverters 134 and 136 respectively clocks a REGister 138 
and sets an S-R flip-flop 140. REGisters so-labelled in FIG. 5 through 9 
will be understood to behave in accordance with the following define 
statement: 
EQU reset=1: out=0 (5). 
edge.sub.-- wclk4.sub.-- n also is inputted to one OR gate of an OR/NAND 
gate indicated at 142. Finally, edge.sub.-- wclk4.sub.-- n is one input to 
an AND gate 144 that drives a D flip-flop 146. It will be understood that 
D flip-flop 146 behaves in accordance with the following define 
statements: 
EQU rst=1: ef.sub.-- n=1 (6); 
EQU set=1: ef.sub.-- n=0 (7). 
The input (in) of REGister 138 is connected to the output (out.sub.-- n) of 
S-R flip-flop 140, as shown. The low-active reset input (resetn) of 
REGister 138 is driven by rs.sub.-- n, which is inverted via an inverter 
148 to drive the rs.sub.-- r input to S-R flip-flop 140, the rs.sub.-- s 
input of which is grounded, as indicated. The low-active output (outf) of 
REGister 138 is input to a NAND gate 150, the other input of which is 
driven by the inverted (inverter 152) output (out.sub.-- n) from S-R 
flip-flop 140. The other NAND input of NAND/OR gate 142 is comp.sub.-- 
ef.sub.-- out ORd with the output of NAND gate 150. The output of OR/NAND 
gate 142 is ORd at 152 with edge.sub.-- rclk2.sub.-- n and the output of 
OR gate 152 is NORd with the output of inverter 136 to drive the 
reset.sub.-- in input of S-R flip-flop 140. 
Referring still to FIG. 5, the inverted output of S-R flip-flop 140 becomes 
one input to the NAND gate of a second OR/NAND gate indicated at 154, the 
other input of which is the output of OR/NAND gate 142 ORd with 
edge.sub.-- rclk2.sub.-- n. The output of OR/NAND gate 154 is ANDed with 
edge.sub.-- wclk4.sub.-- n to become the set input to D flip-flop 146. The 
(d) input to D flip-flop 146 is tied high, as indicated by the upwardly 
directed arrow, and the clock input (ck) is driven by urclk. D flip-flop 
146 is reset by rt. The output of S-R flip-flop 146 is ef.sub.-- n, the 
empty flag indicator. 
Turning next to FIG. 6, rs.sub.-- n may be seen to be inverted by inverter 
156, the output of which is fed to the reset inputs of REGisters 158, 160 
and to one input of an OR gate 162. REGisters 158, 160 are clocked (elk) 
by the outputs of inverters 164, 166 which invert, respectively, 
edge.sub.-- wclk4.sub.-- n and edge.sub.-- rclk.sub.-- n. The inputs to 
REGisters 158, 160 are both pae.sub.-- n, as indicated, which signal is 
optionally delayed at DELAY 132, which optionally delayed signal is 
inverted at 168. The inverted version of pae.sub.-- n is ORd at 170 with 
edge.sub.-- wclk4.sub.-- n and the OR gate output becomes a first input to 
the NAND gate of OR/NAND gates indicated at 172, 174. The output (out) of 
REGister 158 is NANDed at 176 with pae.sub.-- n to produce a signal that 
becomes an OR gate input to the OR/NAND gate 172 the other OR gate input 
to which is comp.sub.-- pae. 
The output (out) of REGister 160 is ORd at 178 with pae.sub.-- n to produce 
a signal that becomes a first OR gate input to an OR/NAND gate indicated 
at 180. The corresponding OR gate input to OR/NAND gate 180 is derived at 
182 by inverting the comp.sub.-- pae.sub.-- r signal. The output of 
OR/NAND gate 180 is input, along with edge.sub.-- wclk2.sub.-- n, to the 
other OR gate input to OR/NAND gate 174. The output of optionally delayed 
pae.sub.-- n is ORd at 184 with edge.sub.-- rclk4.sub.-- n and the OR gate 
output effectively is inputted to the other NAND gate of OR/NAND gate 180. 
The output of OR gate 184 also is inputted to the NAND gate of an OR/NAND 
gate indicated at 186. The other NAND gate input is the logical OR of the 
output of OR/NAND gate 172 and edge.sub.-- rclk2.sub.-- n. 
The output of OR/NAND gate 186 used to set (set.sub.-- in) an S-R flip-flop 
188, which is reset (reset.sub.-- in) by the signal output by OR/NAND gate 
174 or which alternatively is reset (rs.sub.-- r) by the inverted 
rs.sub.-- n signal. The inverted rs.sub.-- n signal output by inverter 156 
is ORd at 162 with the output of OR/NAND gate 186, as shown, to produce 
one of two reset inputs (reset) to a two-stage D-synchronizer (D-SYNC) 
190. The other reset input (reset) to D-SYNC 190 is simply rs.sub.-- n 
inverted at 156. So-labelled D-SYNCs in FIGS. 6 through 9 will be 
understood to behave in accordance with the following define statement: 
EQU reset=1: q=0 (8). 
The set input (rs.sub.-- s) of S-R flip-flop 188 is tied low, as indicated, 
and its output (out.sub.-- n) is pae.sub.-- n, described immediately 
above. pae.sub.-- n also is the (d) input to D-SYNC 190, which is clocked 
(ck) by urclk. The output of D-SYNC 190 is pae.sub.-- sy.sub.-- n, the 
low-active, synchronized almost empty flag output of invented apparatus 
10. 
Referring briefly and collectively to FIGS. 7 and 8, those of skill in the 
arts will appreciate that there are significant topologic similarities 
among the half empty flag generation logic illustrated in FIG. 6 and 
described immediately above, the full status flag generation logic 
illustrated in FIG. 7 and the almost full flag generation logic 
illustrated in FIG. 8. These topological similarities will be appreciated 
to be a result of the fact that the requirements of such logic are similar 
in that all require an understanding of the asserted and de-asserted 
predictive possibilities based upon write and read pointer differences, 
impending asynchronous read and/or write clock activity and 
synchronization with a defined read or write clock edge. 
Referring specifically now to FIG. 7, rs.sub.-- n may be seen to be fed to 
the reset inputs (resetn) of REGisters 198, 200 and to be inverted at 202. 
REGisters 198, 200 are clocked (clk) by the outputs of inverters 204, 206 
which invert, respectively, edge.sub.-- rclk4.sub.-- n and edge.sub.-- 
wclk4.sub.-- n (which clocking will be appreciated to be the opposite of 
that of corresponding REGisters 158, 160 of FIG: 6). The inputs (in) to 
REGisters 198, 200 are both hf.sub.-- n, as indicated, which signal is 
optionally DELAYed as shown and as understood, which optionally delayed 
signal is inverted at 208. The inverted version of hf.sub.-- n is ORd at 
210 with edge.sub.-- rclk4.sub.-- n and the OR gate output becomes a first 
input to the NAND gate of OR/NAND gates indicated at 212, 214. The output 
(out) of REGister 198 is NANDed at 216 with hf.sub.-- n to produce a 
signal that becomes an OR gate input to the OR/NAND gate 212, the other OR 
gate input to which is comp.sub.-- hf. 
The output (out) of REGister 200 is ORd at 218 with hf.sub.-- n to produce 
a signal that becomes a first OR gate input to an OR/NAND gate indicated 
at 220. The corresponding OR gate input to OR/NAND gate 220 is derived at 
222 by inverting the comp.sub.-- hf.sub.-- r signal. The output of OR/NAND 
gate 220 is inputted, along with edger.sub.-- clk2.sub.-- n (contrast 
corresponding edge.sub.-- wclk2.sub.-- n input of FIG. 6), to the other OR 
gate input to OR/NAND gate 214. The output of optionally delayed hf.sub.-- 
n is ORd at 224 with edge.sub.-- wclk4.sub.-- n (contrast the 
corresponding edge.sub.-- rclk4.sub.-- n signal used in FIG. 6) and the OR 
gate output effectively is input to the other NAND gate of OR/NAND gate 
220. The output of OR gate 224 also effectively is input to the NAND gate 
of an OR/NAND gate indicated at 226. The other NAND gate input is the 
logical OR of the output of OR/NAND gate 212 and edge.sub.-- wclk2.sub.-- 
n (contrast the corresponding edge.sub. -- rclk2.sub.-- n OR input in FIG. 
6). 
The output of OR/NAND gate 216 used to set (set.sub.-- in) an S-R flip-flop 
218, which is reset (reset.sub.-- in) by the signal output by OR/NAND gate 
214 or which alternatively is reset (rs.sub.-- r) by the inverted 
rs.sub.-- n signal. The inverted rs.sub.-- n signal outputted by inverter 
202 also is used to set a D-SYNC 230. One reset (rst) input to D-SYNC 230 
is the output of OR/NAND gate 216, and the other reset input (rst2) to 
D-SYNC 230 is simply tied low. The reset input (rs.sub.-- s) of S-R 
flip-flop 218 is tied low, as indicated, and its output (out.sub.-- n) is 
hf.sub.-- n, described immediately above. hf.sub.-- n also is the (d) 
input to D-SYNC 230, which is docked (ck) by uwclk (contrast the 
corresponding urclk clock input of FIG. 6). The output of D-SYNC 230 is 
hf.sub.-- sy.sub.-- n, the low-active, synchronized half full flag output 
of invented apparatus 10. 
Turning next to FIG. 8, rs.sub.-- n may be seen to be fed to the reset 
inputs (resetn) of REGisters 238, 240 and to be inverted at 242. REGisters 
238, 240 are clocked (elk) by the outputs of inverters 244, 246 which 
invert, respectively, edge.sub.-- rclk4.sub.-- n and edge.sub.-- 
wclk4.sub.-- n. The inputs (in) to REGisters 238, 240 are both paf.sub.-- 
n, as indicated, which signal is optionally DELAYed as shown and as 
understood, which optionally delayed signal is inverted at 248. The 
inverted version of paf.sub.-- n is ORd at 250 with edge.sub.-- 
rclk4.sub.-- n and the OR gate output becomes a first input to the NAND 
gate of OR/NAND gates indicated at 252, 254. The output (out) of REGister 
238 is NANDed at 256 with paf.sub.-- n to produce a signal that becomes an 
OR gate input to the OR/NAND gate 252 the other OR gate input to which is 
comp.sub.-- paf. 
The output (out) of REGister 240 is ORd at 258 with paf.sub.-- n to produce 
a signal that becomes a first OR gate input to an OR/NAND gate indicated 
at 260. The corresponding OR gate input to OR/NAND gate 260 is derived at 
262 by inverting the comp.sub.-- paf.sub.-- r signal. The output of 
OR/NAND gate 260 is input, along with edge.sub.-- rclk2.sub.-- n, to the 
other OR gate input to OR/NAND gate 254. The output of optionally delayed 
paf.sub.-- n is ORd at 264 with edge.sub.-- wclk4.sub.-- n and the OR gate 
output effectively is inputted to the other NAND gate of OR/NAND gate 260. 
The output of OR gate 264 also effectively is input to the NAND gate of an 
OR/NAND gate indicated at 266. The other NAND gate input is the logical OR 
of the output of OR/NAND gate 252 and edge.sub.-- wclk2.sub.-- n. 
The output of OR/NAND gate 266 used to set (set.sub.-- in) an S-R flip-flop 
268, which is reset (reset.sub.-- in) by the signal output by OR/NAND gate 
254 or which alternatively is reset (rs.sub.-- r) by the inverted 
rs.sub.-- n signal. The inverted rs.sub.-- n signal output by inverter 242 
also is used to set a D-SYNC 270. One reset (rst) input to D-SYNC 270 is 
the output of OR/NAND gate 256, and the other reset input (rst2) to D-SYNC 
270 is simply tied low. The reset input (rs.sub.-- s) of S-R flip-flop 268 
is tied low, as indicated, and its output (out.sub.-- n) is paf.sub.-- n, 
described immediately above. pafn also is the (d) input to D-SYNC 270, 
which is clocked (ck) by uwclk. The output of D-SYNC 270 is paf.sub.-- 
sy.sub.-- n, the low-active, synchronized almost full flag output of 
invented apparatus 10. 
Referring finally to FIG. 9, the full flag logic of apparatus 10 made in 
accordance with a preferred embodiment of the invention will be described. 
A REGister 272 is reset (resetn) upon the (low-active) assertion of 
rs.sub.-- n, and an S-R flip-flop 274 is reset (rs.sub.-- r) upon the 
de-assertion thereof, via an inverter 276. The output (outn) of S-R 
flip-flop 274 is inverted at 278 and the inverted output is fed back to 
the input (in) of REGister 272. REGister 272 is docked by edge.sub.-- 
rclk.sub.-- n, as such is inverted via an inverter 280. With one of its 
set inputs (rs.sub.-- s) being tied low, as indicated, S-R flip-flop 274 
is set at its set.sub.-- in input terminal by edge.sub.-- rclk.sub.-- n, 
as such is inverted via another inverter 282. Those of skill in the art 
will appreciate that, within the spirit and scope of the invention, 
duplicate inverter functions such as those of inverters 280 and 282 may be 
combined, such that edge.sub.-- rclk.sub.-- n need be inverted only once 
and fanned out to all receiving gates such as REGister 272 and S-R 
flip-flop 274. Those skilled in the art will appreciate that such 
combinations have possibly adverse timing and fanout impacts that would 
have to be comprehended in order to accomplish the important timing 
requirements of the present invention. 
The output of inverter 278 is NANDed at 284 with the output (out) of 
REGister 272 to produce one input to a first OR gate of an OR/NAND gate 
indicated at 286. The other input of such first OR gate is comp.sub.-- ff, 
as shown. The second OR gate of OR/NAND gate 286 has only edge.sub.-- 
rclk.sub.-- n as its input. The output of OR/NAND gate 286 is ORd at 288 
with edge.sub.-- wclk2.sub.-- n and input along with the output of 
inverter 282 to a NOR gate 290 the output of which resets (reset.sub.-- 
in) S-R flip-flop 274. The output of inverter 278 also is the sole input 
to an OR gate of an OR/NAND gate indicated at 292 the other OR gate of 
which ORs the output of OR/NAND gate 286 and edge.sub.-- wclk2.sub.-- n. 
The output of OR/NAND gate 292 is ANDed at 294 with edge.sub.-- rclk.sub.-- 
n to produce a signal connected to the reset (rst) input of a D flip-flop 
296. The (d) input of D flip flop 296 is tied high, as shown, and the 
flip-flop is clocked by uwclk such that the ff.sub.-- n output will 
transition only in synchronous response to a FIFO write command. D 
flip-flop 296 initially is set (thus de-asserting low-active output if-n) 
upon the occurrence of either rs (master reset) or rt (retransmit), as 
they are ORd at 298. Accordingly, if a FIFO full pending status is 
indicated and a write clock occurs without an intervening read clock, then 
the FIFO full flag is asserted with the leading edge of such a write 
clock. 
The preferred method of the invention now may be understood, in view of the 
invented apparatus. For use in connection with a first-in first-out memory 
device (FIFO) having read and write address pointers capable of 
asynchronous indexing, the invented status flag generation method 
preferably includes 1) determining an indexed distance between the read 
and write address pointers, e.g. via read clock 12a, write clock 12b, read 
counter 14a, write counter 14b, read pointer 16a, write pointer 16b and 
comparator 18; 2) comparing such distance with predefined criteria for 
predicting a status condition of the memory device, e.g. also via 
comparator 18; 3) producing a corresponding predicted status signal for 
passage through circuitry, e.g. glitch suppression circuitry 24, which 
suppresses transient predicted status signals; and after suppression of 
transient status signals, 4) passing the predicted status signal to a 
state machine, e.g. asynchronous state machine 26, for output as a status 
flag in synchronous relation to a defined time base such as one of the 
read and write clock signals, the defined time base corresponding to the 
indexing of a selected one of the read and write address pointers. 
It will be appreciated that the distance between the read and write address 
pointer represents the quantitative content of the memory device, such 
content being compared with predefined criteria which represent a 
quantitative content of the memory device at which point a status flag is 
to change, as described above. Preferably, the predefined criteria 
represent a memory content which is a predetermined distance, e.g. one, as 
described above for the half full status flag, from the quantitative 
content at which a status flag is to change. In other words, the 
predefined criteria preferably represent an address count which is one 
address away from an address count at which a status flag is to change. 
It will be appreciated that the address count at which a flag is to change, 
in accordance with the preferred method, is approachable to increment only 
from both above and below, with the predefined criteria representing a 
difference from the address count of a predetermined amount. Of course, 
such a status flag output is changed in synchronous relation to a defined 
time base, provided that a second time base is not pulsed. In other words, 
such status flag output changes are conditioned upon the occurrence of a 
pulse in a defined time base, e.g. the write clock, and upon the 
non-occurrence of an intervening pulse in a second time base, e.g. the 
read clock, as described in detail above by reference to the preferred 
embodiment of apparatus 10 and the exemplary half full status flag. 
An alternative way of describing the preferred method of the invention 
follows. For use in the generation of a status flag in a first-in 
first-out memory device which includes a read address pointer indexed by a 
read clock and a write address pointer indexed by a write clock, such 
alternative preferred method includes 1) comparing the read address 
pointer to the write address pointer to determine an address count 
representing the quantitative content of the memory device, e.g. via. read 
counter 14a, write counter 14b, read pointer 16a, write pointer 16b and 
comparator 18; and where the status flag is inactive, 2) comparing the 
address count with a predefined assertion predictor value, equality of the 
assertion predictor value and the address count predicting status flag 
assertion upon a chosen subsequent pulse of a first predetermined clock, 
e.g. also via comparator 18. 
The alternative preferred method preferably further includes upon 
predicting assertion of the status flag, 3) producing a status flag 
assertion signal for passage through circuitry, e.g. glitch suppression 
circuitry 24, which suppresses transient assertion status signals to a 
state machine, e.g. asynchronous state machine 26, for assertion of the 
status flag synchronously with the first predetermined clock; where the 
status flag is active, similarly 4) comparing the address count with a 
predefined de-assertion predictor value, equality of the de-assertion 
predictor value and the address count predicting status flag de-assertion 
upon a chosen subsequent pulse of a second predetermined clock; and upon 
predicting de-assertion of the status flag, 5) producing a status flag 
de-assertion signal for passage through circuitry which suppresses 
transient de-assertion status signals to a state machine for de-assertion 
of the status flag synchronously with the second predetermined clock. 
Preferably, the distance between the read and write address point 
represents the quantitative content of the memory device, such content 
being compared with predefined criteria which represent a quantitative 
content of the memory device at which point a status flag is to change. 
More preferably, the predefined criteria represents a memory content which 
is a predetermined distance from the quantitative content at which a 
status flag is to change, as described in detail above with reference to 
apparatus 10 in its preferred embodiment. 
Those of skill in the art will appreciate that markedly improved dynamic 
resolution is achieved by the present invention, yet at reasonable cost. 
Such is accomplished, in accordance with invention, by providing 
look-ahead logic that generates write or read clock synchronized FIFO flag 
output signals based upon early and glitch-free input predictor signals. 
Flag access times are reduced by a factor of two or three over 
conventional apparatus, and false indications of a FIFO's internal status 
are avoided altogether. Those of skill in the art will appreciate that the 
detailed circuit diagrams provided herein are believed amply to illustrate 
a workable embodiment that takes account of important timing and fanout 
considerations of IC implementations. Still, alternative circuit 
topologies, device types, schematic layouts and gate timings are 
contemplated and are within the spirit and scope of the invention. 
Accordingly, while the present invention has been shown and described with 
reference to the foregoing preferred method and apparatus, it will be 
apparent to those skilled in the art that other changes in form and detail 
may be made therein without departing from the spirit and scope of the 
invention as defined in the appended claims.