Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2003-11-01
2004-11-02
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S050000
Reexamination Certificate
active
06812866
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to data compression and decompression systems based on the LZ data compression and decompression methodology and more particularly to the LZW decompression protocols.
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 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 image communication protocol and is utilized in the TIFF image communication protocol. GIF is a development of CompuServe Incorporated and the name GIF is a Service Mark thereof. A reference to the GIF specification is found in GRAPHICS INTERCHANGE FORMAT, Version 89a, 31 Jul., 1990. TIFF is a development of Aldus Corporation and the name TIFF is a Trademark thereof. Reference to the TIFF specification is found in TIFF, Revision 6.0, Final—Jun. 3, 1992.
LZW has also been adopted as the standard for V.42 bis modem compression and decompression. A reference to the V.42 bis standard is found in CCITT Recommendation V.42 bis, Data Compression Procedures For Data Circuit Terminating Equipment (DCE) Using Error Correction Procedures, Geneva 1990. The V.42 bis standard is further described in an article entitled “V.42 bis: The New Modem Compression Standard” by J. E. MacCrisken in the Spring 1991 issue of the Journal Of Data & Computer Communications—Modem Compression, pages 23-29.
Examples of LZ dictionary based compression and decompression systems are described in the following U.S. patents: U.S. Pat. No. 4,464,650 by Eastman et al., issued Aug. 7, 1984; U.S. Pat. No. 4,876,541 by Storer, issued Oct. 24, 1989; U.S. Pat. No. 5,153,591 by Clark, issued Oct. 6, 1992; U.S. Pat. No. 5,373,290 by Lempel et al., issued Dec. 13, 1994; U.S. Pat. No. 5,838,264 by Cooper, issued Nov. 17, 1998; and U.S. Pat. No. 5,861,827 by Welch et al., issued Jan. 19, 1999.
In the above dictionary based LZ compression and decompression systems, the compressor and decompressor dictionaries may be initialized with all of the single character strings of the character alphabet. In some implementations, the single character strings are considered as recognized and matched although not explicitly stored. In such systems the value of the single character may be utilized as its code and the first available code utilized for multiple character strings would have a value greater than the single character values. In this way the decompressor can distinguish between a single character string and a multiple character string and recover the characters thereof. For example, in the ASCII environment the alphabet has an 8 bit character size supporting an alphabet of 256 characters. Thus, the characters have values of 0-255. The first available multiple character string code can, for example, be 258 where the codes
256
and
257
are utilized as control codes as is well known.
In the prior art dictionary based LZ decompression systems, data character strings are stored and accessed in the decompressor dictionary utilizing well known searchtree architectures and protocols. Typically, the searchtree is arranged in nodes where each node represents a character, and a string of characters is represented by a node-to-node path through the tree. The nodes are stored as linked locations in the dictionary, a location storing the character corresponding thereto with a code assigned to the terminal node. An input compressed code fetched by the decompressor accesses the terminal node and the character stored thereat is saved. The linked locations up the tree to the root are each accessed in turn saving the respective characters. As a result, the characters of the string represented by the fetched code are accessed in reverse order. A character reversal operation is required to provide the characters in appropriate order. Additionally, numerous dictionary accesses are required to recover the characters of a string.
Although the known dictionary architectures and protocols provide efficient data decompression systems, it is desirable to eliminate the requirement for character order reversal and to eliminate the numerous required dictionary accesses.
The data compressors of said Ser. Nos. 10/195,795; 10/271,196; 10/351,210 and Ser. No. 10/448,620 provide an improvement over the prior art by replacing the known dictionary architecture by matrices of logic elements thereby eliminating dictionary accesses. A data decompressor utilizing a matrix of logic elements to replace the known dictionary arrangements is not available in the prior art.
SUMMARY OF THE INVENTION
The present invention replaces the conventional dictionary arrangements with digital logic elements and switches to provide a new architecture and protocols which, it is believed, will improve the performance of LZ type data decompression systems. The embodiments of the present invention eliminate both dictionary accesses and character order reversal requirements. Additionally, the architecture of the present invention provides an efficient arrangement for performing the LZW exception case processing where a string of characters is not yet stored for a fetched input code.
The present invention is embodied in a data decompressor for decompressing an input stream of codes to recover an output stream of data characters corresponding thereto, a code corresponding to a string of data characters. The decompressor includes a code decoder with a plurality of code decoder outputs corresponding to a respective plurality of codes to be assigned to strings, the code decoder being responsive to an input code for selectively energizing a code decoder output in accordance with the input code. Further included in the decompressor is a plurality of logic elements corresponding to the respective plurality of codes, a logic element having an input and an output with the inputs of the logic elements coupled to the code decoder outputs, respectively. A character storage table is responsive to the code decoder outputs and has a plurality of storage locations for storing respective data characters. A storage location is accessed by a code decoder output to provide the data character stored therein.
A coupling arrangement is included for selectively coupling outputs of the logic elements to inputs thereof so that the data characters of the string corresponding to the input code are provided by the character storage table, thereby providing the output stream of data characters. The coupling arrangement selectively couples the outputs of the logic elements to inputs thereof so that energization of the code decoder output corresponding to the input code propagates through sequentially coupled logic elements to access storage locations thereby providing the data characters of the string corresponding to the input code.
An update extended string is recorded in the decompressor and a code assigned thereto by storing the first character of the string corresponding to the input code in the storage location of the character storage table accessible by the code decoder output corresponding to a next code to be assigned to a string. The coupling arrangement couples the output of the logic element corresponding to the next code to be assigned to the input of the logic element corresponding to the code received previously to the input code. The extended string comprising the string corresponding to the previously received code extended by the first character of the string corresponding to the input code is thereby recorded and the next code assigned thereto.
Exception case processing is performed for a currently fetched code to which a recorded string has not
Atlass Michael B.
Cooper Albert B.
Lauture Joseph
Starr Mark T.
Unisys Corporation
LandOfFree
Data decompressor utilizing sequentially coupled logic elements 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 decompressor utilizing sequentially coupled logic elements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data decompressor utilizing sequentially coupled logic elements will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346962