Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
1999-02-01
2001-07-10
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
Reexamination Certificate
active
06259388
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an arithmetic coding technique, and more particularly, to an arithmetic coding technique with low computational complexity and a low cost hardware implementation.
2. Description of the Related Art
The compression of data into fewer bits is often utilized in order to achieve a desired rate of data of transfer or to store data in a limited memory space. Some time after the data is compressed, the original data is to be retrieved by decompressing the originally compressed data.
Arithmetic coding is one technique for achieving data compression and decompression. In arithmetic coding, one decision after another is encoded to define successively smaller, lesser-included intervals along a number line. Arithmetic coding provides that each decision has a plurality of possible exclusive outcomes or events. Each outcome or event is represented by a symbol.
In accordance with prior art arithmetic coding teachings, a probability line has a current interval defined therealong. The first current interval is 0 to 1. The current interval is divided into segments in which each segment corresponds to one possible outcome for the next decision. Where there are only two possible outcomes for each decision, the current interval is divided into two segments. The length of each segment is based on its respective associated probability. The respective probabilities may remain fixed or may adapt as decision data is entered.
The power of arithmetic codes resides in the compression they achieve and the flexibility of arithmetic codes resides in their ability to encode strings modeled by stationary or non-stationary sources with equal ease. Arithmetic codes permit encoding of binary strings without the need for alphabetic extension, and also encode strings with symbols drawn from alphabets containing more than two characters.
An arithmetic code updates the probability P(s) of a so-far processed source string s, by the multiplication P(s)*P(i/s) where P(i/s) is a conditional probability of the symbol i given s. The multiplication required for augmenting the probability is relatively expensive and slow, even in the case where the probabilities are represented by binary numbers having at most a fixed number of significant digits.
U.S. Pat. No. 4,467,317 implements a recursive technique which simplifies the encoding operation of a binary symbol stream by approximating the probability of a less probable signal (LPS) with an integral power of one-half. However, this technique is not easily generalized to non-binary alphabets because n-ary alphabet symbol probabilities cannot be accurately approximated as powers of one-half. This limitation is significant in view of the growing parallelism in data structures and operations in present day processors. Further, the recursive technique depends upon the existence of a sophisticated modeling unit capable of calculating and providing source statistical characteristics. Implicit in the calculation of source statistical characteristics is a default of a skew number calculation operation to the modeling unit, an operation which adds to the complexity of the overall data compression problem.
U.S. Pat. No. 4,652,856 discloses an arithmetic coding technique which is capable of coding a multi-character alphabet, without multiplication or division in order to generate a binary code stream in response to simplified data source statistical characteristics that preserve the very desirable property of concurrent updating of the both the code stream and an internal coding variable. The 4,652,856 Patent is based upon an encoding algorithm that accepts symbol occurrence counts in binary form, subjects those counts to simple magnitude shift operations to approximate the contextual probability of each symbol of the symbol stream, augments the coded stream, and then simultaneously locates the w least significant bits of the code stream and adjusts the value of an internal coding variable determinant of the next coding sub-interval in response to one of the shifted occurrence counts.
Arithmetic coding is a statistical compression method and thus must work with a model that estimates the probability of each possible symbol in the modeled source. The model can be fixed, semi-fixed or adaptive. A fixed model has a probability distribution P
1
, P
2
, . . . , p
n
, where
1
,
2
, . . . , n are the symbols in the modeled source.
Arithmetic coding works based upon a interval transformation, which transforms one interval [l
k
, h
k
) into another interval [l
k
+
1
, h
k
+
1
), provided that a symbol i is encoded, where
l
k
+
1
=
l
k
+
r
k
∑
j
=
0
i
-
1
P
j
(
1
)
h
k
+
1
=
l
k
+
r
k
∑
j
=
0
i
P
j
(
2
)
r
k+1
=h
k+1
−l
k+1
(3)
r
k
denotes the range of the interval [l
k
, h
k
). Initially, the encoder starts with the unit interval [
0
,
1
). This implies l
0
=0, h
0
=1, r
0
=1.
Arithmetic encoding cannot be implemented on a finite precision computer, since all operations involved in equations (1)-(3) are floating-point math. However, it turns out, arithmetic coding can be best accomplished using standard 16-bit and 32-bits integer operations, Floating-point math is neither required nor helpful. What is required is an incremental transmission scheme.
As a simple example consider the case for n=2, i.e., a binary source employing a 0-order Markov model to estimate the probabilities p
0
and P
1
. In this example, equation (1), (2) and (3) can be simplified to
r
k+1
=r
k
P
0
, for i=0 (4)
l
k+1
=l
k
+r
k
p
0
,r
k+1
=r
k
P
1
, for i=1 (5)
where i is the so far encoded symbol.
For a practical implementation of equation (4) and (5), p
0
and p
1
is replaced with frequency counts c
0
and c
1
, which may be adaptively adjusted during the encoding process.
p
0
=c
0
/(c
0
+c
1
),p
1
=c
1
/(c
0
+c
1
) (6)
In conventional designs for arithmetic coding, the encoder uses two registers of size 16 bits, L and R, to store the fraction value of l
k
and r
k
respectively. Combining (4), (5) and (6) yields
L:=L, R:=Rc
0
/(c
0
+c
1
),i=0 (7)
L:=L+Rc
0
/(c
0
+c
1
), R:=Rc
1
/(c
0
+c
1
),i=1 (8)
where m-bits integer operations are involved, and m-bits integer rounding is used (where m is a typical hardware register size, such as 8, 16, or 32). Most algorithms now available are based upon equation (7) and (8) or their variations. Note that equations (7) and (8) include integer multiplications and divisions and therefore, are not suitable for hardware design, such as digital signal processor (DSP) and Smart card implementations, where no division instruction is available.
SUMMARY OF THE INVENTION
The present inventions provides an arithmetic coding implementation for bit-level arithmetic coding. The present invention performs arithmetic coding without multiplications and divisions. In particular, the encoding and decoding performed in the present invention receives frequency counts, namely, a frequency count representing a fractional value of the probability of 0, a frequency count representing the fractional value of the probability of 1, and the so-far encoded symbol, in order to encode/decode subsequent symbols.
The present invention also eliminates the need for conventional carry over techniques, such as bit stuffing. In the present invention, a magnitude determination is not necessary and the value of the register is adjusted before encoding a bit, whereas in conventional designs which require a magnitude determination, the bit is encoded before adjusting the value of the register.
In the present invention, the initial values of the two registers are set to 1 and random, in contrast to 2
m−1
or 2
m−1
and 0. As a result, the first word in the output stream can be used to denote synchro
Lucent Technologies - Inc.
Williams Howard L.
LandOfFree
Multiplication-free arithmetic coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiplication-free arithmetic coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplication-free arithmetic coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2465581