Abstract:
A Video Display FIFO includes a circular buffer and counters that allow the FIFO to properly recover from data alignment problems caused by FIFO underflow. A pair of counters store read and write pointers, which indicate the addresses of data read from and written into the buffer. Another counter stores a count of data in the buffer. Buffer underflow causes the count to go negative and the read pointer to advance ahead of the write pointer. Data written into the buffer while the total count is negative is not read out of the buffer. This allows alignment of the data to be restored.

Description:
BACKGROUND OF THE INVENTION 
     The invention relates to video display systems. The invention also relates to digital communications. 
     Data encoding is very important to the television industry, especially with the emergence of direct broadcast television systems. In a direct broadcast system, digital signals carrying near-perfect video images and audio waveforms are encoded according to the MPEG specification, transmitted to a satellite orbiting the earth, and relayed by the satellite on the Ku band to any home equipped with a small dish antenna and a receiver unit. Encoding is required to fit the massive amount of digital words describing the video images and audio waveforms within the Ku band. The encoded signals received by the dish antenna are decoded by the receiver unit and displayed on a television. At the heart of every receiver unit is an MPEG video decoder. 
     All current MPEG video decoders utilize the same memory system to reconstruct, store, copy, and display the video images. The memory system must handle up to three images simultaneously. The memory system must also buffer channel data for video and audio, and store On-Screen Display (OSD) bitmaps. That&#39;s an awful lot of tasks for a single memory system to perform. It is only through very sophisticated control that the video and audio is decoded, reconstructed, and displayed without interruption. However, 90-95% of available memory bandwidth is used. 
     In order to use precious memory bandwidth as efficiently as possible, the memory system includes small on-chip FIFO (First-In, First-Out) buffers for the various processing modules in the video decoder. Some FIFOs are filled up slowly and then write their data to external memory in a quick burst. Others receive bursty inputs from memory, and are then emptied at a slower, more constant rate. Among these FIFOs is a Video Display FIFO, which receives bursty inputs of data from a video retrieval module and outputs data at a constant and continuous rate to a video display device. 
     It is possible that errors may occasionally occur at the Video Display FIFO. In one instance, the data supplied to the Video Display FIFO is erroneous. Perhaps the data is accessed from a wrong address in the video retrieval module or the data from the video retrieval module is corrupted due to system noise. These types of errors are difficult to detect, so the erroneous data is displayed by the video display. Fortunately, this type of error almost never occurs in a properly designed system. Thus, there is no practical need to worry about it. 
     In another instance, the video retrieval module fills up the Video Display FIFO faster than it can be emptied. As a result, the Video Display FIFO overflows, good data is lost, and incomplete images are displayed. Fortunately, overflow of the Video Display FIFO can be detected early and prevented before data is lost. Practically speaking, overflow isn&#39;t an issue either. 
     In yet another instance, the Video Display FIFO becomes starved for data because the video retrieval module does not retrieve or generate data fast enough to supply the demand from the display device. Underflow occurs. This is a more realistic problem, and can occur quite early due to other systems and dataflow problems. Underflow can happen quite easily. If the underflow is not corrected, erroneous data is displayed during the underflow. Moreover, the insertion of erroneous data causes the image to shift. The Video Display FIFO has no &#34;knowledge&#34; of what data should appear on the display device and where that data should appear. Position of the data on the display device is determined solely by the time at which the data is read out from the Video Display FIFO. Since the timing is affected by the erroneous data read out during underflow, this &#34;extra&#34; data shifts the remainder of the image to the right. Compare the &#34;good&#34; image in FIG. 1a to the shifted image in FIG. 1b. 
     SUMMARY OF THE INVENTION 
     The problems caused by underflow of the Video Display FIFO are overcome by a method of writing and reading elements into and out of a buffer in accordance with the present invention. According to one broad aspect of the invention, the method comprises the steps of keeping track of a number of erroneous reads; and not reading a corresponding number of elements written into the buffer following the erroneous reads. 
     According to another aspect of the present invention, a video display FIFO comprises a buffer; means for keeping track of a number of erroneous reads from the buffer due to underflow; and means for reading from the buffer. A corresponding number of elements written into the buffer following the erroneous reads are not read out of the buffer by the reading means. 
     According to yet another aspect of the present invention, a digital video system comprises a video module; a display device; and a Video Display FIFO. The Video Display FIFO includes a buffer; a write pointer for indicating the addresses at which elements are written into the buffer from the video module; and a read pointer for indicating the addresses from which the elements are read out of the buffer to the display device. Unlike a conventional FIFO, the read pointer is allowed to advance past the write pointer when an erroneous read occurs. 
     The elements written into the buffer behind the read pointer are not read out of the buffer. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1a is an illustration of a video image provided by a digital video system; 
     FIG. 1b is an illustration of the video image resulting from an underflow of a Video Display FIFO in a digital video system according to the prior art; 
     FIG. 1c is an illustration of the video image resulting from an underflow of a Video Display FIFO in a digital video system according to the present invention; 
     FIG. 2 is a block diagram of the digital video system according to the present invention; 
     FIG. 3 is a block diagram of the Video Display FIFO, which forms a part of the digital video system shown in FIG. 2; 
     FIG. 4 is a timing diagram of read and write operations performed by the Video Display FIFO shown in FIG. 3; and 
     FIGS. 5a, 5b and 5c illustrate the read and write operations in the Video Display FIFO according to the timing diagram shown in FIG. 4. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 2 shows a digital video system 10 according to the present invention. A video retrieval module 12 retrieves and/or generates bursts of data representing frames of video images. The video retrieval module 12 can be an MPEG video decoder. A Video Display FIFO 14 receives the bursts of data from the video retrieval module 12, buffers the data and outputs the data at a constant and continuous rate. The data is read out to a display device 16 such as a video digital-to-analog converter (DAC) or an NTSC converter. The output rate of the Video Display FIFO 14 can be controlled internally (in which data is read out every n cycles) or externally (the data is read out upon request from another chip, such as the video DAC or NTSC converter). The Video Display FIFO 14 can be located on-chip with the video retrieval module 12 or it can be provided as an external memory device. 
     FIG. 3 shows the Video Display FIFO 14 in greater detail. 
     The Video Display FIFO 14 includes a circular buffer 18 for storing data from the video retrieval module 12. Data is written into the circular buffer 18 by supplying pulses on a WRITE line and by supplying data on a DATA --  IN line to the circular buffer 18. The pulses are received by a write-address incrementer 20, which increments its count (the count is hereinafter referred to as write pointer WRITE --  PTR), and a write-enable (WE) of the circular buffer 18. The circular buffer 18 stores the data placed on the DATA --  IN line at the address(es) indicated by the write pointer WRITE --  PTR. The pulses on the WRITE line are supplied by the video retrieval module 12. The write-address incrementer 20 is a modulo counter having a modulus equal to the size of the circular buffer 18. That is, the write-address incrementer 20 increments the write pointer WRITE --  PTR from zero to a number n-1 (where n indicates the size of the circular buffer 18) and back to zero. 
     New data is read out of the circular buffer 18 in response to a pulse on a READ line. The pulse on the READ line can be provided by either an internal source on the chip (in which case data is pushed out of the circular buffer 18) or from an external source (in which case data is pulled out of the circular buffer 18). The pulse on the READ line causes a read-address incrementer 22 to increment its count (the count is hereinafter referred to as read pointer READ --  PTR), and the circular buffer 18 to read out the data at the address(es) indicated by the read pointer READ --  PTR. The read-address incrementer 22 is also a modulo counter having a modulus equal to the size of the circular buffer 18. 
     A word counter 24 keeps a total count NUM --  COUNT of the number of words written into the circular buffer 18. The wordcounter 24 increments the total count NUM --  COUNT in response to a pulse on the WRITE line and decrements the total count in response to a pulse on the READ line. The total count NUM --  COUNT ranges between positive and negative values. 
     The circular buffer 18 can be a dual-port RAM. The incrementers 20 and 22 and counter 24 can be realized by hardware counters. In the alternative, the incrementers 20 and 22, counter 24 and even the circular buffer 18 itself can be eliminated, and their functions can be performed under software control of the video retrieval module 12. 
     Under normal operation, bursts of data are written into the circular buffer 18. Data is read out of the circular buffer 18 at a constant rate and the read pointer READ --  PTR never passes the write pointer WRITE --  PTR. That is, the FIFO never underflows. 
     Image retrieval problems can interrupt the normal operation and cause the circular buffer 18 to eventually become empty (i.e., the total count NUM --  COUNT equals zero, and the read pointer READ --  PTR equals the write pointer WRITE --  PTR). As the circular buffer 18 underflows, the read pointer READ --  PTR temporarily passes the write pointer WRITE --  PTR, the total count NUM --  COUNT becomes negative, and erroneous data is read out of the circular buffer 18. Erroneous data reads continue until image retrieval is restored and data is written into the circular buffer 18 again. At that point, circular buffer 18 fills up, the total count NUM --  COUNT increases to zero and then becomes positive, and the write pointer WRITE --  PTR catches up to, and passes, the read pointer READ --  PTR. Data written into the circular buffer 18 while the total count is negative is not read out of the circular buffer 18. Once the total count becomes positive, correct data is once again read out of the circular buffer 18. 
     An example of the operation of the Video Display FIFO 14 is illustrated in FIGS. 4, 5a, 5b and 5c. During a first set of normal write-read operations (see FIG. 5a), the write pointer WRITE --  PTR stays ahead of, or even with, the read pointer READ --  PTR. A burst of thirty pulses on the WRITE line is supplied to the write-address incrementer 20, circular buffer 18 and word counter 24, and data on the DATA --  IN line is supplied to the circular buffer 18. For each pulse, data on the DATA --  IN line is written into the circular buffer 18 at an address indicated by the write pointer WRITE --  PTR. At the end of the first write operation, data is stored in thirty consecutive addresses A1:A30 of the circular buffer 18, the total count NUM --  COUNT is thirty, and the write pointer WRITE --  PTR is ahead of the read pointer READ --  PTR by thirty. Then, twenty pulses on the READ line are supplied to the read-address incrementer 22 and word counter 24. The total count NUM --  COUNT is decremented to ten, the read pointer READ --  PTR is incremented to twenty, and the data at the first twenty addresses A1:A20 is read out from the circular buffer 18. 
     During a second set of read-write operations (see FIG. 5b), another twenty pulses on the READ line are supplied to the read-address incrementer 22 and word counter 24. The first ten of those pulses cause data at another ten addresses A21:A30 to be read out of the circular buffer 18, the total count NUM --  COUNT to be decremented to zero, and the read pointer READ --  PTR to pull even with the write pointer WRITE --  PTR. The circular buffer 18 is now empty, and a buffer empty signal M --  T is issued by the word counter 24. The next ten of those pulses on the READ line cause underflow to occur. The read pointer READ --  PTR moves ahead of the write pointer WRITE --  PTR, the total count NUM --  COUNT becomes negative, and data at the next ten addresses A31:A40 is read out of the circular buffer 18. The data at those ten addresses A31:A40 (which was left over from previous reads to the circular buffer 18) can be supplied to the display device even though it is old. In the alternative, the old data can be blanked out by the empty signal M --  T, or the old data can be replaced with &#34;neutral&#34; data (e.g. average values of adjacent pixels in the video image ) when the empty signal M --  T goes high. 
     The second write operation causes the write pointer WRITE --  PTR and total count NUM --  COUNT to be incremented thirty more times. At the end of the second write operation, data is written into another thirty consecutive addresses A31:A60 of the circular buffer 18, the total count NUM --  COUNT is increased from -10 to +20, and the write pointer WRITE --  PTR is advanced ahead of the read pointer READ --  PTR by twenty. 
     During a third read operation (see FIG. 5c), another twenty pulses on the READ line come in, and the correct data at the last twenty addresses A41:A60 is read out of the circular buffer 18. At the end of the third read operation, the word count NUM --  COUNT is equal to zero, the read and write pointers READ --  PTR and WRITE --  PTR are even, and the circular buffer 18 is once again empty. The data written into the ten addresses A31:A40 of the circular buffer 18 was not read out of the circular buffer 18. This is because those ten addresses were behind the read pointer READ --  PTR. The data written into the addresses A41:A60 was ahead of the read pointer READ --  PTR and, therefore, was read out of the circular buffer 18. 
     Thus disclosed is a video system that properly recovers from an underflow of its Video Display FIFO. Whereas a prior art video system would not properly recover and produce the video image shown in FIG. 1b, the video system according to the present invention produces the video image shown in FIG. 1c. Recovery is accomplished without an increase in memory usage. Increased memory usage is a penalty that commercial video systems such as MPEG decoders simply cannot afford, since so much of the available bandwidth (90-95%) is already used up. 
     It is understood that various changes and modifications may be made without departing from the spirit and scope of the invention. The size of the circular buffer and the range of the pointers WRITE --  PTR and READ --  PTR and total count NUM --  COUNT can be selected to tolerate a desired number of underflow errors by increasing the counter size to count as many negative items as desired. 
     It is also understood that the invention is not limited to the operation shown in FIGS. 4, 5a, 5b and 5c. Nor is the invention limited to the recovery of underflow. It can be used to recover from any error that causes a shift in the display of a video image. 
     Finally, it is understood that the invention is not limited to MPEG video decoders, video DACs and NTSC converters. The video retrieval module can process data that is not encoded, or it can process data encoded according to a standard such as MPEG-1, MEG-2, Digicipher I and II, or JPEG. These standards are currently being used in a wide array of consumer products employing video encoding, such as direct broadcast television systems, cable TV and direct audio broadcast systems. The invention can be applied to video/audio MPEG decoders and graphics accelerator boards for personal computers. In fact, the invention can include any module that generates bursty outputs and any device that requires data at a constant and continuous rate, or the invention can include any module that receives data at a constant and continuous rate and outputs data in bursts. Accordingly, the present invention is not limited to the precise embodiment described hereinabove. Instead, it is defined by the claims that follow.