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

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

Data Communication · Chapter 8: Information Theory and Coding

- Asked in: 2074 Chaitra, 8 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-2bit
- Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8

## Question

Applying a 1/2 rate, 4-state convolutional code, correct errors of two bits with the help of its trellis diagram.

## Short answer

Using a rate-1/2, 4-state convolutional code (g1=111, g2=101) and Viterbi decoding on the trellis, the two-bit errors are corrected, recovering the message 1 0 1 1.

## Answer

#### Code used
Rate 1/2, 4-state (K = 3) convolutional code, g1 = 111, g2 = 101. States: a = 00, b = 10, c = 01, d = 11 (state = s1 s2; next state = (input, 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 and received data
Message 1 0 1 1 plus tail 0 0:
- transmitted: **11 10 00 01 01 11**
- received (2 bit errors, in steps 2 and 5): **11 00 00 01 11 11**

#### Viterbi decoding on the trellis
Each branch gets a metric equal to the Hamming distance between the received pair and the branch output. The decoder adds metrics along each path and keeps only the lowest metric (survivor) at every state.

```text
 time :  t0   t1   t2   t3   t4   t5   t6
 rx   :       11   00   00   01   11   11
 a    :  0*    2    2    2    3    2    2*
 b    :   -    0*   4    1*   3    3    2
 c    :   -    -    1*   2    2    2*   3
 d    :   -    -    1    2    1*   2    3
 (number = accumulated error count, * = survivor path)
```
Example (t2): state c is reached from b by input 0 (output 10, received 00, distance 1) with total 0 + 1 = 1.

#### Traceback
The code ends in state a with total metric **2**, which means two bit errors. Following survivors backwards:

a ← c ← d ← b ← c ← b ← a

The path is a → b → c → b → d → c → a with inputs 1, 0, 1, 1, 0, 0, and outputs 11 10 00 01 01 11, which is the transmitted sequence.

**Decoded message = 1 0 1 1 (tail 00). Both errors (step 2: 00 received instead of 10; step 5: 11 received instead of 01) are corrected.**

Since d_free = 5, any pattern of 2 bit errors in the stream is corrected.

## Check yourself

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

1. In the 4-state code, what does a state represent?
   A. The last two input bits (s1 s2)
   B. The output pair
   C. The number of errors
   D. The received bits
   Answer: A. State = (s1 s2); a=00, b=10, c=01, d=11, and the next state is (input, s1). (Key point: State definition)

2. What final metric shows how many errors the decoder corrected?
   A. 0
   B. 1
   C. 2
   D. 4
   Answer: C. The surviving path into state a has metric 2, matching the two bit errors. (Key point: Decoding result)

3. What is the decoded message?
   A. 1 0 1 1 (tail 00)
   B. 1 1 0 1
   C. 0 1 0 0
   D. 1 0 0 1
   Answer: A. The survivor path inputs are 1,0,1,1,0,0, i.e. message 1011 plus tail 00. (Key point: Decoded message)

## Close variants set in other exams

- [Trellis decoding of 1/2 rate conv. code (3-bit errors)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aconv-trellis-3bit) — 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