Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2002-07-03
2004-01-06
Glaude, Jean Bruner Jean (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S055000, C341S050000, C341S161000
Reexamination Certificate
active
06674373
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for decompressing a compressed data stream to reconstruct the original uncompressed data.
2. Background Art
Data compression technology is used to increase the virtual capacity of many types of storage devices. In general, data is compressed as it is written to a storage device from a host processor. The data is then decompressed as the host processor subsequently reads the data back from the storage device. Depending upon the particular application, various types of compression algorithms may be used to provide a significant compression ratio. However, the compression/decompression algorithm often presents a botdeneck to the data transfer rates that these types of storage devices can otherwise achieve.
In one existing approach to data compression and decompression, compressed data is represented as a series of literal references or as history references. Literal references are single bytes of data and are encoded as nine-bit values. History references are encoded in varying lengths and replace the data which they are referencing. A history reference provides an address and a count to an identical string of data that is located in a history buffer, which contains up to 1024 bytes, for example, of the most recent data that has already passed by in the data stream.
During decompression, history references are processed to generate corresponding addresses within the history buffer. These addresses are used to provide the corresponding data from the history buffer. The data obtained from the history buffer is combined in the appropriate sequence with the literal data references to reconstruct the original data stream.
When reading a data stream from a data storage device, compressed data can be transferred at a high effective rate. One prior art approach outputs a single byte of decompressed data each clock cycle. This approach results in a relatively low data transfer rate of decompressed data to the host processor channel. Advancements in technology allow the decompression function to run at about 50 MHz (for FPGA implementations) or 100 MHz (for ASIC implementations) which can provide channel transfer rates of 50 MB/s to 100 MB/s, respectively. However, current interfaces (such as Fibre Channel interfaces) can reach speeds of 200 MB/s or more. As such, the prior art approach for decompressing the data is not able to keep up with the maximum speed of currently available host processor interfaces.
SUMMARY OF THE INVENTION
The present invention provides a method and system for reconstructing data from a compressed data stream. The present invention provides a parallel data decompression approach that uses a multiple stage pipeline process to extract two or more references from the compressed data stream. The extracted literal and history references are converted to individual bytes of data or history buffer addresses and are pipelined in parallel toward the history buffer. The history buffer is replicated for each byte of data to allow substantially simultaneous accesses to two different locations. An output stage determines whether the literal bytes or the data bytes that have been read from one or the other of the history buffers will be output to the channel. The parallel data decompression system and method according to the present invention can continue to output multiple bytes of data as long as compressed data continues to be available from the storage device.
The modular design of the present invention allows multiple bytes of compressed data to be extracted, e.g. during each clock cycle. This design may be expanded to include “n” bytes of data in parallel with additional history buffers added corresponding in the number to the “n” bytes of data. Because of the nature of how history and literal references are extracted from the compressed data stream, stages of the pipeline may tend to go partially empty. This results in an inability to sustain an output of multiple bytes per clock cycle. As such, the present invention includes control logic that can generate multiple history buffer addresses from one history reference, to refill multiple stages of the pipeline in an attempt to keep the pipeline full. The invention also includes control logic to synchronize the history buffers by writing identical data to each of the history buffers substantially simultaneously, e.g. during the same clock cycle. Because multiple bytes of data can be accessed from the history buffers, the present invention also includes logic to resolve history buffer access contention.
In one embodiment according to the present invention, the system and method include extracting literal reference or history reference data from the compressed data stream, converting history reference data to a plurality of corresponding addresses that may be used to selectively access substantially simultaneously at least two history reference memories to retrieve previously stored uncompressed data associated with the history reference data via the corresponding addresses, and substantially simultaneously providing at least two bytes of uncompressed data to corresponding output registers, wherein the at least two bytes of uncompressed data are reconstructed from the literal data, the history reference memories, or both.
The present invention provides a number of advantages relative to the prior art. For example, the present invention provides the ability to substantially increase the rate at which compressed data can be read from a storage device. In fact, the effective rate of transfer of the decompressed data can be multiplied up to “n” times faster, where “n” represents the number of history buffers that are incorporated. This can be accomplished using available technology without sacrificing backward compatibility. As such, the present invention allows the decompression logic to read data at the same rate as the industry's current standard channel rates, and provides an architecture that can be extended to meet future demands. In that regard, it should be noted that the increased speed provided by the present invention is achieved regardless of the technology used for decompression or interface functions.
REFERENCES:
patent: 5155484 (1992-10-01), Chambers, IV
patent: 5184126 (1993-02-01), Nagy
patent: 5247638 (1993-09-01), O'Brien et al.
patent: 5374916 (1994-12-01), Chu
patent: 5467087 (1995-11-01), Chu
patent: 5602764 (1997-02-01), Eskandari-Gharnin
Jones Larry D.
Solfermoser Doug
Brooks & Kushman P.C.
Glaude Jean Bruner Jean
Storage Technology Corporation
LandOfFree
System and method for data decompression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for data decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for data decompression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3256992