Coded data generation or conversion – Digital code to digital code converters – To or from bit count codes
Reexamination Certificate
2000-09-06
2001-07-31
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from bit count codes
C341S051000
Reexamination Certificate
active
06268811
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to data compression particularly with respect to providing data compression embodiments with embedded run-length encoding that have heretofore not been developed in the prior art.
2. Description of the Prior Art
Professors Abraham Lempel and Jacob Ziv provided the theoretical basis for LZ data compression and decompression systems that are in present day widespread usage. Two of their seminal papers appear in the IEEE Transactions on Information Theory, IT-23-3, May 1977, pp. 337-343 and in the IEEE Transactions on Information Theory, IT-24-5, September 1978, pp. 530-536. A ubiquitously used data compression and decompression system known as LZW, adopted as the standard for V.42 bis modem compression and decompression, is described in U.S. Pat. No. 4,558,302 by Welch, issued Dec. 10, 1985. LZW has been adopted as the compression and decompression standard used in the GIF and TIFF image communication protocols.
Another type of data compression and decompression, denoted as Run-Length Encoding (RLE), compresses a repeating character run by providing a compressed code indicating the character and the length of the run. RLE is thus effective in encoding long strings of the same character. For example, RLE is effective in compressing a long sequence of blanks that may be included at the beginning of a data file. RLE is also effective in image compression where an image contains a long run of consecutive pixels having the same value, such as in the sky portion of a land-sky image.
In the prior art, run-length encoding has been combined with an LZ system by applying the data to a run-length encoder and then applying the run length encoded data to the LZ based system. In such an architecture, a run-length encoder is utilized at the front end of the compressor and a run-length decoder is utilized at the output end of the decompressor. Such a system suffers from the disadvantages of increased equipment, expense, control overhead and processing time.
Run-length encoding has also been included in the LZW based system of U.S. Pat. No. 5,389,922 by Seroussi et al, issued Feb. 14, 1995. In the system of this patent certain output codes from the compressor are suppressed in the presence of a run of repeating input data characters. A special run enhancement engine is utilized at the input to the decompressor to regenerate the missing codes.
Another data compression and decompression system involving the encoding of data character runs is disclosed in U.S. Pat. No. 5,861,827 by Welch et al., issued Jan. 19, 1999. In the compressor of this system, when a partial string W and character C are found, a new string is stored with C as an extension character on the string PW where P was the string conveyed in the last transmitted output compressed code. With this compression algorithm, a run of characters is encoded in two compressed codes regardless of its length. The decompressor of this system uses a special unrecognized code process to maintain synchronism with the compressor.
It is an object of the present invention to provide further data compression embodiments that utilize run-length encoding.
SUMMARY OF THE INVENTION
The compressor of the present invention generates a sequence of numerically increasing output codes corresponding to numerically increasing contiguous segments of a run of data characters. Consecutive characters that differ with respect to each other are transmitted directly and in synchronism with incrementing the compressor code counter.
REFERENCES:
patent: 4929946 (1990-05-01), O'Brien et al.
patent: 4971407 (1990-11-01), Hoffman
patent: 4988998 (1991-01-01), O'Brien
patent: 5247638 (1993-09-01), O'Brien et al.
patent: 5389922 (1995-02-01), Seroussi et al.
patent: 5764167 (1998-06-01), Adams et al.
patent: 5861827 (1999-01-01), Welch et al.
patent: 6137428 (2000-10-01), Coopeer
patent: 0734126A1 (1996-09-01), None
patent: WO 00/02319 (2000-01-01), None
Internet site: http://www.boutell.com/gd, pp. 1-3.
Adornato Rocco L.
Cooper Albert B.
Starr Mark T.
Unisys Corporation
Williams Howard L.
LandOfFree
Data compression method and apparatus with embedded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression method and apparatus with embedded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression method and apparatus with embedded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520979