DCN Notes

Topic Error Correction or Detection

A) Error Correction
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data. Data can be corrupt during transmission for a Reliable communication error must be delete or correcpt. The general definitions of the terms are as follows: 1. Error detection is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver. 2. Error correction is the detection of errors and reconstruction of the original, error-free data. Types of Error:

1) Single Bit error: A single bit error is change 0 to 1 and 1 to 0. Exp: 000100 Change 010100
2) Bust error: In the bust error if two or more then 2 bit are change. Exp: 000100 change 111010

Error Correction Technique: Error correction may generally be realized in two different ways: 1) Automatic repeat request (ARQ) or backward error correction 2) Forward error correction (FEC) 3) Hybrid schemes 1) Automatic repeat request (ARQ) This is an error control technique whereby an error detection scheme is combined with requests for retransmission of erroneous data. Every block of data received is checked using the error detection code used, and if the check fails, retransmission of the data is requested this may be done repeatedly, until the data can be verified. Automatic Repeat reQuest (ARQ) is an error control method for data transmission that makes use of error-detection codes, acknowledgment and/or negative acknowledgment messages, and timeouts to achieve reliable data transmission. An acknowledgment is a message sent by the receiver to indicate that it has correctly received a data frame. Three types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ, and Selective Repeat ARQ.

Created By Nitin Shukla 1

DCN Notes

2) Forward error correction (FEC) or Error-correcting code An error-correcting code (ECC) or forward error correction (FEC) code is a system of adding redundant data, or parity data, to a message, such that it can be recovered by a receiver even when a number of errors (up to the capability of the code being used) were introduced, either during the process of transmission, or on storage. The sender encodes the data using an error-correcting code (ECC) prior to transmission. The additional information (redundancy) added by the code is used by the receiver to recover the original data. In general, the reconstructed data is what is deemed the "most likely" original data.

3) Hybrid schemes RQ and FEC may be combined, such that minor errors are corrected without retransmission, and major errors are corrected via a request for retransmission: this is called hybrid automatic repeatrequest (HARQ). Hybrid ARQ is a combination of ARQ and forward error correction. There are two basic approaches: a)Messages are always transmitted with FEC parity data (and error-detection redundancy). A receiver decodes a message using the parity information, and requests retransmission using ARQ only if the parity data was not sufficient for successful decoding (identified through a failed integrity check). b)Messages are transmitted without parity data (only with error-detection information). If a receiver detects an error, it requests FEC information from the transmitter using ARQ, and uses it to reconstruct the original message. The latter approach is particularly attractive on an erasure channel when using a rateless erasure code.

Created By Nitin Shukla 2

DCN Notes

Hamming code
Hamming code is a set of error-correction code s that can be used to detect and correct bit errors that can occur when computer data is moved or stored. Hamming code is named for R. W. Hamming of Bell Labs. Like other error-correction code, Hamming code makes use of the concept of parity and parity bit s, which are bits that are added to data so that the validity of the data can be checked when it is read or after it has been received in a data transmission. Using more than one parity bit, an error-correction code can not only identify a single bit error in the data unit, but also its location in the data unit. In data transmission, the ability of a receiving station to correct errors in the received data is called forward error correction (FEC) and can increase throughput on a data link when there is a lot of noise present. Hamming codes make FEC less expensive to implement through the use of a block parity mechanism. Hamming rule: p d + p + 1 < = 2 (1) Where d is the number of data bits and p is the number of parity bits. The total of the two is called the Hamming code word, which is generated by multiplying the data bits by a generator matrix. Note:
In telecommunication, a Hamming code is a linear error-correcting code named after its inventor, Richard Hamming. Hamming codes can detect up to two simultaneous bit errors, and correct single-bit errors; thus, reliable communication is possible when the Hamming distance between the transmitted and received bit patterns is less than or equal to one. By contrast, the simple parity code cannot correct errors, and can only detect an odd number of errors. Hamming worked on weekends, and grew increasingly frustrated with having to restart his programs from scratch due to the unreliability of the card reader. Over the next few years he worked on the problem of error-correction, developing an increasingly powerful array of algorithms. In 1950 he published what is now known as Hamming Code, which remains in use today in applications such as ECC memory.

Created By Nitin Shukla 3

DCN Notes

B)

Error detection or Scheme

Error Detection Technique: Error detection is most commonly realized using a suitable hash function (or checksum algorithm). A hash function adds a fixed-length tag to a message, which enables receivers to verify the delivered message by recomputing the tag and comparing it with the one provided. Repetition codes 1) Parity bits 2) Check Sums 3) Cyclic redundancy checks (CRCs) 4) Cryptographic hash functions

1) Repetition

Codes

A repetition code is a coding scheme that repeats the bits across a channel to achieve error-free communication. Given a stream of data to be transmitted, the data is divided into blocks of bits. Each block is transmitted some predetermined number of times. Repetition codes are not very efficient, and can be susceptible to problems if the error occurs in exactly the same place for each group (e.g., "1010 1010 1010" in the previous example would be detected as correct). The advantage of repetition codes is that they are extremely simple, and are in fact used in some transmissions of numbers stations.

2) Parity bits
A parity bit is a bit that is added to a group of source bits to ensure that the number of set bits (i.e., bits with value 1) in the outcome is even or odd. It is a very simple scheme that can be used to detect single or any other odd number (i.e., three, five, etc.) of errors in the output. An even number of flipped bits will make the parity bit appear correct even though the data is erroneous.

Created By Nitin Shukla 4

DCN Notes

3) Check Sum
A checksum of a message is a modular arithmetic sum of message code words of a fixed word length (e.g., byte values). The sum may be negated by means of a one's-complement prior to transmission to detect errors resulting in all-zero messages. Checksum schemes include parity bits, check digits, and longitudinal redundancy checks. Some checksum schemes, such as the Luhn algorithm and the Verhoeff algorithm, are specifically designed to detect errors commonly introduced by humans in writing down or remembering identification numbers.

4) CRC
A cyclic redundancy check (CRC) is a single-burst-error-detecting cyclic code and non-secure hash function designed to detect accidental changes to digital data in computer networks. It is characterized by specification of a so-called generator polynomial, which is used as the divisor in a polynomial long division over a finite field, taking the input data as the dividend, and where the remainder becomes the result. Cyclic codes have favorable properties in that they are well suited for detecting burst errors. CRCs are particularly easy to implement in hardware, and are therefore commonly used in digital networks and storage devices such as hard disk drives.

5) Cryptographic hash functions

Created By Nitin Shukla 5

DCN Notes

Created By Nitin Shukla 6