Entropy coding using adaptable prefix codes

Details Entropy coding using adaptable prefix codes Entropy coding using adaptable prefix codes

2001-02-08

2003-10-14

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

C341S051000

Reexamination Certificate

active

06633242

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates primarily to the field of data compression, and in particular to an entropy coding method using adaptive prefix codes.
Portions of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all rights whatsoever.
2. Background Art
Computer systems are increasingly being used to play back multimedia (audio and video) files. Current computer systems are often unable to transfer data from a file quickly enough from storage to permit adequate playback of a multimedia file. This delay is directly proportional to the amount of data to be transferred.
One way to solve the problem of transmitting a large file is to compress the data for transmission and decompress it back at the destination. However, some compression schemes are not suitable for environments where there is little processing power available (thin clients), or either the compression or decompression schemes are difficult to perform, or require prior knowledge of certain parameters in the schemes.
As mentioned earlier, computers are often used to process, play back, and display video data. This data may come from sources such as storage devices, on-line services, VCRs, cable systems, broadcast television tuners, etc. Video data is not only memory intensive, that is, video data requires large amounts of memory for storage and use by a computer system, but requires the computer system to continuously and uninterruptedly process, play back, and display the data.
To reduce the transmission bandwidth and memory requirements when working with video data, various compression schemes have been developed so that less storage space is needed to store video information and a smaller bandwidth is needed to transmit it. Prior art video compression schemes include Motion JPEG, MPEG-1, MPEG-2, Indeo, QuickTime, True Motion-S, CinePak, etc.
Entropy Coding
Entropy coding is a method of compressing data that is used by video and graphics compression schemes. Entropy coding produces a unique code for each entity of text, audio, video, or graphics data in the file. The length of these code words is based on the probability of the occurrence of the data represented by the code word. Huffman and Golomb coding schemes are two known entropy encoding methods that are extensively used by most present text, audio, video, and graphics compression schemes.
Huffman Coding Scheme
The Huffman coding scheme is perhaps the best and most widely used form of entropy coding. It uses an algorithm known as the “greedy” algorithm to accomplish its task. The greedy algorithm obtains an optimal solution to a problem by making a sequence of choices. For each decision point in the algorithm, the choice that seems best at the moment is chosen. This heuristic strategy does not always produce an optimal solution, but does in most cases. Two ingredients of the Huffman greedy algorithm are the greedy-choice property (a global optimal solution can be derived at by making a locally optimal choice) and optimal substructure (the optimal solution to a problem contains within it optimal solutions to subproblems).
Entropy encoding can be either fixed length or variable length. Consider an example of compressing an alphanumeric file. ASCII coding schemes use 8 bits for each alphanumeric (letter or number) character. Thus, a file that contains 100,000 characters requires 800,000 bits to represent its data. Assume that the file comprises of just six characters, viz. “a”, “b”, “c”, “d”, “e” and “f”.
Entropy encoding is implemented by determining the frequency of the occurrence of the characters in the file. The table below represents the frequency of occurrence of each character in the example file and proposes a coding solution for fixed length and variable length coding schemes.
TABLE 1
a
b
c
d
e
f
Frequency
40000
10000
12000
18000
5000
7000
Fixed-length
000
001
010
011
100
101
codeword
Variable-length
0
10
01
00
001
000
codeword
Fixed Length Encode
In the fixed length encoding scheme, the maximum number of bits needed to represent the actual number of characters used in the file is determined. If this number of bits is less than the number of bits needed to represent all characters in the alphanumeric set, then compression is possible. For example, with six characters, three bits are needed to encode the six alphabets where “a”=000, “b”=001, “c”=010, “d”=011, “e”=100, and “f”=101. (By comparison, a file with nine characters needs four bits to encode, and a file with more than 128 characters (but less than 257) needs eight bits to encode). Using this scheme requires 3*100,000=300,000 bits to encode the entire example file. This is a savings of approximately 62.5% (300,000 bits as compared to 800,000 bits) over the uncompressed version. (It must be noted though, that a file with more than 128 characters (but less than 257) will require the same number of bits to store or transmit in both the compressed and uncompressed versions because the codeword for the characters will need 8 bits to encode, meaning no compression is achieved).
Variable Length Encoding
Variable-length coding schemes assign frequent characters short codewords and infrequent characters long codewords. In the example, we have encoded “a” with a single bit since it is the most frequently occurring character (40,000 occurrences). The next most frequently occurring characters “b”, “c”, and “d” are represented by with two bits, and “e” and “f” with are represented by three bits as the least frequently occurring characters. Using variable length encoding, the scheme requires 156,000 bits (40000*1=10000*2=12000*2=18000*2=5000*3=7000*3) to encode the entire file. This is a savings of approximately 80.5% (156,000 bits as compared to 800,000 bits) over the uncompressed version and significant savings over the fixed length encoding scheme.
Decode
Using either of the above mentioned code schemes, the decoding process occurs as follows: the first bit is received and checked with the table to see if it represents an allowed codeword. If so, the decode process is over. If not, the second bit (if one exists) is received, and the two bits in combination are checked with the table to see if they represent an allowed codeword. As long as an allowed codeword has not been received, the process of receiving new bits and the checking of the ensemble of bits with the table continues, which can be a lengthy and tedious procedure.
Drawbacks With Huffman's Scheme
There are several drawbacks with the Huffman coding scheme. Firstly, a binary code has to be chosen for the frequency occurrence of characters (alphabets, numbers, punctuation characters, and audio, video, or color entities) for each data file, which will vary from one file to another depending on the frequency of occurrence of the character in the file. This means that the scheme will vary from not only data file to data file, but also if changes are made to the data file in the future. Secondly, in order to calculate the frequency occurrence of characters in a data file, the scheme has to first make a quantitative assessment of the characters, after which it has to go back to the beginning of the data file to assign the chosen binary code for each character. This means that the scheme has to make two passes of the file in order to encode—a time consuming procedure. In order to avoid lengthy encoding computations, like in the case of MPEG and JPEG, fixed Huffman codes are sometimes used which reduces the lengthy procedure to some extent. Thirdly, the decoding process may become difficult to accomplish since the contents of the data file are read by the computer as one long string of 1's and 0's and there is no definitive marker to separate the codew

Affiliated with

Also associated with

Rating

Entropy coding using adaptable prefix codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Entropy coding using adaptable prefix codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy coding using adaptable prefix codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3165337