---
title: "Short note: Viterbi decoding algorithm"
subject: "Wireless Communication"
chapter: 6
key: "semester_7/wireless_communication:viterbi-decoding-algorithm"
source: https://www.bctengineer.com/q/semester_7/wireless_communication/viterbi-decoding-algorithm
site: BCT Engineering
---

# Short note: Viterbi decoding algorithm

Wireless Communication · Chapter 6: Speech and Channel Coding

- Asked in: 2075 Bhadra, 3 marks; 2072 Asoj, 3 marks; 2070 Bhadra, 3 marks; 2070 Magh, 4 marks (asked 4 times)
- Video: [Viterbi Decoding Algorithm | How error correction works? | Simple Explanation with example](https://www.youtube.com/watch?v=ytjvvUrOvHk) — Arksquad
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/wireless_communication/viterbi-decoding-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_7/wireless_communication/chapter-6

## Question

Write a short note on Viterbi decoding algorithm.

## Short answer

The Viterbi algorithm is a maximum-likelihood decoding method for convolutional codes using a trellis. It computes branch metrics (Hamming or Euclidean distance) between received symbols and each branch, then performs add-compare-select per state to keep the survivor path with minimum cumulative metric, finally tracing back to decode.

## Answer

The **Viterbi algorithm** is a maximum-likelihood decoding method for **convolutional codes**. It finds the path through the code trellis whose output sequence is closest to the received sequence (minimum Hamming distance for hard decision, or Euclidean distance for soft decision).

**Steps**

1. Draw the **trellis**: 2ᴷ⁻¹ states (K = constraint length), with branches labelled by encoder output bits.
2. For each received symbol group, compute the **branch metric** = Hamming distance between received bits and each branch's output.
3. **Add–compare–select:** for every state, add branch metric to the path metric of each incoming path; keep the smaller one as the **survivor**, discard the other.
4. Repeat for the whole sequence (the encoder is flushed to state 00 with tail zeros).
5. **Trace back** the survivor ending in state 00 with the smallest metric; its input bits are the decoded data.

**Example:** rate 1/2, K = 3 code, g₁ = 111, g₂ = 101.
- Data 1011 + two tail zeros → transmitted 11 10 00 01 01 11.
- Received with one error: 11 10 **1**0 01 01 11.
- The survivor ending in state 00 has metric 1 and gives 1 0 1 1 0 0, so the error is corrected.

**Features:** complexity grows as 2ᴷ⁻¹ (linear in message length); soft-decision gives about 2 dB extra gain. Used in GSM, IS-95 and as the MLSE equalizer.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. For constraint length K, how many states does the code trellis have?
   A. 2K
   B. K^2
   C. 2^K
   D. 2^(K-1)
   Answer: D. The shift register holds K-1 bits, giving 2^(K-1) states. (Key point: Number of states)

2. What is done at each state in add-compare-select?
   A. Both incoming paths are kept
   B. Branch metrics are added to path metrics and the smaller total is kept as survivor
   C. The larger metric is kept
   D. Only the received bits are compared with zero
   Answer: B. For every state the lower-metric incoming path is the survivor and the other is discarded. (Key point: Add-compare-select)

3. What is the branch metric for hard-decision decoding?
   A. Euclidean distance of soft samples
   B. Number of states
   C. Hamming distance between received bits and branch output bits
   D. Code rate
   Answer: C. Hard decision uses Hamming distance; soft decision uses Euclidean distance. (Key point: Branch metric)

4. Why are tail zeros added and traceback done from state 00?
   A. To increase code rate
   B. The encoder is flushed to state 00, so the best survivor ending there is traced back to get the data
   C. To measure the pitch
   D. To reduce the number of states
   Answer: B. Tail zeros return the encoder to state 00, and the smallest-metric survivor ending there gives the decoded input bits. (Key point: Traceback)