--- title: "Hamming distance and weight importance; syndrome decoding" subject: "Communication Systems" chapter: 8 key: "semester_6/communication_systems:hamming-importance-syndrome-decoding" source: https://www.bctengineer.com/q/semester_6/communication_systems/hamming-importance-syndrome-decoding site: BCT Engineering --- # Hamming distance and weight importance; syndrome decoding Communication Systems · Chapter 8: Error Detection and Correction Coding - Asked in: 2071 Shrawan (CS II), 2+5 marks - Video: [Error Correcting Codes: What is Hamming Distance and Minimum Hamming Distance ?](https://www.youtube.com/watch?v=7SVSXiWc0-o) — ALL ABOUT ELECTRONICS - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/hamming-importance-syndrome-decoding - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-8 ## Question What is the importance of hamming distance and hamming weight in coding theory? Explain with example the syndrome decoding method in linear block coding. ## Short answer Hamming weight and distance define error detection/correction capability; dmin = minimum non-zero weight for linear codes. Syndrome decoding computes s=rH^T; if non-zero, the syndrome pattern identifies the error. Example: for (6,3) code, r=100011 gives s=(110), matching column 3, so bit 3 is in error; corrected codeword 101011. ## Answer #### Importance of Hamming distance and weight - **Hamming weight** (number of 1s) and **Hamming distance** (number of differing positions) measure how far codewords are apart. - For a linear code, minimum distance $d_{min}$ = minimum non-zero weight, so it is found easily. - $d_{min}$ sets the error-control power of the code: it detects up to $d_{min}-1$ errors and corrects up to $\lfloor(d_{min}-1)/2\rfloor$ errors. - Decoders choose the codeword at minimum Hamming distance from the received word (maximum-likelihood for a binary symmetric channel). #### Syndrome decoding in linear block codes For a code with generator $G=[I_k\mid P]$ and parity-check matrix $H=[P^T\mid I_{n-k}]$, every codeword satisfies $\mathbf{c}H^T=\mathbf{0}$. A received word is $\mathbf{r}=\mathbf{c}\oplus\mathbf{e}$, where $\mathbf{e}$ is the error pattern. The **syndrome** is $$ \mathbf{s}=\mathbf{r}H^T=\mathbf{c}H^T\oplus\mathbf{e}H^T=\mathbf{e}H^T $$ so it depends only on the error, not on the sent codeword. **Steps:** 1. Compute $\mathbf{s}=\mathbf{r}H^T$. 2. If $\mathbf{s}=\mathbf{0}$, accept $\mathbf{r}$ as the codeword. 3. Otherwise look up the **coset leader** (most likely error pattern, usually single-bit) with that syndrome; for a single error in bit $i$, $\mathbf{s}$ equals the $i$-th column of $H$. 4. Correct: $\hat{\mathbf{c}}=\mathbf{r}\oplus\mathbf{e}$. #### Example: (6,3) code $$ H=\begin{bmatrix}1&0&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\end{bmatrix} $$ Syndrome table (single errors): | Error pattern | Syndrome | |---|---| | 000000 | 000 | | 100000 | 101 | | 010000 | 011 | | 001000 | 110 | | 000100 | 100 | | 000010 | 010 | | 000001 | 001 | Message 101 gives codeword $\mathbf{c}=101011$. Suppose $\mathbf{r}=100011$ (bit 3 flipped). $$ \mathbf{s}=\mathbf{r}H^T=\text{col}_1\oplus\text{col}_5\oplus\text{col}_6=(1,0,1)\oplus(0,1,0)\oplus(0,0,1)=(1,1,0) $$ From the table, $\mathbf{e}=001000$, so $\hat{\mathbf{c}}=100011\oplus001000=101011$, message **101** recovered. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is d_min found for a linear block code? A. As the maximum codeword weight B. As the minimum nonzero codeword weight C. As the number of parity bits D. As the number of message bits Answer: B. Because the sum of two codewords is a codeword, d_min equals the smallest nonzero weight. (Key point: d_min of a linear code) 2. Why does the syndrome depend only on the error pattern? A. s = rH^T = cH^T + eH^T and cH^T = 0, so s = eH^T B. Because r = e C. Because H is the identity D. Because the codeword is always zero Answer: A. Every codeword satisfies cH^T = 0, so only the error contributes. (Key point: Syndrome independence) 3. If one bit i is in error, what is the syndrome? A. The i-th row of G B. The all-ones vector C. The i-th message bit D. The i-th column of H Answer: D. e has a single 1 at position i, so eH^T selects the i-th column of H. (Key point: Single-error location) 4. For the (6,3) code, r = 100011 has syndrome 110. What follows? A. e = 100000 and the codeword is 000011 B. e = 000100 and the codeword is 100111 C. e = 001000 and the codeword is 101011 D. No error exists Answer: C. Syndrome 110 is in the table for error 001000, so flipping bit 3 gives 101011 (message 101). (Key point: Worked example) ## Related in Communication Systems - [Short note: Syndrome calculation in linear systematic block code](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ashort-note-syndrome-calculation) — 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 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 - [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 - [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 - [Linear block coding with example](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Alinear-block-code-explain) — Data Communication, chapter 8, asked 3× - [Sampling, holding, quantizing, coding and decoding](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Asampling-quantizing-coding-terms) — Digital Control System, chapter 1 - [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×