Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-04-10
2003-06-24
Beausoliel, Robert (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S807000
Reexamination Certificate
active
06584584
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of digital communications and, more particularly, to error detection in a First-In-First-Out (FIFO) buffer.
2. Description of the Related Art
Digital electronics frequently require the communication of data between systems (or components thereof) of varying clock frequencies. In such a case, one system may have the ability to transmit data at a faster rate than another system is capable of receiving and processing. Also, various components may have clocks which originate from different sources or clock domains. Such clock signals may have the same frequencies, but have phase differences. In order to compensate for a disparity in transmission rates between sender and receiver, First-In-First-Out (FIFO) buffers are frequently used. A FIFO is a memory buffer which may store data and returns that stored data in the same order in which it was received. A FIFO typically comprises a fixed number of memory storage locations and circuitry for selecting read and write locations. By storing received data in a FIFO, a slower system may receive data at a rate which is higher than the rate at which it can process data, or data may be synchronized between different clock domains.
As is well known, because spikes, transients, glitches and other noise may exist within an electrical system, circuitry which reads from and writes to a FIFO may operate incorrectly. Consequently, a write to a full FIFO or a read from an empty FIFO may occur. Alternately, data may be read from or written to a wrong location in a FIFO. As a result, data which is assumed to be correct, but is actually erroneous, may be read from the FIFO.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a FIFO and method as described herein. Additional circuitry is included which enables a read from a FIFO to compare a value stored with the data to an expected value. When a mismatch between the stored value and expected value occurs, an error is detected. Advantageously, greater confidence may be had in the data which is read from a FIFO and the incidence of the transmission of erroneous data may be reduced.
Broadly speaking, a FIFO is contemplated. The FIFO includes a number of locations for storing data, each having an associated verification bit. Upon initialization, the verification bits are set to an alternating sequence of binary values. Also included is write circuitry which may write data to an entry of the FIFO. When data is written to an entry in the FIFO, the verification bit associated with that entry is toggled.
Also contemplated is a method. The method includes initializing a number of verification bits to an alternating sequence of binary values, where each verification bit corresponds to a storage location in a FIFO. Data may be written to a storage location of the FIFO and the corresponding verification bit toggled in response to that write.
Also contemplated is a FIFO which includes a number of verification bits and read circuitry. Each of the verification bits corresponds to a storage location. The read circuitry may read data from a storage location and the verification bit which corresponds to that storage location. The read circuitry includes an expected value bit which is compared to the verification bit on reads of data from the FIFO. Based on this comparison, errors may be detected. In addition, the expected value bit is toggled in response to reads. Though in the case where the FIFO has an even number of locations and it is the last entry which is read from the FIFO, the expected value is not toggled.
Finally, a method of error detection in a FIFO is contemplated. The method includes reading data and a corresponding verification bit from the FIFO, detecting an error in the FIFO by comparing the verification bit to an expected value bit, and toggling the expected value bit in response to a read and a first condition.
REFERENCES:
patent: 5469443 (1995-11-01), Saxena
patent: 5469449 (1995-11-01), Park
patent: 5469558 (1995-11-01), Lieberman et al.
patent: 5473756 (1995-12-01), Traylor
patent: 5513318 (1996-04-01), van de Goor et al.
patent: 5594743 (1997-01-01), Park
patent: 5813040 (1998-09-01), Rathke
patent: 5978935 (1999-11-01), Kim et al.
patent: 6088817 (2000-07-01), Haulin
patent: 6108802 (2000-08-01), Kim et al.
patent: 6145055 (2000-11-01), Fujimoto
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6442657 (2002-08-01), Fan et al.
patent: 6457067 (2002-09-01), Byers et al.
patent: 6480942 (2002-11-01), Hirairi
Beausoliel Robert
Chu Gabriel
Merkel Lawrence J.
Meyertons Hood Kivlin Kowert & Goetzel PC
OpenTV, Inc.
LandOfFree
Method and apparatus for detecting errors in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting errors in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting errors in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3090973