1. Parity Bits
- Definition: A simple error-detection method where a single bit (parity bit) is added to a data set to make the total number of 1s either even or odd.
- Types of Parity:
- Even Parity: Ensures total number of 1s is even.
- Odd Parity: Ensures total number of 1s is odd.
- Usage:
- Detects single-bit errors in transmitted data.
- Does not correct errors.
- Key Formula:
Parity Bit = XOR (Exclusive OR) of all bits in the data. - Applications:
- Memory error checking (RAM).
- Data transmission in simple protocols.
2. CRC (Cyclic Redundancy Check)
- Definition: A robust error-detection technique that generates a checksum by dividing data bits with a predetermined polynomial.
- How it Works:
- Data bits are treated as a binary number.
- Divided by a generator polynomial (e.g.,
x³ + x + 1). - Remainder (CRC code) is appended to the data.
- Key Points:
- Detects burst errors (multiple consecutive errors).
- Does not correct errors, only detection.
- Example Polynomial:
- Commonly used: CRC-32, CRC-16, etc.
- Applications:
- Network protocols (Ethernet, HDLC).
- Storage devices (hard drives, SSDs).
- File integrity verification.
3. Hamming Code
- Definition: An error-detection and error-correction technique that uses redundant bits to detect and correct single-bit errors.
- How it Works:
- Data bits are interspersed with parity bits at specific positions (powers of 2: 1, 2, 4, etc.).
- Parity bits are calculated for overlapping groups of data bits.
- Errors are identified and corrected by analyzing the parity bits.
- Key Formula:
2r≥m+r+12^r \geq m + r + 1- rr: Number of parity bits.
- mm: Number of data bits.
- Steps to Correct Error:
- Parity check identifies the position of the error.
- Flip the bit at the identified position to correct it.
- Applications:
- Satellite communication.
- Data storage (ECC memory).
- Reliable data transmission over noisy channels.
Comparison Table
| Feature | Parity Bits | CRC | Hamming Code |
|---|---|---|---|
| Error Detection | Single-bit errors. | Single and burst errors. | Single-bit errors. |
| Error Correction | No. | No. | Yes, single-bit errors. |
| Complexity | Low. | Moderate. | Higher (requires computation). |
| Usage | Simple protocols (RAM). | Networks, storage, file checks. | Critical data transmission. |
Easy Mnemonics to Remember
Hamming Code: H for Help, as it helps fix single-bit errors.
Parity Bit: P for Parity, P for Prevent, detects single-bit errors.
CRC: Think of Check Redundancy Carefully to detect burst errors.
MCQ
What is the purpose of a parity bit?
a) To add redundancy to a signal
b) To check and correct errors
c) To detect single-bit errors
d) To encode data
Answer: c) To detect single-bit errors
What are the two types of parity?
a) Bit and Byte
b) Odd and Even
c) Forward and Reverse
d) High and Low
Answer: b) Odd and Even
What does an even parity bit ensure?
a) Total number of 1s is odd
b) Total number of 1s is even
c) Total number of 0s is even
d) Total number of bits is even
Answer: b) Total number of 1s is even
Parity bits are ineffective in detecting:
a) Single-bit errors
b) Burst errors
c) Even-numbered errors
d) Both b and c
Answer: d) Both b and c
Where are parity bits commonly used?
a) Satellite communication
b) File compression algorithms
c) RAM error checking
d) Video streaming
Answer: c) RAM error checking
What does CRC stand for?
a) Cyclic Rotational Check
b) Cyclic Redundancy Check
c) Coded Redundancy Check
d) Cyclic Resource Check
Answer: b) Cyclic Redundancy Check
What does CRC primarily detect?
a) Single-bit errors
b) Burst errors
c) Packet loss
d) Noise interference
Answer: b) Burst errors
What is used in CRC to calculate the remainder?
a) Division by binary numbers
b) Exclusive-OR (XOR) operation
c) Logical AND
d) Subtraction
Answer: b) Exclusive-OR (XOR) operation
Which of the following is a commonly used CRC polynomial?
a) x³ + x + 1
b) x⁴ + x² + 1
c) x² + 1
d) x⁵ + 1
Answer: a) x³ + x + 1
What is the main limitation of CRC?
a) Cannot detect burst errors
b) Cannot correct errors
c) Low accuracy in detection
d) Inefficient for small data packets
Answer: b) Cannot correct errors
Which of these is NOT an application of CRC?
a) Ethernet networks
b) Hard disk error checking
c) File verification
d) Error correction in Hamming codes
Answer: d) Error correction in Hamming codes
How is the CRC value added to the data?
a) Appended at the beginning
b) Appended at the end
c) Inserted randomly in the data stream
d) Encoded within the data bits
Answer: b) Appended at the end
What is the main purpose of Hamming code?
a) Data encryption
b) Error correction
c) File compression
d) Burst error detection
Answer: b) Error correction
Hamming code can correct which type of errors?
a) Burst errors
b) Double-bit errors
c) Single-bit errors
d) Multi-bit errors
Answer: c) Single-bit errors
In Hamming code, where are parity bits placed?
a) At the end of the data
b) In positions that are powers of 2
c) In positions that are multiples of 3
d) At random positions
Answer: b) In positions that are powers of 2
Which of the following is an application of Hamming code?
a) CRC error checking
b) RAM error correction
c) File compression
d) Network address translation
Answer: b) RAM error correction
What is the result when no errors are found in Hamming code parity checks?
a) A non-zero error syndrome
b) All parity bits are 0
c) Parity bits are 1
d) The data is discarded
Answer: b) All parity bits are 0
Hamming code is unable to correct which of the following errors?
a) Single-bit errors
b) Double-bit errors
c) Errors in parity bits
d) Errors in first data bit
Answer: b) Double-bit errors
What is the minimum Hamming distance required for single-bit error correction?
a) 1
b) 2
c) 3
d) 4
Answer: c) 3
Which technique detects errors but cannot correct them?
a) Parity bits
b) CRC
c) Hamming code
d) Both a and b
Answer: d) Both a and b
Which of the following is the most robust for detecting burst errors?
a) Parity bits
b) CRC
c) Hamming code
d) None of these
Answer: b) CRC
Which error detection method uses a polynomial generator?
a) Parity bit
b) CRC
c) Hamming code
d) Checksum
Answer: b) CRC
How does Hamming code correct errors?
a) By recalculating parity bits
b) By flipping the identified erroneous bit
c) By discarding erroneous data
d) By using CRC for correction
Answer: b) By flipping the identified erroneous bit
What is the main advantage of Hamming code over parity bits?
a) Higher speed
b) Burst error detection
c) Ability to correct single-bit errors
d) Simplicity of implementation
Answer: c) Ability to correct single-bit errors
Focus Points:
- Parity bits are simple and detect single-bit errors only.
- CRC detects burst errors but does not correct them.
- Hamming code detects and corrects single-bit errors.
- Remember the formula for parity bits in Hamming code: 2r≥m+r+12^r \geq m + r + 12r≥m+r+1.
- CRC is used in networks like Ethernet, while Hamming code is used in RAM and satellite communication.