Viterbi Decoding

Convolutional codes are only as useful as the algorithm that decodes them. The Viterbi algorithm is the standard maximum likelihood decoding method for convolutional codes, and it achieves optimal decoding by exploiting the trellis structure of the encoder. Proposed by Andrew Viterbi in 1967, the algorithm is now embedded in virtually every wireless communication chip, from mobile phones to satellite receivers, making it one of the most practically important algorithms in digital communications.

Core Concept of the Viterbi Algorithm

The brute force approach to maximum likelihood decoding of a convolutional code would require comparing all 2^(k.L) possible transmitted sequences against the received sequence, where L is the sequence length. This becomes computationally impossible even for moderate L. The Viterbi algorithm achieves the same result with dramatically lower complexity by using the principle of dynamic programming: the best path to any state depends only on paths reaching that state, not on where those paths came from.

The encoder operation can be visualized as a trellis diagram: a time-extended state diagram where each column represents one time step, each row represents an encoder state, and each arrow represents a state transition (one input bit, producing n output bits). The Viterbi algorithm processes received bits time step by time step and at each step computes a path metric for every surviving path leading to each state. Only the best path (lowest metric for hard decoding, or highest for soft decoding) reaching each state is kept. All other paths are discarded. This is the ACS (Add-Compare-Select) operation.

For hard decision decoding, the received bits are quantized to 0 or 1 first, and the path metric is the Hamming distance between the branch output and the received bits. For soft decision decoding, the received analog samples are used directly and the metric is typically Euclidean distance or log-likelihood ratio. Soft decision decoding provides approximately 2 to 3 dB of additional coding gain over hard decision decoding, which is very significant in practice.

Mathematical Expression

Let the state at time t be S(t). The accumulated path metric M(S, t) is computed as:

• M(S, t) = min over all predecessor states S' of [ M(S', t-1) + branch_metric(S' → S) ]
• Branch metric = Hamming distance between expected output on that branch and received bits at time t.
• After processing all received bits, the state with the minimum final metric gives the end of the best path.
• Traceback from this end state through stored survivor decisions recovers the decoded input sequence.

The computational complexity of Viterbi decoding is O(L . 2^(K-1)) which is linear in sequence length L, compared to the exponential cost of exhaustive search. The decoding depth (traceback length) is typically chosen as 5K to allow path memory to converge. For K=7, traceback depth of 35 is standard.

Practical Understanding

Viterbi decoding is implemented in every 3G, 4G, WiFi, and digital broadcast receiver chip. In 4G LTE, convolutional codes with Viterbi decoding are used for control channel information such as DCIs and BCCHs, where low latency is essential. For data channels in LTE, turbo codes replaced Viterbi-decoded convolutional codes due to better performance near Shannon limit, but Viterbi remains dominant for shorter blocks and control signaling.

In satellite communication, the Voyager spacecraft uses a rate 1/2 K=7 convolutional code decoded by Viterbi algorithm. The 64-state trellis of K=7 gives high coding gain while keeping VLSI implementation manageable. This was the first space mission to use the Viterbi algorithm, demonstrating its reliability across billions of kilometers.

Given:
Convolutional code: Rate 1/2, K=3, g1=111, g2=101
Received sequence (hard decision): 11 10 00 01
Transmitted: 11 10 00 01 (no error case for clarity)
Initial state: 00

Why this formula applies:
Path metric at each state = sum of Hamming distances between branch expected output and received bits.

Formula:
M(S, t) = M(S_prev, t-1) + HammingDistance(expected_output, received_bits_at_t)

Time t=1, received = 11:
From state 00, input 0 → output 00, next state 00: metric = HD(00,11) = 2
From state 00, input 1 → output 11, next state 10: metric = HD(11,11) = 0
Survivor: State 00 has metric 2, State 10 has metric 0

Time t=2, received = 10:
From state 00 (metric 2), input 0 → output 00, next state 00: 2+HD(00,10)=2+1=3
From state 00 (metric 2), input 1 → output 11, next state 10: 2+HD(11,10)=2+1=3
From state 10 (metric 0), input 0 → output 10, next state 01: 0+HD(10,10)=0+0=0
From state 10 (metric 1), input 1 → output 01, next state 11: 0+HD(01,10)=0+2=2

Survivor metrics: S00=3, S10=3, S01=0, S11=2

Final Answer:
Viterbi selects minimum metric path at each step.
Traceback from state with lowest final metric recovers decoded sequence: 1 0 1 1 (correct)

Exam Tip: In GATE problems, compute path metrics step by step using Hamming distance for hard decoding. The survivor path at each state is the one with minimum accumulated metric. Traceback depth should be at least 5K for reliable decisions.

Quick Revision

• Viterbi algorithm = maximum likelihood decoding of convolutional codes using dynamic programming on a trellis.
• ACS operation: Add branch metric, Compare two paths reaching same state, Select survivor (minimum metric).
• Hard decision metric = Hamming distance. Soft decision metric = Euclidean distance or LLR.
• Complexity = O(L . 2^(K-1)): linear in sequence length, exponential in constraint length K.
• Soft decision decoding provides 2 to 3 dB gain over hard decision. Always preferred when analog samples are available.
• Traceback depth = 5K is standard. For K=7, traceback of 35 time steps is used.
• Exam trap: Viterbi is optimal only for convolutional codes decoded on an AWGN channel. It is not optimal for block codes or for channels with memory.