---
title: "Trellis decoding of 1/2 rate conv. code (3-bit errors)"
subject: "Data Communication"
chapter: 8
key: "semester_5/data_communication:conv-trellis-3bit"
source: https://www.bctengineer.com/q/semester_5/data_communication/conv-trellis-3bit
site: BCT Engineering
---

# Trellis decoding of 1/2 rate conv. code (3-bit errors)

Data Communication · Chapter 8: Information Theory and Coding

- Asked in: 2075 Asoj, 10 marks
- Video: [Maximum Likelihood Decoding of Convolution Code | Viterbi Algorithm](https://www.youtube.com/watch?v=ZtCyjXy9Rlk) — RTU Wallah
- Answer checked by Claude Sonnet 5.5 on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/data_communication/conv-trellis-3bit
- Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8

## Question

Considering a 1/2 rate, 4-state convolutional code, correct 3 bits errors using its trellis diagram.

## Short answer

Rate 1/2, 4-state code (g1=111, g2=101). Received sequence with 3 errors: 11 00 00 00 01 01 00. Viterbi decoding on trellis yields decoded message 10110, correcting all errors. Survivor path metric = 3.

## Answer

#### Code used
Rate 1/2, 4-state convolutional code (K = 3) with generators g1 = 111, g2 = 101. State = (s1 s2): a = 00, b = 10, c = 01, d = 11. Next state is (b, s1).

| State | Input 0 (next, out) | Input 1 (next, out) |
|---|---|---|
| a | a, 00 | b, 11 |
| b | c, 10 | d, 01 |
| c | a, 11 | b, 00 |
| d | c, 01 | d, 10 |

#### Transmitted data
Message 1 0 1 1 0 plus tail 0 0 (7 steps, return to state a):
transmitted: **11 10 00 01 01 11 00**

Received, with 3 bit errors (one each in steps 2, 4 and 6):
received: **11 00 00 00 01 01 00**

#### Trellis and Viterbi decoding (hard decision)
Branch metric = Hamming distance between received pair and branch output. At each state keep only the survivor with the lowest accumulated metric. Accumulated metrics:

| State | t0 | t1 | t2 | t3 | t4 | t5 | t6 | t7 |
|---|---|---|---|---|---|---|---|---|
| a | 0 | 2 | 2 | 2 | 2 | 3 | 3 | **3** |
| b | – | 0 | 4 | 1 | 2 | 3 | 3 | 2 |
| c | – | – | 1 | 2 | 2 | 2 | 2 | 4 |
| d | – | – | 1 | 2 | 2 | 2 | 3 | 4 |

(Rows show the best metric reaching each state after each received pair; ties are broken arbitrarily.)

```text
 time :  t0   t1   t2   t3   t4   t5   t6   t7
 rx   :       11   00   00   00   01   01   00
 a    :  0*    2    2    2    2    3    3*   3*
 b    :   -    0*   4    1*   2    3    3    2
 c    :   -    -    1*   2    2    2*   2    4
 d    :   -    -    1    2    2*   2    3    4
 (number = accumulated error count, * = survivor path)
```

#### Traceback
Start at state a at t7 (metric 3 = number of errors corrected) and follow the survivors backwards:
a(t7) ← a(t6) ← c(t5) ← d(t4) ← b(t3) ← c(t2) ← b(t1) ← a(t0).

Path: a → b → c → b → d → c → a → a with inputs 1, 0, 1, 1, 0, 0, 0 and outputs 11 10 00 01 01 11 00.

**Decoded message = 1 0 1 1 0 (tail 00), identical to the transmitted one. The path differs from the received sequence in exactly 3 bits, which are the 3 errors corrected.**

Because d_free = 5, any 2 errors are always corrected; 3 errors are corrected when they are spread apart as here (more than a constraint length apart). Three errors packed close together could cause a wrong decision.

## Check yourself

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

1. In hard-decision Viterbi decoding, what is the branch metric?
   A. The Hamming distance between received pair and branch output
   B. The Euclidean energy
   C. The number of 1s in the input
   D. The state number
   Answer: A. Each branch is scored by the Hamming distance between the received bits and the branch output. (Key point: Branch metric)

2. What is kept at each state?
   A. All paths
   B. The path with the highest metric
   C. The path with the lowest accumulated metric (survivor)
   D. The most recent path only
   Answer: C. Only the minimum-metric path into each state survives. (Key point: Survivor selection)

3. The final metric at state a is 3. What does it mean?
   A. The decoded message has 3 bits
   B. The decoded path differs from the received sequence in 3 bits, i.e. 3 errors corrected
   C. 3 states were visited
   D. d_free = 3
   Answer: B. The final metric equals the number of received bits that disagree with the chosen path. (Key point: Number of corrected errors)

4. When are 3 errors corrected with d_free = 5?
   A. Always, wherever they are
   B. Only when they are spread apart; packed together they may cause a wrong decision
   C. Never
   D. Only for tail bits
   Answer: B. d_free = 5 guarantees only 2 errors; 3 are corrected if well separated. (Key point: Limits of correction)

## Close variants set in other exams

- [Trellis decoding of 1/2 rate conv. code (2-bit errors)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aconv-trellis-2bit) — Data Communication, chapter 8, asked 2×

## Related in other subjects

- [Short note: Trellis diagram of convolutional encoder](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ashort-note-trellis-1010-half-rate) — Communication Systems, chapter 8