---
title: "Redundancy, Hamming distance, linear vs cyclic"
subject: "Data Communication"
chapter: 8
key: "semester_5/data_communication:redundancy-hamming-linear-cyclic"
source: https://www.bctengineer.com/q/semester_5/data_communication/redundancy-hamming-linear-cyclic
site: BCT Engineering
---

# Redundancy, Hamming distance, linear vs cyclic

Data Communication · Chapter 8: Information Theory and Coding

- Asked in: 2071 Chaitra, 1+1+3 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 Sonnet 5.5 on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/data_communication/redundancy-hamming-linear-cyclic
- Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8

## Question

Discuss the concept of redundancy in error detection and correction. Define Hamming distance. Differentiate between linear block codes and cyclic codes.

## 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.

## Answer

#### 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 |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the trade-off of adding more redundancy?
   A. Better detection/correction but lower code rate k/n and more bandwidth
   B. Higher code rate and less bandwidth
   C. No effect on bandwidth
   D. Worse error detection but faster transmission
   Answer: A. Extra n - k bits improve error control but reduce the rate k/n and need more bandwidth. (Key point: Redundancy)

2. What is d(10110, 11100)?
   A. 1
   B. 2
   C. 3
   D. 4
   Answer: B. The words differ in the second and fourth positions, so the distance is 2. (Key point: Hamming distance)

3. A code with d_min detects and corrects how many errors?
   A. Detects d_min errors, corrects d_min/2
   B. Detects d_min - 1, corrects floor((d_min - 1)/2)
   C. Detects d_min + 1, corrects d_min - 1
   D. Detects floor((d_min - 1)/2), corrects d_min - 1
   Answer: B. The standard result is detection of d_min - 1 errors and correction of floor((d_min - 1)/2) errors. (Key point: Capability from d_min)

4. What extra property do cyclic codes have over linear block codes?
   A. A cyclic shift of a codeword is also a codeword
   B. The sum of two codewords is a codeword
   C. They need no parity bits
   D. They use a generator matrix only
   Answer: A. Cyclic codes are linear codes in which cyclic shifts of codewords are codewords; they use g(x) and simple shift registers. (Key point: Linear vs cyclic)

## Related in Data Communication

- [Forward error correction using Hamming code](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Afec-hamming) — Data Communication, chapter 8
- [Cyclic codes](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Acyclic-codes) — Data Communication, chapter 8, asked 3×
- [Short note: Hamming codes](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahamming-codes-short-note) — Data Communication, chapter 8
- [Hamming codes and their properties](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahamming-code-properties) — 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
- [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×

## Related in other subjects

- [Convolutional vs block codes; (7,4) cyclic code for 1011](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aconv-vs-block-cyclic-7-4-1011) — Communication Systems, chapter 8, asked 2×
- [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 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×
- [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