by Dinesh Thakur Category: Communication Networks

**Cyclic Redundancy Check **(CRC) An error detection mechanism in which a special number is appended to a block of data in order to detect any changes introduced during storage (or transmission). The CRe is recalculated on retrieval (or reception) and compared to the value originally transmitted, which can reveal certain types of error. For example, a single corrupted bit in the data results in a one-bit change in the calculated CRC, but multiple corrupt bits may cancel each other out.

A CRC is derived using a more complex algorithm than the simple CHECKSUM, involving MODULO ARITHMETIC (hence the 'cyclic' name) and treating each input word as a set of coefficients for a polynomial.

• CRC is more powerful than VRC and LRC in detecting errors.

• It is not based on binary addition like VRC and LRC. Rather it is based on binary division.

• At the sender side, the data unit to be transmitted IS divided by a predetermined divisor (binary number) in order to obtain the remainder. This remainder is called CRC.

• The CRC has one bit less than the divisor. It means that if CRC is of n bits, divisor is of n+ 1 bit.

• The sender appends this CRC to the end of data unit such that the resulting data unit becomes exactly divisible by predetermined divisor *i.e. *remainder becomes zero.

• At the destination, the incoming data unit *i.e. *data + CRC is divided by the same number (predetermined binary divisor).

• If the remainder after division is zero then there is no error in the data unit & receiver accepts it.

• If remainder after division is not zero, it indicates that the data unit has been damaged in transit and therefore it is rejected.

• This technique is more powerful than the parity check and checksum error detection.

• CRC is based on binary division. A sequence of redundant bits called CRC or CRC remainder is appended at the end of a data unit such as byte.

A CRC will be valid if and only if it satisfies the following requirements:

1. It should have exactly one less bit than divisor.

2. Appending the CRC to the end of the data unit should result in the bit sequence which is exactly divisible by the divisor.

**• The various steps followed in the CRC method are**

1. A string of n as is appended to the data unit. The length of predetermined divisor is n+ 1.

2. The newly formed data unit *i.e. *original data + string of n as are divided by the divisor using binary division and remainder is obtained. This remainder is called CRC.

3. Now, string of n Os appended to data unit is replaced by the CRC remainder (which is also of n bit).

4. The data unit + CRC is then transmitted to receiver.

5. The receiver on receiving it divides data unit + CRC by the same divisor & checks the remainder.

6. If the remainder of division is zero, receiver assumes that there is no error in data and it accepts it.

7. If remainder is non-zero then there is an error in data and receiver rejects it.

• For example, if data to be transmitted is 1001 and predetermined divisor is 1011. The procedure given below is used:

1. String of 3 zeroes is appended to 1011 as divisor is of 4 bits. Now newly formed data is 1011000.

1. Data unit 1011000 is divided by 1011.

2. During this process of division, whenever the leftmost bit of dividend or remainder is 0, we use a string of Os of same length as divisor. Thus in this case divisor 1011 is replaced by 0000.

3. At the receiver side, data received is 1001110.

4. This data is again divided by a divisor 1011.

5. The remainder obtained is 000; it means there is no error.

• CRC can detect all the burst errors that affect an odd number of bits.

• The probability of error detection and the types of detectable errors depends on the choice of divisor.

• Thus two major requirement of CRC are:

(a) CRC should have exactly one bit less than divisor.

(b) Appending the CRC to the end of the data unit should result in the bit sequence which is exactly divisible by the divisor.

**Polynomial codes **

• A pattern of Os and 1s can be represented as a polynomial with coefficient of o and 1.

• Here, the power of each term shows the position of the bit and the coefficient shows the values of the bit.

• For example, if binary pattern is 100101, its corresponding polynomial representation is x^{5} + x^{2} + 1. Figure shows the polynomial where all the terms with zero coefficient are removed and x J is replaced by x and XO by 1.

• The benefits of using polynomial codes is that it produces short codes. For example here a 6-bit pattern is replaced by 3 terms.

• In polynomial codes, the degree is 1 less than the number of bits in the binary pattern. The degree of polynomial is the highest power in polynomial. For example as shown in fig degree of polynomial x^{5} +x^{2} + 1 are 5. The bit pattern in this case is 6.

• Addition of two polynomials is based on modulo-2 method. In such as case, addition and subtraction is same.

• Addition or subtraction is .done by combining terms and deleting pairs of identical terms. For example adding x^{5} + x^{4} + x^{2} and x^{6} + x^{4} + x^{2} give x^{6} + x^{5}. The terms x^{4} and x^{2} are deleted.

• If three polynomials are to be added and if we get a same term three times, a pair of them is detected and the third term is kept. For example, if there is x^{2} three times then we keep only one x^{2}

• In case of multiplication of two polynomials, their powers are added. For example, multiplying x^{5} + x^{3} + x^{2} + x with x^{2}+ x+ 1 yields:

(X^{5} + x^{3} + x^{2} + x) (x^{2} + x + 1)

= x^{7} + x^{6}+ x^{5}+ x^{5}+ x^{4}+ x^{3}+ x^{4}+ x^{3}+ x^{2}+ x^{3}+ x^{2}+ x

=X^{7}+x^{6}+x^{3}+X

In this, first polynomial is multiplied by all terms of second. The result is then simplified and pairs of equal terms are deleted.

• Incase of division, the two polynomials are divided as per the rules of binary division, until the degree of dividend is less than that of divisor.

**CRC generator using polynomials **

• If we consider the data unit 1001 and divisor or polynomial generator 1011their polynomial representation is:

• Now string of n 0s (one less than that of divisor) is appended to data. Now data is 1001000 and its corresponding polynomial representation is x^{6 }+ x^{3}.

• The division of x^{6}+x^{3} by x^{3}+x+ 1 is shown in fig.

• The polynomial generator should have following properties:

1. It should have at least two terms.

2. The coefficient of the term x^{0} should be 1.

3. It should not be divisible by x.

4. It should be divisible by x+ 1.

• There are several different standard polynomials used by popular protocols for CRC generation. These are:

Related Articles on Computer Networking

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.

#### ALOHA - What is ALOHA?

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

#### 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?

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

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

#### Cyclic Redundancy Check (CRC)

#### Sliding Window Protocol

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

#### Hamming Code

#### Bluetooth - What is Bluetooth?

#### Stop & Wait Protocol

#### What is piggybacking?

#### IEEE 802.5 Token Ring

#### Data Link Layer

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

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

#### 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

#### Broadband versus Baseband

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

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

#### Encoding Techniques and Codec

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

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

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

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

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

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

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

#### ARPANET - What is ARPANET?

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

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

#### Error Control in Communication Networks

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

#### ARCNet - What is ARCNet

#### What are Transmission Errors?

#### What is NICs (Network Adapter)

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

#### Data Communication

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

#### What is Parity Check?

#### Quality of Service (QOS)

#### Flooding – What is flooding?

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

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

#### Digital signal Transmission

#### Tunneling – What is Tunneling?

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

#### 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

#### Optical Source

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

#### Data Communication Software

#### Ethernet Expansion

#### Layering The Communications Process

#### 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

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

#### Optical Connectors

#### Transceiver - What is Transceiver?

#### What is transmission Baseband?

#### What is Broadband ISDN?

#### 100VG-Any LAN

#### What is Parity bit?

#### What is half duplex?

#### What is AppleTalk?

#### What is Ethernet Frame?

#### What is Asynchronous?

#### What is Communications?

#### What is Bit Error?

#### 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 802.15 (WPAN) ?

#### what is network transmission?

#### 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 the difference between computer networks and network communications?

#### What is IEEE 802.11e?

#### Applications of Wifi

#### What is IEEE 802.11n?

#### The Digitization of Signals

#### Passive Optical Network

#### Infrared and Laser Transmission

#### Ethernet networks at 10 Mbit/s

#### Ethernet Passive Optical Network (EPON)

Basic Courses

Advance Courses

- What is SDRAM (synchronous DRAM)? - Definition
- What is Non-Volatile Random Access Memory (NVRAM)? - Definition
- Relational Algebra - What is Relational Algebra?
- Definition of Network Operating System
- Definition of Real Time Operating Systems
- Definition of Multitasking Operating System
- what is processor in computer? Types of Microprocessor