Error Detection and Correction Codes: Parity, CRC, Repetition and Hamming Code

Error Detection and Correction Codes in Digital Electronics

Short idea: Error detection and correction codes are special digital codes used to find and sometimes correct errors in binary data during communication, storage, or processing. These codes add extra bits, called redundant bits or check bits, to make data more reliable.

In digital electronics and computer communication, data is transferred in the form of binary bits, that is, 0 and 1. During transmission or storage, these bits may change due to noise, interference, weak signal, hardware fault, magnetic disturbance, or other unwanted effects. For example, a transmitted bit 1 may be received as 0. This unwanted change is called an error.

Error detection and correction codes are used to improve the reliability of digital systems. These codes help the receiver check whether the received data is correct or not. Some codes can only detect the error, while some codes can detect and correct the error automatically.

Why Error Detection and Correction is Important

Modern digital systems such as computers, mobile phones, memory devices, satellites, routers, embedded systems and industrial control systems depend on accurate data. Even a single wrong bit can create a wrong result, corrupted file, communication failure or system malfunction.

That is why error detection and correction techniques are widely used in:

Computer memory systems
Digital communication systems
Data storage devices
Microprocessor and microcontroller systems
Networking and internet data transfer
Satellite and wireless communication
Industrial automation and control systems

What are Redundant Bits or Check Bits?

To detect or correct an error, extra bits are added to the original message. These extra bits are known as redundant bits or check bits. They do not carry new information, but they help the receiver verify the correctness of the received data.

Example: If the original data is 1011, an error detection system may add one or more extra bits to it. The receiver checks these extra bits to decide whether the received data is correct.

The main disadvantage of redundant bits is that they increase the total number of transmitted bits. This reduces efficiency. However, this small loss of efficiency is acceptable because it improves reliability.

Types of Errors in Digital Data

Type of Error	Meaning	Example
Single-bit error	Only one bit changes from 0 to 1 or 1 to 0.	`101100` becomes `101000`
Multiple-bit error	More than one bit changes in the data word.	`101100` becomes `100010`
Burst error	A group of consecutive bits is affected.	Common in communication channels

Difference Between Error Detection and Error Correction

Point	Error Detection	Error Correction
Purpose	Finds whether an error has occurred.	Finds and corrects the wrong bit or bits.
Output	Only tells that data is wrong.	Restores the correct data.
Complexity	Simple	More complex
Example	Parity code, CRC	Hamming code, repetition code

Parity Code

A parity code is one of the simplest methods of error detection. In this method, one extra bit is added to the data. This extra bit is called the parity bit. The parity bit is selected in such a way that the total number of 1s in the code becomes either even or odd.

Even Parity

In even parity, the parity bit is added so that the total number of 1s in the transmitted data becomes even.

Example:
Data = 01000001
Number of 1s = 2, which is already even.
Even parity bit = 0
Transmitted data = 001000001 if the parity bit is placed at the beginning.

Odd Parity

In odd parity, the parity bit is added so that the total number of 1s becomes odd.

Example:
Data = 01000001
Number of 1s = 2, which is even.
Odd parity bit = 1
Transmitted data = 101000001 if the parity bit is placed at the beginning.

Advantages of Parity Code

Very simple to understand and implement.
Requires only one extra bit.
Useful for detecting single-bit errors.
Commonly used in basic digital systems.

Limitations of Parity Code

It cannot correct errors.
It cannot identify the exact error location.
It fails when an even number of bits are changed.
It is not suitable for highly reliable systems by itself.

Repetition Code

In repetition code, each data bit or block of data is transmitted multiple times. At the receiver side, the repeated bits are checked. If one bit is different from the majority, it can be corrected using the majority rule.

Threefold Repetition Code

In threefold repetition, each bit is transmitted three times:

1 is transmitted as 111
0 is transmitted as 000

Example:
If 111 is transmitted and 101 is received, then the majority bit is 1. So, the receiver decides that the correct bit is 1.

This method is easy but inefficient because it increases the number of transmitted bits. If one bit is repeated three times, the transmission size becomes three times larger.

Advantages of Repetition Code

Easy to understand.
Can detect and correct single-bit errors in a repeated group.
Uses simple majority logic.

Disadvantages of Repetition Code

Very inefficient because it requires many extra bits.
Transmission speed becomes lower.
Not practical for large data transfer.
More repetitions are required to correct more errors.

Cyclic Redundancy Check Code

Cyclic Redundancy Check, commonly called CRC, is a powerful error detection method used in digital communication and networking. It provides strong error detection capability with a small number of extra bits.

In CRC, the data word is divided by a special binary number called the generator polynomial or divisor. The remainder obtained after modulo-2 division is added to the original data. This remainder is known as the CRC bits.

Basic Steps of CRC Generation

Select a generator polynomial or divisor.
Append zeros to the original data equal to the number of CRC bits.
Perform modulo-2 binary division.
Take the remainder as CRC bits.
Attach the CRC bits to the original data and transmit it.

CRC Checking at Receiver Side

At the receiver side, the received code word is divided by the same divisor. If the remainder is zero, the data is considered error-free. If the remainder is non-zero, an error is detected.

Important point: CRC is very good for detecting burst errors, which commonly occur in communication channels.

Applications of CRC

Ethernet communication
USB data transfer
Hard disk and storage systems
Wireless communication
File transfer and data packet checking

Hamming Code

Hamming code is an important error detection and correction code. It can detect and correct single-bit errors. It can also detect two-bit errors, but basic Hamming code cannot correct two-bit errors.

The main idea of Hamming code is to place parity bits at special positions. These parity bits are arranged so that each error produces a unique pattern. This pattern helps to find the exact position of the wrong bit.

What is Hamming Distance?

Hamming distance is the number of bit positions in which two binary code words differ.

Example:
Code word 1 = 101100
Code word 2 = 100110
Different positions = 2
Hamming distance = 2

A larger Hamming distance improves the ability of a code to detect and correct errors.

Position of Parity Bits in Hamming Code

In Hamming code, parity bits are placed at positions that are powers of 2:

Position 1 = P1
Position 2 = P2
Position 4 = P3
Position 8 = P4
Position 16 = P5

All other positions are used for data bits.

General Form of Hamming Code

The general arrangement of Hamming code is:

P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7 D8...

Here, P represents parity bits and D represents data bits.

Condition for Number of Parity Bits

If there are m data bits and r parity bits, then the number of parity bits must satisfy:

2^r ≥ m + r + 1

This condition ensures that enough parity combinations are available to identify each bit position and also represent the no-error condition.

Hamming (7,4) Code

The most commonly explained Hamming code is the Hamming (7,4) code. It has:

4 data bits
3 parity bits
7 total bits

The code word format is:

P1 P2 D1 P3 D2 D3 D4

Example: Hamming Code for 0110

Let the data bits be:

D1 = 0, D2 = 1, D3 = 1, D4 = 0

The Hamming code positions are:

Position	1	2	3	4	5	6	7
Bit	P1	P2	D1	P3	D2	D3	D4

Using even parity, the final Hamming code for 0110 becomes:

Hamming code = 1100110

Error Detection in Hamming Code

Suppose the received code is:

1110110

This means one bit has changed during transmission. The receiver checks the parity relations and generates checking bits. These checking bits form a binary number that indicates the position of the error bit.

If the checking result is 011, its decimal value is 3. Therefore, the 3rd bit is in error. After changing the 3rd bit, the correct code becomes:

1100110

Comparison of Error Detection and Correction Codes

Code	Main Function	Can Correct Error?	Efficiency	Common Use
Parity Code	Detects single-bit error	No	High	Simple digital systems
Repetition Code	Detects and corrects using majority rule	Yes	Low	Basic theory and simple systems
CRC	Detects burst errors	No	High	Networking and data communication
Hamming Code	Detects and corrects single-bit error	Yes	Good	Memory and communication systems

Common Mistakes Beginners Make

Confusing error detection with error correction.
Thinking parity code can correct errors.
Forgetting that parity fails for even number of bit errors.
Placing Hamming parity bits at wrong positions.
Using normal binary division instead of modulo-2 division in CRC.
Not understanding that redundant bits improve reliability but reduce efficiency.

Real-Life Example

Imagine sending a message from one computer to another computer over a noisy channel. If the transmitted data changes during transmission, the receiver may read a wrong message. Error detection codes like CRC help the receiver know that the received data is incorrect. Error correction codes like Hamming code can go one step further and correct a single wrong bit without asking for retransmission.

Frequently Asked Questions

What is error detection?

Error detection is the process of finding whether received digital data contains errors or not.

What is error correction?

Error correction is the process of finding and correcting the wrong bit or bits in received data.

What is a parity bit?

A parity bit is an extra bit added to binary data to make the number of 1s either even or odd.

Can parity code correct errors?

No. Parity code can only detect some errors. It cannot locate or correct the error bit.

Why is CRC used?

CRC is used because it detects burst errors with high reliability and requires relatively fewer redundant bits.

What is Hamming code used for?

Hamming code is used to detect and correct single-bit errors in digital communication and memory systems.

What is Hamming distance?

Hamming distance is the number of different bit positions between two binary code words.

Key Takeaways

Errors can occur in digital data due to noise and system disturbances.
Redundant bits are added to detect or correct errors.
Parity code is simple but can only detect limited errors.
Repetition code can correct errors but is inefficient.
CRC is widely used for reliable error detection.
Hamming code can detect and correct single-bit errors.

Conclusion

Error detection and correction codes are essential for reliable digital systems. Parity code, repetition code, CRC and Hamming code are commonly used methods for protecting data from errors. Parity is simple, CRC is powerful for error detection, repetition code is easy to understand, and Hamming code is useful for single-bit error correction. For students of digital electronics, computer organization and communication systems, these codes are very important because they form the foundation of reliable data transfer and storage.

Keywords

Error detection and correction codes, parity code, repetition code, cyclic redundancy check, CRC code, Hamming code, Hamming distance, digital electronics error correction, error detection in computer networks, redundant bits, check bits, single bit error correction.