Context-adaptive
variable-length coding (CAVLC) is a form of
entropy coding
In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method ...
used in
H.264/MPEG-4 AVC video encoding. It is an inherently
lossless compression
Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistic ...
technique, like almost all entropy-coders. In H.264/MPEG-4 AVC, it is used to encode residual, zig-zag order, blocks of transform coefficients. It is an alternative to context-based adaptive binary
arithmetic coding
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic e ...
(CABAC). CAVLC requires considerably less processing to decode than CABAC, although it does not compress the data quite as effectively. CAVLC is supported in all H.264 profiles, unlike CABAC which is not supported in Baseline and Extended profiles.
CAVLC is used to encode residual, zig-zag ordered 4×4 (and 2×2) blocks of transform coefficients. CAVLC is designed to take advantage of several characteristics of quantized 4×4 blocks:
* After prediction, transformation and quantization, blocks are typically sparse (containing mostly zeros).
* The highest non-zero coefficients after zig-zag scan are often sequences of +/− 1. CAVLC signals the number of high-frequency +/−1 coefficients in a compact way.
* The number of non-zero coefficients in neighbouring blocks is correlated. The number of coefficients is encoded using a look-up table; the choice of look-up table depends on the number of non-zero coefficients in neighbouring blocks.
* The level (magnitude) of non-zero coefficients tends to be higher at the start of the reordered array (near the DC coefficient) and lower towards the higher frequencies. CAVLC takes advantage of this by adapting the choice of VLC look-up table for the “level” parameter depending on recently coded level magnitudes.
Coded elements
Parameters that required to be encoded and transmitted include the following table:
CAVLC examples
In all following examples, we assume that table Num-VLC0 is used to encode coeff_token.
![4x4CAVLC](https://upload.wikimedia.org/wikipedia/commons/e/e1/4x4CAVLC.svg)
0, 3, 0, 1, −1, −1, 0, 1, 0…
TotalCoeffs = 5 (indexed from highest frequency
to lowest frequency
TotalZeros = 3
T1s = 3 (in fact there are 4 trailing ones but only 3 can be encoded as a “special
case”)
Encoding:
The transmitted bitstream for this block is 000010001110010111101101.
Decoding:
The output array is “built up” from the decoded values as shown below. Values added to the output array at each stage are underlined.
The decoder has inserted two zeros; however, TotalZeros is equal to 3 and so another 1 zero is inserted before the lowest coefficient, making the final output array: 0, 3, 0, 1, −1, −1, 0, 1
See also
*
H.264 (entropy coding)
*
Data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...
*
Lossless compression
Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistic ...
External links
Context adaptive variable length coding tutorial (out of date)
Lossless compression algorithms
MPEG
Video compression
{{comp-sci-stub