 |
Description  |
|
|
FIELD OF THE INVENTION
The present invention relates to the field of data compression and
decompression systems; particularly, the present invention relates to a
method and apparatus for parallel encoding and decoding of data in
compression/decompression systems.
BACKGROUND OF THE INVENTION
Data compression is an extremely useful tool for storing and transmitting
large amounts of data. For example, the time required to transmit an
image, such as a facsimile transmission of a document, is reduced
drastically when compression is used to decrease the number of bits
required to recreate the image.
Many different data compression techniques exist in the prior art.
Compression techniques can be divided into two broad categories, lossy
coding and lossless coding. Lossy coding involves coding that results in
the loss of information, such that there is no guarantee of perfect
reconstruction of the original data. The goal of lossy compression is that
changes to the original data are done in such a way that they are not
objectionable or detectable. In lossless compression, all the information
is retained and the data is compressed in a manner which allows for
perfect reconstruction.
In lossless compression, input symbols are converted to output codewords.
If the compression is successful, the codewords are represented in fewer
bits than the number of input symbols. Lossless coding methods include
dictionary methods of coding (e.g., Lempel-Ziv), run length encoding,
enumerative coding and entropy coding. For more information on run length
coding, see H. Meyr, H. G. Roskolsky, and T. S. Huang, "Optimum Run Length
Codes," IEEE Transactions on Communications, Vol. COM-22, No. 6, June
1974, pgs. 826-835. See also G. G. Langdon, Jr., "An Adaptive Run-Length
Coding Algorithm," IBM Technical Disclosure Bulletin, Vol. 26, No. 7B,
December 1983, pgs. 3783-3785 (A coding system using R2(k) codes for
dynamically variable k values is attributed to Langdon). See S. W. Golomb,
Run-Length Encoding, IEEE Trans., IT-12, (July 1966), pg. 399. For more
information regarding run length codes and their use in conjunction with
facsimile transmission, see M. Takagi and T. Tsuda, "A Highly Efficient
Run-Length Coding Scheme For Facsimile Transmission," Electronics and
Communications in Japan, Vol. 58-A, No. 2, 1975, pgs. 30-38. See also U.S.
Pat. No. 4,325,085, entitled "Method and Apparatus for Adaptive Facsimile
Compression Using a Two Dimensional Maximum Likelihood Predictor" (R. P.
Gooch), issued Apr. 13, 1982.
Entropy coding consists of any method of lossless (i.e., perfect
reconstruction is possible) coding which attempts to compress data close
to the entropy limit using known or estimated symbol probabilities.
Entropy codes include Huffman codes, arithmetic codes and binary entropy
codes. Huffman coding uses a fixed length to variable length code which
produces an integral number of bits for each symbol. However, Huffman
coding cannot code symbols with less than one bit and, thus, cannot
efficiently represent single symbols with probabilities of greater than
50%. Arithmetic coders are based on theoretical coding techniques
involving infinite precision floating point numbers. However, arithmetic
coders can only be implemented with finite precision arithmetic so their
coding efficiency is reduced from the theoretical maximum. Practical
arithmetic coders, such as the Q-coder of International Business Machines
(IBM), use additional techniques that result in faster software or less
hardware at the expense of compression efficiency. The Q-coder is a binary
arithmetic coder in which additions have been substituted for
multiplications, probabilities are limited to discrete values, and
probability estimates are updated when bits are output.
Binary entropy coders are lossless (i.e., perfect reconstruction is
possible) coders which act only on binary (yes/no) decisions, often
expressed as the most probable symbol (MPS) and the least probable symbol
(LPS). Examples of binary entropy coders include IBM's Q-coder and a coder
referred to as the B-coder. The B-coder is a binary entropy coder which
uses a finite state machine for compression. For more information on the
B-coder, see co-pending application Ser. No. 07/931,156, entitled "Method
and Apparatus For Entropy Coding" filed Aug. 17, 1992.
FIG. 1 shows a block diagram of a prior art compression/decompression
system using a binary entropy coder. For coding, data is input into
context model (CM) 101. CM 101 translates the input data into a set or
sequence of binary decisions and provides the context bin for each
decision. Both the sequence of binary decisions and their associated
context bins are output from CM 101 to the probability estimation module
(PEM) 102. PEM 102 receives each context bin and generates a probability
estimate for each binary decision. The actual probability estimate is
typically represented by a class, referred to as PClass. Each PClass is
used for a range of probabilities. PEM 102 also determines whether the
binary decision (result) is or is not in its more probable state (i.e.,
whether the decision corresponds to the MPS). The bit-stream generator
(BG) module 103 receives the probability estimate (i.e., the PClass) and
the determination of whether or not the binary decision was likely as
inputs. In response, BG module 103 produces a compressed data stream,
outputting zero or more bits, to represent the original input data.
For decoding, CM 104 provides a context bin to PEM 105, and PEM 105
provides the probability class (PClass) to BG module 106 based on the
context bin. BG module 106 is coupled to receive the probability class. In
response to the probability class, BG module 106 returns a bit
representing whether the binary decision (i.e., the event) is in its most
probable state. PEM 105 receives the bit, updates the probability estimate
based on the received bit, and returns the result to CM 104. CM 104
receives the returned bit and uses the returned bit to generate the
original data and update the context bin for the next binary decision.
The context model is typically application specific. Since any type of data
can be reduced to bits, a binary entropy coder with the proper context
model can be used for any data. An example of a context model is given by
the JBIG Standard (ISO/IEC International Standard, "Coded Representation
of Picture and Audio Information--Progressive Bi-level Image Compression
Standard").
"Model templates define a neighborhood around a pixel to be coded. The
values of the pixels in these neighborhoods, plus spatial phase in
differential layers, define a context." Another example of a context model
is given by the JPEG Standard (Digital Compression and Coding of
Continuous-tone Still Images. ISO/IEC International Standard).
Since the context model is application specific, general coders are built
by considering the probability estimation module and bit-stream generator
only. Some probability estimation modules and bit-stream generators can be
used interchangeably. Other probability estimation modules are dependent
specifically on one particular bit-stream generator. For instance, IBM
Q-coder is a combined probability estimation module and bit-stream
generator. The B-coder is only a bit-stream generator. Therefore, the
B-coder may be used with any probability estimation module.
One problem with decoders using binary entropy codes, such as IBM's Q-coder
and the B-coder, is that they are slow, even in hardware implementation.
Their operation requires a single large, slow feedback loop. To restate
the decoding process, the context model uses past decoded data to produce
a context. The probability estimation module uses the context to produce a
probability class. The bit-stream generator uses the probability class and
the compressed data to determine if the next bit is the likely or unlikely
result. The probability estimation module uses the likely/unlikely result
to produce a result bit (and to update the probability estimate for the
context). The result bit is used by the context model to update its
history of past data. All of these steps are required for decoding a
single bit. Because the context model must wait for the result bit to
update its history before it can provide the next context, the decoding of
the next bit must wait. Therefore, parallel decoding of a single coded
data stream does not occur in the prior art. It is desirable to decode
data in parallel in order to increase the speed at which compressed data
is decoded.
The present invention provides a lossless compression and decompression
system. The present invention also provides a simple decoder which
provides fast decoding. The present invention also provides a decoding
system which decodes data in parallel. The present invention also provides
an encoding system which encodes data such that it can be decoded in
parallel.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for encoding and
decoding data in parallel. The present invention provides a system for
decompressing a data stream having multiple bits. The system includes an
input channel that receives the data stream. The system also includes a
decoder which decodes each bit of the data stream, wherein at least two of
the codewords in the data stream are decoded at the same time, such that
the data stream is decoded in parallel.
In one embodiment, the present invention processes context bins in
parallel. In another embodiment, the present invention processes
probability classes in parallel.
In the present invention, coded data is supplied to many bit-stream
generators. In one embodiment, multiple channels are used. In another
embodiment, a single, non-interleaved channel is used. In another
embodiment, a single, interleaved channel is used.
The present invention provides the use of R-codes in conjunction with the
parallel decoding and encoding systems of the present invention. The
R-coder of the present invention uses R2(k) codes in conjunction with at
least one type of Rn(k) code, where n is a natural number. In one
embodiment, the R-coder of the present invention uses R2(k) and R3(k)
codes.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be understood more fully from the detailed
description given below and from the accompanying drawings of the
preferred embodiments of the invention which, however, should not be taken
to limit the invention to the specific embodiments, but are for
explanation and understanding only.
FIG. 1 is a block diagram of a prior art binary entropy encoder and
decoder.
FIG. 2A is a block diagram of a prior art decoder.
FIG. 2B is a block diagram of the decoder of the present invention.
FIG. 2C is a block diagram of the decoder of the present invention which
processes context bins in parallel.
FIG. 2D is a block diagram of the decoder of the present invention which
processes probability classes in parallel.
FIG. 3 is one example of a probability estimation table and bit-stream
generator for the R-coder of the present invention.
FIG. 4 is a graph of coding efficiency versus MPS probability.
FIG. 5 is a block diagram of the R-coder decompression system of the
present invention.
FIG. 6 is a block diagram of one embodiment of the R-coder of the present
invention.
FIG. 7 is a block diagram of an R-coder in the present invention.
FIG. 8 is one example of a circuit schematic of the control logic of an
R-coder according to the present invention.
FIG. 9 is one example of a schematic for a PEM for an R-coder.
FIG. 10 is one example of a schematic for the shifter, decoder and counter
of an R-coder.
FIG. 11 is a block diagram of a non-interleaved multi-channel parallel
architecture.
FIG. 12 illustrates a block diagram of a non-interleaved multi-channel
parallel decoding architecture.
FIG. 13 is a block diagram of a non-interleaved single channel parallel
architecture.
FIG. 14 illustrates a block diagram of a non-interleaved single channel
parallel decoding architecture.
FIG. 15 is an example of a concatenated code stream used in the present
invention.
FIG. 16 illustrates a block diagram of a non-interleaved single channel
parallel decoding architecture which uses an R-coder.
FIG. 17 illustrates a block diagram of one embodiment of an interleaved
parallel decoding system that processes context bins according to the
present invention.
FIG. 18 illustrates a block diagram of one embodiment of an interleaved
parallel decoding system that processes probability classes according to
the present invention.
FIG. 19 illustrates a block diagram of an interleaved parallel decoding
system that supports multiple requests simultaneously.
FIG. 20 is a block diagram of one embodiment of the parallel encoding
architecture of the present invention.
FIG. 21 is a block diagram of one embodiment of the snooper decoder of the
present invention.
FIG. 22 is a block diagram of one embodiment of the parallel encoding
architecture of the present invention.
FIG. 23 is a block diagram of a high bandwidth system using the present
invention.
FIG. 24 is a block diagram of a bandwidth matching system employing the
present invention.
FIG. 25 is a block diagram of a real-time video system using the present
invention.
DETAILED DESCRIPTION OF THE INVENTION
A method and apparatus for parallel encoding and decoding of data is
described. In the following description, numerous specific details are set
forth, such as specific numbers of bits, numbers of coders, specific
probabilities, types of data, etc., in order to provide a thorough
understanding of the preferred embodiments of the present invention. It
will be understood to one skilled in the art that the present invention
may be practiced without these specific details. Also, well-known circuits
have been shown in block diagram form rather than in detail in order to
avoid unnecessarily obscuring the present invention.
General Overview Of Parallel Decoding
The present invention provides a system which decodes losslessly encoded
data in parallel. This invention is based on the observation that the
bottleneck of most entropy compression systems is the feedback loop
between the context model and the decoder. In the present invention, this
loop is broken by dedicating coders to a given context bin, such that the
system speed is dictated only by the smaller, faster feedback loop within
the context model and the speed of codeword delivery to the system. The
present invention achieves the decoupling between the coders and the
context model through the recognition that the context model, in effect,
reorders a coded data stream into a number of different data streams, one
for each context bin. By having the coded data in order by context bin
rather than pure data stream order, the coders can decode any or all of
the coded data without waiting for feedback from the context model. (Note
that these streams could be created by probability class instead of or as
well as by context bin.)
FIG. 2A illustrates the traditional decoder with input buffer 201 coupled
to receive the coded data and a feedback signal from decoder 202. Input
buffer 201 feeds the coded data to decoder 202 according to the decoder's
request via the feedback signal. Decoder 202 decodes the coded data
according to its context and its probability estimate and supplies the
decoded data to context model 203 which outputs the decoded data. Once
decoder 202 sends the decoded data to context model 203, context model 203
is able to update the context and send the necessary information over a
feedback signal to decoder 202 to begin decoding the next bit. In turn,
decoder 202 requests more coded data from input buffers 201 using its
feedback signal. Thus, two feedback signals operate sequentially to decode
the coded data stream.
FIG. 2B illustrates the decoder of the present invention without the slow
feedback loop of the prior art. As in FIG. 2A, an input buffer 204
receives coded data (i.e., codewords) and a feedback signal from decoder
205 and supplies coded data in context bin order to decoder 205 of the
present invention, which decodes the coded data. Decoder 205 comprises
multiple decoders (e.g., 205A, 205B, 205C, etc.), one for each context
bin. Each of the decoders in decoder 205 is supplied coded data for its
corresponding context bin from input buffer 204. Each decoder 205A, 205B,
205C, etc. produces the decoded data for its context bin. The context
model is not required to associate coded data with a particular context
bin. The decoded data is sent by decoder 205 to decoded data storage 207
(e.g., 207A, 207B, 207C, etc.).
Operating independently, context model 206 is coupled to receive the
previously decoded data from decoded data storage 207 (i.e., 207A, 207B,
207C, etc.) in response to a feedback signal it sends to decoded data
storage 207. Therefore, two independent feedback loops exist, one between
decoder 205 and input buffer 204 and a second between context model 206
and decoder data storage 207. Since the large feedback loop is eliminated,
the decoders in decoder 205 (e.g., 205A, 205B, 205C, etc.) are able to
decode their associated codewords as soon as they are received from input
buffer 204.
The context model provides the memory portion of the coding system and
divides a set of data (e.g., an image) into different categories (e.g.,
context bins) based on the memory. In the present invention, the context
bins are considered independent ordered sets of data. In one embodiment,
each context bin has its own probability estimation model. Thus, each
context bin could use a different probability estimation model and/or
bit-stream generator. Also in another embodiment, where probability
estimation models are shared, each context bin can have its own state.
In the present invention, the context model divides the data (e.g., the
image) into several data streams. In other words, the context model
reorders a set of data or an image into multiple data streams, one for
each context bin. In one embodiment, individual coders are dedicated to a
given context bin.
By dedicating coders to a given context bin, the feedback loop between the
context model and the coder can be eliminated. The feedback is eliminated
because each coder does not need to receive an indication of the context
for the previous bit before it can be decoded since the previous bit came
from the same bin, i.e., it is the same context. In other words, there is
no context feedback that must be completed before the next bit can be
decoded.
The present invention delivers the separate coded data streams from each
context bin in parallel, such that the bits for all of the context bins
are received by the bit-stream generators in parallel. Each of the
bit-stream generators returns a bit representing whether the binary
decision is in its more probable state, which the probability estimation
module uses to return decoded bits (i.e., the binary decision). The
context model produces a decoded data stream by selecting the decoded bits
from the bit-stream generators in the proper sequence, thereby recreating
the original data. That is, the context model simply chooses the decoded
results from the different codestreams in a manner similar to that of a
multiplexer. Therefore, by having the coded data stream in order by
context bin (or class) rather than in a specific order (e.g., raster
scan), the coders can decode the coded data corresponding to any or all
context bins without waiting for the feedback from the context model. It
should be noted that the probability estimation model is not eliminated by
the present invention, i.e. a probability estimation feedback loop
remains.
Numerous implementations exist for the parallel decoding systems of the
present invention. In one embodiment, the coded data streams corresponding
to the multiple context bins can be interleaved into one stream ordered by
the demands of the various coders. In the currently preferred embodiment
of the present invention, the coded data is ordered such that each coder
is constantly supplied with data even though the coded data is delivered
to the decoder serially.
By using small simple coders that can be cheaply replicated in integrated
circuits, coded data can be decoded quickly in parallel. In one
embodiment, the coders are implemented in hardware using field
programmable gate array (FPGA) chips or a standard cell application
specific integrated circuit (ASIC) chip. The combination of parallelism
and simple bit-stream generators allow the decoding of coded data to occur
at speeds in excess of the prior art decoders, while maintaining the
compression efficiency of the prior art decoding systems.
Binary entropy codes use multiple context bins and multiple probability
estimate states (classes). The method and apparatus of the present
invention allow parallelism to process context bins in parallel or handle
probability classes in parallel. When processing context bins in parallel,
a probability estimation module is associated with each bit-stream
generator. It indicates to its associated bit-stream generator which code
to utilize to produce a data stream from the input codewords. An example
of such a system is shown in FIG. 2C where coded data is coupled as an
input to channel control 221. Channel control 221 receives the coded data
and directs coded data to each of multiple bit-stream generators (e.g., BG
222, BG 223, BG 224, etc.). Each of the bit-stream generators is coupled
to receive the coded data and provides the result of whether the codeword
was in its most likely state or not to its associated probability
estimation module, in response to the probability class provided by the
probability estimation module (PEM). PEMs 225, 226, 227, etc. are coupled
to BGs 222, 223, 224, etc. respectively. Each bit-stream generators can
operate independently of the others because it is decoding coded data
which always has the same context bin. The context model 228 is coupled to
each of the probability estimation modules and selects the probability
estimation modules to obtain the decoded data in the determination order
of the application. In this manner, decoded data is produced by processing
context bins in parallel.
On the other hand, when handling probability classes in parallel, the
context model and probability estimation model are combined. In this case,
each bit-stream generator is assigned to a specific probability class and
receives knowledge of the result. An example of a system which handles
probability classes in parallel is shown in FIG. 2D. Referring to FIG. 2D,
the coded data stream is coupled to channel control 231 for directing to
one of multiple bit-stream generators (e.g., BG 232, BG 233, BG 234,
etc.), which are coupled to receive it. Each of the bit-stream generators
is coupled to PEM 235. PEM 235 is also coupled to CM 236. In this
configuration, each of the bit-stream generators decodes coded data and
the results of the decoding are selected by PEM 235 (instead of by CM
236). Each of the bit-stream generator receives coded data from a source
associated with one probability class (i.e., where the coded data could
from any context bin). PEM 235 selects the bit-stream generators using a
probability class. The probability class is dictated by the context bin
provided to it by CM 236. In this manner, decoded data is produced by
processing probability classes in parallel. Thus, the present invention
provides for decoding data that is encoded using a coding scheme that
includes context and probability as attributes.
By processing contexts and probability classes in parallel, the serial
ordering of the code stream required in prior art decoders is avoided.
Note that the present invention operates with all types of data, including
image data.
Types Of Codes and Bit-Stream Generators For Parallel Decoding
The present invention could employ existing coders, such as Q-coders or
B-coders, as the bit-stream generation elements which are replicated in
parallel. However, other codes and coders may be used. The coders and
their associated codes employed by the present invention are simple
coders.
In the present invention, using a bit-stream generator with a simple code
instead of complex code, such as the arithmetic code used by the Q-coder
or the multi-state codes used by the B-coder, offers advantages. A simple
code is advantageous in that the hardware implementation is much faster
and simpler and requires less silicon than a complex code. Another
advantage is that decoding efficiency can be improved. A code that uses a
finite amount of state information cannot perfectly meet the Shannon
entropy limit for every probability. Codes that allow a single bit-stream
generator to handle multiple probabilities or contexts require constraints
that reduce coding efficiency. Removing the constraints needed for
multiple contexts or probability classes allows the use of codes that
comes closer to meeting the Shannon entropy limit.
Two codes which may be used in the parallel decoding schemes of the present
invention are R-codes and A-codes.
R-codes
The code (and coder) employed by the currently preferred embodiment of the
present invention is referred to as an R-codes. R-codes are adaptive codes
which include Golomb run length codes (i.e., R2(k) codes). In the
currently preferred embodiment, the R-codes are parameterized so that many
different probabilities can be handled by a single decoder design.
Moreover, the R-codes of the present invention can be decoded by simple,
high-speed hardware.
In the present invention, R-codes are used by an R-coder to perform
encoding or decoding. In the currently preferred embodiment, an R-coder is
a combined bit-stream generator and probability estimation module. For
instance, in FIG. 1, an R-coder could include the combination of
probability estimation module 102 and bit-stream generator 103 and the
combination of probability estimation module 105 with bit-stream generator
106.
Codewords represent runs of the most probable symbol (MPS). A MPS
represents the outcome of a binary decision with more than 50%
probability. On the other hand, the least probable symbol (LPS) represents
the outcome in a binary decision with less than 50% probability. Note that
when two outcomes are equally probable, it is not important which is
designated MPS or LPS as long as both the encoder and decoder make the
same designation. The resulting bit sequence in the compressed file is
shown in Table 1, for a given parameter referred to as MAXRUN.
TABLE 1
______________________________________
Bit-generation Encoding
Codeword Meaning
______________________________________
0 MAXRUN Consecutive MPSs
1N N Consecutive MPSs followed by
LPS, N < MAXRUN
______________________________________
To encode, the number of MPSs in a run are counted by a simple counter. If
that count equals the MAXRUN count value, a 0 codeword is emitted into the
codestream and the counter is reset. If an LPS is encountered, then a 1
followed by the bits N, which uniquely describe the number of MPS symbols
before the LPS, is emitted into the codestream. (Note that there are many
ways to assign the N bits to describe the run length). Again the counter
is reset. Note that the number of bits needed for N is dependent on the
value of MAXRUN. Also note that the 1's complement of the codewords could
be used.
To decode, if the first bit in the codestream is 0, then the value of
MAXRUN is put in the MPS counter and the LPS indication is cleared. Then
the 0 bit is discarded. If the first bit is a 1, then the following bits
are examined to extract the bits N and the appropriate count (N) is put in
the MPS counter and the LPS indicator is set. Then the codestream bits
containing the 1N codeword are discarded.
R-codes are generated by the rules in Table 1. Note that the definition of
a given R-code Rx(k) is defined by the MAXRUN. For instance:
MAXRUN for Rx(k)=x*2.sup.k-1,
thus
MAXRUN for R2(k)=2*2.sup.k-1, MAXRUN for R3(k)=3*2.sup.k-1, etc.
Note that R-codes are an extension of Golomb codes. Golomb codes use R2()
codes only. The R-codes of the present invention allow the use of both
R2(k) and R3(k) codes, and other Rn(k) codes if desired. In one
embodiment, R2(k) and R3(k) codes are used. Note that Rn exists for n=2
and n equals any odd number (e.g., R2, R3, R5, R7, R9, R11, R13, R15). In
one embodiment, for R2(k) code, the run count, r, is encoded in N; the run
count, r, is described in k bits, such that 1N is represented with k+1
bits. Also in one embodiment, for an R3(k) code, the bits N can contain 1
bit to indicate if n<2.sup.(k-1) or n.gtoreq.2.sup.(k-1) and either k-1 or
k bits to indicate the run count, r, such that the variable N is
represented by a total k or k+1 bits respectively. In other embodiments,
the 1's complement of N could be used in the codeword. In this case, the
MPS tends to produce code streams with many 0s and LPS tends to produce
code streams with many 1s.
Tables 2, 3, 4 and 5 depict some efficient R-codes utilized for the current
preferred embodiment of the present invention. It should be noted that
other run length codes may also be used in the present invention. An
example of alternative run length code for R2(2) is shown in Table 6.
TABLE 2
______________________________________
R2(0)
p(0) = 0.500
uncoded data codeword
______________________________________
0 0
1 1
______________________________________
TABLE 3
______________________________________
R2(1)
p(0) = 0.707
uncoded data codeword
______________________________________
00 0
01 10
1 11
______________________________________
TABLE 4
______________________________________
R3(1)
p(0) = 0.794
uncoded data codeword
______________________________________
000 0
001 100
01 101
1 11
______________________________________
TABLE 5
______________________________________
R2(2)
p(0) = 0.841
uncoded data codeword
______________________________________
0000 0
0001 100
001 101
01 110
1 111
______________________________________
TABLE 6
______________________________________
Alternative
R2(2)
______________________________________
0000 0000
0001 111
001 101
01 110
1 100
______________________________________
Probability Estimation Model for R-Codes
In the currently preferred embodiment, the R2(0) code performs no coding:
an input of 0 is encoded into a 0 and an input of 1 is encoded into a 1
(or vice versa) and is optimal for probabilities equal to 50%. In the
currently preferred embodiment, an R3(0) code is not utilized. The R2(1)
code of the currently preferred embodiment is optimal for probabilities
equal to 0.707 (i.e., 70.7%) and the R3(1) is optimal for the 0.794
probability (79.4%). The R2(2) code is optimal for the 0.841 probability
(84.1%). Table 7 below depicts the near-optimal Golomb code, where the
probability skew is defined by the following equation:
Probability skew=-log.sub.2 (LPS).
TABLE 7
______________________________________
probability
probability skew
Best Golomb Code
______________________________________
.500 1.00 R2(0)
.707 1.77 R2(1)
.841 2.65 R2(2)
.917 3.59 R2(3)
.958 4.56 R2(4)
.979 5.54 R2(5)
.989 6.54 R2(6)
.995 7.53 R2(7)
.997 8.53 R2(8)
.999 9.53 R2(9)
______________________________________
Note that the codes are near-optimal in that the probability range, as
indicated by the probability skew, is covering the space relatively evenly
even though the optimal probabilities do not differentiate as much in the
higher k values as in the lower k values.
An R2(k) for a fixed k is called a Golomb run-length code. However, a fixed
k is only near-optimal for a fixed probability. It is noted that when
coding at an optimal probability, an R-code according to the present
invention uses a 0 and 1N codewords with equal frequency. In other words,
half the time, the R-coder of the present invention outputs one code and
the other half of the time, the R-coder outputs the other. By examining
the number of 0 and 1N codewords, a determination can be made as to
whether the best code is being used. That is, if too many 1N codewords are
being output, then the run-length is too long; on the other hand, if too
many 0 codewords are being output, then the run length is too short.
The probability estimation model used by Langdon examines the first bit of
each codeword to determine whether the source probability is above or
below the current estimate. Based on this determination, k is increased or
decreased. For example, if a codeword indicating MPS is seen, the
probability estimate is too low. Therefore, according to Langdon, k is
increased by 1 for each 0 codeword. If a codeword indicating less than
MAXRUN MPS followed by an LPS is seen, the probability estimate is too
high. Therefore, according to Langdon, k is decreased by 1 for each 1N
codeword.
The present invention allows more complex probability estimation than the
simple increase or decrease of k by 1 every codeword. The present
invention includes a probability estimation module state that determines
the code to use. Many states may use the same code. Codes are assigned to
states using a state table or state machine.
In the present invention, the probability estimate changes state every
codeword output. Thus, in the present invention, the probability
estimation module increases or decreases the probability estimate
depending on whether a codeword begins with a 0 or a 1. For instance, if a
"0" codeword is output, an increase of the estimate of the MPS probability
occurs. On the other hand, if a "1" codeword is output, the estimate of
MPS probability is decreased.
The Langdon coder of the prior art only used R2(k) codes and increased or
decreased k for each codeword. The present invention, alternatively, uses
R2(k) and R3(k) codes, in conjunction with the state table or state
machine, to allow the adaptation rate to be tuned to the application. That
is, if there is a small amount of stationary data, adaptation must be
quicker to result in more optimal coding, and where there is a larger
amount of stationary data, the adaptation time can be longer so that the
coding can be chosen to achieve better compression on the remainder of the
data. Note that where variable numbers of state changes can occur,
application specific characteristics may also influence the adaptation
rate. Because of the nature of the R-codes, the estimation for R-codes is
simple and requires little hardware, while being very powerful.
The incorporation of the R3(k) codes allows more probability space to be
covered with a finer resolution. An example probability estimation state
table according to the present invention is shown in FIG. 3. Referring to
FIG. 3, the probability estimation state table includes both a state
counter and the code associated with each of the separate states in the
table. Note that the table includes both positive and negative states. The
table is shown having 37 positive state and 37 negative states, including
the zero states. The negative states signify a different MPS than the
positive states. In one embodiment, the negative states can be used when
the MPS is 1 and the positive states can be used when the MPS is 0, or
vice versa. Note that the table shown in FIG. 3 is an example only and
that other tables might have more or less states and a different state
allocation.
Initially, the coder is in state 0 which is the R2(0) code (i.e., no code)
for probability estimate equal to 0.50. After each codeword is processed,
the state counter is incremented or decremented depending on the first bit
of the codeword. In the currently preferred embodiment, a codeword of 0
increases the magnitude of a state counter; a codeword stating with 1
decreases the magnitude of the state counter. Therefore, every codeword
causes a change to be made in the state by the state counter. In other
words, the probability estimation module changes state. However,
consecutive states could be associated with the same code. In this case,
the probability estimation is accomplished without changing codes every
codeword. In other words, the state is changed every cycle; however, the
state is mapped into the same probabilities at certain times. For
instance, states 5 to -5 all use the R2(0) code, while states 6 through 11
and -6 through -11 use the R2(1) code. Using the state table of the
present invention, probability estimation is allowed to stay with the same
coder in a non-linear manner.
It should be noted that more states with the same R-code are included for
the lower probabilities. This is done because the loss of efficiency when
using the wrong code at low probabilities is great. The nature of the run
length codes state table is to transfer between states after each
codeword. In a state table designed to change codes with every change in
state, when toggling between states at the lower probabilities, the code
toggles between a code which is very close to the entropy efficiency limit
and code whic | | |
