An Entropy Coding Based on Binary Encoding for Mixed-Radix Digits
Na Wang, Wei Yan, Sian-Jheng Lin, Yuliang Huang · 2022
In the conventional range asymmetric numeral systems (rANS), state$x$becomes larger after encoding a symbol$s$. In contrast, the proposed scheme directly outputs an$n$-bit digit$cdf_{s}+x\ (\text{mod}\ f_{s})$for symbol$s$, and decrease$x$via$x\leftarrow\lfloor x/f_{s}\rfloor$, where$2^{n}$denotes the denominator of the quantized frequency distribution,$f_{s}$and$cdf_{s}= \sum olimits_{i=0}^{s-1}f_{i}$represent the frequency of symbol$s$and the cumulative frequency counts, respectively. Therefore,$x$will become too small after encoding several symbols. To solve this issue, our proposal forces the state$x$always at a specific interval$I= [2^{T-vn}, 2^{T})$, and$I_{s}:=\left[f_{s}\times 2^{T-vn}, 2^{T}\right)$indicates the interval corresponding to symbol$s$, where$T, v\in \mathbb{N}$. The specific algorithm can be implemented based on the deque. Precisely, for a symbol$s$to be encoded, if the current$x$is within$I_{s}$, we encode it to an$n$-bit digit$cdf_{s}+x\ (\text{mod}\ f_{s})$and push the digit to deque. Otherwise, we first pop data from the deque to enlarge$x$before encoding. Finally, the remaining data in the deque is the desired encoded bit sequence.