4.6.2 Decoding

The decoder reconstructs the most likely sequence of information bits that produced the received sequence of coded bits. Using the same tree or trellis structure as the encoder, the decoder moves between states based on the received codewords, outputting ‘1’s or ‘0’s as appropriate. This process is straightforward in an ideal, error-free channel. However, in practice, errors occur due to noise and interference, and the decoder must exploit the redundancy introduced by the encoder.

Because each output codeword in a convolutional encoder depends on the current input bit and the previous (K–1) bits, information about each input bit is distributed across K consecutive codewords. The decoder can therefore use this redundancy to detect and correct errors. For Viterbi decoding with hard decisions, each increment in constraint length improves the required E_b/N₀ by a factor of 0.5 dB at a probability of bit error of 10^–5.

In direct (maximum-likelihood) decoding, the decoder compares each permissible path through the code tree with the received sequence. The path whose sequence of codewords most closely matches the received sequence (in terms of minimum distance) is selected as the most probable transmitted path. This method guarantees optimal performance but becomes computationally infeasible for long message sequences because the number of possible paths grows exponentially with the constraint length.

In sequential decoding, used primarily for large-constraint-length codes, the decoder follows the path through the trellis that is closest to the received sequence and maintains a cumulative error metric at each node. When the accumulated metric exceeds a defined threshold, the decoder assumes that the current path is incorrect and backtracks to a previous node to explore alternative paths. This process continues until the correct path is found. Although sequential decoding can achieve very low error probabilities and lower complexity than direct decoding, its computation time increases as channel noise rises, and it requires substantial memory to store intermediate path metrics. Because of this complexity, sequential decoding is typically implemented with hard-decision data, as soft-decision decoding would further increase computational and storage requirements.