Static information storage and retrieval – Read/write circuit – Serial read/write
Reexamination Certificate
2001-06-30
2002-09-03
Dinh, Son T. (Department: 2824)
Static information storage and retrieval
Read/write circuit
Serial read/write
C365S189050, C365S235000, C710S057000
Reexamination Certificate
active
06445635
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to FIFO buffers generally, and more specifically, to a high speed asynchronous and programmable state machine configured to generate Almost Empty synchronous flags in a synchronous FIFO buffer.
2. Discussion of the Prior Art
A FIFO is a two-port memory based on dual-ported RAM cells. One port is used for writing data into the memory, while the other port is used for reading data out. A memory location in a FIFO is written to and is read from simultaneously, and a FIFO's first-in/first-out architecture or device, defines the method for storing and retrieving data from memory: data is written into a FIFO at one value at a time, and is read from the device in the same order as it was written in.
A FIFO doesn't require an address to access data, unlike RAM, or read-only memories (ROM). Another difference between a FIFO and a RAM, or ROM, is the data retention: in a RAM or ROM, data at a particular address remains unchanged until another value is written into the memory, and reading a data value out does not change the data value stored at a particular address. In a FIFO, data written into the memory is retained until it is read out. However, once the data word is read out, it no longer exists in the memory and cannot be accessed again. The exception is a FIFO that has a retransmit feature. The retransmission feature allows for a segment of a FIFO's memory to be read many times, although the data is written into the FIFO only once.
Due to the nature of their data retention, a FIFO (without a retransmission feature) has a state of “Data Fullness” associated with it. More specifically, a FIFO can be Empty, Almost Empty, partially Empty, partially Full, Almost Full, and Full. Thus, a FIFO requires additional signal lines, or flags, to indicate the state of its memory content. The number of data words a FIFO can store before it is Full depends on its size.
Because of a FIFO's unique features, like the lack of addressing requirements, FIFOs are useful in a class of applications with a serial streams of data. A FIFO provides data at the read port in the same order the data was presented at the write port, so that no additional circuitry is needed to implement a store-and-forward buffer. In the store-and-forward buffer, the data is written into the FIFO by a high-speed data source and is read out onto a lower-speed data bus. Thus, the FIFO converts the data rate from a high speed to a lower speed without any specific relationship between its input and output data rates. This means that a FIFO can serve as a link between two asynchronous interfaces.
While a random-access memories (RAM) can perform write and read operations only sequentially, a FIFO can do these operations simultaneously. Thus, a FIFO has twice the throughput of a conventional RAM. When its shift-in and shift-out signals are derived from independent frequency sources, a FIFO is operating asynchronously. If this is the case, the relationship between the output system clock and an output-ready signal is not known, either with respect to frequency, or with respect to phase.
However, when its shift-in and shift-out signals are derived from a common frequency source or clock, so that there is a precise, known relationship between them- the FIFO is by definition is in the synchronous mode. The key advantages of the synchronous FIFO over the asynchronous FIFO, are as follows:
(A) Registered interfaces at the input and output provide the simplest and fastest FIFO interfacing because all signals are synchronized to the rising edges of the read or write system clocks, which run continuously and are applied directly to the FIFO;
(B) Read and write operations are easily manipulated by external, synchronous read and write state machines, which in turn are controlled by the read and write system clocks; the flags are internally synchronized to their respective clocks, and external synchronizers are no longer needed;
(C) Read and write operations are controlled by enables, thereby eliminating any need for externally-generated read and write strobes; noise immunity is improved because the enable signals are sampled during the rising edge of the clock rather than in response to a level, thus increasing the reliability.
Accordingly, the following discussion is focused on synchronous FIFOs. Typical FIFO includes a 64 Kbit depth and 80 bits width, whereas the word is typically 80 bits long. One pointer, read or write, points to only one word. However, the “read out” or “write in” operations can be implemented in 4 modes: (a) read out 80-mode, (b) write in 80-mode (at each clock the whole word is read out or written in), (c) read out 40-mode, and (d) write in 40-mode (at each two clocks the whole word is read out or written in).
The number of words N retained in the FIFO memory is as follows:
N=W−R;
(1)
wherein W is the number of words written into the memory; and R is the number of words that are read out from the memory.
To prevent a “too fast” read out, a read enables clock is activated only after a first word is written into the FIFO memory buffer. Thus, the read out operation has to wait depending on the particular FIFO device between (2-4) clocks before the first word is read out. For the second word there is no such limitation. Each time a FIFO is completely read out, an Empty flag is generated by a state machine. An enabling signal delays the generation of an Empty flag, that is the change of the Empty flag state from “zero” to “one is delayed, by a waiting period between (2-4) clocks needed for the first word to be read out. This prevents reading out a word that has not been written in yet. The reading out of a word before the word has been written is called underflow. The time needed for the first word to come out from the FIFO buffer is called the fall through time.
For the complementary situation, when the writing in is done very fast, and the read out is very slow, a FIFO can be filled over capacity. This situation is called overflow. To prevent the overflow from happening, the Full flag is generated by the enabling Full signal to indicate that the writing into the FIFO should stop before the first word is read out.
The prior art “Almost” Empty flags were used to indicate that only few words X are left in the FIFO buffer. Thus, an offset X defining the word “Almost”, is also an “Almost Empty” threshold. The Almost Empty offset, or threshold, X is a user programmable offset. The user can set an offset value X anywhere between Full and Empty so that if the number of words N left in a FIFO is less than the threshold X, the read out is impossible, and an Almost Empty Flag is generated:
If ((
N=W−R
)≦
X
) then Almost_Empty
—
N=
0; (2)
wherein W is the number of words that are written in, R is the number of words that are read out, and Almost_Empty_N is a read pointer.
Complementary, if the programmable threshold for the amount of memory space (measured in words) left is Y, and if the actual memory space left in a FIFO is less than the threshold Y, the write in to the FIFO is restricted, and an Almost Full flag is generated:
If (((Depth−(
W−R
))≦
Y
) then Almost_Full
—
N=
0; (3)
wherein Depth is the depth of the FIFO, W is the number of words that are written in, R is the number of words that are read out, and Almost_Full_N is a write pointer.
The prior art implementation of the Almost Empty and Almost Full flag generators was done by using a traditional “adder approach”. In this traditional “adder approach”, the relationship (2) and /or (3) are implemented by using a write counter, a read counter, a program value offset register, a triple input carry look ahead adder/comparator (including a prediction algorithm to predict the next value), and an adder glitch filter (to minimize noise).
The problem with this prior art “adder approach” is that the triple input carry look ahead adder/comparator is too slow because in order to do additions a
Au Johnie
Chang Chia Jen
Mekara Parinda
Cypress Semiconductor Corporation
Dinh Son T.
Malorana, P.C. Christopher P.
LandOfFree
High speed asynchronous and programmable state machine for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed asynchronous and programmable state machine for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed asynchronous and programmable state machine for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2848074