Coded data generation or conversion – Digital code to digital code converters – Unnecessary data suppression
Reexamination Certificate
1998-03-16
2001-05-01
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Unnecessary data suppression
C341S051000
Reexamination Certificate
active
06225922
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to data compression systems and in particular to a data compression system and method for dynamically encoding data into a compressed format and decoding the compressed format without the use of stored or referenced symbol tables or encoding trees for increased efficiency for some data sets.
2. Related Art
Data comprised of text, sounds, images, and video can be encoded so that fewer bits are used to store, transmit, or process the data more efficiently. After the encoded data is stored, transmitted, or processed, the encoded data is decoded to obtain the original data. Encoded data can save storage space of a particular storage medium or can reduce the time it takes to transmit data from one location to another. Thus, current data encoding systems and methods are very important, useful and popular.
As a result, many different data encoding systems and methods exist. This is because the efficiency of any data compression scheme is dependent on the data that is being compressed. One basic type of data encoding system that is used as a basis for many data compression systems is Huffman coding. Huffman coding is a data compression technique that varies the length of the encoded symbol in proportion to its information content. In other words, when a symbol or token is used frequently, a relatively short binary string is used to represent the symbol or token in a compressed stream. Huffman codes can be properly decoded because they obey the prefix property, which means that no code can be a prefix of another code, and so the complete set of codes can be represented as a binary tree, known as a Huffman tree. Each leaf of the Huffman tree corresponds to a letter. The goal is to build a tree with the minimum external path weight. Huffman coding requires a stored or referenced encoding a tree symbol for proper decoding.
Run-length encoding is another basic encoding system. Run-length encoding involves replacing strings of repeated characters, or other units of data, with a single character and a count. For example, a recurring sequence of numbers is first identified and then that sequence is represented with a single number. As a result, run-length encoding can only efficiently compress data that is repetitive. For text files, a similar technique is key-word encoding. Key-word encoding involves replacing frequently occurring words with a 2-byte token. This replacement saves one or more bytes of storage for every instance of that word in a text file. Key-word encoding also requires a stored or referenced symbol table for proper decoding.
Another compression system that is frequently used to compress image data is the Lempel-Ziv Welch (LZW) compression system. LZW compression relies on the reoccurrence of byte sequences or strings in its input. A table mapping input strings to their associated output codes is maintained. Mappings for all possible strings of length one are initially contained in the table. Input is taken one byte at a time in order to determine the longest initial string present in the table. The code for the longest initial string is first output, and then the string is extended with one more input byte.
Next, a new entry is added to the table mapping the extended string to the next unused code and can be obtained by incrementing a counter. The process is repeated, starting from the input byte. The number of bits in an output code (the maximum number of entries in the table) is typically fixed, and once this limit is reached, no more entries are added. Decompression can be accomplished by receiving the compressed code signals and generating a string table similar to that constructed during compression to produce a lookup table of received code signals. This enables recovery of the data character signals comprising a stored string. Thus, a stored or referenced symbol table is required for proper decoding.
From the foregoing it will be apparent that there is a need to encode data dynamically and to decode the encoded data without the use of stored or referenced symbol tables or encoding trees for increased efficiency for some data sets. Therefore, what is needed is a system and method to realize adaptive field encoding and decoding of data.
Whatever the merits of the above mentioned systems and methods, they do not achieve the benefits of the present invention.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention, in a preferred embodiment, provides a data compression system that encodes data dynamically and decodes the data without the use of stored or referenced symbol tables or encoding trees. A data compression system and method embodying the invention compresses data efficiently for some data sets and utilizes a simple scheme for decompressing the data.
The data compression system of the preferred embodiment compresses data of an input data stream having field widths for holding data values of a data set. The term “field width” specifically refers to the space required to store information. Each field width is represented by a field value, such as a bit size if the binary base storage system is used. Although the term “bit” is used as a field value throughout the specification, any suitable base storage system could be used. The data compression system includes an adaptive processor having an encode module for encoding the input signal and dynamically changing the field widths at various positions in the data stream. This minimizes a storage space required to represent the entire data set. Also, a decode module can be included in the system for decoding the compressed format and producing an output signal having a lossless representation of the input signal.
The foregoing and still further features and advantages of the present invention as well as a more complete understanding thereof will be made apparent from a study of the following detailed description of the invention in connection with the accompanying drawings and appended claims.
REFERENCES:
patent: 5123061 (1992-06-01), Pritchard
patent: 5153591 (1992-10-01), Clark
patent: 5455577 (1995-10-01), Slivka et al.
patent: 5463389 (1995-10-01), Klayman
patent: 5488717 (1996-01-01), Gibson et al.
patent: 5608396 (1997-03-01), Cheng et al.
patent: 5825830 (1998-10-01), Kopf
Hewlett--Packard Company
Jean-Pierre Peguy
LandOfFree
System and method for compressing data using adaptive field... 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 compressing data using adaptive field..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for compressing data using adaptive field... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2495029