  Trellis decoders are a general decoding technique first applied to
qubit-based quantum error correction codes by Ollivier and Tillich in 2006.
Here we improve the scalability and practicality of their theory, show that it
has strong structure, extend the results using classical coding theory as a
guide, and demonstrate a canonical form from which the structural properties of
the decoding graph may be computed. The resulting formalism is valid for any
prime-dimensional quantum system. The modified decoder works for any stabilizer
code $S$ and separates into two parts: a one-time, offline computation which
builds a compact, graphical representation of the normalizer of the code,
$S^\perp$, and a quick, parallel, online query of the resulting vertices using
the Viterbi algorithm. We show the utility of trellis decoding by applying it
to four high-density, length 20 stabilizer codes for depolarizing noise and the
well-studied Steane, rotated surface, and 4.8.8/6.6.6 color codes for $Z$-only
noise. Numerical simulations demonstrate a 20\% improvement in the
code-capacity threshold for color codes with boundaries by avoiding the mapping
from color codes to surface codes. We identify trellis edge number as a key
metric of difficulty of decoding, allowing us to quantify the advantage of
single-axis decoding for Calderbank-Steane-Shor codes and block-decoding for
concatenated codes.
