encoding.info
You are hereSourcePredictionTransformEntropy codingFiltersFramesDecisionsRate controlPerceptionQualityBitstreamSettingsEncoder map
Page 6 of 7 in Decisions

Trellis quantization

Decisions · concept · added 2026-11-13

In Brief:
Trellis quantization chooses a block's coefficient levels by weighing reconstruction error against estimated bit cost, in place of a rounding rule. Because one level changes what the others cost, it searches for a low-cost combination for the whole block.

Trellis quantization chooses coefficient levels by weighing reconstruction error against estimated bit cost. A level is the integer that quantization assigns to a coefficient. The choices are linked, because changing one level can change what the others cost to code, so the search looks for a low-cost combination for the whole block:

cost J = squared error + λ × bits

Why decide jointly

Plain rounding judges each coefficient alone, by distance. Bit cost does not work that way. Keeping a nonzero coefficient late in the scan can also require signaling the zeros before it; removing it may let the coded block end earlier, saving more bits than the coefficient alone would cost. And in adaptive arithmetic coding, coding one coefficient can change the estimated cost of later ones.

Rounding 7 −4 3 1 −2 1 0 −1 0 1 Search 7 −3 3 1 −1 0 0 0 0 0 low frequency high frequency 39 modeled bits with rounding; 24 with the search. Trailing zeros cost nothing once no level follows them.
Example at λ = 0.10, the starting setting of the model below. Coral marks the levels the search changed.

Try changing the price of a bit

Ten coefficients of one block, low frequency on the left. Gray bars show the original coefficients in units of the quantization step. Rings are plain rounding; teal dots are what the search picks. For each nonzero rounded level the search may keep it or move it one step closer to zero: 4 can become 3, and −4 can become −3.

This example uses invented bit costs and checks every permitted combination. It shows why coefficient choices interact; it does not reproduce x264's trellis algorithm.

0.10
← bits are free: same as roundingbits are expensive →
Original coefficientRoundedSearch
MethodModeled bitsSquared errorCost J
Rounding
Search
Simplified demo: the coefficients and the bit costs are invented. A zero before the last nonzero level costs 1 bit, a nonzero level costs 3 bits or more, nothing is sent after the last nonzero level, and every block carries 1 bit of overhead, even an all-zero one. Error is in quantization steps squared. The two candidates per coefficient match x264's; checking every combination does not.

At the starting setting the search saves 15 bits and adds 0.44 of squared error. With λ at 0.10 the bit savings outweigh the extra error, so the cost falls from 5.46 to 4.40. A lower cost does not mean less error or a better-looking picture.

Move λ from 0.03 to 0.04 to watch a joint decision: coefficients 6 and 8 go to zero together, and the block now ends after coefficient 5.

How x264's trellis works for its arithmetic coder

  1. Round to nearest. This gives each coefficient's starting level. The dead zone offsets are not used.
  2. Two candidates per nonzero level. Keep it, or move it one step closer to zero. x264 does not try a magnitude above the rounded one. That is x264's restriction, not part of what trellis quantization means.
  3. Walk the block in reverse scan order. x264 keeps the lowest-cost path into each of up to eight states of the level coder, pricing every candidate with estimated bits for its level and for the flags that mark nonzero positions and the last one.
  4. Follow the cheapest surviving path. It gives the levels to send.

The result is the best path through this restricted trellis under estimated costs, not a guarantee of the fewest real bits. In 8×8 blocks some positions share coding contexts, and x264's source says the search does not model that exactly. For its variable-length coder x264 uses a different search, which its source says is not a true trellis.

What encoders offer

EncoderSettingMedium preset
x264--trellis 0 off; 1 on the final encode of each macroblock; 2 also inside mode decision1
x265--rdoq-level 0 fixed rounding offsets, no cost search; 1 levels chosen by rate-distortion cost; 2 also considers zeroing whole groups of coefficients and dropping trailing levels of 10

Other presets and tunings change these: in both encoders the slow preset and those slower than it use 2. x265 calls the tool rate-distortion optimized quantization.

Trade-offs

Sources

Read 2026-11-13, at the commits linked.