by Dinesh Thakur Category: Communication Networks

**Error detection and correction **has great practical importance in maintaining data (information) integrity across noisy Communication Networks channels and lessthan- reliable storage media.

**Error Correction : **Send additional information so incorrect data can be corrected and accepted. Error correction is the additional ability to reconstruct the original, error-free data.

There are two basic ways to design the channel code and protocol for an error correcting system :

• **Automatic Repeat-Request (ARQ) : **The transmitter sends the data and also an error detection code, which the receiver uses to check for errors, and request retransmission of erroneous data. In many cases, the request is implicit; the receiver sends an acknowledgement (ACK) of correctly received data, and the transmitter re-sends anything not acknowledged within a reasonable period of time.

• **Forward Error Correction (FEC) : **The transmitter encodes the data with an error-correcting code (ECC) and sends the coded message. The receiver never sends any messages back to the transmitter. The receiver decodes what it receives into the "most likely" data. The codes are designed so that it would take an "unreasonable" amount of noise to trick the receiver into misinterpreting the data.

**Error Detection : **Send additional information so incorrect data can be detected and rejected. Error detection is the ability to detect the presence of errors caused by noise or other impairments during transmission from the transmitter to the receiver.

**Error Detection Schemes : **In telecommunication, a redundancy check is extra data added to a message for the purposes of error detection. Several schemes exist to achieve error detection, and are generally quite simple. All error detection codes transmit more bits than were in the original data. Most codes are "systematic": the transmitter sends a fixed number of original data bits, followed by fixed number of check bits usually referred to as redundancy which are derived from the data bits by some deterministic algorithm.

The receiver applies the same algorithm to the received data bits and compares its output to the received check bits; if the values do not match, an error has occurred at some point during the transmission. In a system that uses a "non-systematic" code, such as some raptor codes, data bits are transformed into at least as many code bits, and the transmitter sends only the code bits.

**Repetition Schemes : **Variations on this theme exist. Given a stream of data that is to be sent, the data is broken up into blocks of bits, and in sending, each block is sent some predetermined number of times. For example, if we want to send "1011", we may repeat this block three times each. Suppose we send "1011 1011 1011", and this is received as "1010 1011 1011".

As one group is not the same as the other two, we can determine that an error has occurred. This scheme is 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 example above will be detected as correct in this scheme. The scheme however is extremely simple, and is in fact used in some transmissions of numbers stations.

**Parity Schemes : **A parity bit is an error detection mechanism . A *parity bit *is an extra bit transmitted with a data item, chose to give the resulting bitseven or odd parity. *Parity *refers to the number of bits set to 1 in the data item. There are 2 types of parity

- an even number of bits are 1 Even parity - data: 10010001, parity bit 1*Even parity*- an odd number of bits are 1 Odd parity - data: 10010111, parity bit 0*Odd parity*

The stream of data is broken up into blocks of bits, and the number of 1 bits is counted. Then, a "parity bit" is set (or cleared) if the number of one bits is odd (or even).This scheme is called even parity; odd parity can also be used. There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors (one, three, five, and so on). If an even number of bits (two, four, six and so on) are flipped, the parity bit appears to be correct, even though the data is corrupt. For example

- Original data and parity: 10010001+1 (even parity)
- Incorrect data: 10110011+1 (even parity!)

Parity usually used to catch one-bit errors

**Checksum : **A checksum of a message is an arithmetic sum of message code words of a certain word length, for example byte values, and their carry value. The sum is negated by means of ones-complement, and stored or transferred as an extra code word extending the message. On the receiver side, a new checksum may be calculated, from the extended message.

If the new checksum is not 0, error is detected.Checksum schemes include parity bits, check digits, and longitudinal redundancy check. Suppose we have a fairly long message, which can reasonably be divided into shorter words (a 128 byte message, for instance). We can introduce an accumulator with the same width as a word (one byte, for instance), and as each word comes in, add it to the accumulator.

When the last word has been added, the contents of the accumulator are appended to the message (as a 129th byte, in this case). The added word is called a *checksum*. Now, the receiver performs the same operation, and checks the checksum. If the checksums agree, we assume the message was sent without error.

**Hamming Distance Based Checks : **If we want to detect d bit errors in an n bit word we can map every n bit word into a bigger n+d+1 bit word so that the minimum Hamming distance between each valid mapping is d+1. This way, if one receives n+d+1 bit word that doesn't match any word in the mapping (with a Hamming distance x <= d+1 from any word in the mapping) it can successfully detect it as an errored word. Even more, d or fewer errors will never transform a valid word into another, because the Hamming distance between each valid word is at least d+1, and such errors only lead to invalid words that are detected correctly.

Given a stream of m*n bits, we can detect x <= d bit errors successfully using the above method on every n bit word. In fact, we can detect a maximum of m*d errors if every n word is transmitted with maximum d errors. The *Hamming distance *between two bit strings is the number of bits you have to change to convert one to the other. The basic idea of an error correcting code is to use extra bits to increase the dimensionality of the hypercube, and make sure the Hamming distance between any two valid points is greater than one.

• If the Hamming distance between valid strings is only one, a single bit error results in another valid string. This means we can't detect an error.

• If it's two, then changing one bit results in an invalid string, and can be detected as an error. Unfortunately, changing just one more bit can result in another valid string, which means we can't detect which bit was wrong; so we can detect an error but not correct it.

• If the Hamming distance between valid strings is three, then changing one bit leaves us only one bit away from the original error, but two bits away from any other valid string. This means if we have a one-bit error, we can figure out which bit is the error; but if we have a two-bit error, it looks like one bit from the other direction. So we can have single bit correction, but that's all.

• Finally, if the Hamming distance is four, then we can correct a single-bit error and detect a double-bit error. This is frequently referred to as a SECDED (Single Error Correct, Double Error Detect) scheme.

**Cyclic Redundancy Checks : **For CRC following some of Peterson & Brown's notation here . .

is the length of the message we want to send,*k**i.e.,*the number of information bits.

is the total length of the message we will end up sending the information bits followed by the check bits. Peterson and Brown call this a*n**code polynomial*.

is the number of check bits. It is also the degree of the generating polynomial. The basic (mathematical) idea is that we're going to pick the n-k check digits in such a way that the code polynomial is divisible by the generating polynomial. Then we send the data, and at the other end we look to see whether it's still divisible by the generating polynomial; if it's not then we know we have an error, if it is, we hope there was no error. The way we calculate a CRC is we establish some predefined n-k+1 bit number P (called the Polynomial, for reasons relating to the fact that modulo-2 arithmetic is a special case of polynomial arithmetic). Now we append n-k 0's to our message, and divide the result by P using modulo-2 arithmetic. The remainder is called the Frame Check Sequence. Now we ship off the message with the remainder appended in place of the 0's. The receiver can either recompute the FCS or see if it gets the same answer, or it can just divide the whole message (including the FCS) by P and see if it gets a remainder of 0. As an example, let's set a 5-bit polynomial of 11001, and compute the CRC of a 16 bit message:*n-k*

*---------------------*

*11001)10011101010101100000*

*11001*

*- - - - -*

*1010101010101100000*

*11001*

*- - - - -*

*110001010101100000*

*11001*

*- - - - -*

*00011010101100000*

*11001*

*- - - - -*

*0011101100000*

*11001*

*- - - - -*

*100100000*

*11001*

*- - - - -*

*10110000*

*11001*

*- - - - -*

*1111000*

*11001*

*- - - - -*

*11100*

*11001*

*- - - - -*

*0101*

* *

In division don’t bother to keep track of the quotient; we don't care about the quotient. Our only goal here is to get the remainder (0101), which is the FCS. CRC's can actually be computed in hardware using a shift register and some number of exclusive-or gates.

About Dinesh Thakur

Dinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.

Search Content

Popular Article

#### What is transmission media ? Types of transmission media.

#### Transmission Media

#### What is Data Transmission? Types of Data Transmission.

#### Transmission Modes - What are the different Transmission Modes?

#### ALOHA - What is ALOHA?

#### What is Congestion Control? Describe the Congestion Control Algorithm commonly used

#### Data Communication - What is Data Communication?

#### Types of Routers

#### What is Error Correction and Detection?

#### What is Difference between UTP and STP Cable?

#### OSI (Open Systems Interconnection) Reference Model

#### MAC Layer - What is MAC Layer Protocols?

#### Coaxial Cable - Write Short Note on Coaxial Cable

#### Twisted-Pair : What is Twisted-Pair Cable?

#### Cyclic Redundancy Check (CRC)

#### Sliding Window Protocol

#### What is Hubs/Repeaters/Bridges/Router/Switches/ Transceivers/ Gateway

#### Hamming Code

#### Bluetooth - What is Bluetooth?

#### IEEE 802.5 Token Ring

#### Stop & Wait Protocol

#### What is piggybacking?

#### Bound transmission media - What is Bound transmission media ? Type of bound transmission media Explain

#### What is an Analog Signal? Characteristics of Analog Signal.

#### Data Link Layer

#### Optical Fibers: What is a Optical Fibers?

#### Unbound transmission media - What is Unbound transmission media. Type of Unbound transmission media

#### Analog vs Digital - Difference and Comparison

#### What is a Digital Signal? Characteristics of Digital Signal

#### IEEE 802.11: WIRELESS LAN

#### How Does a Single Bit Error Differs From Burst Error.

#### Asynchronous vs. Synchronous Transmission Modes

#### Wireless Communication - What is Wireless Communication?

#### Broadband versus Baseband

#### Encoding Techniques and Codec

#### Gigabit Ethernet: 1000Base-SX, 1000Base-LX, 1000Base-CX, 1000 Base-T

#### RS-232C - What is RS-232C?

#### Ethernet Cables - What Is an Ethernet Cable?

#### Microwave Transmission – What is a Microwave Transmission?

#### Routers – What is Router? Characteristics of Routers. Router Protocols

#### Fast Ethernet : 100 Base-TX, 100 Base-FX, 100 Base-T4

#### Optical Fiber - Optical Transmission Modes Advantages and Disadvantages of Optical Fiber

#### Satellite Communication – What is a Satellite Communication?

#### Infrared Transmission– What is a Infrared Transmission?

#### Radio Wave – What is a Radio Wave Transmission?

#### ARPANET - What is ARPANET?

#### ARCNet - What is ARCNet

#### What is NICs (Network Adapter)

#### Bridges – What is Bridges? Bridge Protocols

#### Error Control in Communication Networks

#### What are Transmission Errors?

#### Data Communication

#### Media Access Control (MAC layer) - Definition

#### Gateways – What is Gateway? Characteristics of Gateways.

#### What is Parity Check?

#### What is Hub | Definition of Hub | Meaning of Hub

#### Flooding – What is flooding?

#### Digital signal Transmission

#### Virtual LAN (VLAN) – What is Virtual LAN? Characteristics of VLAN.

#### Repeaters – What is Repeaters? Classification of Repeaters

#### Quality of Service (QOS)

#### Tunneling – What is Tunneling?

#### What is Ethernet? - Definition

#### Switching Hubs – What is Switching Hubs? Characteristics of Switching Hub.

#### Network Architectures

#### 10BASE T - What is 10BASET (Twisted Pair Ethernet) ?

#### 100Base T - What is 100Base T (Fast Ethernet)? Type of 100Base T

#### Data Communication Software

#### Optical Source

#### 10 Base 2 – What is 10Base2 (Thin Net/Black Ethernet)

#### Layering The Communications Process

#### Ethernet Expansion

#### Implementation of LAN Using Fiber-Optic Cable

#### 10 Base 5 - What is 10Base5 (Thick Net/Yellow Ethernet)?

#### BNC/T-connector

#### CDDI (Cable Distributed Data Interface)

#### Implementation of LAN Using Wireless Technology

#### Optical Connectors

#### Transmission System – What is an Transmission System?

#### Transceiver - What is Transceiver?

#### What is transmission Baseband?

#### What is Broadband ISDN?

#### 100VG-Any LAN

#### What is Parity bit?

#### What is AppleTalk?

#### What is half duplex?

#### What is Asynchronous?

#### What is Communications?

#### What is Bit Error?

#### What is Ethernet Frame?

#### What is EtherTalk?

#### What is Transfer rate?

#### What is the difference between Wi-Fi vs. Mobile Broadband

#### Functions of the MAC Layer

#### What is WiMAX (Worldwide Interoperability for Microwave Access)?

#### what is network transmission?

#### What is 802.15 (WPAN) ?

#### Cable networks (CATV)

#### How to Set Up a Wireless Router Installation & Configuration

#### ISO Architecture

#### How to Networking Your Devices

#### Features of the package level or network layer

#### What is IEEE 802.11e?

#### Applications of Wifi

#### What is IEEE 802.11n?

#### The Digitization of Signals

#### Passive Optical Network

#### Infrared and Laser Transmission

#### What is the difference between computer networks and network communications?

#### Ethernet Passive Optical Network (EPON)

#### Ethernet networks at 10 Mbit/s

Basic Courses

Advance Courses