--- title: "Hamming distance and weight; rate 1/3 convolutional encoder" subject: "Communication Systems" chapter: 8 key: "semester_6/communication_systems:hamming-third-rate-convolutional" source: https://www.bctengineer.com/q/semester_6/communication_systems/hamming-third-rate-convolutional site: BCT Engineering --- # Hamming distance and weight; rate 1/3 convolutional encoder Communication Systems · Chapter 8: Error Detection and Correction Coding - Asked in: 2074 Chaitra (CS II), 2+6 marks - Video: [GEL7114 - Module 5.15 - Convolutional encoder example - 1/3 code rate](https://www.youtube.com/watch?v=N8RicfhHaqI) — Leslie Rusch - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/hamming-third-rate-convolutional - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-8 ## Question Define Hamming distance and Hamming weight. Explain the operation of a 1/3 convolutional encoder. ## Short answer Hamming weight is the count of 1s in a vector; Hamming distance is the number of differing positions between two vectors. A rate-1/3 convolutional encoder uses a shift register, three modulo-2 adders with specific generator taps, and a commutator to output three bits per input bit, with flushing zeros appended. ## Answer #### Hamming weight and distance - **Hamming weight** $w(\mathbf{c})$: number of 1s in a code vector. $w(1101001)=4$. - **Hamming distance** $d(\mathbf{c}_1,\mathbf{c}_2)$: number of positions in which two vectors differ, $=w(\mathbf{c}_1\oplus\mathbf{c}_2)$. $d(1101001,1001011)=w(0100010)=2$. The minimum distance $d_{min}$ of a code sets its error-control power: it detects up to $d_{min}-1$ errors and corrects up to $\lfloor(d_{min}-1)/2\rfloor$ errors. #### Rate-1/3 convolutional encoder A **rate-1/3 convolutional encoder** produces 3 output bits for every input bit. It uses a shift register of length $K$ (constraint length), three modulo-2 adders and a commutator. Example with $K=3$ and generators $g^{(1)}=100$, $g^{(2)}=101$, $g^{(3)}=111$: ```text m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ] | | | +-----------------------------> c1 = mi +----(+)----------------+-----> c2 = mi+mi-2 +----(+)----+----(+)----+-----> c3 = mi+mi-1+mi-2 commutator reads c1, c2, c3 in turn ``` **Operation:** 1. The register starts cleared (00). 2. A message bit enters stage 1; older bits shift right. 3. Each adder forms the mod-2 sum of the stages connected to it (taps given by its generator). 4. The commutator sends $c_1c_2c_3$, so the output rate is three times the input rate ($r=1/3$). 5. After the message, $K-1=2$ zeros flush the register back to 00. #### Example: input 101 | $m_i$ | Register $(m_i,m_{i-1},m_{i-2})$ | $c_1c_2c_3$ | |---|---|---| | 1 | 1 0 0 | 111 | | 0 | 0 1 0 | 001 | | 1 | 1 0 1 | 100 | | 0 (flush) | 0 1 0 | 001 | | 0 (flush) | 0 0 1 | 011 | Output: **111 001 100 001 011**. The encoder has $2^{K-1}=4$ states; its behaviour can be shown by a code tree, state diagram or trellis, and it is decoded with the Viterbi algorithm. The low rate gives a large free distance and strong error correction, at the cost of three times the bandwidth. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. For c1 = 1101001 and c2 = 1001011, what are w(c1) and d(c1,c2)? A. w = 3, d = 2 B. w = 4, d = 2 C. w = 4, d = 4 D. w = 5, d = 3 Answer: B. c1 has four 1s; c1 XOR c2 = 0100010 has weight 2. (Key point: Weight and distance) 2. How many errors can a code with minimum distance d_min detect and correct? A. Detect d_min - 1, correct floor((d_min - 1)/2) B. Detect d_min, correct d_min/2 C. Detect floor((d_min-1)/2), correct d_min - 1 D. Detect and correct d_min - 1 Answer: A. Detection needs d_min - 1 and correction needs floor((d_min-1)/2). (Key point: Error capability) 3. What does a rate-1/3 convolutional encoder do? A. Produces 1 output bit for every 3 input bits B. Uses 3 shift registers and one adder C. Adds 3 zeros after every input bit D. Produces 3 output bits for every input bit, so bandwidth is tripled Answer: D. Rate k/n = 1/3 means n = 3 coded bits per input bit, hence 3 times the bandwidth. (Key point: Rate 1/3 meaning) 4. Why are K-1 zeros appended after the message, and how many states does K = 3 give? A. To double the output rate; 8 states B. To add parity; 2 states C. To clear the register back to all-zero state; 4 states D. To reset the commutator; 3 states Answer: C. K-1 = 2 zeros return the register to 00, and there are 2^(K-1) = 4 states. (Key point: Flushing and states) ## 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 - [Hamming weight and distance; (7,4) cyclic code for 1011](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahamming-weight-cyclic-1011) — Communication Systems, chapter 8, asked 2× - [Hamming weight/distance; validate x = 0111000 with given H](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahamming-code-vector-0111000) — Communication Systems, chapter 8, asked 2× - [Hamming distance and weight; (6,3) code check for 100101](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahamming-6-3-h-100101) — Communication Systems, chapter 8 - [Hamming weight and distance; validate code 100011](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahamming-6-3-h-100011) — Communication Systems, chapter 8 ## Related in other subjects - [Hamming distance and minimum distance](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahamming-distance-define) — Data Communication, chapter 8, asked 2× - [Redundancy, Hamming distance, linear vs cyclic](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aredundancy-hamming-linear-cyclic) — Data Communication, chapter 8 - [Minimum Hamming distance; find k and n](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Amin-hamming-k-n) — Data Communication, chapter 8 - [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