--- title: "Convolutional encoding of 10011 with state and trellis" subject: "Communication Systems" chapter: 8 key: "semester_6/communication_systems:convolutional-encoder-10011" source: https://www.bctengineer.com/q/semester_6/communication_systems/convolutional-encoder-10011 site: BCT Engineering --- # Convolutional encoding of 10011 with state and trellis Communication Systems · Chapter 8: Error Detection and Correction Coding - Asked in: 2080 Chaitra, 8 marks - Video: [Convolution Encoder - Part 1 - Trellis diagram, State diagram, Code tree](https://www.youtube.com/watch?v=vHNB6iQFRkk) — AK ECE - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/convolutional-encoder-10011 - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-8 ## Question Determine the encoded sequence for the following input message (m₀, m₁, m₂, m₃, m₄) = (1 0 0 1 1) using convolutional encoder having shift registers with three flip flops. Draw state and trellis diagrams. ## Short answer For input 10011 with generators 111 and 101, the encoded sequence is 11 10 11 11 01 01 11. The state and trellis diagrams show transitions and outputs for each state. ## Answer **Assumption:** the encoder is the standard rate-1/2 encoder with a three-stage shift register (present bit and two delay flip-flops, constraint length $K=3$) and generator sequences $g^{(1)}=(1,1,1)$, $g^{(2)}=(1,0,1)$. ```text Encoder: g1 = 111, g2 = 101 (K = 3, rate 1/2) m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ] | | | +---(+)----+-----------+---> c1 = mi+mi-1+mi-2 | | +---(+)----------------+---> c2 = mi+mi-2 output per bit: c1 c2 ``` $$ c_i^{(1)}=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_i^{(2)}=m_i\oplus m_{i-2} $$ #### Encoded sequence Message $(m_0\dots m_4)=10011$, followed by two 0s to return the register to 00. | $i$ | $m_i$ | $m_{i-1}$ | $m_{i-2}$ | $c^{(1)}$ | $c^{(2)}$ | |---|---|---|---|---|---| | 0 | 1 | 0 | 0 | 1 | 1 | | 1 | 0 | 1 | 0 | 1 | 0 | | 2 | 0 | 0 | 1 | 1 | 1 | | 3 | 1 | 0 | 0 | 1 | 1 | | 4 | 1 | 1 | 0 | 0 | 1 | | 5 | 0 | 1 | 1 | 0 | 1 | | 6 | 0 | 0 | 1 | 1 | 1 | By polynomials: $c^{(1)}(D)=(1+D^3+D^4)(1+D+D^2)=1+D+D^2+D^3+D^6$ and $c^{(2)}(D)=(1+D^3+D^4)(1+D^2)=1+D^2+D^3+D^4+D^5+D^6$, which give the same bits. **Encoded sequence: 11 10 11 11 01 01 11** #### State diagram State = previous two inputs $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11. | Present state | Input | Output $c_1c_2$ | Next state | |---|---|---|---| | a (00) | 0 | 00 | a (00) | | a (00) | 1 | 11 | b (10) | | b (10) | 0 | 10 | c (01) | | b (10) | 1 | 01 | d (11) | | c (01) | 0 | 11 | a (00) | | c (01) | 1 | 00 | b (10) | | d (11) | 0 | 01 | c (01) | | d (11) | 1 | 10 | d (11) | ```text +--0/00--+ v | [ a 00 ]---+ ^ \ 0/11 | \ 1/11 | v [ c 01 ]<--0/10--[ b 10 ] | ----1/00---> | ^ | 1/01 0/01 | v +-------------[ d 11 ]--+ ^ | 1/10 +------+ label = input/output bits ``` #### Trellis diagram ```text t0 t1 t2 t3 t4 t5 t6 t7 a 00 * o o * o o o * \ / \ / \ / \ / b 10 o * o / o * o o / o \ / \ / \ / \ / c 01 o o * o o \ o * o \ / \ / d 11 o o o o o * o o in: 1 0 0 1 1 0 0 out: 11 10 11 11 01 01 11 ``` At each stage every state has two branches (input 0 and 1) as in the table; the path for 10011 is marked with *. The output read along the path is 11 10 11 11 01 01 11. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. For the encoder with g1 = 111 and g2 = 101, what are the two outputs? A. c1 = mi + mi-1 + mi-2, c2 = mi + mi-2 B. c1 = mi + mi-2, c2 = mi + mi-1 C. c1 = mi-1 + mi-2, c2 = mi D. c1 = mi, c2 = mi + mi-1 + mi-2 Answer: A. The generator sequences 111 and 101 select the taps of the three register stages. (Key point: Output equations) 2. What is the encoded sequence for message 10011 (with two flushing 0s)? A. 11 10 11 11 01 01 11 B. 11 01 11 11 10 10 11 C. 11 10 11 00 01 01 11 D. 10 10 11 11 01 01 11 Answer: A. The table of c1, c2 for i = 0 to 6 gives 11, 10, 11, 11, 01, 01, 11 (14 bits). (Key point: Encoded sequence) 3. From state b (10), input 1: what is the output and next state? A. Output 10, next state c (01) B. Output 01, next state d (11) C. Output 11, next state b (10) D. Output 00, next state a (00) Answer: B. c1 = 1+1+0 = 0 and c2 = 1+0 = 1 give output 01; the register now holds 11, state d. (Key point: State diagram) 4. How many states are in the state diagram and why are two extra 0s sent after the message? A. 8 states; to add parity B. 4 states (2^(K-1)); to return the register to 00 C. 3 states; to synchronise the clock D. 4 states; to change the code rate Answer: B. With two memory elements there are 4 states, and K-1 = 2 zeros flush the register back to 00. (Key point: Number of states and flushing) ## Related in Communication Systems - [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 - [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 - [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 - [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 ## Related in other subjects - [Sequence detector 1101 using SR flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1101-sr) — Digital Logic, chapter 9, asked 7× - [Sequence detector 1101 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1101-t) — Digital Logic, chapter 9, asked 7× - [Sequence detector 001 using JK flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-001-jk) — Digital Logic, chapter 9, asked 7× - [Sequence detector 011 using JK flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-011-jk) — Digital Logic, chapter 9, asked 7×