Fast Adaptive Binary Arithmetic Coding (M Coder)

The so-called M coder [1] is a fast adaptive binary arithmetic coding scheme. It replaces the computational critical multiplication in the interval subdivision of binary arithmetic coding with a table lookup. Probability estimation is performed by employing a finite-state machine with tabulated transition rules. For approximately uniformly distributed symbols, an optional bypass of the probability estimator results in an additional speed-up.

A block diagram of the M coder is depicted below. The coding interval is represented by its lower boundary L and its width R. For the encoding of a bin, the coding interval is subdivided into two subintervals. One of width RLPS and one of width R - RLPS.

Instead of using a costly, but precise multiplication for the derivation of RLPS, a fast, but less precise table lookup is employed. The coding interval width R is quantized to an index RIDX. The probability estimate of the bin to be encoded is given as a probability index, which is used together with RIDX to carry out the table-based interval subdivision by looking up a value for RLPS in a 2D lookup table. Depending on the value of the bin, one of the two subintervals is selected and forwarded to the renormalization and bit writing stage. Renormalization derives the new coding interval [L,L + R) from the selected subinterval [LSUB, LSUB + RSUB), potentially writing bits to the bit stream. Encoding of bypass bins (as depicted in the block diagram above) only requires to update L and to write bits to the bit stream and has thus a particularly low complexity.

A member of the M coder family is a normative part of the CABAC [2] entropy coding scheme as used in the H.264/AVC and H.265/HEVC video compression standards. This M coder variant provides virtually the same coding efficiency as a conventional multiplication- and division-based implementation of binary arithmetic coding at significantly higher throughput rates corresponding to speed-up factors in the range of 1.5-2.5. Compared to the MQ coder (as part of JBIG2 or JPEG2000), an increase in throughput of up to 18% can be achieved, depending on the implementation platform. At the same time, the M coder obtains average bit rate savings of 2-4% relative to the MQ coder in its native H.264/AVC CABAC environment.

References

  1. D. Marpe and T. Wiegand, A highly efficient multiplication-free binary arithmetic coder and its application in video coding, International Conference on Image Processing (ICIP 2003), Barcelona, Spain, September 2003, doi:10.1109/ICIP.2003.1246667.
  2. D. Marpe, H. Schwarz, and T. Wiegand, Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard, IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 620–636, July 2003, ISSN: 1051-8215, doi:10.1109/TCSVT.2003.815173, Erratum: On p. 631, left column below Table VI, "max(...)" must be replaced by "min(...)" in the two expressions for specifying context index increments for bins related to absolute values of transform coefficients.