Binary Arithmetic Coding System with Adaptive Probability Estimation by “Virtual Sliding Window” презентация

Window”

Eugeniy Belyaev
Marat Gilmutdinov
Andrey Turlikov

estimation
Buffer with W cells is used for keeping W last processed symbols. W is window length
Frequencies of symbols are calculated basing on buffer content

estimation for xt encoding

Estimation by Krichevsky-Trofimov formula:

…

symbol xt encoding by arithmetic encoder

Step 3: Modification of sliding window content

xt

xt-W

Finite State Machine with 2W states

xt-2

xt-3

xt-W+2

xt-W+1

…

for buffer of sliding window
Necessity to store individual buffers with W cells for each context model
Frequent context model changing is critical for memory cache
Critical for DSP application

n-state finite-state estimation procedure

1996 – B.Y.Ryabko
Randomization procedure;
Imaginary Sliding Window (ISW)
Non-binary case

1996 – A.Zandi, G.G.Langdon
Randomization procedure;
Binary case

2004 – E.Meron, M.Feder
Avoiding randomization procedure in
Imaginary Sliding Window (ISW)

states
Method does not require to store buffer for previously processed data
Random variable is used to estimate value of symbol xt-w removed from the sliding window

sliding window algorithm (exception: ISW uses evaluation of St for probability estimation)
Step 3: Modification of St evaluation.

yt – random binary value

Randomized Finite State Machine with W+1 states

the encoder and decoder sizes

cell (removed from sliding window)

Disadvantage – float point operation with St

E.Meron, M.Feder (2004)

of random values;
float-point operations with St calculation

Coding

Non-binary
data

Arithmetic Coding

bitstream

Binarization of value Q (simplified scheme):

P-frames

Non-Regular Initialization of P-frames