- 2071 Chaitra · 1+1+3 marks
Redundancy, Hamming distance, linear vs cyclic
Short answer
Redundancy provides error control by adding (n−k) extra bits; Hamming distance counts differing bits and d_min determines detection (d_min−1) and correction ⌊(d_min−1)/2⌋. Linear block codes satisfy codeword sum as a codeword; cyclic codes also guarantee any cyclic shift is a codeword, enabling simple shift-register implementation.
Discuss the concept of redundancy in error detection and correction. Define Hamming distance. Differentiate between linear block codes and cyclic codes.
Redundancy
Redundancy means sending extra bits beyond the data bits. These extra bits carry no new information but let the receiver check the data: a code with k data bits and n total bits has n − k redundant bits (redundancy ratio (n − k)/n). More redundancy gives better detection and correction ability but lowers the code rate k/n and needs more bandwidth. Example: parity bit, CRC bits, Hamming parity bits.
Hamming distance
The Hamming distance between two equal-length words is the number of bit positions in which they differ, e.g. d(10110, 11100) = 2. The minimum distance d_min of a code decides its power: it detects d_min − 1 errors and corrects ⌊(d_min − 1)/2⌋ errors.
Linear block code vs cyclic code
| Point | Linear block code | Cyclic code |
|---|---|---|
| Property | Sum of two codewords is a codeword | Linear and a cyclic shift of a codeword is a codeword |
| Description | Generator matrix G | Generator polynomial g(x), dividing xⁿ + 1 |
| Encoding | c = m·G (matrix multiplication) | c(x) = m(x)·g(x) or division by g(x) |
| Implementation | More complex logic | Simple shift registers |
| Relation | Larger class | A subclass of linear codes |
| Examples | Hamming code (general) | CRC, BCH, Reed-Solomon |
✓ Answer checked by Claude Sonnet 5.5
Related questions
- Forward error correction using Hamming code · Data Communication, chapter 8
- Cyclic codes · Data Communication, chapter 8 · asked 3×
- Short note: Hamming codes · Data Communication, chapter 8
- Hamming codes and their properties · Data Communication, chapter 8
- Minimum Hamming distance; find k and n · Data Communication, chapter 8
- Linear block coding with example · Data Communication, chapter 8 · asked 3×
- Convolutional vs block codes; (7,4) cyclic code for 1011 · Communication Systems, chapter 8 · asked 2×
- Error detection vs correction; rate ½ convolutional encoder · Communication Systems, chapter 8
- Hamming weight and distance; (7,4) cyclic code for 1011 · Communication Systems, chapter 8 · asked 2×
- Error correction vs detection, bit stuffing · Computer Networks and Security, chapter 3