FIFO status indicator

Details FIFO status indicator FIFO status indicator

1997-01-15

2001-09-11

Nguyen, Madeleine (Department: 2622)

Pulse or digital communications

Synchronizers

Phase displacement, slip or jitter correction

C375S371000, C711S155000

Reexamination Certificate

active

06289065

ABSTRACT:

The invention relates to a status indicator which indicates the status (empty or full) of a First In, First Out (FIFO) register used in the transfer of data between two computers. The status indicator produces two outputs, which are synchronized to two different clocks.
BACKGROUND OF THE INVENTION
There are numerous different ways for a computer, named B, to transfer data to a computer, A. For example, if the two computers operate at different clock frequencies, they may use a FIFO (First In, First Out) buffer for the transfer. The FIFO is a holding station for the data while en route from computer B to computer A.
The FIFO may be viewed as a pipeline. Computer B, the sender, loads a sequence of data words, such as W
1
, followed by W
2
, then W
3
, and so on, into the pipeline. The pipeline holds the data words, and makes them available to computer A in serial fashion. Computer A, the receiver, reads data from the pipeline in the same order as they were loaded: W
1
first, W
2
next, and so on.
The fact that the order of reading the FIFO, by computer A, is the same as the order of loading, by computer B, gives rise to the name “First In, First Out.”
Two problems arise in such an approach. First, the FIFO has a limited capacity. The sender must not attempt to load data words into a fully loaded FIFO. Second, the receiver must not attempt to read data words from an empty FIFO.
There are several approaches to solving these problems. One is to divide the data into blocks which are exactly the size of the FIFO. For example, if the FIFO holds eight words, the sender fully loads the FIFO with a burst of eight data words. Then, the sender waits an appropriate length of time, while the receiver reads the eight words. Then the sender loads another eight words.
Plainly, this approach imposes a delay on the transfer.
Another approach will be explained with reference to FIG.
1
. Assume that a COUNTER produces an output which indicates the number of words presently contained in the FIFO. (
FIG. 1
indicates a 74-193 COUNTER, which is commercially available.)
Before any data words are loaded into the FIFO, the counter output is set to 0000, as indicated by the sketch in the upper left quadrant of FIG.
1
. Assume that the SENDER, B, places four words, W
1
through W
4
, into the FIFO, as indicated in the upper right quadrant of FIG.
1
.
As each word is loaded, the SENDER issues a pulse to the COUNT UP input of the COUNTER. Each pulse increments the COUNTER's output. The final output is 0100 (which equals 4 in decimal notation). The COUNTER's output of 0100 indicates that it contains four words.
Then the RECEIVER reads the words. As the RECEIVER reads each word, it issues a pulse to the COUNT DOWN input of the COUNTER, as shown in the lower left quadrant of the Figure. Each pulse decrements the COUNTER's output. The final output of the COUNTER is 0000, as indicated in the lower right quadrant, showing that the FIFO is empty.
A problem with this approach is that the SENDER cannot apply its COUNT UP pulse while the RECEIVER simultaneously applies its COUNT DOWN pulse. The COUNTER cannot respond to these contradictory pulses. Some arbitrator must be provided which prevents simultaneous COUNT UP and COUNT DOWN signals, thereby preventing the SENDER from loading data while the RECEIVER is reading data.
OBJECTS OF THE INVENTION
It is an object of the invention to provide improved data transfer between a sender and a receiver.
It is a further object of the invention to provide a system which monitors the status of a FIFO buffer used in data transfer, and produces full- and empty signals in accordance with the status of the FIFO.
SUMMARY OF THE INVENTION
In one form of the invention, a FIFO is used as a buffer to hold data while en route from a sender to a receiver. The sender and receiver are asynchronous. The invention monitors the status (empty or full) of each level of the FIFO, and issues a FIFO_FULL signal when all levels are full, and a FIFO_EMPTY signal when all levels are empty. Each signal is synchronous with one of the respective clocks of the sender or receiver.


REFERENCES:
patent: 4159532 (1979-06-01), Getson, Jr. et al.
patent: 4525849 (1985-06-01), Wolf
patent: 4596026 (1986-06-01), Cease et al.
patent: 4694426 (1987-09-01), Mason
patent: 4718074 (1988-01-01), Mannas et al.
patent: 4873703 (1989-10-01), Crandall et al.
patent: 4907186 (1990-03-01), Racey
patent: 4933901 (1990-06-01), Tai et al.
patent: 4965794 (1990-10-01), Smith
patent: 5134562 (1992-07-01), Hattori et al.
patent: 5311511 (1994-05-01), Reilly et al.
patent: 4012707 (1989-11-01), None
patent: 4801877 (1991-06-01), None
IBM Technical Disclosure Bulletin, vol. 15, No. 9, dated Feb., 1989, pp. 4722-4727.
IBM Technical Disclosure Bulletin, vol. 12, No. 11, dated Apr., 1970, pp. 2036-2037.

Affiliated with

Also associated with

Rating

FIFO status indicator 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 status indicator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FIFO status indicator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2522154