10.2 State Diagrams and Trellis Representations

Convolutional codes are powerful error-correcting codes used in digital communications. State diagrams and trellis representations are essential tools for understanding and working with these codes, providing visual ways to depict encoder behavior and decode received messages.

These diagrams help us grasp the inner workings of convolutional encoders and decoders. By exploring state transitions, branch metrics, and path metrics, we can see how these codes protect data from errors and how receivers can recover the original message.

State and Trellis Diagrams

Representing Convolutional Codes with State Diagrams

• State diagrams visually represent the behavior of a convolutional encoder
• Consist of nodes representing encoder states and edges representing state transitions
• Each edge is labeled with the input bit and corresponding output bits
• Provide a compact way to describe the encoding process

Trellis Diagrams: Unfolding the State Diagram

• Trellis diagrams are an alternative representation of convolutional codes
• Obtained by unfolding the state diagram over time
• Each stage in the trellis corresponds to a time step in the encoding process
• Nodes at each stage represent the possible encoder states at that time
• Edges connecting nodes represent state transitions and are labeled with input/output bits

Exploring Encoder States and Transitions

• The number of states in a convolutional encoder depends on the constraint length ($K$)
• For a rate $1/n$ encoder with constraint length $K$, there are $2^{K-1}$ states
• Each state corresponds to a unique sequence of the past $K-1$ input bits
• State transitions occur based on the current state and the incoming input bit
• The output bits for each transition are determined by the generator polynomials

Trellis Sections and Encoding

• A trellis section represents one time step in the encoding process
• It consists of nodes representing the current states and edges representing transitions
• The input bit determines which transition is taken from each state
• The output bits associated with each transition form the encoded sequence
• By traversing the trellis section for each input bit, the entire message is encoded

Metrics and Paths

Branch Metrics: Measuring Transition Likelihood

• Branch metrics quantify the likelihood or "distance" of a particular state transition
• Calculated by comparing the received bits with the expected output bits for each transition
• Common branch metric is the Hamming distance (number of bit differences)
• Branch metrics are assigned to each edge in the trellis diagram
• Lower branch metrics indicate a closer match between received and expected bits

Path Metrics: Accumulating Branch Metrics

• Path metrics represent the accumulated likelihood or "distance" of a sequence of state transitions
• Calculated by summing the branch metrics along a path through the trellis
• Each path corresponds to a possible transmitted sequence
• Path metrics are updated at each stage of the trellis based on the incoming branch metrics
• The path with the lowest metric is considered the most likely transmitted sequence

Survivor Paths and Decoding Decisions

• At each stage in the trellis, multiple paths may converge at a given state
• The path with the lowest metric among the converging paths is called the survivor path
• Survivor paths are retained for each state, while the other paths are discarded
• Decoding decisions are made by tracing back the survivor paths through the trellis
• The traced-back path with the lowest overall metric is selected as the decoded sequence

Advanced Trellis Concepts

Time-Varying Trellis Structures

• Time-varying trellises have a structure that changes over time
• The number of states, state transitions, or output bits may vary at different stages
• Useful for representing convolutional codes with time-varying properties
• Examples include punctured codes and codes with periodic structures
• Decoding time-varying trellises requires adapting the metric calculations and path management

Trellis Termination Techniques

• Trellis termination ensures that the encoder ends in a known state
• Achieved by appending a fixed sequence of input bits to the message
• The termination sequence drives the encoder to a predetermined final state (usually all-zero state)
• Termination reduces the number of possible paths at the end of the trellis
• Simplifies the decoding process and improves error performance
• Common termination techniques include zero-tail termination and tail-biting