Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-04-20
2001-05-08
De Cady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C345S023000, C345S111000
Reexamination Certificate
active
06230296
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of error correction in computer systems.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever. Sun, Sun Microsystems, the Sun logo, Java, JavaBeans, HotJava and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
2. Background Art
In a computer system data is typically generated by a data source and provided to a data consumer, or terminal. In some computer systems, the data consumer is only interested in a final or current state of some data rather than the intermediate steps traversed to reach the final, or current state. One such consumer of data is a display means for display of information to a user. Sometimes portions of data can be lost or dropped when moving from the source to the display, resulting in an error condition. It is necessary to correct the error condition so that correct data can be displayed. Existing schemes for error correction interrupt and delay the display of data, inhibiting performance of the computer system.
In some systems, a data source causes the display of data to be effected by sending a series of commands to a display generator (in the present application, the display generator is referred to as the terminal). Each command in the series has an associated sequence number and the sequence numbers are in numerical sequence with no gaps in the numbering. When the terminal receives the commands, one of the things the terminal does is to examine the sequence numbers of each command to see if it is the expected next sequence number. If the terminal receives a command that has an out of order sequence number, there is an assumption that the commands whose sequence numbers are between the sequence number of the last received command and the sequence number of the out of order command are missing. In a typical prior art scheme, the terminal stops generating display data until the missing commands are provided.
An example of the operation of one prior art scheme is illustrated in FIG.
2
.
FIG. 2
consists of a 4×4 grid of pixels. This is a subset of the entire display area used for purposes of example. The grid consists of columns A, B, C, and D, and rows 1, 2, 3, and 4. Pixel locations are thus identified by their column and row number, e.g. pixel B-2 is the second pixel in the second row, pixel C-4 is the third pixel in the fourth row, and so on.
Consider the situation where the display area is all one color, and it is desired to change the display to a second color. In
FIG. 2
at time T
0
, all of the pixels are one color, as shown by the “R” in each grid box. A series of commands are received from a source that is writing to that particular display area. The description assumes one command for each pixel for purposes of the example, but in reality, a single command could initiate the drawing of multiple pixels. The commands in the example of
FIG. 2
are to change each pixel to the color blue. At time T
1
, assume that the terminal has received commands with the following sequence numbers, C-1, C-2, C-3, C-4, C-5, C-7, C-8, C-9, C-10, C-11, C-12, C-13, C-14, C-15, and C-16. In other words, command sequence number C-6 is missing.
In the prior art, the commands of the correctly received commands C-1 through C-5 are executed so the display appears as is shown at time T
1
. However, when the next command sequence number C-7 appears, the prior art system stops to request that the missing command be re-sent by the source. Even though the subsequent commands C-7 through C-16 are available, the prior art system does not execute the commands, so that the display remains only partially updated. The display thus remains at time T
2
the same as at time T
1
. Finally, at time T
3
, the terminal has received the missing block C-6 and executes the commands for C-6 and previously received commands C-7 through C-16 so that the display new displays all blue pixels as at time T
3
of FIG.
2
.
In operation, the error correction scheme of the example of
FIG. 2
causes noticeable delays and hesitation in the display of data. To a user, it appears as if the computer is slow or temporarily inoperative. Such an experience is undesirable.
Another example of how the prior art error correction scheme causes unnecessary delay is illustrated in FIG.
3
. In this example, the pixels are being changed from red to blue to green. At time T
0
, all of the pixels are red. The terminal then receives commands to change the pixels to blue, followed by commands to change the pixels to green. As in the example of
FIG. 2
, command sequence number C-6 is missing, so that at time T
1
, the display has only changed the first row of pixels from red to blue, and the first pixel on the second row. The remaining pixels remain red. Again the terminal requests the missing data sequence block. Meanwhile, commands C-17 through C-32 have been received with commands to turn the pixels from blue to green. However, because the terminal is still waiting for the missing command block, the display remains at time T
2
as it did at time T
1
.
When the missing block is received, the terminal continues to execute the commands in order, so that at time T
3
, all pixels are changed to blue pixels. Finally, at time T
4
, the terminal has executed commands C-17 through C-32 and has changed the pixels from blue to green. A disadvantage of the “stop and wait” system of the prior art is that updating the display comes to a halt while the terminal requests data from the source. To a user, it can appear that the display has “frozen” or that there is a buffering of response to user commands. This limits the user experience and prevents it from being a substantially instantaneous interaction.
SUMMARY OF THE INVENTION
The invention is directed to an error correction scheme used in a computer system where data is provided from a central source to a terminal. The data is dynamically changing, and the user is interested more in a final or current state of the data than in intermediate states. Data is provided in a stream of blocks with sequential “sequence” numbers associated with each block. The invention assumes that the data provider transmits data blocks in order of sequence. The terminal tracks the sequence numbers of incoming blocks. When the terminal finds that one or more blocks have been skipped or are missing, the terminal sends a request to the central source for update data. Unlike prior art systems, which request that the missing block or blocks be re-sent, the present invention requests that the information contained in the missing command be provided, for example the current data at the display area associated with the missing block. The central source maintains the current data state of all display areas, and so sends a data block containing the requested data. In the meantime, the terminal continues to receive and display all received data blocks without waiting for the update request to be filled. This differs from many prior art schemes where display is halted until replacement data is received.
REFERENCES:
patent: 4692761 (1987-09-01), Robinton
patent: 5260742 (1993-11-01), Kikkawa
patent: 5291585 (1994-03-01), Sato et al.
patent: 5335320 (1994-08-01), Iwata et al.
patent: 5345550 (1994-09-01), Bloomfield
patent: 5347627 (1994-09-01), Hoffmann et al.
patent: 5384911 (1995-01-01), Bloomfield
patent: 5412772 (1995-05-01), Monson
patent: 5414806 (1995-05-01), Richards
patent: 5423034 (1995-06-01), Cohen-Levy et al.
patent: 5430836 (1995-07-01), Wolf et al.
patent: 5436637 (1995-07-01), Gayraud et al.
patent: 5448695 (1995-09-01), Douglas et al.
patent: 5461399 (1995-10-01), Cragun
patent: 5461710 (1995-10-01), Bloomfi
Hanko James G.
Ruberg Alan T.
Cady Albert De
Sun Microsystems Inc.
The Hecker Law Group
Ton David
LandOfFree
Method and apparatus for providing error correction 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 providing error correction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing error correction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2550682