--- title: "Short note: Trellis diagram of convolutional encoder" subject: "Communication Systems" chapter: 8 key: "semester_6/communication_systems:short-note-trellis-1010-half-rate" source: https://www.bctengineer.com/q/semester_6/communication_systems/short-note-trellis-1010-half-rate site: BCT Engineering --- # Short note: Trellis diagram of convolutional encoder Communication Systems · Chapter 8: Error Detection and Correction Coding - Asked in: 2081 Chaitra, 5 marks - Video: [L 20 | Trellis Diagram | Convolution Code | Information Theory & Coding | Digital Communication |](https://www.youtube.com/watch?v=T87uAuLpCiE) — Dopamine - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/short-note-trellis-1010-half-rate - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-8 ## Question Write a short note on trellis diagram of a message 1010 using a ½ rate 3-state memory block convolutional encoder. ## Short answer A trellis diagram shows encoder states over time with branches for each input. For a rate-1/2, K=3 encoder (generators 111, 101), message 1010 with two flushing zeros produces output 11 10 00 10 11 00, tracing a unique path through states a→b→c→b→c→a→a. ## Answer A **trellis diagram** is a time-expanded state diagram of a convolutional encoder. The encoder states (contents of the memory) are drawn as rows of nodes, time runs left to right, and each branch shows the transition caused by one input bit, labelled with the output bits. Each message traces one path through the trellis; the Viterbi decoder searches the trellis for the closest path. **Assumed encoder** ("3-state memory" read as a three-stage shift register, i.e. constraint length $K=3$: the present bit plus 2 memory flip-flops, giving $2^2=4$ states), rate 1/2, generators $g^{(1)}=111$, $g^{(2)}=101$: $$ c_1=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_2=m_i\oplus m_{i-2} $$ States $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11. #### Encoding 1010 (with two 0s to flush) | Input | State before | Output | State after | |---|---|---|---| | 1 | a (00) | 11 | b (10) | | 0 | b (10) | 10 | c (01) | | 1 | c (01) | 00 | b (10) | | 0 | b (10) | 10 | c (01) | | 0 (flush) | c (01) | 11 | a (00) | | 0 (flush) | a (00) | 00 | a (00) | Encoded sequence: **11 10 00 10 11 00**. #### Trellis with the message path ```text t0 t1 t2 t3 t4 t5 t6 a 00 * o o o o *======* \ / \ / b 10 o * o * o / o o \ / \ / \ / \ / c 01 o o * o * o o d 11 o o o o o o o in: 1 0 1 0 0 0 out: 11 10 00 10 11 00 ``` In the full trellis every state has two branches leaving it (input 0 and input 1). After $K-1=2$ steps the pattern of branches repeats at every stage. The path marked with * (= for a horizontal branch) is the unique path for 1010; any received sequence is decoded by finding the path with the minimum Hamming distance from it. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is a trellis diagram? A. A table of parity check equations B. A time-expanded state diagram with branches labelled by output bits for each input C. A plot of error rate against Eb/N0 D. A tree whose number of branches doubles at every stage Answer: B. Nodes are encoder states, time runs left to right, and each branch is one input bit with its output; a message traces a single path. (Key point: What a trellis is) 2. For the assumed encoder with K = 3 (two memory flip-flops), how many states does the trellis have? A. 2 B. 3 C. 4 D. 8 Answer: C. 2^(K-1) = 2^2 = 4 states: 00, 10, 01, 11. (Key point: Number of states) 3. What is the encoded sequence for 1010 plus two flushing 0s with g1 = 111, g2 = 101? A. 11 10 00 10 11 00 B. 11 01 00 10 11 00 C. 11 10 11 10 00 00 D. 10 11 00 10 11 00 Answer: A. Stepping through the states a, b, c, b, c, a, a gives outputs 11, 10, 00, 10, 11, 00. (Key point: Encoded output) 4. Why are two 0s appended to the message and how is the trellis used for decoding? A. To increase the code rate; the decoder picks the path with the maximum Hamming distance B. To return the register to state 00; the decoder picks the path with minimum Hamming distance from the received sequence C. To add parity; the decoder uses syndromes D. To double the number of states; the decoder uses a code tree Answer: B. K-1 = 2 zeros bring the encoder back to the all-zero state, and Viterbi decoding searches for the closest path. (Key point: Flushing and decoding) ## Related in Communication Systems - [Error detection vs correction; rate ½ convolutional encoder](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aerror-detect-correct-conv-half-rate) — Communication Systems, chapter 8 - [Rate 1/3 convolutional encoder: encode 10011](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aconv-encoder-third-rate-10011) — Communication Systems, chapter 8 - [Convolutional vs block coder; (7,4) cyclic code for 1010](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aconv-vs-block-cyclic-7-4-1010) — Communication Systems, chapter 8, asked 2× - [Convolutional encoding of 10011 with state and trellis](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aconvolutional-encoder-10011) — Communication Systems, chapter 8 - [Hamming distance and weight; rate 1/3 convolutional encoder](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahamming-third-rate-convolutional) — Communication Systems, chapter 8 - [Stereo FM encoder and decoder block diagram](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Astereo-fm-encoder-decoder-blocks) — Communication Systems, chapter 3 ## Related in other subjects - [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× - [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× - [Convolutional encoder c(3,1,3), input 00110](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aconv-encoder-313-00110) — Data Communication, chapter 8 - [Convolutional encoder c(3,1,3), input 111011](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aconv-encoder-313-111011) — Data Communication, chapter 8