Transform Coefficient Level Coding for CABAC

Entropy Coding Engine

Context-based adaptive binary arithmetic coding (CABAC) is specified as the single operation mode for entropy coding in HEVC. From the encoder perspective, CABAC consists of three processing stages.

  1. Binarization: Decomposition of non-binary values into a sequence of bins (bin string).
  2. Context Modeling: Selection of an adaptive binary probability model.
  3. Binary Arithmetic Coder (BAC): Core engine also known as M Coder.

Two operation modes are specified for CABAC.

  1. Regular mode: A context model has to be specified. The internal probability representation (state) is updated after the coding of a bin. This probability update results in a feedback loop for the coding process, both for encoder and decoder.
  2. Bypass mode: The low-complexity mode of BAC. No context model is required and bins are coded with equi-probability. Hence, more bins can be processed for a given time constant comparing to the regular mode.

Novelties of Transform Coefficient Level Coding in HEVC

HEVC includes dyadic transform block sizes ranging from 4×4 to 32×32. In order to improve the support for the variety of transform block sizes in terms of complexity and coding performance, further developments have been made regarding the binarization and context modeling stages.

Complexity reduction

  1. Decomposition into sub-blocks is the core of the transform coefficient level coding of CABAC in HEVC. This coherent design allows the same logic and procedures for all transform block sizes.
  2. Less context models are required comparing to the straightforward extension of the H.264/AVC context modeling scheme to 16×16 and 32×32 transform blocks. This results in less area for hardware implementations and as consequence a shorter critical path. This in turn leads to a higher throughput for CABAC.
  3. Less regular coded bins are coded comparing to the binarization scheme for transform coefficient levels in H.264/AVC by using adaptive binarization. This results in a higher throughput for CABAC.


Coding improvement

  1. Local templates adapt the context modeling stage to the local activity of the transform coefficient levels in HEVC.
  2. Adaptive scan patterns further improve the compression gain together with the sign inference technique.

Sub-Block Decomposition and Scan Patterns

Transform blocks larger than 4×4 are decomposed into disjoint 4×4 sub-blocks. Scan patterns define the sequential processing order of the sub-blocks as well as the frequency position covered by the sub-blocks. Fig. 1 shows an example for the decomposition into sub-blocks and the reverse scan patterns using for sub-blocks as well as the frequency positions covered by the sub-blocks. The horizontal and the vertical scan pattern are applied for 4×4 and 8×8 luma transform blocks using predefined intra prediction modes. Fig. 2 shows the directional intra modes using horizontal or vertical scan pattern.

Insignificance/Significance Flags

Before encoding the levels, insignificance flags are transmitted in different hierarchical levels. They specify the non-existence of non-zero levels for a specific area.

  1. No residual syntax flag: Transmitted in the root node of the residual quadtree. If this flag is equal to one, all sample values covered by the coding unit are equal to zero.
  2. Coded block flag: Transmitted for the transform blocks and specifies the insignificance for the sample values covered by a transform block.
  3. Last significant scan position: Transmitted as spatial offset from the DC frequency position of the transform block. The x coordinate is transmitted first followed by the y coordinate. Hence, the insignificance is specified for sub-blocks and frequency positions in the sub-block covering the last significant scan positions.
  4. Coded sub-block flag: Transmitted for each sub-block specifying the insignificance for a sub-block.

Adaptive Binarization

Before processing a sub-block, the transform coefficient levels are binarized using three concatenated schemes.

  1. Unary code: The Golomb-Rice code with an order equal to zero. If a level z exceeds the maximum representable value b0of this code, the remaining value given by z - b0 is binarized using the second scheme. The threshold b0 is set equal to three before processing a sub-block. After a level greater than two has been binarized, b0 is set equal to two. Furthermore, b0is further set equal to one when eight levels greater than one have been binarized.
  2. Golomb-Rice codes: A set of parameterizable codes suitable for different statistics of levels. The order kk has been binarized, the order is increased by one and furthermore the order is limited to four. When zexceeds the threshold b1, the remaining value of z - b1 is binarized with the third scheme.
  3. Exp-Golomb codes: Another set of parameterizable codes suitable for different statistics of levels. The order is set equal to k + 1.

Bins related to the unary code are coded in the regular mode of BAC. The remaining bins of the bin string are coded in the low-complexity bypass mode of BAC. In order to minimize the switches between the regular and the bypass mode, regular-coded bins are coded first for all levels of the sub-block followed by the sign and the remaining magnitudes.

Bins related to the unary code are coded in the regular mode of BAC. The remaining bins of the bin string are coded in the low-complexity bypass mode of BAC. In order to minimize the switches between the regular and the bypass mode, regular-coded bins are coded first for all levels of the sub-block followed by the sign and the remaining magnitudes.

Data Processing and Data Partitioning

Transform coefficient levels are coded in five stages for each sub-block as the result of the interleaving of bins.

Regular Mode:

  1. Significance map specifies insignificant frequency positions of the sub-block.
  2. The information on whether absolute level is greater than on is coded for up to eight significant scan positions.
  3. The information whether greater than two is coded for the first scan position with an absolute level greater than one.

Bypass Mode:

  1. The signs are transmitted for each significant scan position. When the sign inference technique is optionally enabled, the sign for the last significant scan position in reverse scan order is inferred from the parity of the absolute level sum. This is done only when the distance between the first and the last significant scan position is larger than three.
  2. The remaining bins of the bin strings are coded for each frequency position with the last regular coded syntax element value specifying the level magnitude is equal to one.

Regular-coded bins require an adaptive context model. The context modeling for insignificance flags are as follows.

  • No residual syntax flag: One single context model.
  • Coded block flag:
    1. Luma: One context model for the residual quadtree depth equal to zero, another context model for the other depths.
    2. Chroma: One separate context model for each residual quadtree depth.
  • Last significant scan position: Depending on the bin index of the bin string. A quantization step size controlled by the transform block size and the color component defines the number of bins using one context model.
  • Coded sub-block flag: The spatial neighborhood is evaluated. One context model is selected when both the above and below sub-block are insignificant. Another context model is selected when both are significant and a separate context model is selected when only one is insignificant (above left in Fig. 4). 

The context modeling for the significance map depends on the spatial position relative to the top-left corner of the sub-block. For 4×4 transform block, an exclusive mapping is used (above center in Fig. 4). For other transform block sizes, one out four mappings is used (above right and below in Fig. 4). The local template as used for the coded sub-block flag is employed.