trellis

In communication theory and signal processing, a trellis is a graph structure that maps the evolution of a finite-state system over discrete time steps. Each vertical slice represents a moment in time, with nodes representing possible states of the system. Edges connect states at consecutive time steps, showing which state transitions are allowed by the encoding or modulation scheme. This structure becomes essential when you need to find the most likely sequence of states that produced a received signal corrupted by noise.

The trellis owes its power to the Viterbi algorithm, which exploits the graph's structure to decode received data efficiently. Instead of checking every possible path through all time steps, the Viterbi algorithm keeps only the most likely path leading to each state at each time, then prunes impossible branches. For a convolutional code with constraint length 7 and binary symbols, the trellis typically has 26 = 64 states per time slice, making the search tractable even for long messages.

Trellis diagrams appear wherever constraint-based encoding is used: convolutional codes in satellite and mobile communications, turbo codes, LDPC codes, and even in the equalization of dispersive channels. The structure of the trellis directly encodes the generator polynomials or parity-check relationships of the code. A rate-1/2 convolutional encoder with two feedback taps will produce a different trellis topology than a rate-1/3 code, and that difference is visible in the number of edges per node and the pattern of connections.

The name "trellis" comes from its resemblance to a garden lattice or vine-support structure: vertical columns (time steps) with diagonal connections (state transitions). This visual metaphor stuck because the diagram actually helps engineers see how states proliferate and reconverge over time. In tail-biting and circular trellis variants, the final time step connects back to the initial states, allowing codes with no wasted padding bits.

A trellis is not unique to any single modulation or code; it is a representation tool that adapts to the system's constraints. The same trellis structure may be traversed by different algorithms: Viterbi for maximum-likelihood decoding, the forward-backward algorithm for soft-output decoding, or belief-propagation methods for factor graphs. Understanding the trellis structure is essential for hardware designers implementing decoders, because the critical path and memory requirements depend directly on the branch and state topology.