Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Utility Patent
1999-06-19
2001-01-02
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S063000
Utility Patent
active
06169499
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to LZW data compression and decompression systems particularly with respect to including run-length encoding and decoding within the LZW compression and decompression processing, respectively.
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 LZ systems as exemplified in the following U.S. Pat. No. 4,929,946 by O'Brien et al., issued May 29, 1990; U.S. Pat. No. 4,971,407 by Hoffman, issued Nov. 20, 1990; U.S. Pat. No. 4,988,998 by O'Brien, issued Jan. 29, 1991; U.S. Pat. No. 5,247,638 by O'Brien et al., issued Sep. 21, 1993; U.S. Pat. No. 5,389,922 by Seroussi et al., issued Feb. 14, 1995; and U.S. Pat. No. 5,861,827 by Welch et al., issued Jan. 19, 1999.
In some prior art systems, 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. U.S. Pat. Nos. 4,971,407 and 4,988,998 exemplify such a system.
In the LZW based system of U.S. Pat. No. 5,389,922, 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.
In the compressor of the system of U.S. Pat. No. 5,861,827, when a partial string W and a 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.
In the system of U.S. Pat. No. 4,929,946 a run is indicated by transmitting one of a predetermined set of reserved reference values followed by a repeat count for the run. The reserved reference values are defined so that the number of bits in the repeat count that follows the reserved reference value is reduced. The requirement of the use of the reserved reference value in the compressed stream for every run that is detected tends to reduce the compression. Additionally, the system is apparently limited to processing relatively small length runs. U.S. Pat. No. 5,247,638 provides descriptions similar to those of U.S. Pat. No. 4,929,946.
Another data compression system involving the encoding of data character runs is disclosed in said patent application Ser. No. 09/264,269. In the compressor of this patent application, runs are processed by successively looking ahead into the input to determine if contiguous numerically increasing segments exist in the run.
Yet another data compression system involving the encoding of data character runs is disclosed in said patent application Ser. No. 09/300,810. In the compressor of this patent application, runs are processed by mathematically determining, from the length of the run, the respective output codes corresponding to the contiguous numerically increasing segments that exist in the run.
It is an object of the present invention to embed run-length encoding and decoding in an LZW data compression and decompression system where a provision is included that does not require the transmission of a special reserved code to inform the decompressor of the existence of the run. It is a further object of the present invention to provide for the processing of very large length runs.
SUMMARY OF THE INVENTION
The present invention enhances the well-known LZW data compression/decompression system by determining when a run of input data characters occurs and by combining the run character count with the existing code value from the compressor code counter to generate a compressor output representative of the run count. The decompressor utilizes the existing code value in the decompressor code counter to recover the run count from the compressor output. In a further feature of the present invention, very large length runs are processed by reducing the run count by a selected predetermined process and outputting the reduced run count preceded by a reserved code representative of the selected predetermined process. In response to the received reserved code, the decompressor applies the predetermined process corresponding to the received reserved code to recover the original run count by increasing the received reduced count in accordance with the predetermined process.
REFERENCES:
patent: 4558302 (1985-12-01), Welch
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-09-01), Adams et al.
patent: 5861827 (1999-01-01), Welch et al.
Internet site:http://www.boutell.com/gd. pp. 1-2.
Adornato Rocco L.
Cooper Albert B.
Jean-Pierre Peguy
Starr Mark T.
Unisys Corporation
LandOfFree
LZW data compression/decompression apparatus and method with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with LZW data compression/decompression apparatus and method with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LZW data compression/decompression apparatus and method with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2513713