Method of coding frequently occurring values

Details Method of coding frequently occurring values Method of coding frequently occurring values

2001-12-26

2003-02-18

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from bit count codes

C341S050000

Reexamination Certificate

active

06522270

ABSTRACT:

COPYRIGHT NOTICE
Portions of this document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent document or the patent application, as it appears in the Patent and Trademark Office file or records, but otherwise reserves all rights whatsoever.
1. Field of the Invention
The present invention relates primarily to the field of data compression, and in particular, to a method for coding at least one designated frequently occurring value.
2. Background of the Invention
Computer systems are increasingly being required to call up, process, and display data, especially multimedia (audio and video) data. However, many computer systems are unable to transfer data quickly and efficiently. This is particularly true for video data. Consequently, the transfer of video data from a multimedia file in storage can be slow, inefficient, unreliable and often inadequate for acceptably immediate and continuous playback.
One reason the transfer of video data is particularly problematic is that video data processing is very memory intensive; i.e., video data requires large amounts of memory for storage and use by a computer system.
Since delay in the transfer of data is directly proportional to the amount of data to be transferred, another solution to the problem of transmitting a large amount of data is to compress the data for transmission and decompress it back at the destination. Some examples of prior art compression schemes are Motion JPEG, MPEG-4 and QuickTime. Many of these prior art coding schemes employ variable length coding.
Variable length coding is a method of compressing data that produces a unique bit sequence, or code, for each entity of text, audio, video, or graphics data in a file. Variable length encoding methods achieve compression by mapping the data (or data sequences) to codes whose average length is less than that of the original representation of the data. Consequently, there is a significant savings of memory space used to store the data.
Using variable length coding, the length of a code is typically based on the probability of the occurrence f the particular data represented by the code, with higher probability data typically having shorter length codes and lower probability data typically having longer length codes. This embodiment of variable length coding is sometimes called entropy coding.
Some prior art coding schemes are not variable but are instead “fixed length” schemes. To show the advantages and operation of variable length coding, as opposed to fixed length coding, assume, as a simplified example, that 10,000 characters in a file are a combination of only five unique characters, “a”, “b”, “c”, “d” and “e”. Further assume that the five unique characters occur with the following frequency: “a” occurs most frequently at 4100 times; “b” occurs 2600 times; “c” occurs 1700 times; “d” occurs 1200 times and “e” occurs least frequently at 400 times.
An exemplary fixed length coding scheme for the example above is shown in Code Mapping Table 1. An exemplary variable length coding scheme, in this example a Huffman coding scheme, could be implemented as also shown in Code Mapping Table 1.
Code Mapping Table 1
a
b
c
d
e
Frequency
4100
2600
1700
1200
400
Fixed Length
000
001
010
011
100
Variable-length
1
01
000
001 0
00 11
As seen in Code Mapping Table 1, a typical fixed length coding scheme assigns each character a unique fixed bit code, in this example a fixed, three bit code. Consequently, the 10,000 characters of the present example would require 30,000 bits to encode using the fixed length coding scheme of the Code Mapping Table 1.
As also seen in Code Mapping Table 1, a typical variable length coding scheme assigns each of the five unique characters a unique variable length code with frequently occurring characters, such as “a”, assigned short codes and infrequently occurring characters, such as “e”, assigned longer codes. In particular, “a” has been encoded with a single bit since it is the most frequently occurring character (4,100 occurrences). As discussed in more detail below, the most frequently occurring character is often referred to herein as the Most Probable Value (MPV). The next most frequently occurring characters, “b” and “c”, are represented by two bits and three bits, respectively, and “d” and “e” are represented by four bits since they are the least frequently occurring characters.
Using variable length coding, the decoding process involves receiving only a first bit and then checking this first bit with each code entry in Code Mapping Table 1 to see if the first bit comprises an allowed code. If the first bit does comprise an allowed code, the mapping is completed and the decoding process is over. However, if the first bit does not comprise an allowed code, a second bit is received, and the two bits in combination are checked with each code entry in Code Mapping Table 1 to determine if the combination of bits comprises an allowed code. This process is repeated for each new bit, with the combination of each new bit and all previously received bits being checked, with each code entry in Code Mapping Table 1 to determine if the combination of bits comprises an allowed code, until an allowed code is detected.
In the example above, using prior art variable length coding, 20,800 bits (4100*1+2600*2+1700*3+1200*4+400*4) were used to encode the entire file. Recall that using fixed length coding 30,000 bits were used. Consequently, despite its cumbersome nature, prior art variable length coding provides a significant savings of approximately 31.7% over fixed length coding. This is a significant improvement to say the least. However, there are several significant drawbacks to prior art variable length encoding schemes.
One significant drawback of variable length coding schemes is the cumbersome and time consuming nature of the decoding process. As discussed with respect to the example provided above, decoding involves receiving new bits one at a time and then, with each new bit received, checking the ensemble of received bits with each code entry of the code mapping table until a unique allowed code is received. Consequently, even for our simplified example, including only five unique characters, the variable length decoding process is long and cumbersome.
To make matters worse, in real systems the number of possible unique characters is typically much larger than our assumed five from above. Consequently, the code mapping table used, such as Code Mapping Table 1 discussed above, can become prohibitively large as the number of unique characters increases. Further, the average length of the codewords is also larger. As explained above, since each bit has to be checked with all the code entries in the code mapping table until a unique allowed code is received, this can become a significant problem. Once again, this is clearly a time consuming, inefficient and cumbersome process.
Other types of variable length coding schemes use variable-bit codes that start with a unary-encoded number (i.e. a sequence of zeroes where the value encoded is the number of zeroes). Golomb, Golomb-Rice, and adaptive prefix coding are all examples of variable-bit codes that start with a unary-encoded number. As discussed in more detail below, for certain implementations that employ a temporary buffer to assist in the extraction of bit sequences from a whole-byte data read in from the input device, the decoder can count the zeroes with less work than actually extracting each zero bit one at a time. For these variable bit codes, the number of zeroes can be used to deduce exactly how many bits you should read to get the next codeword. This provides a somewhat more efficient process than the Huffman type variable length decoding process described above, however, the process is still cumbersome and inefficient.
The problems discussed above with respect to prior art coding schemes were particularly pronounced since, using prior art schemes, each and every character was typically subjec

Affiliated with

Also associated with

Rating

Method of coding frequently occurring values does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of coding frequently occurring values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of coding frequently occurring values will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3166927