Efficient data encoding and decoding processes

Details Efficient data encoding and decoding processes Efficient data encoding and decoding processes

2001-10-02

2004-02-24

Young, Brian (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from variable length codes

C341S050000, C358S426130

Reexamination Certificate

active

06696992

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FED SPONSORED R & D
Not Applicable
REFERENCE TO A MICROFICHE APPENDIX
Not Applicable
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to the field of data compression and decompression of the compressed data.
2. Description of the Related Art
Data compression is a process of converting data such that the converted data can be encoded in fewer bits or bytes. When being decompressed, the compressed data is recovered to its original form. Compressed data saves data storage since smaller-sized data takes less space to store. Compressed data can also enhance data transmission rates since smaller-sized data requires less time to transmit. Compression techniques have long been used in storage media such as tapes, disks, and flash cards, as well as communication equipment, such as the modem and Ethernet. With the rapidly growing demand for the Internet as well as handheld and wireless devices, compression plays an even bigger role than ever in terms of data transmission and storage.
As shown in
FIG. 1
, a typical LZ data compression method processes an input data stream
10
to generate a compressed output data stream
17
by comparing an unprocessed data portion
12
of the input data stream
10
to already processed data in a history buffer
11
. If a data string
13
found in the history buffer
11
matches a current data string
14
in the unprocessed data portion
12
, the current data string
14
is replaced by a pointer (P, L) that corresponds to an offset P
15
and a match length L
16
. The offset P
15
and match length L
16
are then encoded individually with either a fixed-length coding or a variable-length coding process. Thus, the current data string
14
is represented by a shorter coded pointer data (P, L)
18
in the compressed output data stream
17
.
As shown in
FIG. 2
, fixed-length coding uses a fixed number of bits to encode a range of numbers. For example, if the number “7” were coded in a 13-bit fixed-length coding scheme, the encoded bit string would be “0000000000111”. In another case, if the number “4096” were coded in a 13-bit fixed-length coding scheme, the encoded bit string would be “1000000000000”. Thus, an n-bit fixed-length coding scheme encodes up to 2
n
numbers ranging from 0 to (2
n
−1). Variable-length coding, on the other hand, uses a variable number of bits to encode a range of numbers. There are many different variable-length coding schemes suited to different needs.
FIG. 3
illustrates an example of a variable-length coding table that encodes up to 8,191 numbers ranging from 0 to 8,190. Variable-length coding typically encodes smaller numbers in fewer bits and larger numbers in more bits. For example, coding the number “4096” using the variable-length coding table shown in
FIG. 3
would take 25 bits. However, coding the number “7” using the same variable-length coding table would only take 7 bits. Thus, compared to variable-length coding, fixed-length coding generally tends to be more efficient in coding larger numbers, but less efficient in coding smaller numbers.
How to encode data efficiently is essential to achieving a good compression result. Prior methods typically encode match length L
16
with variable-length coding and offset P
15
with fixed-length coding. While match length L
16
is normally a small number, offset P
15
falls within a wide range of values determined by the size of the history buffer
11
. Offset P
15
has an upper bound that increases as the size of the history buffer
11
increases. Thus, coding offset P
15
strictly with fixed-length coding as do most of the prior methods is less desirable when offset P
15
turns out to be a small number, e.g. “7”. On the other hand, coding offset P
15
strictly in variable-length coding is less desirable either when offset P
15
happens to be a large number, e.g. “4096”. Thus, combining different coding schemes into a single coding scheme is able to maximize the efficiencies of data encoding.
Since smaller data requires fewer bits to encode prior methods try to reduce the number of bits to encode data through methods such as replacing a matching data string with a pointer data (P, L) as illustrated in FIG.
1
. However, it is desirable to further reduce the value of a data before encoding.
BRIEF SUMMARY OF THE INVENTION
A data encoding and decoding system for improving data compression performance is provided in accordance with the principles of this invention. The data encoding and decoding system comprises a composite fixed-variable-length coding process and an offset-difference coding process for encoding and decoding data. The encoding process of composite fixed-variable-length coding encodes an input data by first comparing the input data to a predetermined threshold, then selecting a coding scheme from two preselected coding schemes and encoding the input data in accordance with the selected coding scheme. The encoding process of composite fixed-variable-length coding also generates an identifier to indicate the selected coding scheme if the response to comparing the input data with a predetermined threshold differs from a statistically determined response. The decoding process of composite fixed-variable-length coding first detects if an identifier exists in a codeword in a coded data stream, then decodes the codeword with a coding scheme that was selected in the corresponding encoding process.
A composite coding system provided in accordance with the principles of this invention encodes a paired input data by encoding the statistically larger one of the paired input data with a composite fixed-variable-length coding process and the statistically smaller one of the paired input data with a stand-alone coding process.
The encoding process of offset-difference coding encodes a paired input data by first determining the greater of the two input data, then calculating the difference between the larger input data and the smaller input data, replacing the larger input data with the calculated difference, and encoding said calculated difference and the smaller input data. The encoding process of offset-difference coding also generates an indicator to indicate the input data that has been replaced if said input data is not statistically larger. The decoding process of offset-difference coding first detects if an indicator exists in a codeword in a coded data stream, then decodes and reconstructs the original data.
The composite fixed-variable-length coding process described in accordance with the principles of this invention combines different coding schemes into a single coding scheme to encode a data. It thus maximizes the efficiencies and minimizes the deficiencies of a coding scheme. The offset-difference coding process described in accordance with the principles of this invention minimizes the number of bits required to encode a data by further reducing the value of the data. Data with smaller values require fewer bits to encode, especially in a variable-length coding scheme. Thus, the two processes improve the compression performance of LZ-based compression methods without compromising the memory resource or compression/decompression speed. The two processes may be used independently or together depending on the application.


REFERENCES:
patent: 4509038 (1985-04-01), Hirano
patent: 4758975 (1988-07-01), Omada et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5109433 (1992-04-01), Notenboom
patent: 5623262 (1997-04-01), Normile et al.
patent: 5801841 (1998-09-01), Suzuki
IEEE, Transactions On Information Theory, vol. II 23, No. 3, May 1977, pp. 337-343 J. Ziv, A. Lempel, “A Universal Algorithm for Sequential Data Compression”.
IEEE, Transactions on Information Theory, vol. II 21, No. 2, Mar. 1975, pp. 194-203, Peter Elias, “Universal Codeword Sets and Representations of the Integers”.
IEEE, Transactions on Information Theory, vol. II 24, No. 5, Sep. 1978, pp. 530-536, J. Ziv, A. Lempel, “Compression of In

Affiliated with

Also associated with

Rating

Efficient data encoding and decoding processes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient data encoding and decoding processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient data encoding and decoding processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3285250