Hierarchical lossless compression

Abstract

A method is provided for data compression. The data compression method transforms a square of data into a tile of data. The tile of data is then divided into quads of data that are converted into a representative element, a first delta element, a second delta element, a third delta element, and a control word. A new tile of data is then formed with the representative elements, and the process is repeated until a single representative element remains. The single representative element is then embedded into an output stream with the control words and corresponding delta elements. Decompression of the data is symmetrical to the encoding once the bit stream has been parsed.

Description

FIELD OF THE INVENTION[0001]The present invention relates to data compression. More particularly, the present invention relates to lossless data compression suitable for hardware implementation.BACKGROUND OF THE INVENTION[0002]Data compression is the process of converting data to be stored using less bits. The two types of data compression are lossy and lossless. Lossy data compression compresses data to a greater degree, but loses data during the process. Thus, during decompression, the data is an approximation of its original form rather than an exact replica. Lossless data compression compresses data to a lesser degree, but does not lose any data during the process. Accordingly, during decompression, the data is reconstructed exactly as it was before compression. The objective of data compression is to reduce the amount of bandwidth necessary for transmission and / or memory necessary for storage.[0003]An example of a common lossless compression technique is Huffman coding. Huffman...

AI Technical Summary

Benefits of technology

The present invention provides a method for compressing data in a hierarchical manner, where a computer divides a primary array of data into smaller subarrays, compresses each subarray, and arranges them in a secondary array. The method can be used to compress a variety of data, such as a square or tile of data. The compression process involves converting each element of the data into representative elements and control words, resulting in a new data tile that can be further divided, converted, and formed. The final tile can then be embedded into an output stream. The technical effects of this invention include improved data compression efficiency and flexibility in the compression process.

Problems solved by technology

The two types of data compression are lossy and lossless.

Lossy data compression compresses data to a greater degree, but loses data during the process.

Unfortunately, a limitation of Huffman coding is that it has a fixed sequence length procedure and cannot compress redundancy in data that exceeds the sequence length.

As a result, Huffman coding is complex and requires a large amount of memory to be effective.

Further, the Huffman technique is asymmetrical by nature, meaning the decoding process is much slower than the encoding process.

Such a characteristic is unacceptable for certain hardware implementations because a computer is generally designed to read and write approximately the same amount of data on a single clock cycle.

Unfortunately, LZW suffers by virtue of the string table it generates.

The dictionary can get very large in a short amount of time.

Further, the entire process is asymmetrical in nature and takes a considerable amount of time longer compressing than decompressing.

Apart from the limitations imposed by the above compression techniques, another major problem is the lack of a uniform compression method for different formats of data.

Images