Arithmetic decoding of an arithmetically encoded information...

Details Arithmetic decoding of an arithmetically encoded information... Arithmetic decoding of an arithmetically encoded information...

2001-10-25

2003-06-17

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

C341S050000, C341S051000

Reexamination Certificate

active

06580379

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to a method of arithmetically decoding an arithmetically encoded information signal into an information signal comprising a serial sequence of n-bit symbols, where n is an integer and n=1, the method comprising the steps of:
(a) receiving the arithmetically encoded information signal,
(b) retrieving from finite-size first and second registers values for an A and a C parameter respectively, the A parameter having a relationship with the size of a value interval, the C parameter having a relationship with a boundary of said interval,
(c) generating at least one probability value for an associated symbol to be decoded,
(d) deriving a symbol in response to the said at least one probability value, and in response to the values for A and C retrieved from said first and second registers, respectively,
(e) updating at least the A parameter in order to obtain the new size of the interval for decoding the next symbol of the information signal,
(i) outputting the decoded symbol,
(j) as the case may be,
renormalizing the updated A parameter so as to obtain a renormalized A parameter, and
updating the C parameter so as to obtain an updated C parameter,
(k) storing the A parameter and the C parameter obtained in step (j) in the first register and the second register, respectively.
The invention also relates to an apparatus for decoding the arithmetically encoded information signal.
BACKGROUND OF THE INVENTION
The method defined in the opening paragraph is known from WO 99/49579 (PHN 16.822). Arithmetic coding is a well-known technique for lossless coding and an introduction can be found in any current source-coding book. For a thorough understanding of the implementations of arithmetic coding that are most relevant for the current work, the reader is referred to [Lang84]. The history of arithmetic coding is comprehensively described in the appendix of said document.
The known method sequentially decodes symbols retrieved from the encoded information signal so as to obtain decoded symbols.
SUMMARY OF THE INVENTION
The implementation of arithmetic coding that is the subject of the present invention uses two finite-size registers, which are usually called C and A. The decoder flow diagram is shown in FIG.
1
.
FIG. 2
shows the flow diagram for the “Output symbol . . . ” block shown in
FIG. 1
, for the case binary symbols have to be decoded. MPS and LPS are the most probable symbol and least probable symbol, respectively. Parameter p is the probability of the LPS. The value of the bit that is decoded is put in b.
FIG. 3
shows a flow diagram of the decoder block denoted “Renormalize . . . ”in FIG.
1
. The blocks in the decoder flow diagram in
FIG. 1
are normally implemented in dedicated hardware to enable the received information to be decoded signal real-time.
FIG. 1
shows a loop. When the decoding process executes the loop one time, one decoded symbol is outputted. The time needed to obtain one decoded symbol depends on the time needed to execute the three operations in the loop shown in FIG.
1
. The execution of an operation should not be started until the execution of a previous operation in the loop has been finalized. To decrease the execution time, the decoder is implemented in dedicated hardware. In a software implementation the execution time of the “Renormalize A . . . ” block is related to the value of the A parameter.
FIG. 3
shows that depending on the value of A, the loop has to be executed a number of times. For example, for the application of SACD, the maximum number of times the loop may be executed is seven times. However, when implemented in dedicated hardware, the execution time is related to the worst case situation and thus to the situation the loop has to be executed that the maximum number of times. Since the worst case situation occurs only a few times in the decoding process, the “Renormalize A . . . ” block is a limiting factor for the time needed to sequentially obtain one decoded symbol.
The invention aims at improving for the above-described arithmetic decoders. In accordance with the invention, the method of arithmetically decoding an arithmetically encoded information signal into an information signal comprising a serial sequence of n-bit symbols, n being an integer for which n≧1, the method being adapted to obtain two subsequent output symbols from the information signal in one decoding cycle, comprises the steps of:
(a) receiving the arithmetically encoded information signal,
(b) retrieving from finite-size first and second registers values for an A and a C parameter respectively, the A parameter having a relationship with the size of a value interval, the C parameter having a relationship with a boundary of said interval,
(c) generating a first probability value for a first symbol to be decoded, said first probability value indicating the probability that the first symbol has a least probable value, and generating a second probability value for a subsequent symbol to be decoded, said second probability value indicating the probability that the second symbol has the least probable value, the first symbol to be decoded being assumed to have the most probable value,
(d) deriving the first symbol in response to the said first probability value, and in response to the values for A and C retrieved from said first and said second registers, respectively,
(e) updating the A parameter so as to obtain an updated A parameter,
(f) updating the value for A retrieved from said first register to a value for a temporary A parameter, using the assumption that the first symbol obtained from decoding has the most probable value,
(g) deriving a temporary C parameter from the C parameter retrieved from said second register,
(h) deriving the second symbol in response to the said second probability value, and in response to the values of the temporary A parameter and the temporary C parameter,
(i) outputting both the first and the second symbol when the first symbol has the most probable value or outputting the first symbol only if the first symbol has the least probable value,
(j) deriving new A and C parameters,
(k) storing the new A and C parameter in the first and second register, respectively.
The invention is based on the following recognition. At the beginning of the execution of the loop the value of the A parameter is ≧½ and <1. The probability value for the first symbol to be decoded being a least probable symbol value, p
1
≦½. When assuming that the first symbol to be decoded has the most probable symbol value, the next value of the A parameter, according to the flow diagram in
FIG. 2
, will be A−Z, wherein Z=A * p
1
. Thus, the next value of A=A * (1−p
1
) and therefore ¼≦ the next value of A<1. This means that when the first symbol to be decoded has the most probable symbol value, the loop in the “Renormalize A . . . ” block has to be executed at most once. The time to execute this “Renormalize A . . . ” function in dedicated hardware will be much shorter than the time to execute the “Renormalize A . . . ” function when decoding only one symbol per decoding cycle, which execution time depends on the maximum number of times the loop in said function could be executed. Thus, in the case that the first output symbol of two subsequent output symbols has the MPS value, the time required to obtain said subsequent output symbols will be shorter than the time required to obtain each of the output symbols sequentially by decoding one output symbol per decoding cycle according to the prior art decoding method.
Therefore, in accordance with the invention, the prior-art decoding method in which one output symbol per decoding cycle is obtained is performed and a method in which two output symbols per decoding cycle are obtained, assuming that the first symbol to be decoded has the most probable value is performed in parallel. Depending on the symbol value of the first decoded symbol one or two decoded symbols will be obtained per decoding cycle.

Affiliated with

Also associated with

Rating

Arithmetic decoding of an arithmetically encoded information... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arithmetic decoding of an arithmetically encoded information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic decoding of an arithmetically encoded information... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3101500