Video Coding in H.26L Kristofer Dovstam, April 2000
14
Figure 1.2a, the interval [0.35, 0.5) is unique for the message ac. Now, the rest of the symbols
will be encoded in the same manner within the interval [0.35, 0.5) and so on. The same
process in each step assures that the message “seen so far” always can be uniquely
represented. More probable symbols will reduce the size of the interval less, adding fewer bits
to the message. The longer the message, the finer the last interval becomes and the more bits
are needed to represent it. When we have reached the last symbol b, the message acab is
represented by the interval [0.3875, 0.4025). However, it is not necessary for the decoder to
know both ends of the interval, a number lying in the interval will suffice, such as 0.4 or
0.3879 or even 0.401345978. For decoding it is also necessary to have knowledge of the
source model, i.e. the symbols and probabilities in Table 1.1a.
The decoding process is essentially a reversed encoding process. However, during
decoding we are faced with a problem; how do we know when to stop decoding? Indeed, any
real number in between 0 and 1 could represent an infinitely long message, since it is always
possible to divide an interval into new subintervals. This problem is solved by adding an end
of message symbol to the alphabet that will be used
only
to terminate messages. When the
decoder encounters the end of message symbol, it knows that the entire message has been
decoded and stops decoding. In the example above, we could choose b to be our end of
message symbol.
Another approach to solving the problem of knowing when to stop decoding is to make
use of contexts. For a particular information source it may be clear within different contexts
how many symbols are to be encoded and decoded. If this is the case, the decoder knows from
the context when to stop decoding, and does not need an end of message symbol. Let us say,
for instance, that the encoder and decoder agree to send messages with only three symbols.
Then, when the decoder in the example above has determined the first three symbols aca, it
knows that it is time to stop decoding and there is no need for the terminating b.
When arithmetic coding is implemented on a computer, the number representing the
message is in turn binary represented and sent to the decoder as a bit-stream. There are two
concerns, however, regarding the implementation of arithmetic coding on a computer. First of
all, not very much of a message need to be encoded before the interval [0,1) has been divided
into a sub-interval too small to be represented on a state of the art computer. Therefore, we
need to decide the precision to which the arithmetic coding is performed. Second, the scheme
described above encodes the entire message before any bits are sent to the decoder. This is not
acceptable in a real time environment, which calls for incremental transmission and reception.
Incremental transmission is easily implemented by realizing that the first decimal in the
two numbers forming the interval that represents the message will not change after a series of
symbols have been encoded. For instance, if the interval representing the message so far is
[0.358, 0.364), we know that the entire message will be represented by a number starting with
0.3... and so, we can send information about the 0.3 and concentrate on the interval [0.058,
0.064). The latter interval forces us to look at one or more of the following symbols in the
message to see if the next decimal is a 5 or a 6. In the computer, the procedure is performed
using binary representation, i.e. with base 2 instead of base 10.
The problem concerning precision in the encoder is solved by periodically normalizing, or
scaling the interval representing the message. In the procedure above, after sending
information about the 0.3, the interval is scaled, or multiplied by 10 to form the interval [0.58,
0.64). The interval is multiplied by 10 because that is the base of the representation, and
hence, in a computer using binary representation, the interval is instead multiplied by 2.