Error Detection and Correction
Error Detection and Correction Definition
Error detection and correction (EDAC) refers to various techniques used in computing, data storage, and data communication to identify and repair corrupted data. Data corruption can happen because of various internal and external factors, such as electrical noise, signal interference, or faulty hardware. Error detection and correction methods differ depending on where they’re applicable.
Error Detection Methods
In general, error detection methods rely on appending an extra bit or value and then comparing it between the sender and receiver. Different methods of determining this extra value can have different applications and levels of efficiency.
- Checksum: Divides the data into equal segments and then derives a numerical value from each segment using a checksum algorithm. A mismatch in checksums of sent and received segments helps identify where the error appears.
- Cryptographic hash function: Derives a value (called a “digest”) through a series of one-way mathematical operations. The operations compute very quickly and are difficult to reverse.
- Cyclic redundancy check (CRC): Attaches a check value to a block of data, based on a polynomial division operation.
- Single parity check: Adds a parity bit to the block of data. The method is simple and adds little redundant data, but it’s not very accurate.
- Two-dimensional parity check: Arranges data in a two-dimensional matrix and assigns a parity bit to each row and column. This allows the system to detect an error and determine where it is, making it easy to correct.
Error Correction Methods
- Convolutional code: Encodes the transmitted data as a continuous stream, relying on both the current input and a sequence of previous inputs. Lost bits can be reconstructed from the outputs following them in the data sequence.
- Hamming code: Uses multiple parity bits. The pattern of parity mistakes points to the exact bits that need to be flipped.
- Low-density parity-check code: Generates matrices with a large number of parity bits over different parts of the transmitted data. Considered to be highly efficient.
- Reed–Solomon code: Creates check values (called “symbols”) that can be used to reconstruct corrupted data. Useful for burst errors, where multiple adjacent bits are damaged at the same time.
Error Detection and Correction Use Examples
- CDs: Use CIRC (Cross-Interleaved Reed-Solomon Coding) to detect and correct lost bits from scratches or manufacturing defects.
- QR codes: Rely on Reed–Solomon correction to stay scannable, even if a large chunk of the code is damaged.
- RAM with error control: Fixes single bits flipped by internal issues like hardware instability or external issues like cosmic rays.
- Satellite and deep-space communication: Uses forward error correction techniques, such as convolutional, Turbo, or LDPC codes, to recover data transmitted across long distances and noisy communication channels.
- TCP/IP: Applies error control on multiple levels to detect and drop or retransmit packets with errors.
Read More
FAQ
Error detection and correction (EDAC) methods usually go hand in hand. Error detection involves detecting the presence of errors in a data transmission, as well as their position, if possible. Error correction is a group of implemented failsafes and recovery methods used to return identified errors to their original values.
The exact methods used generally depend on the type of storage. CDs, DVDs, and some hard drives might use Reed–Solomon codes to fix errors caused by physical damage to the disc. SSDs may rely on other error correction methods like low-density parity-check codes.
It depends on the error detection method applied. Detection and correction capabilities are commonly described using Hamming distance. In general, methods with a larger Hamming distance can detect and correct more errors. For example, single parity can reliably detect a single-bit error, while two-dimensional parity checks provide stronger protection and can often identify the location of a single-bit error for correction.
45-Day Money-Back Guarantee