Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1999-10-07
2002-08-13
Gossage, Glenn (Department: 2187)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S052000, C711S109000, C711S156000, C365S221000, C365S189070, C377S034000
Reexamination Certificate
active
06434642
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a first in, first out (FIFO) memory system. More particularly, this invention relates to a method and structure for controlling an asynchronous FIFO memory system, and for determining the amount of data currently stored in a FIFO memory of the asynchronous FIFO memory system.
DESCRIPTION OF THE PRIOR ART
Data values sequentially written to a memory of a FIFO memory system are sequentially read from the memory in a first in, first out manner. Most FIFO memory systems are implemented with random access memories having two separate address counters. One address counter is used to maintain a current read address and the other counter is used to maintain a current write address. A FIFO memory system in which both the read address counter and the write address counter are clocked by the same clock signal is referred to as a “synchronous” FIFO memory system. In contrast, a FIFO memory system in which the read address counter and the write address counter are clocked by different clock signals is referred to as an “asynchronous” FIFO memory system.
In both synchronous and asynchronous FIFO systems, both the read and write address counters are circular counters that wrap around to an initial address after a last address is accessed. The read and write address counter output signals are either multiplexed to address a single-port random access memory (RAM), or they are separately provided to address different input ports of a multi-port RAM (e.g., a dual-port RAM). In either scheme, two extreme conditions, namely FIFO EMPTY and FIFO FULL, must be detected to ensure proper operation of the FIFO memory system. The FIFO EMPTY condition must be detected so that read operations from the memory can be prevented during the time that the memory is empty (since there are no valid data values present in the memory to read). The FIFO FULL condition must be detected so that write operations to the memory can be prevented during the time that the memory is full (since there is no memory space present in the memory to store any additional data values).
The contents of the read and write address counters are typically used to determine whether the memory is empty or full. To do this, the contents of the read and write address counters are compared. If the contents of the read address counter are identical to the contents of the write address counter, the memory is either empty or full. However, identifying that the contents of the read address counter and the write address counter are identical, by itself, does not distinguish whether the memory is empty or full. That is, the contents of the read address counter are identical to the contents of the write address counter when the memory is empty, and also when the memory is full.
One conventional method used to determine whether the memory is empty or full is to detect what type of operation caused the contents of the read and write address counters to match. If a read operation was performed (i.e., the read address counter was incremented), the resulting equality of the read and write address counters indicates a FIFO EMPTY condition. Conversely, if a write operation was performed (i.e., the write address counter was incremented), the resulting equality of the read and write address counters indicates a FIFO FULL condition. However, determining the type of operation that caused the contents of the read and write address counters to match can become complicated, particularly when the read and write address counters are clocked asynchronously.
Another prior art system subtracts the contents of the read and write address counters to determine when the read address is within one address of catching up to the write address and when the write address is within one address of catching up to the read address. Again, the subtraction circuitry for such a system is unreliable when the read and write address counters are clocked asynchronously.
Yet another prior art system, disclosed in co-owned U.S. Pat. No. 5,898,893, includes a direction circuit and a control circuit for generating FIFO FULL and FIFO EMPTY command signals. (U.S. Pat. No. 5,898,893 is hereby incorporated by reference.) The circular sequences of the write address and read address are divided into segments, and portions of the write address and read address are encoded to indicate the segments in which the current read address and current write address are located within their respective circular sequences. The direction circuit is connected to receive the encoded portions of the read and write addresses. In response, the direction circuit generates a DIRECTION signal that is set to a first state when the read address is in the segment prior to the segment of the write address, and is set to a second state when the write address is in the segment prior to the segment of the read address. The DIRECTION signal is used to determine whether the FIFO memory is empty or full when the read address equals the write address.
In addition to FIFO FULL and FIFO EMPTY conditions, it is also valuable for a FIFO memory system to generate status information regarding the amount of occupied memory at any point in time. For example, some users require status information to control burst read or write operations when the memory is half-full or half-empty. Such status information is relatively easy to obtain in synchronous systems by subtracting a currently-generated binary read address signal from a currently-generated binary write address signal. However, status information is much more difficult to obtain in asynchronous FIFO memory systems because of the danger of “glitches” (i.e., momentary erroneous values produced when an address counter increments from an initial value to a next-sequential value). Because the read and write clock signals are asynchronous, if the subtraction operation is clocked by the write clock signal, there is a danger that glitches in the read address can produce erroneous subtraction results. Conversely, if the subtraction operation is clocked by the read clock signal, there is a danger of glitches in the write address at the moment that the subtraction operation is performed.
Status information can be derived in an asynchronous system using the encoded portions of the write address and read address taught in co-owned U.S. Pat. No. 5,898,893, but this derived status information would be inaccurate and unreliable under certain conditions, and therefore not very useful to a user under those conditions.
It would therefore be desirable to have a reliable structure and method for detecting full and empty conditions of a FIFO that overcome the problems associated with the conventional structures, described above. It would also be desirable to have a reliable and accurate structure and method for determining the amount of data stored in asynchronous FIFO memories.
SUMMARY OF THE INVENTION
The present invention provides a reliable and robust structure and method for controlling an asynchronous FIFO memory system, and for accurately determining the amount of data stored in the FIFO memory system. Unlike prior art FIFO memory systems, the present invention sacrifices one memory location to simplify the full/empty determination process (i.e., a FULL control signal is generated when the current binary write address is one memory location behind the current binary read address, thereby preventing the write address counter from “catching up” to the read address counter). In addition, unlike prior art asynchronous FIFO memory systems, the present invention provides accurate information regarding the amount of data currently stored in the FIFO memory by synchronizing a current read address to the write clock, thereby providing reliable information that can be used to determine the current capacity of the FIFO memory without the danger of errors caused by glitches.
The present FIFO memory system includes a memory, a write address counter, a read address counter, a flag control circuit for generating FULL and EMPTY command signals, and an optional status
Alfke Peter H.
Camilleri Nicolas J.
Ebeling Christopher D.
Bever Patrick T.
Cartier Lois D.
Gossage Glenn
Xilinx , Inc.
LandOfFree
FIFO memory system and method with improved determination of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with FIFO memory system and method with improved determination of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FIFO memory system and method with improved determination of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960240