--- title: "Error detection vs correction; rate ½ convolutional encoder" subject: "Communication Systems" chapter: 8 key: "semester_6/communication_systems:error-detect-correct-conv-half-rate" source: https://www.bctengineer.com/q/semester_6/communication_systems/error-detect-correct-conv-half-rate site: BCT Engineering --- # Error detection vs correction; rate ½ convolutional encoder Communication Systems · Chapter 8: Error Detection and Correction Coding - Asked in: 2079 Chaitra, 2+4+4 marks - Video: [Convolutional Encoder Example-Part 1](https://www.youtube.com/watch?v=Ie6BHGsA_z0) — Rupali - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/error-detect-correct-conv-half-rate - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-8 ## Question Differentiate error-detection and error-correction. Design a convolutional encoder having code-rate of ½. Also, draw the code-tree and trellis diagram for the same assuming any three-bit input. ## Short answer Error detection identifies errors; error correction identifies and corrects them. For rate-1/2 convolutional encoder with generators 111 and 101, code tree and trellis diagram show outputs for each input bit and state transitions. ## Answer #### Error detection vs error correction | Point | Error detection | Error correction | |---|---|---| | Aim | Only finds that an error occurred | Finds and fixes the error | | Redundancy | Few check bits (parity, CRC) | More check bits | | Action on error | Request retransmission (ARQ) | Corrected at receiver (FEC) | | Capability | Detects $d_{min}-1$ errors | Corrects $\lfloor (d_{min}-1)/2\rfloor$ | | Return channel | Needed | Not needed | | Examples | Parity, checksum, CRC | Hamming, BCH, convolutional | #### Rate-1/2 convolutional encoder (design) Choose $k=1$ input bit, $n=2$ output bits ($r=1/2$), constraint length $K=3$ (two memory flip-flops, 4 states) and generators $g^{(1)}=111$, $g^{(2)}=101$. ```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 ``` A commutator samples $c_1$ then $c_2$ for each input bit, so two bits go out for every bit in. 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) | #### Code tree (three-bit input) Upper branch = input 0, lower branch = input 1; labels are outputs. ```text 00 a (000) 00 a ---< / 11 b (001) 00 a ---< / \ 10 c (010) / 11 b ---< / 01 d (011) start< \ 11 a (100) \ 10 c ---< \ / 00 b (101) 11 b ---< \ 01 c (110) 01 d ---< 10 d (111) bit: 1 2 3 ``` Read along a path: input 101 gives 11, 10, 00, i.e. root (down 11) to b, (up 10) to c, (down 00) to b. #### Trellis diagram, input 101 (plus 00 to flush) ```text t0 t1 t2 t3 t4 t5 a 00 * o o o o * \ / \ / b 10 o * o * o / o \ / \ / \ / \ / c 01 o o * o * o d 11 o o o o o o in: 1 0 1 0 0 out: 11 10 00 10 11 ``` Encoded output for 101: **11 10 00 10 11**. Every state in the full trellis has two outgoing branches; after the first two stages the trellis structure repeats. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which pairing correctly contrasts error detection and error correction? A. Detection fixes errors with FEC; correction asks for retransmission B. Detection only finds errors and uses retransmission (ARQ); correction fixes them at the receiver (FEC) without a return channel C. Detection needs more redundancy than correction D. Both always need a return channel Answer: B. Detection (parity, CRC) needs few check bits and ARQ; correction (Hamming, convolutional) needs more redundancy but no return channel. (Key point: Detection vs correction) 2. In terms of dmin, how many errors can a code detect and correct? A. Detect floor((dmin-1)/2), correct dmin-1 B. Detect dmin-1, correct floor((dmin-1)/2) C. Detect dmin, correct dmin/2 D. Detect dmin+1, correct dmin-1 Answer: B. Detection works up to dmin-1 errors, correction up to floor((dmin-1)/2). (Key point: Capability from dmin) 3. The rate-1/2 encoder designed has k = 1, n = 2, K = 3. What does this mean? A. 1 input bit gives 2 output bits, with 2 memory flip-flops and 4 states B. 2 input bits give 1 output bit, with 3 states C. 1 input bit gives 2 output bits, with 3 memory flip-flops and 8 states D. 1 input bit gives 1 output bit, with 4 states Answer: A. Rate = k/n = 1/2; K = 3 means the present bit plus two memory elements, so 2^2 = 4 states. (Key point: Designed encoder) 4. In the code tree, upper branch = input 0 and lower branch = input 1. What outputs does input 101 give? A. 11, 10, 00 B. 11, 01, 00 C. 00, 11, 10 D. 11, 10, 11 Answer: A. Start (down 11) to b, (up 10) to c, (down 00) to b, giving 11, 10, 00. (Key point: Reading the code tree) ## Related in Communication Systems - [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 - [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 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 - [T1 and E1 bit rate and bandwidth; DPCM encoder](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3At1-e1-bitrate-dpcm) — Communication Systems, chapter 5 - [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 - [Short note: Error detection and correction capability](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ashort-note-error-detect-correct-capability) — Communication Systems, chapter 8 ## 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× - [Error correction vs detection, bit stuffing](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Aerror-correct-detect-bitstuff) — Computer Networks and Security, chapter 3 - [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